Parallel-search trie-based scheme for fast IP lookup

Roberto Rojas-Cessa, Lakshmi Ramesh, Dong Ziqian, Cai Lin, Nirwan Ansari

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

15 Scopus citations

Abstract

As data rates in the Internet increase, the Internet Protocol (IP) address lookup is required to be resolved in shorter resolution times. IP address lookup involves finding the longest matching prefix from a database of prefixes that better matches the destination address of a packet. The fastest IP-address lookup solutions are based on ternary content addressable memories (TCAMs), which can resolve the IP lookup in one memory-access time. However, TCAMs have a high power consumption and large complexity that may limit their scalability and storage capacity. An alternative is to use random access memory (RAM) that stores a forwarding table in a trie form. Proposed trie-based solutions for IP lookup require three or more memory-access times in the worst-case scenario. This makes them unattractive despite their reduced power consumption. In this paper, we propose a flexible and fast trie-based IP-lookup algorithm where parallel searching is performed. This algorithm performs lookup in two memoryaccess times whith a feasible amount of memory or three memory access times with reduced memory.

Original languageEnglish (US)
Title of host publicationIEEE GLOBECOM 2007 - 2007 IEEE Global Telecommunications Conference, Proceedings
Pages210-214
Number of pages5
DOIs
StatePublished - 2007
Event50th Annual IEEE Global Telecommunications Conference, GLOBECOM 2007 - Washington, DC, United States
Duration: Nov 26 2007Nov 30 2007

Publication series

NameGLOBECOM - IEEE Global Telecommunications Conference

Other

Other50th Annual IEEE Global Telecommunications Conference, GLOBECOM 2007
Country/TerritoryUnited States
CityWashington, DC
Period11/26/0711/30/07

All Science Journal Classification (ASJC) codes

  • General Engineering

Keywords

  • Hashing
  • Parallel search
  • Prefix expansion
  • RAM based
  • Trie search

Fingerprint

Dive into the research topics of 'Parallel-search trie-based scheme for fast IP lookup'. Together they form a unique fingerprint.

Cite this