skip to main content
article

O(logW) multidimensional packet classification

Published: 01 April 2007 Publication History

Abstract

We use a collection of hash tables to represent a multidimensional packet classification table. These hash tables are derived from a trie-representation of the multidimensional classifier. The height of this trie is O(W), where W is the sum of the maximum possible length, in bits, of each of the fields of a filter. The leaves at level i of the trie together with markers for some of the leaves at levels j such that j > i are stored in a hash table Hi. The placement of markers is such that a binary search of the Hi's successfully locates the highest-priority filter that matches any given packet. The number of hash tables equals the trie height, O(W). Hence, a packet may be classified by performing O(log W) hash-table lookups. So the expected lookup-complexity of our data structure for multidimensional packet classification is O(log W). Our proposed scheme affords a memory advantage over the O(log W) 1-D scheme of Waldvogel et al. For multidimensional packet classification, our proposed scheme provides both a time and memory advantage over the extended grid-of-tries scheme of Baboescu et al.

References

[1]
{1} F. Baboescu and G. Varghese, "Scalable packet classification," presented at the ACM SIGCOMM, San Diego, CA, 2001.
[2]
{2} F. Baboescu and G. Varghese, "Fast and scalable conflict detection for packet classifiers," in Proc. 10th IEEE Int. Conf. Network Protocols (ICNP'02), 2002, pp. 270-279.
[3]
{3} F. Baboescu, S. Singh, and G. Varghese, "Packet classification for core routers: Is there an alternative to CAMs?," in Proc. IEEE INFOCOM, 2003, pp. 53-63.
[4]
{4} F. Braun, J. Lockwood, and M. Waldvogel, "Reconfigurable router modules using network protocol wrappers," in Field-Programmable Logic and Applications (FPL 2001). Berlin, Germany: Springer-Verlag, Aug. 2001, vol. 2147, Lecture Notes in Computer Science, pp. 254-263.
[5]
{5} M. Berg, M. Kreveld, and J. Snoeyink, "Two- and three-dimensional point location in rectangular subdivisions," J. Alg., vol. 18, no. 2, pp. 256-277, 1995.
[6]
{6} A. Broder and M. Mitzenmacher, "Using multiple hash functions to improve IP lookups," in Proc. IEEE INFOCOM, 2001, pp. 1454-1463.
[7]
{7} M. Buddhikot, S. Suri, and M. Waldvogel, "Space decomposition techniques for fast layer-4 switching," in Protocols for High-Speed Networks , 1999, pp. 25-42.
[8]
{8} P. V. Emde Boas, R. Kass, and E. Zijlstra, "Design and implementation of an efficient priority queue," Math. Syst. Theory, vol. 10, pp. 99-127, 1977.
[9]
{9} D. Eppstein and S. Muthukrishnan, "Internet packet filter management and rectangle geometry," in Proc. 12th ACM-SIAM Symp. Discrete Algorithms , 2001, pp. 827-835.
[10]
{10} A. Feldman and S. Muthukrishnan, "Tradeoffs for packet classification," in Proc. IEEE INFOCOM, 2000, pp. 1193-1202.
[11]
{11} P. Gupta and N. McKeown, "Packet classification using hierarchical intelligent cuts," presented at the ACM SIGCOMM, Cambridge, MA, 1999.
[12]
{12} P. Gupta, Recursive Flow Classification (RFC). Stanford Univ. {On-line}. Available: http://klamath.stanford.edu/~pankaj/rfcv1.0.tar.gz.
[13]
{13} P. Gupta and N. Mckeown, "Algorithms for packet classification," IEEE Network, vol. 15, no. 2, pp. 24-32, 2001.
[14]
{14} A. Hari, S. Suri, and G. Parulkar, "Detecting and resolving packet filter conflicts," in Proc. IEEE INFOCOM, 2000, pp. 1203-1212.
[15]
{15} E. Horowitz, S. Sahni, and S. Rajasekeran, Computer Algorithms/C++ . New York: W. H. Freeman, 1997.
[16]
{16} Internet Algorithms Lab. {Online}. Available: http://www.ial.ucsd.edu/ classification/.
[17]
{17} K. Kim and S. Sahni, "IP lookup by binary search on length," J. Interconnect. Netw., vol. 3, pp. 105-128, 2002.
[18]
{18} T. Lakshman and D. Stiliadis, "High speed policy-based packet forwarding using efficient multi-dimensional range matching," presented at the ACM SIGCOMM, Vancouver, BC, Canada, 1998.
[19]
{19} Merit, IPMA Statistics. {Online}. Available: http://nic.merit.edu/ipma
[20]
{20} L. Qiu, G. Varghese, and S. Suri, "Fast firewall implementations for software and hardware-based routers," in Proc. 9th Int. Conf. Network Protocols (ICNP), 2001, pp. 241-250.
[21]
{21} M. Ruiz-Sanchez, E. Biersack, and W. Dabbous, "Survey and taxonomy of IP address lookup algorithms," IEEE Network, vol. 15, no. 2, pp. 8-23, Mar.-Apr. 2001.
[22]
{22} S. Sahni, K. Kim, and H. Lu, "Data structures for one-dimensional packet classification using most-specific-rule matching," Int. J. Found. Comput. Sci., vol. 14, no. 3, pp. 337-358, 2003.
[23]
{23} H. Samet, Application of Spatial Data Structures: Computer Graphics, Image Processing, and GIS. Reading, MA: Addison-Wesley, 1989.
[24]
{24} V. Srinivasan, G. Varghese, S. Suri, and M. Waldvogel, "Fast and scalable layer 4 switching," presented at the ACM SIGCOMM, Vancouver, BC, Canada, 1998.
[25]
{25} V. Srinivasan, S. Suri, and G. Varghese, "Packet classification using tuple space search," in ACM SIGCOMM, Cambridge, MA, 1999.
[26]
{26} V. Srinivasan and G. Varghese, "Fast address lookups using controlled prefix expansion," ACM Trans. Comput. Syst., vol. 17, no. 1, pp. 1-40, Feb. 1999.
[27]
{27} V. Srinivasan, "A packet classification and filter management system," in Proc. IEEE INFOCOM, 2001, pp. 1464-1473.
[28]
{28} X. Sun and Y. Zhao, "Packet classification using independent sets," in IEEE Symp. Computers and Communications (ISCC 2003), 2003, pp. 83-90.
[29]
{29} Filter Set Generator. {Online}. Available: http://www.arl.wustl.edu/ ~det3/.
[30]
{30} M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, "Scalable high-speed prefix matching," ACM Trans. Comput. Syst., vol. 19, no. 4, pp. 440-482, Nov. 2001.
[31]
{31} D. E. Willard, "Log-logarithmic worst-case range queries are possible in space θ(N)," Inf. Process. Lett., vol. 17, pp. 81-84, 1983.

Cited By

View all
  • (2021)Enhancing the Performance of Flow Classification in SDN-Based Intelligent Vehicular NetworksIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2020.301404422:7(4141-4150)Online publication date: 1-Jul-2021
  • (2020)Many-field packet classification using CR-treeJournal of High Speed Networks10.3233/JHS-20063426:2(125-140)Online publication date: 1-Jan-2020
  • (2019)Clustering-based many-field packet classification in Software-Defined NetworkingJournal of Network and Computer Applications10.1016/j.jnca.2019.102428147:COnline publication date: 1-Dec-2019
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 15, Issue 2
April 2007
232 pages

Publisher

IEEE Press

Publication History

Published: 01 April 2007
Published in TON Volume 15, Issue 2

Author Tags

  1. binary search on levels
  2. expected complexity
  3. multidimensional packet classification

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 17 Feb 2025

Other Metrics

Citations

Cited By

View all

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media