Paper Info
Title
Grid of Segment Trees for Packet Classification
Abstract
Packet classification problem has received much attention and continued to be an important topic in recent years. In packet classification problem, each incoming packet should be classified into flows according to a set of pre-defined rules. Grid-of-tries (GoT) is one of the traditional algorithmic schemes for solving 2-dimensional packet classification problem. The advantage of GoT is that it uses the switch pointers to avoid backtracking operation during the search process. However, the primary data structure of GoT is base on binary tries. The traversal of binary tries decreases the performance of GoT due to the heights of binary tries are usually high. In this paper, we propose a scheme called GST (Grid of Segment Trees). GST modifies the original GoT by replacing the binary tries with segment trees. The heights of segment trees are much shorter than those of binary tries. As a result, the proposed GST can inherit the advantages of GoT and segment trees to achieve better performance. Experiments conducted on three different kinds of rule tables show that our proposed scheme performs better than traditional schemes, such as hierarchical tries and grid-of-tries.
Year
DOI
Venue
2010
10.1109/AINA.2010.38
AINA
Keywords
Field
DocType
traditional algorithmic,got,gst,2-dimensional packet classification problem,traditional algorithmic scheme,proposed gst,grid computing,tree data structures,segment trees,packet classification,data structures,data structure,traditional scheme,grid-of-tries,better performance,proposed scheme,binary try,predefined rules,segment tree,incoming packet,backtracking operation,packet classification problem,grid of segment trees,computer science,application software,classification algorithms,2 dimensional,quality of service,memory management,switches
Data structure,Tree traversal,Computer science,Network packet,Tree (data structure),Computer network,Theoretical computer science,Backtracking,Statistical classification,Grid,Binary number
Conference
ISSN
ISBN
Citations 
1550-445X
978-1-4244-6695-5
2
PageRank 
References 
Authors
0.38
0
3
Name
Order
Citations
PageRank
Yeimkuan Chang124727.93
Yung-Chieh Lin216710.50
Chen-Yu Lin320.38