Fast IP routing lookups for high performance routers

T. Kijkanjanarat, H. J. Chao

Research output: Contribution to journalArticlepeer-review

Abstract

The key to the success of the next generation IP networks to provide good services relies on the deployment of high performance routers to do fast IP routing lookups. In this paper, we propose a new algorithm for fast IP lookups using a so-called two-trie structure. The two-trie structure provides the advantages in that less memory space is required for representing a routing table than the standard trie while it still provides fast IP lookups. Based on the simulation result, the memory space can be saved around 27% over the standard trie while a lookup operation takes 1.6 memory accesses in the average case and 8 memory accesses in the worst case. Also, the structure is not based on any assumptions about the distribution of the prefix lengths in routing tables. Thus, increasing the lengths from 32 to 128 bit (from IPv4 to IPv6) does not affect the main structure.

Original languageEnglish (US)
Pages (from-to)1415-1422
Number of pages8
JournalComputer Communications
Volume22
Issue number15
DOIs
StatePublished - Sep 25 1999

ASJC Scopus subject areas

  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Fast IP routing lookups for high performance routers'. Together they form a unique fingerprint.

Cite this