Layered cutting scheme for packet classification

Yeim-Kuan Chang, Han Chen Chen

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

6 Citations (Scopus)

Abstract

Packet classification is an important topic for highspeed routers nowadays. There are many packet classification algorithms based on decision tree like Hicuts, Hypercuts and Hypersplit. Because Hicuts and Hypercuts divides the rule sets by cutting the address space into equal-sized subspaces, their cutting efficiency is not good. Although Hypersplit proposed a good end-point-based cutting scheme, the resulting tree depth is still very high. In this paper, we propose a multi-dimensional cutting algorithm to significantly reduce the decision tree depth and a multi-layered scheme to dramatically reduce the usage of memory. Our experimental results show that the proposed layered scheme needs much less memory than Hypersplit for Firewall and IPC rule tables with a factor of 2 to 106 improvement while the proposed layered scheme needs a little more memory than Hypersplit for some of ACL tables. In addition, in terms of number of memory accesses, the proposed layered scheme and Hypercuts are better than Hicuts and Hypersplit for all tables while the proposed layered scheme is better than Hypercuts for ACL and Firewall tables. In terms of number of memory accesses, our layered cutting scheme and Hypercuts perform equally well for small rule tables. But, in larger rule tables, the proposed layered cutting scheme has better performance.

Original languageEnglish
Title of host publicationProceedings - 25th IEEE International Conference on Advanced Information Networking and Applications, AINA 2011
Pages675-681
Number of pages7
DOIs
Publication statusPublished - 2011 Jun 3
Event25th IEEE International Conference on Advanced Information Networking and Applications, AINA 2011 - Biopolis, Singapore
Duration: 2011 Mar 222011 Mar 25

Publication series

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

Other

Other25th IEEE International Conference on Advanced Information Networking and Applications, AINA 2011
Country/TerritorySingapore
CityBiopolis
Period11-03-2211-03-25

All Science Journal Classification (ASJC) codes

  • General Engineering

Fingerprint

Dive into the research topics of 'Layered cutting scheme for packet classification'. Together they form a unique fingerprint.

Cite this