IP lookup with low memory requirement and fast update

Michael Stübert Berger

doi:10.1109/HPSR.2003.1226720

IP lookup with low memory requirement and fast update

Michael Stübert Berger

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research

755 Downloads (Orbit)

Abstract

The paper presents an IP address lookup algorithm with low memory requirement and fast updates. The scheme, which is denoted prefix-tree, uses a combination of a trie and a tree search, which is efficient in memory usage because the tree contains exactly one node for each prefix in the routing table. The time complexity for update operations is low for the prefix-tree. The lookup operation for the basic binary prefix-tree may require that a high number of nodes be traversed. The paper presents improvements to decrease lookup time, including shortcut tables and multi-bit trees. The prefix-tree is compared to a trie and a path compressed trie using prefixes from a real routing table.

Original language	English
Title of host publication	Workshop on High Performance Switching and Routing, 2003, HPSR.
Publisher	IEEE
Publication date	2003
ISBN (Print)	0-7803-7710-9
DOIs	https://doi.org/10.1109/HPSR.2003.1226720
Publication status	Published - 2003
Event	2003 Workshop on High Performance Switching and Routing - Torino, Italy Duration: 24 Jun 2003 → 28 Jun 2003 http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=8691

Workshop

Workshop	2003 Workshop on High Performance Switching and Routing
Country/Territory	Italy
City	Torino
Period	24/06/2003 → 28/06/2003
Internet address	http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=8691

Bibliographical note

Copyright: 2003 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE

Access to Document

10.1109/HPSR.2003.1226720

BergerFinal published version, 411 KB

OpenUrl availability

Full text

Cite this

@inproceedings{9dcc048b49984905b0ba9641fb801ce6,

title = "IP lookup with low memory requirement and fast update",

abstract = "The paper presents an IP address lookup algorithm with low memory requirement and fast updates. The scheme, which is denoted prefix-tree, uses a combination of a trie and a tree search, which is efficient in memory usage because the tree contains exactly one node for each prefix in the routing table. The time complexity for update operations is low for the prefix-tree. The lookup operation for the basic binary prefix-tree may require that a high number of nodes be traversed. The paper presents improvements to decrease lookup time, including shortcut tables and multi-bit trees. The prefix-tree is compared to a trie and a path compressed trie using prefixes from a real routing table.",

author = "Berger, \{Michael St{\"u}bert\}",

note = "Copyright: 2003 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE; 2003 Workshop on High Performance Switching and Routing, HPSR 2003 ; Conference date: 24-06-2003 Through 28-06-2003",

year = "2003",

doi = "10.1109/HPSR.2003.1226720",

language = "English",

isbn = "0-7803-7710-9",

booktitle = "Workshop on High Performance Switching and Routing, 2003, HPSR.",

publisher = "IEEE",

address = "United States",

url = "http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=8691",

}

TY - GEN

T1 - IP lookup with low memory requirement and fast update

AU - Berger, Michael Stübert

N1 - Copyright: 2003 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE

PY - 2003

Y1 - 2003

N2 - The paper presents an IP address lookup algorithm with low memory requirement and fast updates. The scheme, which is denoted prefix-tree, uses a combination of a trie and a tree search, which is efficient in memory usage because the tree contains exactly one node for each prefix in the routing table. The time complexity for update operations is low for the prefix-tree. The lookup operation for the basic binary prefix-tree may require that a high number of nodes be traversed. The paper presents improvements to decrease lookup time, including shortcut tables and multi-bit trees. The prefix-tree is compared to a trie and a path compressed trie using prefixes from a real routing table.

AB - The paper presents an IP address lookup algorithm with low memory requirement and fast updates. The scheme, which is denoted prefix-tree, uses a combination of a trie and a tree search, which is efficient in memory usage because the tree contains exactly one node for each prefix in the routing table. The time complexity for update operations is low for the prefix-tree. The lookup operation for the basic binary prefix-tree may require that a high number of nodes be traversed. The paper presents improvements to decrease lookup time, including shortcut tables and multi-bit trees. The prefix-tree is compared to a trie and a path compressed trie using prefixes from a real routing table.

U2 - 10.1109/HPSR.2003.1226720

DO - 10.1109/HPSR.2003.1226720

M3 - Article in proceedings

SN - 0-7803-7710-9

BT - Workshop on High Performance Switching and Routing, 2003, HPSR.

PB - IEEE

T2 - 2003 Workshop on High Performance Switching and Routing

Y2 - 24 June 2003 through 28 June 2003

ER -

IP lookup with low memory requirement and fast update

Abstract

Workshop

Bibliographical note

Access to Document

OpenUrl availability

Fingerprint

Cite this