FMPC: A Fast Multi-Dimensional Packet Classification Algorithm

Abstract:

With the rapid development of the Internet, the number of firewall rules is increasing. The enormous quantity of rules challenges the performance of the packet classification that has already become a bottleneck in firewalls. This dissertation proposes a rapid and multi-dimensional algorithm for packet classification based on BSOL(Binary Search On Leaves), which is named FMPC(FastMulti-dimensional Packet Classification). Different from BSOL, FMPC cuts all dimensions at the same time to decompose rule spaces and stores leaf spaces into hash tables; FMPC constructs a Bloom Filter for every hash table and stores them into embedded SRAM. When classifying a packet, FMPC performs parallel queries on Bloom Filters and determines how to visit hash tables according to the results. Algorithm analysis and the result of simulations show: the average number of hash-table lookups of FMPC is 1 when classifying a packet, which is much smaller than that of BSOL; inthe worst case, the number of hash-table lookups of FMPCisO(logwmax+1⁡), which is also smaller than that of BSOL in multi-dimensional environment, where w_max is the length, in bits, of the dimension whose length is the longest..

• Periodical: Applied Mechanics and Materials (Volumes 644-650)
• Pages: 3365-3370
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.644-650.3365
• Online since: September 2014
• Authors: Zhen Hong Guo*, Lin Li, Qing Wang, Meng Lin, Rui Pan
• Keywords: Bloom Filter, Firewall Rule, Hash Table, Multi-Dimensional, Packet Classification

References

[1] Haibin Lu, SartajSahni. O(logW) Multidimensional Packet Classification. IEEE Transactions on Networking, 2007, 15(2): 462-472.

[2] P. Gupta, N. McKeown. Packet Classification Using Hierarchical Intelligent Cuttings. IEEE Micro, 2000, 20(1): 34-41.

DOI: 10.1109/40.820051

[3] V. Srinivasan, G. Varghese, S. Suri, et al. Fast and Scalable Layer Four Switching. SIGCOMM'98, Vancouver, Canada: ACM, 1998, 191-202.

DOI: 10.1145/285243.285282

[4] T.V. Lakshman, D. Stiliadis. High-Speed Policy-based Packet Forwarding Using Efficient Multi-dimensional Range Matching. SIGCOMM'98, Vancouver, Canada: ACM, 1998, 203-214.

DOI: 10.1145/285243.285283

[5] F. Baboescu, G. Varghese. Scalable Packet Classification. SIGCOMM'01, San Diego, USA: ACM, 2001, 199-210.

DOI: 10.1145/964723.383075