Layer partitioned search tree for packet classification

Yeim-Kuan Chang, Chao Yen Chien

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

6 Citations (Scopus)

Abstract

Packet classification is an important building block of the Internet routers for many network applications. In this paper, we propose a scheme called Layer Partitioned Search Tree (LPST) to solve multi-field packet classification problem. LPST improves the traditional decision tree based schemes (e.g. Hyper Cuts and EffiCuts) by reconstructing the leaf nodes of the decision tree as an approximately balanced search tree. The rules may be stored not only in the buckets of leaf nodes but also in the internal nodes of LPST. Thus, searches on LPST may be completed immediately without searching all the buckets on the path to some leaf node if the packet already matches an internal node. The experimental results show that LPST requires less memory storage even if LPST categorizes the rules by two fields to reduce rule duplication rather than five fields in EffiCuts. Besides, in terms of number of memory accesses, LPST is better than Hyper Cuts and EffiCuts.

Original languageEnglish
Title of host publicationProceedings - 26th IEEE International Conference on Advanced Information Networking and Applications, AINA 2012
Pages276-282
Number of pages7
DOIs
Publication statusPublished - 2012 May 14
Event26th IEEE International Conference on Advanced Information Networking and Applications, AINA 2012 - Fukuoka, Japan
Duration: 2012 Mar 262012 Mar 29

Publication series

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

Other

Other26th IEEE International Conference on Advanced Information Networking and Applications, AINA 2012
CountryJapan
CityFukuoka
Period12-03-2612-03-29

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Layer partitioned search tree for packet classification'. Together they form a unique fingerprint.

Cite this