封包分類是路由器中的一個重要組件，它有許多應用例如:服務質量(QoS)、安全、監測、分析與網路入新偵測等。在這篇論文中我們提出了一個稱作分層搜尋樹的方法來解決多維的封包分類問題。分層搜尋樹把決策樹的樹節點重新建成一個趨近平衡的搜尋樹，以此改善傳統決策樹的方法。比起傳統的決策樹方法把rule儲存在樹節點的bucket中，分層搜尋樹的任何節點都設有bucket。因此，在搜尋時一旦封包吻合內部節點則可直接搜尋該節點的bucket，而不需要一直走到葉節點。在軟體環境中，實驗結果顯示分層搜尋樹使用較少的記憶體，即使EffiCuts事先用五維歸類來減少rule replication，所得到的記憶體結果也比分層搜尋樹只用前兩維歸類來的多。此外，在讀取記憶體次數的比較中，分層搜尋樹表現的比HyperCuts與EffiCuts來的好。 並且，我們也對分層搜尋樹設計了硬體的搜尋引擎，以管線化設計(pipeline)與平行處理的架構來實作在Xilinx Virtex-5 的FPGA環境中。由於分層搜尋樹需要較少硬體資源的特性，我們的搜尋引擎最大可以支援到ACL、FW與IPC三種的50K rule table。此外，分層搜尋樹也可達到路由器的高link rate (比如: OC-768)，在假設每個最小封包大小為40Bytes的封包下分層搜尋樹的搜尋引擎使用中埠的記憶體可得到超過120 Gps的產能。

Packet classification is an important building block of the Internet routers for many network applications, such as Quality of Service (QoS), security, monitoring, analysis, and network intrusion detection (NIDS). In this thesis, we propose a scheme called Layer based Search Tree (LST) to solve multi-field packet classification problem. LST improves the traditional decision tree based schemes (e.g. HyperCuts and EffiCuts) by reconstructing the leaf nodes of the decision tree as an approximately balanced search tree. Since all the address subspace covered by each node of LST is disjoint, the buckets of the leaf and internal nodes in LST must not be empty. Thus, only the rules in one bucket can match the header values of the incoming packet. Searches on LST are completed immediately after the packet matches a rule in some internal node. In software environment, the experimental results show that LST requires less memory storage even if LST categorizes the rules by two fields to reduce rule duplication rather than five fields in EffiCuts. Besides, LST needs less number of memory accesses than HyperCuts and EffiCuts. In addition, we design the hardware search engine with pipeline and parallel architecture for the LST in Xilinx Virtex-5 FPGA environment. Because the memory usage of LST is very efficient, our search engine can support the ACL, FW, and IPC tables of 50k rules. LST search engine with dual ported memory can sustain the throughput of over 120 Gbps for the packets of minimum size (40 bytes).

