loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Eighth IEEE Symposium on Computers and Communications
IP Lookup By Binary Search On Prefix Length
Kemer-Antalya, Turkey
June 30-July 03
ISBN: 0-7695-1961-X
ASCII Text
x 
 
Kun Suk Kim, Sartaj Sahni, "IP Lookup By Binary Search On Prefix Length," Computers and Communications, IEEE Symposium on, pp. 77, Eighth IEEE Symposium on Computers and Communications, 2003.
 
 
BibTex
x
 
@article{ 10.1109/ISCC.2003.1214104,
author = {Kun Suk Kim and Sartaj Sahni},
title = {IP Lookup By Binary Search On Prefix Length},
journal ={Computers and Communications, IEEE Symposium on},
volume = {0},
year = {2003},
issn = {1530-1346},
pages = {77},
doi = {http://doi.ieeecomputersociety.org/10.1109/ISCC.2003.1214104},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computers and Communications, IEEE Symposium on
TI - IP Lookup By Binary Search On Prefix Length
SN - 1530-1346
SP
EP
A1 - Kun Suk Kim,
A1 - Sartaj Sahni,
PY - 2003
KW - Packet routing
KW - router tables
KW - longest-prefix matching
KW - controlled prefix expansion
KW - binary search on length
KW - dynamic programming
VL - 0
JA - Computers and Communications, IEEE Symposium on
ER -
 
Kun Suk Kim, University of Florida, Gainesville
Sartaj Sahni, University of Florida, Gainesville
Waldvogel et al. [10] have proposed a collection of hash tables (CHT) organization for an IP router table. IP lookup can be done with O(log ldist) hash-table searches, where ldist is the number of distinct prefix-lengths (also equal to the number of hash tables in the CHT). Srinivasan and Varghese [9] have proposed the use of controlled prefix-expansion to reduce the value of ldist. The algorithm of [8] does not minimize the storage required by the prefixes and markers for the resulting set of prefixes. We develop an algorithm that minimizes storage requirement but takes O(nW3 + kW4) time, where k is the desired number of distinct lengths, n is the number of prefixes, and W is the length of the longest prefix. Also, we propose improvements to the heuristic of [8].
Index Terms:
Packet routing, router tables, longest-prefix matching, controlled prefix expansion, binary search on length, dynamic programming
Citation:
Kun Suk Kim, Sartaj Sahni, "IP Lookup By Binary Search On Prefix Length," iscc, pp.77, Eighth IEEE Symposium on Computers and Communications, 2003
Usage of this product signifies your acceptance of the Terms of Use.