High-speed packet classification using binary search on length

Hyesook Lim, Ju Hyoung Mun

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

15 Scopus citations

Abstract

Packet classification is one of the major challenges for next generation routers since it involves complicated multi-dimensional search as well as it should be performed in wire-speed for all incoming packets. Area-based quad-trie is an excellent algorithm in the sense that it constructs a two-dimensional trie using source and destination prefix fields for packet classification. However, it does not achieve good search performance since search is linearly performed for prefix length. In this paper, we propose a new packet classification algorithm which applies binary search on prefix length to the area-based quad-trie. In order to avoid the pre-computation required in the binary search on length, the proposed algorithm constructs multiple disjoint tries depending on relative levels in rule hierarchy. We also propose two new optimization techniques considering rule priorities. For different types of rule sets having about 5000 rules, performance evaluation result shows that the average number of memory accesses is 18 to 67 and the memory consumption is 22 to 41 bytes per rule.

Original languageEnglish
Title of host publicationANCS'07 - Proceedings of the 2007 ACM Symposium on Architecture for Networking and Communications
Pages137-144
Number of pages8
DOIs
StatePublished - 2007
Event3rd ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2007 - Orlando, FL, United States
Duration: 3 Dec 20074 Dec 2007

Publication series

NameANCS'07 - Proceedings of the 2007 ACM Symposium on Architecture for Networking and Communications

Conference

Conference3rd ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2007
Country/TerritoryUnited States
CityOrlando, FL
Period3/12/074/12/07

Keywords

  • area-based quad-trie
  • best matching rule
  • binary search on length
  • hashing
  • packet classification

Fingerprint

Dive into the research topics of 'High-speed packet classification using binary search on length'. Together they form a unique fingerprint.

Cite this