Packet Classification Using Two-Dimensional Binary Search on Length 


Vol. 32,  No. 9, pp. 577-588, Sep.  2007


PDF
  Abstract

The rapid growth of the Internet has stimulated the development of various new applications and services, and the service providers and the Internet users now require different levels of service qualities rather than current best-effort service which treats all incoming packet equally. Therefore, next generation routers should provide the various levels of services. In order to provide the quality of services, incoming packets should be classified into flows according to pre-defined rules, and this should be performed for all incoming packets in wire-speed. Packet classification not only involves multi-dimensional search but also finds the highest priority rule among all matching rules. Area-based quad-trie is a very good algorithm that constructs a two-dimensional trie using source and destination prefix fields. However, it performs the linear search for the prefix length, and hence it does not show very good search performance. In this paper, we propose to apply binary search on length to the area-based quad-trie algorithm. In improving the search performance, we also propose two new algorithms considering the priority of rules in building the trie.

  Statistics
Cumulative Counts from November, 2022
Multiple requests among the same browser session are counted as one view. If you mouse over a chart, the values of data points will be shown.


  Cite this article

[IEEE Style]

J. H. Mun and H. Lim, "Packet Classification Using Two-Dimensional Binary Search on Length," The Journal of Korean Institute of Communications and Information Sciences, vol. 32, no. 9, pp. 577-588, 2007. DOI: .

[ACM Style]

Ju Hyoung Mun and Hyesook Lim. 2007. Packet Classification Using Two-Dimensional Binary Search on Length. The Journal of Korean Institute of Communications and Information Sciences, 32, 9, (2007), 577-588. DOI: .

[KICS Style]

Ju Hyoung Mun and Hyesook Lim, "Packet Classification Using Two-Dimensional Binary Search on Length," The Journal of Korean Institute of Communications and Information Sciences, vol. 32, no. 9, pp. 577-588, 9. 2007.

Search
(IN TITLE, AUTHOR, ABSTRACT,KEYWORDS)

Advanced Search ▼

POPULAR KEYWORDS
(TOP 10 KEYWORDS)

Recent Publications
(LAST 3 YEARS)






pISSN : 1226 - 4717
eISSN : 2287 - 3880