Information Technology Reference
In-Depth Information
1.
Introduction
In next generation networks (NGNs), packet classification is important in fulfilling the re-
quirements of differentiated services. By using pre-defined filters, packet classification
could categorize an incoming packet to a forwarding class, such as those indicated by the
differentiated services codepoint (DSCP field) in the
DiffServ
model [1]. It has been ex-
tensively employed in the Internet for secure filtering and service differentiation. Various
devices, such as routers, firewalls and network intrusion detection systems, have used packet
classification to practical effect. Therefore, the performance of packet classification is im-
portant in the deployment of NGNs. However, packet classification with a potentially large
number of filters is complex and exhibits poor worst-case performance [2, 3].
To perform packet classification, network devices would need a database of header
filters with two or five fields. The value in each field could be a variable-length prefix,
range, explicit value or wildcard [4]. The fields include the source/destination IP address
prefix, source/destination port range of the transport protocol and the protocol type in the
packet header. The number of fields used to inspect packet headers is determined by the
particular application of packet classification. For example, packet classification with two-
field filters is useful for QoS packet forwarding with traffic-engineered source-destination
paths and multicasting [5], whereas with the five-field filters it can be applied to flow-based
traffic engineering or network security [4]. Since two-field filters can be handled by packet
classification with five-field filters, we focus on the latter in this paper. In a packet classifier,
each filter is associated with an action, and each action is assigned a cost. Formally, we
define a filter
F
with
d
fields as
F =(f
1
,f
2
,...,f
d
)
. A packet header
P
is said to match a
particular filter
F
if for all
i
, the
i
th
field of the header satisfies
f
i
. The packet classification
problem is to determine to which action each packet should take by inspecting the header
fields of the packet and comparing them to a list of filters.
The problem of packet classification resembles point location problems in the multi-
dimensional space [2, 3]. The point location problem is a set-membership problem that
finds the enclosed region of a point within a set of non-overlapping regions. The best upper
bounds classifying packets on
N
filters with
d
fields are either O(
logN
) time and O(
N
d
)
space or O(
log
d−1
N
) time and O(
N
) space. In other words, the performance would be
totally unacceptable in the worst case. For instance, assume we attempt to process 1,024
filters of
four
fields in a router. An algorithm with O(
log
d−1
N
) execution time and O(
N
)
space requires 1,000 memory accesses per packet, which is impractical for network appli-
cations. If we use an O(
log N
) time and O(
N
d
) space algorithm, the space requirement
becomes unrealistically large in the range of
one
terabyte. Furthermore, none of the above
algorithms addresses the problem of arbitrary overlaps.
Much effort has been devoted to packet classification in recent years, yielding a number
of algorithms. However, the existing algorithms may not scale well for large filter databases
and sometimes a tradeoff between space and time is inevitable. For example, the trie-based
algorithms [6,7] and hash-based algorithms [8] have superior storage performance, but their
search performance is limited. While the decision-tree-based algorithms [9, 10] and the
combination-based algorithms [2, 6] have excellent search performance, they cannot sup-
port filter databases with numerous
wildcards
or
distinct field specifications
. Ternary CAMs
(TCAMs) have superior performance in both space and time performance, but the capac-
