Gigabit packet classification by using lookahead caching

Pi Chung Wang*, Wei Chun Tseng, Chia Tai Chan, Yaw-Chung Chen

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

1 Scopus citations


Hashing is a widely used method to perform fast lookup. Several schemes have been proposed to support Internet lookup that includes IP lookup and packet classification. Rectangular search is a well-known packet classification scheme 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 satisfactory. 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 insufficient to provide gigabits throughput. In this paper, we proposed a novel "Lookahead Caching" which can significantly improve the performance of hash-based algorithm. 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 improve the performance by a factor of two. The scheme can be further enhanced using parallel processing.

Original languageEnglish
Article number1044541
Pages (from-to)117-121
Number of pages5
JournalProceedings - IEEE Computer Society's International Computer Software and Applications Conference
StatePublished - 26 Aug 2002
Event26th Annual International Computer Software and Applications Conference - Oxford, United Kingdom
Duration: 26 Aug 200229 Aug 2002

Fingerprint Dive into the research topics of 'Gigabit packet classification by using lookahead caching'. Together they form a unique fingerprint.

Cite this