Priority tries for IP address lookup

Hyesook Lim, Changhoon Yim, Earl E. Swartzlander

Research output: Contribution to journalArticlepeer-review

44 Scopus citations

Abstract

High-speed IP address lookup is essential to achieve wire speed packet forwarding in Internet routers. The longest prefix matching for IP address lookup is more complex than exact matching because it involves dual dimensions: length and value. This paper presents a new formulation for IP address lookup problem using range representation of prefixes and proposes an efficient binary trie structure named a priority trie. In this range representation, prefixes are represented as ranges on a number line between 0 and 1 without expanding to the maximum length. The best match to a given input address is the smallest range that includes the input. The priority trie is based on the trie structure, with empty internal nodes in the trie replaced by the priority prefix which is the longest among those in the subtrie rooted by the empty nodes. The search ends when an input matches a priority prefix, which significantly improves the search performance. Performance evaluation using real routing data shows that the proposed priority trie is very good in performance metrics such as lookup speed, memory size, update performance, and scalability.

Original languageEnglish
Article number5416681
Pages (from-to)784-794
Number of pages11
JournalIEEE Transactions on Computers
Volume59
Issue number6
DOIs
StatePublished - 2010

Keywords

  • Binary trie
  • IP address lookup
  • Internet
  • Priority trie
  • Range representation
  • Router

Fingerprint

Dive into the research topics of 'Priority tries for IP address lookup'. Together they form a unique fingerprint.

Cite this