A Smart Set-Pruning Trie for Packet Classification 


Vol. 36,  No. 11, pp. 1285-1296, Nov.  2011


PDF
  Abstract

Packet classification is one of the basic and important functions of the Internet routers, and it became more important along with new emerging application programs requiring real-time transmission. Since packet classification should be accomplished in line-speed on each incoming input packet for multiple header fields, it becomes one of the challenges in designing Internet routers. Various packet classification algorithms have been proposed to provide the high-speed packet classification. Hierarchical approach achieves effective packet classification performance by significantly narrowing down the search space whenever a field lookup is completed. However, hierarchical approach involves back-tracking problem. In order to solve the problem, set-pruning trie and grid-of-trie algorithms are proposed. However, the algorithm either causes excessive node duplication or heavy pre-computation. In this paper, we propose a smart set-pruning trie which reduces the number of node duplication in the set-pruning trie by the simple merging of the lower-level tries. Simulation result shows that the proposed trie has the reduced number of copied nodes by 2-8% compared with the set-pruning 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]

S. Min, N. Lee, H. Lim, "A Smart Set-Pruning Trie for Packet Classification," The Journal of Korean Institute of Communications and Information Sciences, vol. 36, no. 11, pp. 1285-1296, 2011. DOI: .

[ACM Style]

Seh-won Min, Nara Lee, and Hyesook Lim. 2011. A Smart Set-Pruning Trie for Packet Classification. The Journal of Korean Institute of Communications and Information Sciences, 36, 11, (2011), 1285-1296. DOI: .

[KICS Style]

Seh-won Min, Nara Lee, Hyesook Lim, "A Smart Set-Pruning Trie for Packet Classification," The Journal of Korean Institute of Communications and Information Sciences, vol. 36, no. 11, pp. 1285-1296, 11. 2011.

Search
(IN TITLE, AUTHOR, ABSTRACT,KEYWORDS)

Advanced Search ▼

POPULAR KEYWORDS
(TOP 10 KEYWORDS)

Recent Publications
(LAST 3 YEARS)






pISSN : 1226 - 4717
eISSN : 2287 - 3880