封包分類在現今高速路由器中是一個重要的功能，它可以提供很多網路服務像是防火牆、頻寬品質管理(QoS)、網路流量控制以及虛擬私有網路(VPNs)等等。為了達到高連線速率OC-768 40Gbps，實作於硬體的路由器是必要的。現今的路由器設計課題是如何容納大量的rule sets並且達到高產能。很多實作於FPGA的方法有很高的產能但是它們因為記憶體使用量超過目前FPGA裝置記憶體支援而無法容納較大且複雜的rule set像是IP Chain 以及Firewall 10K的table。在此論文中，我們提出了一個多維度的端點(endpoint)切割演算法明顯的減少了決策樹的高度導致有較短的回應時間，而多層方法來大幅度的減少記憶體使用量。此外，我們使用上述的方法提出了一個高產能且低成本的管線化硬體架構。當我們使用管線化架構時，在儲存bucket rule記憶體使用量占了總記憶體使用量很大的部分。因此，我們提出了一個bucket壓縮的方法來減少bucket rule重複複製的情況。實作在Xilinx Virtex-5 FPGA裝置上，實驗結果顯示我們提出的方法比現今其他實作在FPGA上的封包分類方法需要更少的記憶體。就我們所知，我們提出的方法是第一個能容納IPC以及FW 10K rule table實作在FPGA上封包分類方法。此外，我們提出的方法可以容納ACL 50K rule table在on-chip 記憶體上。透過管線化設計以及平行處裡技巧和雙通道記憶體，在使用每個最小封包大小為40Bytes的封包下我們架構可以維持高的產能超過100Gbps。我們的產能能夠勝過大部分實作在FPGA上的封包分類方法。

Packet classification is one of the important functions that can support many networking services such as firewall, Quality of Service (QoS), traffic control and virtual private networks (VPNs) in today’s high speed routers. To achieve a high throughput of OC-768 (40Gbps), the hardware router solution is desired. How to support large rule sets and still achieve high throughput is the major topic of current router design. Many existing FPGA-based approaches can achieve a very high throughput but cannot accommodate the large rule tables like IP Chain and Firewall of 10K rules because their data structures need more memory than that supported by the most advanced FPGA devices. In this thesis, we shall propose a recursive multi-dimensional endpoint-based cutting algorithm to reduce the decision tree depth and the response time and a multi-layered scheme to dramatically reduce the usage of memory. Furthermore, we propose a high-throughput and low-cost pipelined hardware architecture based on our proposed recursive endpoint-cutting scheme. When a pipelined architecture is considered, the memory needed to store the rules in buckets accounts for a large part of total required memory. Therefore, we also propose a bucket compression scheme to lower the rule duplication in buckets. Based on Xilinx Virtex-5 FPGA device, our experimental results show that the proposed scheme needs much less block RAMs than the existing FPGA-based packet classification approaches. To the best of our knowledge, our proposed scheme is the first FPGA-based packet classification scheme that can support IPC and FW tables of 10K rules. Furthermore, our proposed scheme can accommodate ACL tables of 50K rules in the on-chip memory of the FPGA devices. By using the pipelined and parallel architecture with dual port memory, the throughput of beyond 100Gbps for minimum sized (40 bytes) packets can be achieved. The proposed architecture outperforms most FPGA-based packet classification engines.

