Information Technology Reference
In-Depth Information
Chapter 8
S
CALABLE
P
ACKET
C
LASSIFICATION
BY
U
SING
H
ASH
-
BASED
A
LGORITHMS
Pi-Chung Wang
Department of Computer Science and Engineering,
National Chung Hsing University, Taichung, Taiwan
Abstract
In next-generation networks, packet classification is used to categorize incoming
packets into multiple forwarding classes based on pre-defined filters and make infor-
mation accessible for quality of service or security handling in the network. In the last
decade, the technique of packet classification has been widely deployed in various net-
work devices, including routers, firewalls and network intrusion detection systems. To
pursue better search performance, numerous algorithms of packet classification have
been proposed and optimized for certain filter databases; however, these algorithms
may not scale in either storage or speed performance or both for the filter databases
with different characteristics. Specifically, packet classification with a large number
of filters usually exhibits poor worst-case performance.
In this chapter, we improve the performance of packet classification by using mul-
tiple hash tables. The existing hash-based algorithms have superior scalability with
respect to the required space; however, their search performance may not be compa-
rable to other algorithms. We observe the characteristics of the hash-based algorithms
and introduce three hash-based algorithms to improve the performance of packet clas-
sification. In the first algorithm, we combine two complementary algorithms, Cross-
producting and Pruned Tuple Space Search, to make packet classification both fast and
scalable. Unlike the existing algorithms whose performance is contingent on the fil-
ter database attributes, our algorithm shows better scalability and feasibility. We also
introduce the procedure of incremental updates. Next, we improve the performance
of Pruned Tuple Space Search by combining the Aggregate Bit Vector algorithm. We
also show the related update procedures. Last, we present a hash-table reordering al-
gorithm to minimize the number of accessed hash tables with the aid of bitmaps. We
also use pre-computation to ensure the accuracy of our search procedure. For each
algorithm, we evaluate the performance with both real and synthetic filter databases of
varying sizes and characteristics. The experimental results demonstrate that the new
algorithms improve the speed and storage performance simultaneously. Moreover, the
results also demonstrate that our schemes are feasible and scalable.
