隨著網際網路的快速成長，網路封包分類技術必須應付與日俱增的封包處理量。在路由器中，封包分類通常都是第一道關卡，正因為分類技術的複雜性，封包分類常常成為網路架構中的瓶頸，然而大部分的解決方式並不彈性且適用於處理大量的資料量。
在本論文中，我們根據二元前置搜尋法，提出一個新的封包分類演算法，多維的封包分類規則表可轉換並實作成多維可搜尋的階層式陣列，每一層陣列可應用二元前置搜尋法快速搜尋。藉由各式各樣的測試資料來評估此演算法的效能，並且和現有的演算法比較。實驗結果顯示我們提出的方法不管在儲存量和查詢速度方面都表現的比現有的方法優異。更精確來說，我們提出的方法在二維的實驗中比既有的方法快了 29-97%；而在五維實驗中，更是比二元區段搜尋法加上整合式位元向量快了63-75%。

Fast packet classification is required for the increasing traffic demand because of the rapid growth of the Internet. Packet classification is often the first packet processing step in routers. Because of the complexity of the matching algorithms, packet classification is often a bottleneck in the performance of the network infrastructure. Most of the algorithmic solutions don’t scale very well.
In this thesis, we proposed a novel packet classification algorithm based on the binary prefix search. The data structure of a d-dimensional rule table is converted to a d-level sorted array for binary search on each level. We evaluated our scheme by a variety of filter tables and compared it with the other existing schemes. Our experiments showed that the proposed scheme performs better than other existing schemes in terms of speed and storage requirements. Specifically, the performance improvements of the proposed scheme in classification speed over the aggregated bit vector are 29-97% and 63-75% for tables of 1K-20K 2D rules and 100-2000 5D, respectively.

[1] Yeim-Kuan Chang, “Fast Binary Search Algorithms for IP Lookups”, 2003.
[2] B. Lampson, V. Srinivasan and G. Varghese, “IP Lookups using Multiway and Multicolumn search,” IEEE/ACM Transactions on Networking, Volume 3, Number 3, Pages 324-334, 1999.
[3] V. Srinivasan, G. Varghese, S. Suri, and M. Waldvogel, “Fast and Scalable Layer Four Switching,” in ACM Sigcomm, June1998
[4] F. Baboescu, S. Singh, and G. Varghese,Packet, “Classification for Core Routers: Is there an alternative to CAMs?,” in IEEE Infocom, 2003.
[5] T.V. Lakshman and D. Stiliadis, “High-Speed Policy-Based Packet Forwarding using Efficient Multi-Dimensional Range Matching, ” in ACM Sigcomm, September 1998.
[6] F. Baboescu and G. Varghese, “Scalable Packet Classification,” in ACM Sigcomm, August 2001.
[7] A. Feldmann, S. Muthukrishnan, “Tradeoffs for Packet Classification” in IEEE Infocom, March 2000.
[8] I. Coorporation, “Using the RDTSC Instruction for Performance Monitoring,” tech. rep., Intel Coorporation, 1997.
[9] P. Gupta and N. McKeown, “Packet Classification using Hierarchical Intelligent Cuttings,” in Hot Interconnects VII, August 1999.
[10] S. Singh, F. Baboecu, G. Varghese, and J. Wang, “Packet Classification Using Multidimensional Cutting,” in Proceedings of ACM Sigcomm’03, August 2003. Karlsruhe, Germany.
[11] V. Srinivasan, S. Suri, and G. Varghese, “Packet classification using tuple space search,” in SIGCOMM 99, pp135-146, 1999.
[12] M. E. Kounavis, A. Kumar, H. Vin, R. Yavatkar, and A. T. Campbell, “Directions in Packet Classification for Network Processors,” in Second Workshop on Network Processors(NP2), February 2003
[13] David E. Taylor and Jonathan S. Turner, “ClassBench: A Packet Classification Benchmark,” WUCSE-2004-28, May 21 2004.
[14] J. van Lunteren and T. Engbersen, “Fast and scalable packet classification,” IEEE Journal on Selected Areas in Communications, vol.21, pp. 560-571, May 2003.
[15] F.P.Preparata and M.I.Shamos, “Computational Geometry : An Introduction,” Springer-Verlag, 1985.
[16] Narlikar, Girija, Anindya Basu, and Francis Zane, “CoolCAMs : Power-Efficient TCAMs for Forwarding Engines” in Proc. IEEE INFOCOM’03, May 2003
[17] Ed Spitznagel, David Taylor, and Jonathan Turner, “Packet Classification Using Extended TCAMs”, in proc. 11th IEEE International Conference on Network Protocols
[18] EZchip Technologies, White Paper, “IPv4 to IPv6 is Not Merely 50% More”
[19] David E. Taylor, “Survey & Taxonomy of Packet Classification Techniques,” WUCSE-2004-24, May 10 2004