Fast Packet Classification Using Bit Vector Encoding
Date Issued
2007
Date
2007
Author(s)
Kung, Ching-Fu
DOI
zh-TW
Abstract
Packet classification plays an important role in many network applications, like firewall, quality of service, virtual private networks, etc.
This paper proposes a method to encode bit vector, called EBV scheme, in order to reduce the length of bit vectors which are basic data structure of Lucent BV scheme. The advantages of compressing bit vectors include lowering the memory space requirement and reducing the memory access times when reading bit vector information from memory. When evaluating the performance, we use the ClassBench, rule set generation tool, to generate nine different rule sets. Testing result shows that the proposed EBV scheme needs a smaller memory storage than the Lucent BV scheme and by using parallel processing in hardware, searching rules with the EBV scheme needs about half of memory access times that are required with the Lucent BV scheme.
We use a Xilinx Vertex4 FX-20 FPGA platform to implement the EBV scheme. With 64-byte packets and rule sets with about 1K rules, the EBV scheme can filter packets up to 500Mbps using a three-stage pipeline architecture and 1Gbps using a five-stage pipeline architecture.
Subjects
封包分類
位元向量
packet classification
bit vector
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-96-J94921003-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):f624f50898a2fef3291016b5f4c19825