Parallel table lookup for next generation internet

Li Che Hung*, Yaw-Chung Chen

*Corresponding author for this work

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

3 Scopus citations

Abstract

The rapid growth of Internet population leads to the shortage of IP addresses. The next generation IP protocol, IPv6, which extends the IP address length from 32 bits to 128 bits, was proposed around mid-ninety to accommodate the problem. IP table lookup is based on the longest prefix matching. Most of the existing lookup algorithms scale poorly as IP address space expands to 128 bits. We propose a table lookup scheme for IPv6 using binary search among prefix-length based on parallel processing to improve the performance. We merge hash tables to reduce the lookup complexity of the worst case and use both pipeline and multi-threading to improve the throughput of the average case. Our scheme is realized based on parallel architecture. The simulation results show that the maximum throughput is one lookup per 100 clock cycles in average. This means that, with 600 MHz clock rate, our proposed scheme is able to accomplish 6 million lookups for IPv6 packets. It is more cost effective comparing with existing commercial products in terms of number of lookups per MHz.

Original languageEnglish
Title of host publicationProceedings - 32nd Annual IEEE International Computer Software and Applications Conference, COMPSAC 2008
Pages52-59
Number of pages8
DOIs
StatePublished - 23 Sep 2008
Event32nd Annual IEEE International Computer Software and Applications Conference, COMPSAC 2008 - Turku, Finland
Duration: 28 Jul 20081 Aug 2008

Publication series

NameProceedings - International Computer Software and Applications Conference
ISSN (Print)0730-3157

Conference

Conference32nd Annual IEEE International Computer Software and Applications Conference, COMPSAC 2008
CountryFinland
CityTurku
Period28/07/081/08/08

Fingerprint Dive into the research topics of 'Parallel table lookup for next generation internet'. Together they form a unique fingerprint.

  • Cite this

    Hung, L. C., & Chen, Y-C. (2008). Parallel table lookup for next generation internet. In Proceedings - 32nd Annual IEEE International Computer Software and Applications Conference, COMPSAC 2008 (pp. 52-59). [4591532] (Proceedings - International Computer Software and Applications Conference). https://doi.org/10.1109/COMPSAC.2008.69