29-01-2011, 07:20 PM
Packet Classi cation Algorithms
Contents
1 Introduction 5
2 Requirement of packet classi cation 7
3 Speci cations of classi cation 8
4 Classi cation algorithms 9
4.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.2 Basic Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.2.1 Linear Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.2.2 Hierarchical Tries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.2.3 Set-pruning tries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.3 Geometric algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.3.1 Grid-of-tries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.4 Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.4.1 Recursive Flow Classi cation (RFC) . . . . . . . . . . . . . . . . . . . . 13
4.4.2 Hierarchical Intelligent Cuttings (HiCuts) . . . . . . . . . . . . . . . . . 14
4.5 Hardware-based algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.5.1 Ternary CAMs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.6 Performance metrics for classi cation algorithms . . . . . . . . . . . . . . . . . . 16
5 Conclusion 17
3
Abstract
The process of categorizing packets into
ows in an Internet router is called packet classi -
cation. All packets belonging to the same
ow obey a pre-de ned rule and are processed in a
similar manner by the router. For example, all packets with the same source and destination
IP addresses may be de ned to form a
ow. Packet classi cation is needed for non \best-
e ort"services, such as re walls and quality of service; services that require the capability to
distinguish and isolate trac in di erent
ows for suitable processing. In general, packet clas-
si cation on multiple elds is a dicult problem. Hence, researchers have proposed a variety of
algorithms which, broadly speaking, can be categorized as basic search algorithms, geometric
algorithms, heuristic algorithms, or hardware-speci c search algorithms. In this tutorial it was
described that algorithms that are representative of each category, and discuss which type of
algorithm might be suitable for di erent applications.
4
1 Introduction
Every router performs forwarding decision on an incoming packet to determine the packet's
next-hop router. This is achieved by looking up the destination address of the incoming packet
in a forwarding table . Packet arrival rate is increased due to high speed links so the complexity
of the forwarding lookup mechanism and the large size of forwarding tables make routing lookup
a dicult task for the internet. Fast and ecient routing lookup algorithms can be used to
overcome the problem up to a certain extent. Until recently, Internet routers provided only
\best-e ort"service, servicing packets in a rst-come- rst-served manner. Routers are now
called upon to provide di erent qualities of service to di erent applications which means routers
need new mechanisms such as admission control, resource reservation, per-
ow queueing, and
fair scheduling. All of these mechanisms require the router to distinguish packets belonging to
di erent
ows. Flows are speci ed by rules applied to incoming packets. We call a collection of
rules a classi er. Each rule speci es a
ow that a packet may belong to based on some criteria
applied to the packet header, as shown in Figure 1.
Figure 1: This gure shows some of the header elds (and their widths) that might be used
for classifying the packet.
To illustrate the variety of classi ers, consider some examples of how packet classi cation
can be used by an ISP to provide di erent services. Figure 2 shows ISP1 connected to three
di erent sites: enterprise networks E1 and E2 and a Network Access Point1 (NAP), which
is in turn connected to ISP2 and ISP3. ISP1 provides a number of di erent services to its
customers, as shown in Table 1. Table 2 shows the
ows that an incoming packet must be
classi ed into by the router at interface X.
Service Example
Packet Filtering Deny all trac from ISP3 (on interface X)
destined to E2.
Policy Routing Send all voice-over-IP trac arriving from
E1 (on interface Y) and destined to E2 via a separate
ATM network.
Accounting and Billing Treat all video trac to
E1 (via interface Y) as highest priority and perform
accounting for the trac sent this way.
Trac Shaping Ensure that no more than 50Mbps of web trac
is injected into ISP2 on interface X.
Table 1:
5
Note that the
ows speci ed may or may not be mutually exclusive. For example, the rst and
second
ow in Table 2 overlap. This is common in practice, and when no explicit priorities are
speci ed,We Follow the convention that rules closer to the top of the list take priority.
Figure 2:Example network of an ISP (ISP1) connected to two enterprise networks (E1 and
E2) and to two other ISP networks across a network access point (NAP).
Flow Relevant Packet Fields:
Email and from ISP2 Source Link-layer Address,
Source Transport port number.
From ISP2 Source Link-layer Address.
From ISP3 and going to E2 Source Link-layer Address,
Destination Network-Layer Address.
All other packets -
Table 2:
Routers must perform packet classi cation at high speed s to eciently implement functions
such as rewalls, Quality Of Service (QOS) routing, packet ltering, policy routing, accounting
and billing, trac rate limiting, trac shaping etc. Packet classi cation requires matching of
each packet against a database of lters or rules and forwarding packets as per the priority of
lters .
6
2 Requirement of packet classi cation
The requirements of packet classi cation can vary depending up on the application and the
location where the classi cation is performed. The classi cation should be done at the line
speeds like TI , T3, OC3, OCI2, OC48 with minimum time required for classi cation and
minimum memory. The requirements can be listed as under:
1. Resource limitations: Packet Classi cation (PC) can be decided on the basis of time
required to perform classi cation per packet or the memory used. Di erent access speeds
are available such as Tl, T3, OC3, OCI2,OC48 etc. so, the solution for PC should match
with speed and minimize memory required.
2. Number of rules to be supported: Number of rules for PC can vary depending on appli-
cations such as rewalls,backbone router etc.
3. Number of elds used: PC applications di er on basis of the elds in IP header used for
classi cation.
4. Nature of rules: The rules are about the pre x mask or general masks used on destination
IP address.
5. Updating the set of rules: The PC should be adaptable to changes in the rules due to
route or policy changes without sacri cing access performance
6. Worst case Vs average case : For performance of PC, focusing should be done on worst
case than average case.
7
3 Speci cations of classi cation
Each rule of a classi er has d components.R[i] is the ith component of rule R, and is a regular
expression on the ith eld of the packet header. A packet P is said to match rule R, if 8i , the
ith eld of the header of P satis es the regular expression R[i] . In practice, a rule component
is not a general regular expression but is often limited by syntax to a simple address/mask
or operator/number(s) speci cation. In an address/mask speci cation, a 0 (respectively 1) at
bit position x in the mask denotes that the corresponding bit in the address is a dont care
(respectively signi cant) bit. Examples of operator/number(s) speci cations are eq 1232 and
range 34-9339. Note that a pre x can be speci ed as an address/ mask pair where the mask is
contiguous i.e., all bits with value 1 appear to the left of bits with value 0 in the mask. It can
also be speci ed as a range of width equal to 2t where t=32
