loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
An O(log n) Dynamic Router-Table Design
March 2004 (vol. 53 no. 3)
pp. 351-363
ASCII Text
x 
 
Sartaj Sahni, Kun Suk Kim, "An O(log n) Dynamic Router-Table Design," IEEE Transactions on Computers, vol. 53, no. 3, pp. 351-363, March, 2004.
 
 
BibTex
x
 
@article{ 10.1109/TC.2004.1261840,
author = {Sartaj Sahni and Kun Suk Kim},
title = {An O(log n) Dynamic Router-Table Design},
journal ={IEEE Transactions on Computers},
volume = {53},
number = {3},
issn = {0018-9340},
year = {2004},
pages = {351-363},
doi = {http://doi.ieeecomputersociety.org/10.1109/TC.2004.1261840},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - JOUR
JO - IEEE Transactions on Computers
TI - An O(log n) Dynamic Router-Table Design
IS - 3
SN - 0018-9340
SP351
EP363
EPD - 351-363
A1 - Sartaj Sahni,
A1 - Kun Suk Kim,
PY - 2004
KW - Packet routing
KW - longest matching prefix
KW - red-black trees.
VL - 53
JA - IEEE Transactions on Computers
ER -
 

Abstract—Internet (IP) packet forwarding is typically done by finding the longest prefix in a router table that matches the packet's destination address. For W{\hbox{-}}{\rm bit} destination addresses, the use of binary tries enables us to determine the longest matching prefix in O(W) time, independent of the number n of prefixes in the router table. New prefixes may be inserted and old ones deleted in O(W) time also. Since n << 2^W in real router tables, it is desirable to develop a data structure that permits longest prefix matching as well as the insertion and deletion of prefixes in O(\log n). These three operations can be done with O(\log n) cache misses using a B-tree data structure [CHECK END OF SENTENCE]. However, the runtime (including operation cost and cost of cache misses) is not O(\log n). In this paper, we develop a data structure in which prefix matching, prefix insertion, and deletion can each be done in O(\log n) time. Experiments using real IPv4 routing databases indicate that, although the proposed data structure is slower than optimized variable-stride tries for longest prefix matching, the proposed data structure is considerably faster for the insert and delete operations.

[1] A. Bremler-Barr, Y. Afek, and S. Har-Peled, Routing with a Clue Proc. ACM SIGCOMM, pp. 203-214, 1999.[2] G. Chandranmenon and G. Varghese, Trading Packet Headers for Packet Processing IEEE Trans. Networking, 1996.[3] G. Cheung, S. McCanne, Optimal Routing Table Design for IP Address Lookups under Memory Constraints Proc. IEEE INFOCOM, 1999.[4] M. Degermark, A. Brodnik, S. Carlsson, and S. Pink, Small Forwarding Tables for Fast Routing Lookups Proc. ACM SIGCOMM, pp. 3-14, 1997.[5] W. Doeringer, G. Karjoth, and M. Nassehi, Routing on Longest-Matching Prefixes IEEE/ACM Trans. Networking, vol. 4, no. 1, pp. 86-97, 1996.[6] F. Ergun, S. Mittra, S. Sahinalp, J. Sharp, and R. Sinha, A Dynamic Lookup Scheme for Bursty Access Patterns Proc. IEEE INFOCOM, 2001.[7] P. Gupta and N. McKeown, Dynamic Algorithms with Worst-Case Performance for Packet Classification IFIP Networking, 2000.[8] E. Horowitz, S. Sahni, and D. Mehta, Fundamentals of Data Structures in C++. New York: W.H. Freeman, 1995.[9] B. Lampson, V. Srinivasan, and G. Varghese, IP Lookup Using Multi-Way and Multicolumn Search Proc. IEEE INFOCOM, 1998.[10] A. McAuley and P. Francis,"Fast Routing Table Lookup Using CAMs," Proc. IEEE Infocom, vol. 3, IEEE CS Press, Los Alamitos, Calif., 1993, pp. 1382-1391.[11] Merit, Ipma Statistics,http://nic.merit.eduipma, 2000.[12] P. Newman et al., "IP Switching and Gigabit Routers," IEEE Comm., Vol. 35, No. 1, Jan. 1997, pp. 64-69.[13] S. Nilsson and G. Karlsson, Fast Address Look-Up for Internet Routers IEEE Broadband Comm., 1998.[14] S. Sahni and K. Kim, Efficient Construction of Fixed-Stride Multibit Tries for IP Lookup Proc. Eighth IEEE Workshop Future Trends of Distributed Computing Systems, 2001.[15] S. Sahni and K. Kim, Efficient construction of Variable-Stride Multibit Tries for IP Lookup Proc. IEEE Symp. Applications and the Internet (SAINT), 2002.[16] S. Sahni and K. Kim, Efficient Dynamic Lookup for Bursty Access Patterns in preparation.[17] K. Sklower, A Tree-Based Routing Table for Berkeley Unix technical report, Univ. of California, Berkeley, 1993.[18] V. Srinivasan and G. Varghese, Faster IP Lookups Using Controlled Prefix Expansion ACM Trans. Computer Systems, pp. 1-40, Feb. 1999.[19] S. Suri, G. Varghese, and P. Warkhede, Multiway Range Trees: Scalable IP Lookup with Fast Updates Proc. GLOBECOM, 2001.[20] M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, Scalable High Speed IP Routing Lookups Proc. ACM SIGCOMM, pp. 25-36, 1997.

Index Terms:
Packet routing, longest matching prefix, red-black trees.
Citation:
Sartaj Sahni, Kun Suk Kim, "An O(log n) Dynamic Router-Table Design," IEEE Transactions on Computers, vol. 53, no. 3, pp. 351-363, Mar. 2004, doi:10.1109/TC.2004.1261840
Usage of this product signifies your acceptance of the Terms of Use.