Grid of segment trees for packet classification

Yeim Kuan Chang, Yung Chieh Lin, Chen Yu Lin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Citations (Scopus)

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.

Original languageEnglish
Title of host publication24th IEEE International Conference on Advanced Information Networking and Applications, AINA 2010
Pages1144-1149
Number of pages6
DOIs
Publication statusPublished - 2010
Event24th IEEE International Conference on Advanced Information Networking and Applications, AINA2010 - Perth, WA, Australia
Duration: 2010 Apr 202010 Apr 23

Publication series

NameProceedings - International Conference on Advanced Information Networking and Applications, AINA
ISSN (Print)1550-445X

Other

Other24th IEEE International Conference on Advanced Information Networking and Applications, AINA2010
Country/TerritoryAustralia
CityPerth, WA
Period10-04-2010-04-23

All Science Journal Classification (ASJC) codes

  • General Engineering

Fingerprint

Dive into the research topics of 'Grid of segment trees for packet classification'. Together they form a unique fingerprint.

Cite this