Priority tries for IP address lookup

Hyesook Lim, Changhoon Yim, Earl E. Swartzlander

Research output: Contribution to journalArticlepeer-review

49 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

Bibliographical note

Funding Information:
The research of the first author (H. Lim) was supported by LG Yonam Foundation under the overseas research professor program and by the MKE(The Ministry of Knowledge Economy), Korea, under the HNRC-ITRC support program supervised by the NIPA (NIPA-2010-C1090-1011-0010). This work was also supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MEST) (2010-0000483). The work of the second author (C. Yim) was supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD) (KRF-2008-013-D00083) and by the MKE under the ITRC support program supervised by the NIPA (NIPA-2010-C1090-1031-0003). The preparation of this paper would not have been possible without the efforts of our students in SOC Design Laboratory at Ewha W. University on simulations. The authors are particularly grateful for Ju Hyoung Mun, A.G. Alagu Priya, and Geum Dan Jin.

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