Fast packet classification through tuple reduction and lookahead caching

Pi Chung Wang, Chia Tai Chan, Shuo Cheng Hu, Wei Chun Tseng, Yaw-Chung Chen

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations


Packet classification is a technique that classifies the flows into different classes. Nowadays the packet classification plays an important role for many new Internet services. Rectangle search is a well-known packet classification scheme which is based on multiple hash accesses for different filter length. It shows good scalability with respect to the number of filters; however, the lookup performance is not fast enough. For example, through experiments, each packet classification takes about 40 hash accesses in a 100,000-filter database and each hash access may take more than one memory access. Obviously, this is not capable to provide gigabits throughput. We propose an efficient scheme to improve the rectangle search. The scheme consists of two parts. In the first part, the "tuple reduction algorithm" based on filter duplication is proposed. In spite of the increased number of filters, the pre-computation information is dramatically reduced. The performance has increased two times while only about one quarter storage is required. Secondly, we propose a novel "lookahead caching" which can further improve the lookup performance. The basic idea is to find out the "un-matched" case for each incoming packet, thus it is different from the traditional caching mechanism. The experimental results indicate that the proposed scheme can fulfill OC-192 throughput.

Original languageEnglish
Title of host publicationProceedings - 10th IEEE International Conference on Networks
Subtitle of host publicationTowards Network Superiority, ICON 2002
Number of pages6
StatePublished - 1 Dec 2002
Event10th IEEE International Conference on Networks: Towards Network Superiority, ICON 2002 - Singapore, Singapore
Duration: 27 Aug 200230 Aug 2002

Publication series

NameIEEE International Conference on Networks, ICON
ISSN (Print)1556-6463


Conference10th IEEE International Conference on Networks: Towards Network Superiority, ICON 2002

Fingerprint Dive into the research topics of 'Fast packet classification through tuple reduction and lookahead caching'. Together they form a unique fingerprint.

Cite this