在此篇論文中，為了解決多維度的封包分類問題，我們提出一種方法叫做Bucket二援搜尋法(BSOB)，BSOB與傳統的決策樹基底演算法非常類似，比如說HiCuts與HyperCuts，其目標即是藉由從根部到特定樹葉造訪決策樹去縮小搜尋空間，BSOB可以藉由在一線性矩陣上執行二元搜尋提高決策樹基底效能的演算法，而此線性矩陣是由決策樹的樹葉的排序所產生，搜尋Key是接收到的封包的五維欄位所產生的位元串列子集合。結果可以看出BSOB可以大幅提升傳統決策樹的搜尋效能，但是嚴重的規則重複問題會消耗過多的記憶體資源。因此，我們提出一個最佳化策略去解決規則重複的問題(Mem-Opt-BSOB)。Mem-Opt-BSOB最主要的概念就是我們留住那些將會複製到子節點的規則於內部節點，此策略可以更加的大幅減少記憶體的耗用。在實作與測試BSOB，Mem-Opt-BSOB，與現存最佳的決策樹基底演算法HyperCuts之後，比較結果可以得知BSOB在各方面的效能都比HyperCuts好，而Mem-Opt-BSOB與BOSB比較，可以更加的減低記憶體使用量。

In this paper, we propose a scheme called binary search on buckets (BSOB) for multi-dimensional packet classification problem. BSOB is similar to the traditional decision-tree-based schemes like HiCuts and HyperCuts that narrow down the search space by traversing the decision tree from the root node to a specific leaf node. BSOB enhances the decision-tree-based schemes by performing the binary search operations on a linear array that is the ordered leaf nodes of the decision tree. The search key is a partial set of bits extracted from the 5-dimensional header field value of the incoming packet. As a result, BSOB can significantly improve the search speed of the traditional decision-tree-based schemes. But the serious rule duplication problem will consume too much memory. We propose a memory optimization scheme (Mem-Opt-BSOB) to fix the rule duplication problem. The basic idea of Mem-Opt-BSOB is that we retain the rules in the internal nodes of the decision tree which otherwise will be duplicated to the child nodes. Mem-Opt-BSOB can further decrease memory usage dramatically. We implement and evaluate the proposed scheme, BSOB and Mem-Opt-BSOB, as well as the best existing decision tree scheme, HyperCuts. The performance comparisons show BSOB outperforms HyperCuts in all aspects and Mem-Mem-Opt-BSOB can further decrease memory usage dramatically compared with BSOB.

[1] verrizon moving to 100 Gbps network in ’09, “http://www.networkworld.com/news/2008/031008-verizon-100gpbsnetwork.html.”
[2] K. Lakshminarayanan, A. Rangarajan, and S. Venkatachary. Algorithms for advanced packet classification with ternary CAMs. In Proc.SIGCOMM, pages 193–204, 2005.
[3] H. Song and J. W. Lockwood. Efficient packet classification for network intrusion detection using FPGA. In Proc. FPGA, pages 238–245, 2005.
[4] F. Yu, R. H. Katz, and T. V. Lakshman. Efficient multimatch packet classification and lookup with TCAM. IEEE Micro, 25(1):50–59, 2005.
[5] S. Dharmapurikar, H. Song, J. S. Turner, and J. W. Lockwood, “Fast packet classification using bloom filters,” in Proc. ANCS, 2006.
[6] I. Papaefstathiou and V. Papaefstathiou, “Memory-efficient 5D packet classification at 40 Gbps,” in Proc. INFOCOM, 2007, pp. 1370–1378.
[7] A. Nikitakis and I. Papaefstathiou, “A memory-efficient FPGA-based classification engine,” in Proc. FCCM, 2008, pp. 53–62.
[8] I. Sourdis, “Designs & algorithms for packet and content inspection,” Ph.D. dissertation, Delft University of Technology, 2007.
[9] F. Baboescu, S. Singh, and G. Varghese, “Packet classification for core routers: Is there an alternative to CAMs?” in Proc. INFOCOM, 2003.
[10] D. E. Taylor, “Survey and taxonomy of packet classification techniques,” ACM Comput. Surv., vol. 37, no. 3, pp. 238–275, 2005.
[11] W. Jiang, Q. Wang, and V. K. Prasanna, “Beyond TCAMs: An SRAMbased parallel multi-pipeline architecture for terabit IP lookup,” in Proc. INFOCOM, 2008, pp. 1786–1794.
[12] K. Lakshminarayanan, A. Rangarajan, and S. Venkatachary. Algorithms for advanced packet classification with ternary CAMs. In Proc. SIGCOMM, pages 193–204, 2005.
[13] H. Song and J. W. Lockwood. Efficient packet classification for network intrusion detection using FPGA. In Proc. FPGA, pages 238–245, 2005.
[14] L. Karthik, and R. Anand, and V. Srinivasan, Algorithms for advanced packet classification with ternary CAMs. ACM Sigcomm, 2005.
[15] M. Buddhikot, and S. Suri, and M. Waldvogel, Space decomposition techniques for fast layer-4 switching. In Proceedings of Protocols for High Speed Networks, August 1999.
[16] V. Srinivasan, and S. Suri, and G. Varghese, Fast and scalable layer four switching. In Proceedings of ACM Sigcomm, September 1998.
[17] P. Gupta and N. McKeown, “Classifying packets with hierarchical intelligent cuttings,” in IEEE Micro, vol. 20, no. 1, pp. 34-41, Jan.-Feb. 2000.
[18] S. Singh, F. Baboescu, G. Varghese, and J. Wang, “Packet classification using multidimensional cutting,” in SIGCOMM 2003, pp. 213-224.
[19] Y. K. Chang, “Fast Binary and Multiway Prefix Searches for Packet Forwarding,” COMPUTER NETWORKS, Volume 51, Issue 3, pp. 588-605, February 2007.
[20] Renesas MARIE Blade 18Mb Full Ternary CAM. http://www.renesas.com. February 2005.
[21] SAMSUNG 18Mb DDRII+ SRAM. http://www.samsung.com. August 2008.
[22] W. Jiang and V. K. Prasanna. Parallel IP lookup using multiple SRAM-based pipelines. In Proc. IPDPS, 2008.
[23] T. V. Lakshman and D. Stiliadis. High-speed policy-based packet forwarding using efficient multi-dimensional range matching. In Proc. SIGCOMM, pages 203–214, 1998.
[24] 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