TY - GEN
T1 - Grid of segment trees for packet classification
AU - Chang, Yeim Kuan
AU - Lin, Yung Chieh
AU - Lin, Chen Yu
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=77954346662&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77954346662&partnerID=8YFLogxK
U2 - 10.1109/AINA.2010.38
DO - 10.1109/AINA.2010.38
M3 - Conference contribution
AN - SCOPUS:77954346662
SN - 9780769540184
T3 - Proceedings - International Conference on Advanced Information Networking and Applications, AINA
SP - 1144
EP - 1149
BT - 24th IEEE International Conference on Advanced Information Networking and Applications, AINA 2010
T2 - 24th IEEE International Conference on Advanced Information Networking and Applications, AINA2010
Y2 - 20 April 2010 through 23 April 2010
ER -