|
Published Articles >> Table of Contents >> Abstract
March 2004 (Vol. 53, No. 3)
pp. 351-363
An O(log n) Dynamic Router-Table Design
Sartaj Sahni, IEEE
Kun Suk Kim
Full Article Text:
   
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/TC.2004.1261840
Send link to a friend
| 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.
|
 References
|
[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.
|
 Additional Information
|
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
|
|
RSS Feed