隨著網際網路的蓬勃發展，封包分類器(Packet Classifier)成為下一代高速路由器中相當重要的元件，可支援具QoS網路服務,高速防火牆, 以網路傳送量的計價方式(Usage-based Billing) 等服務。雖然封包分類演算法曾被廣泛討論。然而，大多數的封包分類演算法需要大量的記憶體，無法將2-3萬分類法則儲藏於記憶容量較小的硬體平台。本論文將針對這個問題進行探討，發展一個嶄新的分割式平行封包分類演算法，採用管線化的架構，並實現於FPGA。我們從探討分類法則分割切入，若能將分類規則適當的進行分群，將可大幅降低儲存空間的需求。因此我們對分類法則進行兩階段的分群，來降低儲存空間，使得大量規則可儲存於硬體平台上。同時我們採用二位元樹(Binary Search Tree)進一步壓縮分類法則所需儲存空間，可以將高達3萬筆ACL型態分類法則，存進FPGA的記憶體中。透個硬體實現，當每個封包大小為40bytes 時，我們所設計封包分類器可達到28 Gbps的效能。

Multi-field packet classification becomes a challenging issue owing to the rapid growth of the Internet traffic and the size of the classification rules. However, existing classification algorithms require large-scale memory, which cannot store in the on-chip memory. In this thesis, we design and implement a scalable packet classification algorithm on FPGA, which can support the large number of classification rules up to 30K. Based on our key observation, the storage requirements of the packet classification algorithm can be reduced significantly if the classification rules are appropriately clustered. We propose a two-stage rule clustering scheme, which divides of the classification rules into 11 clusters and rules in different cluster are searched in parallel and pipeline fashion. Furthermore, to reduce memory requirements, a 2-D Binary-Search-Tree is used in the algorithm design. To shorten the lookup time, we use parallel processing with pipeline architecture in our design. Therefore, the chip can achieve one lookup per clock cycle. Two strategies: controlled prefix expansion and MinMax are used to further optimize the system architecture. We use Post-Place & Route simulation to verify the performance of the proposed system. The results show that the proposed multi-filed packet classifier can achieve approximately 86.6 million packets per second at 86.6 MHz system clock.

[1] 林天民, ABV+: 一個高效率封包分類演算法, 碩士論文-長庚大學,2009年1月。

[2] 黃鼎峰, 基於R*-Tree 的位元圖交集封包分類演算法, 碩士論文-國立交通大學,2011年6月。

[3] H. Lee, W. Jiang, and V. K. Prasanna, “Scalable High-Throughput SRAM-Based
Architecture for IP Lookup Using FPGA,” In Proc. Field Programmable Logic and Applications (FPL ’08), pp. 203–214 , 2008.

[4] P. Gupta, and N. McKeown, “Algorithms for packet classification,” IEEE Network, vol. 15, no. 2, pp.24-32, 2001.

[5] T. V. Lakshman and D. Stiliadis, “High-speed policy-based packet forwarding
using efficient multi-dimensional range matching," In Proc. ACM SIGCOMM,
pp. 203–214, 1998.

[6] H. Song and J. W. Lockwood, “Efficient packet classification for network intrusion detection using FPGA,” In Proc. ACM/SIGDA 13th ACM International Symposium on FPGA, pp. 238–245, 2005.

[7] V. Srinivasan and G. Varghese, “Fast IP lookup using controlled prefix expansion,” ACM Trans. Computer Systems, vol. 26, no. 1, pp. 1-40, Feb. 1999.

[8] Anindya Basu and Girija Narlikar, “Fast Incremental Updates for Pipelined Forwarding Engines,” IEEE/ACM Trans. Networking., Vol. 13, no.3, 2005.

[9] D. E. Taylor and J. S. Turner, “ClassBench: A Packet Classification Benchmark,” IEEE/ACM Trans. Networking., Vol15, no.3 pp. 499-511, 2007.

[10] W. Jiang and V. K. Prasanna, “Large-scale wire-speed packet classification on
FPGAs,” In Proc. Field Programmable Logic and Applications (FPL ’09), pp. 219-228, 2009.

[11] 趙彥博, 以四元樹為基礎的封包分類輔處理器之設計與實現, 碩士論文-
國立台灣科技大學, 2004年7月。

[12] A. Kennedy, X. Wang, Z. Liu, and B. Liu, “Low power architecture for high
speed packet classification,” in Proc. ACM/IEEE Symposium on Architectures
for Networking and Communications Systems, pp. 131-140, 2008.

[13] H. Song and J. W. Lockwood, “Efficient packet classification for network
intrusion detection using FPGA,” in Proc. Field Programmable Logic and Applications, pp. 238–245, 2005

[14] G. S. Jedhe, A. Ramamoorthy, and K. Varghese, “A scalable high throughput
firewall in FPGA,” in Proc. Field-Programmable Custom Computing Machines,
pp. 43-52, 2008.

[15] W. Jiang and V. K. Prasanna. Parallel IP lookup using multiple SRAM-based
pipelines. In Proc. IPDPS, 2008.