[1] F. Baboescu and G. Varghese. “Scalable Packet Classification,” Proc. ACM SIGCOMM, vol. 31, pp. 199–210, Oct. 2001.
[2] Yeim-Kuan Chang, "Efficient Multidimensional Packet Classification with Fast Updates," IEEE Trans. Computers, vol. 58, no. 4, pp. 463-479, Apr. 2009.
[3] Yeim-Kuan Chang, Y.-C. Lin, and C.-Y. Lin, "Grid of Segment Trees for Packet Classification," Proc. Advanced Information Networking and Applications (AINA), pp. 1144-1149, 2010.
[4] Yeim-Kuan Chang, Yi-Shang Lin, and Cheng-Chien Su," A High-Speed and Memory Efficient Pipeline Architecture for Packet Classification," IEEE Symposium on Field-Programmable Custom Computing Machines, pp.215 - 218, 2010.
[5] E. Cohen and C. Lund. “Packet Classification in Large ISPs: Design and Evaluation of Decision Tree Classifiers” Proc. SIGMETRICS, pp. 73 – 84, 2005.
[6] S. Dharmapurikar, H. Song, J. Turner, and J. Lockwood, “Fast Packet Classification Using Bloom Filters,” Proc. ACM/IEEE ANCS, pp. 61-70, 2006.
[7] P. Gupta and N. McKeown, “Packet Classification Using Hierarchical Intelligent Cuttings,” Proc. Hot Interconnects VII, 1999.
[8] P. Gupta and N. McKeown. “Packet Classification on Multiple Fields,” Proc. ACM SIGCOMM, vol. 29, pp. 147–160, Oct. 1999.
[9] W. Jiang and V. K. Prasanna. “Large-Scale Wire-Speed Packet Classification on FPGAs,” Proc. FPGA, pp. 219-228, 2009.
[10] A. Kennedy, X. Wang, Z. Liu, and B. Liu, “Low Power Architecture for High Speed Packet Classification,” Proc. ACM/IEEE ANCS, pp. 131-140, 2008.
[11] H. Lim and J. H. Mun, “High-Speed Packet Classification Using Binary Search on Length,” Proc. ACM/IEEE ANCS, pp. 137-144, 2007.
[12] A. Nikitakis and I. Papaefstathiou, “A Memory-Efficient FPGABased Classification Engine,” Proc. IEEE FCCM, pp. 53-62, Apr. 2008.
[13] I. Papaefstathiou and V. Papaefstathiou, “Memory-Efficient 5D Packet Classification at 40 Gbps,” Proc. IEEE INFOCOM, pp. 1370-1378, 2007.
[14] Y. Qi, L. Xu, B. Yang, Y. Xue, and J. Li. “Packet Classification Algorithms: From Theory to Practice,” Proc. IEEE INFOCOM, pp. 648– 656, 2009.
[15] Y. Qi, J. Fong, W. Jiang, B. Xu, J. Li and V. K. Prasanna, “Multi-dimensional Packet Classification on FPGA: 100 Gbps and Beyond,” Proc. Field-Programmable Technology, pp. 241-248, Dec. 2010.
[16] S. Singh, F. Baboescu, G. Varghese, and J. Wang, “Packet Classification using Multidimensional Cutting,” Proc. ACM SIGCOMM, pp. 213-224, 2003.
[17] H. Song and J. W. Lockwood, “Efficient Packet Classification for Network Intrusion Detection Using FPGA,” Proc. ACM FPGA, pp. 238-245, 2005.
[18] V. Srinivasan, G. Varghese, S. Suri, and M. Waldvagel, “Fast and Scalable Layer Four Switching,” Proc. ACM SIGCOMM, pp. 191- 202, Aug. 1998.
[19] D.E. Taylor and J.S. Turner, “ClassBench: a packet classification benchmark,” Proc. INFOCOM, vol.3, pp. 2068-2079, Mar. 2005.
[20] David E. Taylor, “Survey and Taxonomy of Packet Classification Techniques,” ACM Computing Surveys, vol. 37, no.3, pp.238-275, Sep. 2005.
[21] B. Vamanan, G. Voskuilen and T.N. Vijaykumar. “EffiCuts: Optimizing Packet Classification for Memory and Throughput,” Proc. ACM SIGCOMM, pp. 207-218, 2010.
[22] Jeffrey M. Wagner, Weirong Jiang and Viktor K. Prasanna. “A SCALABLE PIPELINE ARCHITECTURE FOR LINE RATE PACKET CLASSIFICATION ON FPGAS,” Proc. Parallel and Distributed Computing and Systems, 2009.
[23] T. Woo. “A modular approach to packet classification: Algorithms and results,” Proc. IEEE INFOCOM, vol.3 ,pp. 1213-1222, 2000.
[24] Xilinx, "Virtex-5 Family Overview", Product Specification, DS100 (v5.0), Feb. 6, 2009, at http://www.xilinx.com.
[25] B. Xu, D. Jiang and J. Li, “HSM: A Fast Packet Classification Algorithm,” Proc. Advanced Information Networking and Applications (AINA), pp. 987-992, 2005.
[26] B. Yang, X. Wang, Y. Xue and J. LI, “DBS: A Bit-level Heuristic Packet Classification Algorithm for High Speed Network,” Proc. Parallel and Distributed Systems (ICPADS), pp.260- 267, 2009.
[27] B. Yang, et al., “Discrete Bit Selection: Towards a Bit-level Heuristic Framework for Multi-dimensional Packet Classification,” Proc. IEEE INFOCOM, pp.1-2, 2009.