[1]. H. J. Chao, “Next generation routers,” Proceedings of the IEEE, vol. 90, no. 9, pp. 1518-1558, Sep. 2002.
[2]. Y. K. Chang, “Efficient Multidimensional Packet Classification with Fast Updates,” IEEE Transactions on Computers, vol. 58, no. 4, pp. 463-479, Apr. 2009.
[3]. Y. K. Chang, Y. S. Lin, and C. C. Su, "A High-Speed and Memory Efficient Pipeline Architecture for Packet Classification," IEEE Symposium on Field-Programmable Custom Computing Machines, pp.215 - 218, 2010.
[4]. Y. K. Chang and H. C. Chen, "Layered Cutting Scheme for Packet Classification," The IEEE 25th International Conference on Advanced Information Networking and Applications (AINA-2011), 2011.
[5]. Y. K. Chang and H. M. Chen, "Set Pruning Segment Trees for Packet Classification," The IEEE 25th International Conference on Advanced Information Networking and Applications (AINA-2011), 2011.
[6]. H. C. Chen, “Recursive Endpoint Based Hyper-Cutting Scheme For Packet Classification,” Unpublished thesis for degree of master of computer science and information engineering, National Cheng-Kung University, Tainan, Taiwan, R.O.C, 2011.
[7]. H. M. Chen, “Partitioned Set-Pruning Segment Trees For Packet Classification,” Unpublished thesis for degree of master of computer science and information engineering, National Cheng-Kung University, Tainan, Taiwan, R.O.C, 2011.
[8]. S. Dharmapurikar, H. Song, J. Turner, and J. Lockwood, “Fast Packet Classification Using Bloom Filters,” Proc. ACM/IEEE ANCS, pp. 61-70, 2006.
[9]. P. Gupta, and N. McKeown, “Classifying packets with hierarchical intelligent cuttings,” IEEE Micro, vol. 20, no. 1, pp. 34-41, Jan.Feb. 2000.
[10]. P. Gupta, and N. McKeown, “Algorithms for packet classification,” IEEE Network, vol. 15, no. 2, pp. 24-32, Mar.-Apr. 2001.
[11]. F. Geraci, M. Pellegrini, and P. Pisata, “Packet classification via improved space decomposition techniques,” in Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies, 2005, pp. 304-312 vol. 1.
[12]. V. Srinivasan, G. Varghese, S. Suri et al., “Fast and scalable layer four switching,” in Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, 1998, pp. 191-202.
[13]. http://www.arl.wustl.edu/~hs1/PClassEval.html
[14]. W. Jiang and V. K. Prasanna. “Large-Scale Wire-Speed Packet Classification on FPGAs,” Proc. FPGA, pp. 219-228, 2009.
[15]. 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.
[16]. T. V. Lakshman, and D. Stiliadis, “High-speed policy-based packet forwarding using efficient multi-dimensional range matching,” in Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, 1998, pp. 203-214.
[17]. H. B. Lu and S. Sahni, “O(log W) multidimensional packet classification, ” IEEE-ACM Transactions on Networking, vol. 15, pp. 462-472, Apr 2007.
[18]. A. Nikitakis and I. Papaefstathiou, “A Memory-Efficient FPGABased Classification Engine,” Proc. IEEE FCCM, pp. 53-62, Apr. 2008.
[19]. I. Papaefstathiou and V. Papaefstathiou, “Memory-Efficient 5D Packet Classification at 40 Gbps,” Proc. IEEE INFOCOM, pp. 1370-1378, 2007.
[20]. Y. Qi, L. Xu, B. Yang, Y. Xue, and J. Li, “Packet Classification Algorithms: From Theory to Practice, ” in Proceedings of the 28th IEEE Conference on Computer Communications (INFOCOM’09), 2009, pp. 648 – 656.
[21]. 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.
[22]. V. Srinivasan, S. Suri, and G. Varghese. Packet classification using tuple space search. in Proceedings of the ACM SIGCOMM’99 conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM ’99), 1999, pp. 135 – 146.
[23]. S. Singh, F. Baboescu, G. Varghese, and J. Wang, “Packet classification using multidimensional cutting,” in Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications (ACM SIGCOMM 2003), 2003, pp. 213–224.
[24]. H. Song and J. W. Lockwood, “Efficient Packet Classification for Network Intrusion Detection Using FPGA,” Proc. ACM FPGA, pp. 238-245, 2005.
[25]. D. E. Taylor, and J. S. Turner, “ClassBench: A packet classification benchmark,” IEEE-ACM Transactions on Networking, vol. 15, no. 3, pp. 499-511, Jun. 2007.
[26]. D. E. Taylor, “Survey and taxonomy of packet classification techniques,” ACM Computing Surveys, vol. 37, no. 3, pp. 238-275, Sep. 2005.
[27]. B. Vamanan, G. Voskuilen, and T. N. Vijaykumar. “EffiCuts: Optimizing Packet Classification for Memory and Throughput,” in Proceedings of the 2010 conference on Applications, technologies, architectures, and protocols for computer communications, 2010, pp. 207-218
[28]. J. M. Wagner, Weirong Jiang and V. K. Prasanna, “A SCALABLE PIPELINE ARCHITECTURE FOR LINE RATE PACKET CLASSIFICATION ON FPGAS,” Proc. Parallel and Distributed Computing and Systems, 2009.
[29]. Xilinx, "Virtex-5 Family Overview", Product Specification, DS100 (v5.0), Feb. 6, 2009, at http://www.xilinx.com.