如今，在能支援各種服務的下一代路由器中，多維度的封包分類技術在其中扮演一個重要的角色。為了達到較高的效能，支援較大rule table的軟體演算法和提供高產能的硬體式架構式缺一不可的。在此論文中，我們提出一個基於Segment Trees的平行管線化架構來解決多維度的封包架構，此方法稱為刪減區段樹，Set-Pruning Segment Trees (SPST)。在刪減區段樹中，不用backtracks能有效使用管線化架構來提高產能，然而刪減類型的方法必須複製rule產生記憶體過度使用的問題。為了解決記憶體使用問題，我們使用一個分群組的方法，稱為Partition by Length (PL)來降低SPST中rule複製數量。此外；我們也提出一個最佳化的方法來降低樹高度以減少反應時間，稱為Set-Pruning Multi-way Segment Trees (SPMST)。
為了更進一步降低記憶體使用量和提高產能，我們提出一個改良的方法和架構叫作Set-Pruning Segment Trees with Buckets。藉由另一種計算分群組分數和排列Buckets的方法來大量降低rule複製數量，並簡化每一個階層的運算動作來增加產能。我們提出的方法特色在於無論是哪一種特性的rule tables都能夠明顯的降低記憶體使用量。在Xilinx Virtex-5的FPGA實驗裝置下，我們能夠支援各種不同特性有10k條rule 的tables，並且在我們所提出的管線化架構使用雙端口記憶體下能達到超過100Gbps的產能。

Multi-field packet classification is one of the most important functions to support various services in next generation routers. Both the memory-efficient data structure to support larger rule tables and hardware architecture to achieve a high throughput are desired. In this thesis, we propose a parallel and pipelined architecture called Set Pruning Segment Trees (SPST) for multi-dimensional packet classification. In SPST, there is no backtracking problem and is suitable for pipeline design. However, there is memory blowup problem caused by rule duplication in Set-Pruning Tries. For solving the memory blowup problem, a grouping scheme called Partition by Length (PL) is used to reduce the rule duplications in SPST. Additionally, we also propose an optimized structure called Set-Pruning Multi-way Segment Trees (SPMST) to reduce the tree level and response time.
To further reduce memory usage and achieve higher throughput, we propose another scheme called Set-Pruning Segment Trees with Buckets (SPSTwB). SPSTwB significantly reduces rule duplication based on a partitioning scheme and an efficient bucket merging scheme. In addition, the logic complexity of each pipeline stage can be simplified to run at a high clock rate. The key feature of our proposed architecture is that memory consumption is reduced significantly regardless of the characteristics of various rule tables. The proposed pipelined architecture can achieve a throughput of over 100 Gbps for the packets of minimum 40 bytes with dual port memory and support the tables of up to 10K rules based on Xilinx Virtex-5 FPGA device.

[1] M.D. Breg, M.V. Kreveld, M. Overmars, and O. Schwarzkopf, “Computational Geometry: Algorithms and Applications”, Springer Verlag, 1997.
[2] Y.-K. Chang and Y.-C. Lin, “Dynamic Segment Trees for Ranges and Prefixes”, IEEE Transactions on Computers, vol. 56, no. 6, pp. 769-784, June 2007.
[3] Y.-K. Chang, Y.-S. Lin, and C.-C. Su, “A High-Speed and Memory Efficient Pipeline Architecture for Packet Classification”, in Proc. of the International IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM-2010) pp.215-218, 2010.
[4] Y.-K. Chang, Y.-C. Lin, and C.-Y. Lin, “Grid of Segment Trees for Packet Classification”, In Proc. of the IEEE 24th International Conference on Advanced Information Networking and Applications (AINA-2010), pp. 1144 - 1149 April, 2010.
[5] S. Dharmappurikar, H. Song, J. Turner, and J. Lockwood, “Fast Packet Classification Using Bloom Filters”, in Proc. of the ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS), 2006.
[6] P. Gupta and N. McKeown, “Classifying packets with hierarchical intelligent cuttings”, IEEE Micro, vol. 20(1), pp. 34-41, 2001.
[7] W. Jiang and V. K. Prasanna, “A Memory-Balanced Linear Pipeline Architecture for Trie-based IP Lookup”, in Proc. of the IEEE Symposium on High-Performance Interconnects (HOTI), pp. 83-90, 2007.
[8] W. Jiang, Q. Wang, and V. K. Prasanna, “Beyond TCAMs: An SRAM-based parallel multi-pipeline architecture for terabit IP lookup”, in Proc. INFOCOM, pp. 1786-1794, 2008.
[9] W. Jiang and V. K. Prasanna, “Large-Scale Wire-Speed Packet Classification on FPGAs”, in Proc. of the ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA), 2009.
[10] W. Jiang and V. K. Prasanna, “Towards Practical Architectures for SRAM-based Pipelined Lookup Engines”, in Proc. INFOCOM Work-in-Progress track, Mar. 2010.
[11] A. Kennedy, X. Wang, Z. Liu, and B. Liu, “Low Power Architecture for High Speed Packet Classification”, in Proc. of the ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS), 2008.
[12] A. Nikitakis and I. Papaefstathiou, “A Memory-Efficient FPGA-Based Classification Engine”, in Proc. of the International IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM), 2008.
[13] I. Papaefstathiou and V. Papaefstathiou, “Memory-Efficient 5D Packet Classifications at 40 Gbps”, in Proc. of the International IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM), 2008.
[14] Y. Qi, L. Xu, B. Yang, Y. Xue, and J. Li, “Packet Classification Algorithms: From Theory to Practice”, in Proc. of 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”, in Proc. of the International Conf. Field-Programmable Technology, Dec. 2010.
[16] V. Srinivasan, G. Varghese, S. Suri, and M. Waldvogel, “Fast and Scable Layer Four Switching”, ACM SIGCOMM Computer Communication Review, vol. 28, pp. 191-202, October 1998.
[17] S. Singh, F. Baboescu, G. Varghese, and J. Wang, “Packet classification using multidimensional cutting”, in Proc. of SIGCOMM, pp. 213-224, 2003.
[18] H. Song and J. W. Lockwood, “Efficient Packet Classification for Network Intrusion Detection Using FPGA”, in Proc. of the ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA), pp. 238-245, 2005.
[19] D. E. Taylor, “Survey and Taxonomy of Packet Classification Techniques”, ACM Computing Surveys, vol. 37, no. 3, pp. 238-275, Sep. 2005.
[20] D. E. Taylor and J. S. Turner, “ClassBench: A Packet Classification Benchmark”, IEEE/ACM Transaction on Network, vol. 15, no. 3, pp. 499-511, June 2007.
[21] Jeffrey M. Wagner, W. Jiang and V. K. Prasanna, “A Scalable Pipeline Architecture for Line Rate Packet Classification on FPGAs”, IEEE Transactions on Parallel and Distributed Computing and Systems, Nov. 2009.
[22] Xilinx, “Virtex-5 Family Overview”, Product Specification, DS100 (v5.0), Feb. 6, 2009, at http://www.xilinx.com.