封包分類演算法被視為是在主幹網路的路由器中最花時間的運算。為了實現在最小的成本下達到最大的處理量，各種的分類法被相繼提出。2sBFCE是一個基於Bloom filter的三階段五維封包分類法，適合實作於高速可編譯硬體，例如FPGA。然而，使用Bloom filter執行prefix搜尋，每次的查詢都需要多次記憶體查找動作才能完成。2sBFCE循序的進行每個階段的查找動作使其執行效能下降。且在2sBFCE的搜尋方法中，range被直接轉換為prefix，以讓port的兩維也適用於使用Bloom filter做搜尋，但轉換所產生的多餘rule使記憶體使用量上升。上述的速度與成本缺點都降低了2sBFCE的整體效能。
在本篇論文中，我們針對2sBFCE提出三個改良方法。前兩個改善方法是基於循序搜尋，而第三個方法基於平行運算架構做考量。首先，我們提了三個分組方法與兩個降低記憶體使用量的方法，用以減少2sBFCE在第二階段中產生的大量crossproduct，同時平衡分組伴隨而來的記憶體使用量增加。接著，我們使用multiway range search針對port的端點做搜尋，以取代將port的range值轉換為prefix的方法，並減少額外產生的rule。隨後我們將multiway range search延伸使用至IP兩維的搜尋，以提升2sBFCE第一階段的搜尋速度。由於使用Bloom filter做搜尋，記憶體的存取次數會受到prefix長度所限制，因此，使用multiway range search存取次數遠小於使用 Bloom filter。最後，我們設計一個四階段的平行運算管線化架構以減少2sBFCE每個階段的搜尋次數。
實驗結果顯示，相較於2sBFCE，我們所提出的方法可以藉由使用一些額外的記憶體，達到有效的降低搜尋時間。我們針對效能的實驗尤其呈現了以下結果。我們所提出的分組方法，可以大幅度的減少第一個階段50%的搜尋時間，對於整體搜尋時間則降低了約30%。使用Multiway range search，更是將第一階段的平均查找次數減少至十四次以下，使總共的搜尋時間只花了原本方法的40%。而我們所提出的平行運算架構，則可以在9%到30%的2sBFCE搜尋時間內完成一個封包的查詢。最後，我們結合了所有先前提出的方法並達到使搜尋能夠在11%到34%的2sBFCE搜尋時間內完成。

Packet classification is considered as the most time consuming operation in backbone Internet routers. Various classifying methods are proposed in an attempt to achieve maximum throughput under minimum cost. The 2sBFCE [13] is a memory efficient 3-stage packet classifier based on Bloom filters. However, each query in 2sBFCE needs too many sequential lookups to search the Bloom filters and thus the system throughput is degraded. Also, direct range-to-prefix conversion for adapting port fields to prefix-based Bloom filters increases memory consumption due to duplicated rules.
In this thesis, three grouping schemes along with two memory cut-down methods are first developed to reduce excess cross-products generated in the second stage of 2sBFCE. Second, direct range-to-prefix conversion on port fields are replaced by multiway range search on endpoints of port field values in order to reduce redundant rules. Furthermore, we extend the multiway range search to IP fields for speeding up search time in the first stage of 2sBFCE. As a result, the number of memory accesses in multiway range search is much smaller than the size of prefixes (32/128 for IPv4/IPv6) needed in 2sBFCE. Finally, we design a parallel and pipelined architecture consisting of four stages in order to reduce the search time required in all the stages of 2sBFCE.
Our experimental results show that the proposed schemes are very effective in reducing the lookup times compared to the original 2sBFCE with some additional memory. Specifically, the proposed grouping methods can reduce 50% lookup times in the second stage and the overall reduction is 30%. By using the multiway range search in the first stage, the average lookup time is limited within 14 cycles and the total lookup times is 40% of 2sBFCE. For the proposed parallel and pipelined architecture, each query packet can be completed in 9% to 30% of the search time needed in 2sBFCE. The overall search time by integrating all of our proposed schemes is only 11% to 34% of the search time taken in 2sBFCE.

[1] F. Baboescu and G. Varghese, “Scalable Packet Classification”, in ACM SIGCOMM, August 2001.
[2] B. Bloom, “Space/time trade-offs in hash coding with allowable errors”, in ACM Communications, July 1970.
[3] Y.-K. Chang and Y.-C. Lin, "Dynamic Segment Trees for Ranges and Prefixes", in IEEE Transactions on Computer, June 2007.
[4] Y.-K. Chang, “Efficient Multidimensional Packet Classification with Fast Updates”, in IEEE Transactions on Computer, April 2009.
[5] S. Dharmapurikar, P. Krishnamurthy, and D. E. Taylor, “Longest Prefix Matching Using Bloom Filters”, in ACM SIGCOMM, August 2003.
[6] Q. Dong, S. Banerjee, J. Wang, and D. Agrawal, “Wire Speed Packet Classification without TCAMs: A Few More Registers (And A Bit of Logic) Are Enough”, in ACM SIGMETRICS, June 2007.
[7] S. Dharmapurikar, H. Song, J. Turner, and J. Lockwood, “Fast Packet Classification Using Bloom filters”, in ACM/IEEE ANCS, December 2006.
[8] P. Gupta and N. McKeown, “Packet Classification using Hierarchical Intelligent Cuttings”, in IEEE Micro, January/Februrary 2000.
[9] P. Gupta and N. Mckeown, “Algorithms for packet classification”, in IEEE Network, March/April 2001.
[10] W. Jiang, and V. K. Prasanna, “Large-Scale Wire-Speed Packet Classification on FPGAs”, in ACM FPGA, Februrary. 2009.
[11] T. V. Lakshman and D. Stiliadis, “High-Speed Policy-based Packet Forwarding Using Efficient Multi-dimensional Range Matching”, in ACM SIGCOMM, September 1998.
[12] B. Lampson, V. Srinivasan, G. Varghese, “IP Lookups Using Multiway and Multicolumn Search”, in IEEE INFOCOM, April 1998.
[13] A. Nikitakis and I. Papaefstathiou, “A memory-efficient FPGA-based classification engine”, in IEEE FCCM, April 2008.
[14] M. V. Ramakrishna, E. Fu, and E. Bahcekapili, “Efficient Hardware Hashing Functions for High Performance Computers”, in IEEE Transactions on Computers, December 1997.
[15] M.A. Ruiz-Sanchez, E.W. Biersack, and W. Dabbous, “Survey and Taxonomy of IP Address Lookup Algorithm,” in IEEE Network, March/April 2001.
[16] H. Song, and J. W. Lockwood, “Efficient Packet Classification for Network Intrusion Detection using FPGA”, in ACM FPGA, February 2005.
[17] D. E. Taylor, J. S. Turner, “Scalable Packet Classification using Distributed Crossproducting of Field Labels”, in IEEE Infocom, March 2005.
[18] D. E. Taylor and J. Turner, “ClassBench: A Packet Classification Benchmark”, in IEEE Infocom, March 2005.
[19] D. E. Taylor, “Surveys and Taxonomy of Packet Classification Techniques”, in ACM Computing Surveys, September 2005.
[20] P.-C. Wang, “Scalable packet classification with controlled cross-producting”, in Computer Networks, April. 2009.