使用位元向量編碼的快速封包分類法

Abstract

封包分類在許多的網路應用中都扮演著非常重要的角色，像是防火牆、頻寬保證服務(Quality of Service, QoS)，虛擬私人網路(Virtual Private Networks, VPN)等等。 本篇論文將會提出一套針對位元向量(Bit Vector)做編碼的方法，稱為EBV演算法，藉此來降低BV演算法中的位元向量長度，這個做法的好處不僅能降低記憶體的用量，也能節省讀取位元向量時所需的記憶體存取次數。我們使用規則庫產生工具ClassBench來產生九種不同的規則庫。測試的結果可以發現EBV演算法的確能大幅降低Lucent BV演算法的記憶體用量，並且藉由硬體的平行處理，在做規則搜尋時大約只需要原本Lucent BV演算法所需要的記憶體讀取次數的1/2。 使用Xilinx Vertex4 FX-20 FPGA實作EBV演算法，在1K的規則庫，使用64bytes封包大小做為最小封包來計算，在三階管線架構下可以達到500Mbps以上的封包過濾速度；使用五階管線架構，則可達到1Gbps以上的封包過濾速度。

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.