More Web Proxy on the site http://driver.im/

research-article

Enhanced Interval Trees for Dynamic IP Router-Tables

Authors:

Sartaj SahniAuthors Info & Claims

IEEE Transactions on Computers, Volume 53, Issue 12

Pages 1615 - 1628

https://doi.org/10.1109/TC.2004.116

Published: 01 December 2004 Publication History

Abstract

We develop an enhanced interval tree data structure that is suitable for the representation of dynamic IP router tables. Several refinements of this enhanced structure are proposed for a variety of IP router tables. For example, the data structure called BOB (binary tree on binary tree) is developed for dynamic router tables in which the rule filters are nonintersecting ranges and in which ties are broken by selecting the highest-priority rule that matches a destination address. Prefix filters are a special case of nonintersecting ranges and the commonly used longest-prefix tie breaker is a special case of the highest-priority tie breaker. When an n-rule router table is represented using BOB, the highest-priority rule that matches a destination address may be found in O(\log ^2 n) time; a new rule may be inserted and an old one deleted in O(\log n) time. For general ranges, the data structure CBOB (compact BOB is proposed). For the case when all rule filters are prefixes, the data structure PBOB (prefix BOB) permits highest-priority matching as well as rule insertion and deletion in O(W) time, where W is the length of the longest prefix, each. When all rule filters are prefixes and longest-prefix matching is to be done, the data structure LMPBOB (longest matching-prefix BOB) permits longest-prefix matching in O(W) time; rule insertion and deletion each take O(\log n) time. On practical rule tables, BOB and PBOB perform each of the three dynamic-table operations in O(\log n) time and with O(\log n) cache misses. The number of cache misses incurred by LMPBOB is also O(\log n). Experimental results also are presented.

References

[1]

C. Macian and R. Finthammer, “An Evaluation of the Key Design Criteria to Achieve High Update Rates in Packet Classifiers,” IEEE Network, pp. 24-29, Nov./Dec. 2001.

Digital Library

[2]

F. Baboescu S. Singh and G. Varghese, “Packet Classification for Core Routers: Is There an Alternative to Cams?” Proc. IEEE INFOCOM, 2003.

[3]

C. Labovitz G. Malan and F. Jahanian, “Internet Routing Instability,” IEEE/ACM Trans. Networking, 1997.

Digital Library

[4]

M. Ruiz-Sanchez E. Biersack and W. Dabbous, “Survey and Taxonomy of IP Address Lookup Algorithms,” Network, vol. 15, no. 2, pp. 8-23, Mar./Apr. 2001.

Digital Library

[5]

S. Sahni K. Kim and H. Lu, “Data Structures for One-Dimensional Packet Classification Using Most-Specific-Rule Matching,” Proc. Int'l Symp. Parallel Architectures, Algorithms, and Networks (ISPAN), May 2002.

Digital Library

[6]

A. McAuley and P. Francis, “Fast Routing Table Lookups Using Cams,” Proc. IEEE INFOCOM, pp. 1382-1391, 1993.

[7]

D. Shah and P. Gupta, “Fast Updating Algorithms for Tcams,” IEEE Micro, vol. 21, no. 1, pp. 36-47, 2001.

Digital Library

[8]

C. Matsumoto, “Cam Vendors Consider Algorithmic Alternatives,” EETimes, May 2002.

[9]

K. Sklower, “A Tree-Based Routing Table for Berkeley Unix,” technical report, Univ. of California, Berkeley, 1993.

[10]

M. Degermark A. Brodnik S. Carlsson and S. Pink, “Small Forwarding Tables for Fast Routing Lookups,” Proc. ACM SIGCOMM, pp. 3-14, 1997.

Digital Library

[11]

W. Doeringer G. Karjoth and M. Nassehi, “Routing on Longest-Matching Prefixes,” IEEE/ACM Trans. Networking, vol. 4, no. 1, pp.nbsp86-97, 1996.

Digital Library

[12]

S. Nilsson and G. Karlsson, “Fast Address Look-Up for Internet Routers,” IEEE Broadband Comm., 1998.

Digital Library

[13]

V. Srinivasan and G. Varghese, “Faster IP Lookups Using Controlled Prefix Expansion,” ACM Trans. Computer Systems, pp.nbsp1-40, Feb. 1999.

Digital Library

[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.

Digital Library

[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.

Digital Library

[16]

P. Gupta S. Lin and N. McKeown, “Routing Lookups in Hardware at Memory Access Speeds,” Proc. IEEE INFOCOM, 1998.

[17]

M. Waldvogel G. Varghese J. Turner and B. Plattner, “Scalable High Speed IP Routing Lookups,” Proc. ACM SIGCOMM, pp. 25-36, 1997.

Digital Library

[18]

B. Lampson V. Srinivasan and G. Varghese, “IP Lookup Using Multi-Way and Multicolumn Search,” Proc. IEEE INFOCOM, 1998.

[19]

A. Basu and G. Narlika, “Fast Incremental Updates for Pipelined Forwarding Engines,” Proc. IEEE INFOCOM, 2003.

[20]

S. Suri G. Varghese and P. Warkhede, “Multiway Range Trees: Scalable IP Lookup with Fast Updates,” Proc. GLOBECOM, 2001.

[21]

S. Sahni and K. Kim, “O(logn) Dynamic Packet Routing,” Proc. IEEE Symp. Computers and Comm., 2002.

Digital Library

[22]

S. Sahni and K. Kim, “Efficient Dynamic Lookup for Bursty Access Patterns,” http://www.cise.ufl.edu/~sahni, 2003.

[23]

F. Ergun S. Mittra S. Sahinalp J. Sharp and R. Sinha, “A Dynamic Lookup Scheme for Bursty Access Patterns,” Proc. IEEE INFOCOM, 2001.

[24]

H. Lu and S. Sahni, “O(logn) Dynamic Router-Tables for Prefixes and Ranges,” Proc. IEEE Symp. Computers and Comm., 2003.

Digital Library

[25]

E. Horowitz S. Sahni and D. Mehta, Fundamentals of Data Structures in C++. New York: W.H. Freeman, 1995.

Digital Library

[26]

P. Gupta and N. McKeown, “Dynamic Algorithms with Worst-Case Performance for Packet Classification,” IFIP Networking, 2000.

Digital Library

[27]

T. Cormen C. Lieserson R. Rivest and C. Stein, Introduction to Algorithms, second ed. MIT Press, 2001.

Digital Library

[28]

M.D. Berg M.V. Kreveld M. Overmars and O. Schwarzkopf, Computational Geometry: Algorithms and Applications. Springer Verlag, 1997.

Digital Library

[29]

S. Sahni, Data Structures, Algorithms, and Applications in Java. New York: McGraw-Hill, 2000.

Digital Library

[30]

Merit, “IPMA Statistics,” http://nic.merit.edu/ipma, 2000, 2001.

Cited By

Erkan ABarr JClear TIzu Cdel Alamo CMohammed HNadimpalli MSheard JKorhonen A(2018)Developing a Holistic Understanding of Systems and Algorithms through Research PapersProceedings of the 2017 ITiCSE Conference on Working Group Reports10.1145/3174781.3174786(86-104)Online publication date: 30-Jan-2018
https://dl.acm.org/doi/10.1145/3174781.3174786
Maindorfer CLauer TOttmann T(2009)New Data Structures for IP Lookup and Conflict DetectionAlgorithmics of Large and Complex Networks10.1007/978-3-642-02094-0_15(319-329)Online publication date: 29-Jun-2009
https://dl.acm.org/doi/10.1007/978-3-642-02094-0_15
Soh SHiryanto LRai S(2008)Efficient Prefix Updates for IP Router Using Lexicographic Ordering and Updatable Address SetIEEE Transactions on Computers10.1109/TC.2007.7077657:1(110-125)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.1109/TC.2007.70776
Show More Cited By

Index Terms

Enhanced Interval Trees for Dynamic IP Router-Tables

Recommendations

Prefix and Interval-Partitioned Dynamic IP Router-Tables

Two schemes prefix partitioning and interval partitioning are proposed to improve the performance of dynamic IP router-table designs. While prefix partitioning applies to all known dynamic router-table designs, interval partitioning applies to the ...
O(\log n) Dynamic Router-Tables for Prefixes and Ranges

Two versions of the Internet (IP) router-table problem are considered. In the first, the router table consists of n pairs of tuples of the form (p,a), where p is an address prefix and a is the next-hop information. In this version of the router-table ...
Data Structures For One-Dimensional Packet Classification Using Most-Specific-Rule Matching
ISPAN '02: Proceedings of the 2002 International Symposium on Parallel Architectures, Algorithms and Networks

We review the data structures that have been proposed for one-dimensional packet classification. Our review is limited to data structures for the case when ties among the rules that match an incoming packet are broken by selecting the matching rule that ...

Reviews

Reviewer: Angele M. Hamel

An approach to the problem of representing dynamic Internet protocol (IP) router tables is proposed in this paper. When packets arrive at an Internet router, certain actions may be performed on them; for example, a packet may be forwarded or dropped. The action performed is determined via a router table. However, searching this table is often a daunting task, and many sophisticated data structures have been proposed for this function. Further, in a dynamic router table, updates to the data structure must be done in real-time, which is an additional challenge. This paper proposes a variation on an interval tree to address this problem. The basic data structure developed is the binary tree on binary tree, or BOB. The BOB builds on the interval trees of Bert et al. [1]. Their interval trees are themselves a variation on red-black trees. A range is a set of consecutive addresses, and each node in an interval tree contains a subset of ranges. The BOB allows empty ranges, and also restricts the number of nodes to at most 2 n , where n is the number of ranges. The authors then develop variations of BOB for different applications. Experimental results are also included. The data structure is a straightforward modification of an existing interval tree. However, it is flexible and promising. The paper represents a solid and interesting contribution to the field. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 53, Issue 12

December 2004

144 pages

ISSN:0018-9340

Issue’s Table of Contents

Copyright © 2004.

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 December 2004

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Erkan ABarr JClear TIzu Cdel Alamo CMohammed HNadimpalli MSheard JKorhonen A(2018)Developing a Holistic Understanding of Systems and Algorithms through Research PapersProceedings of the 2017 ITiCSE Conference on Working Group Reports10.1145/3174781.3174786(86-104)Online publication date: 30-Jan-2018
https://dl.acm.org/doi/10.1145/3174781.3174786
Maindorfer CLauer TOttmann T(2009)New Data Structures for IP Lookup and Conflict DetectionAlgorithmics of Large and Complex Networks10.1007/978-3-642-02094-0_15(319-329)Online publication date: 29-Jun-2009
https://dl.acm.org/doi/10.1007/978-3-642-02094-0_15
Soh SHiryanto LRai S(2008)Efficient Prefix Updates for IP Router Using Lexicographic Ordering and Updatable Address SetIEEE Transactions on Computers10.1109/TC.2007.7077657:1(110-125)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.1109/TC.2007.70776
Chang YLin Y(2007)Dynamic Segment Trees for Ranges and PrefixesIEEE Transactions on Computers10.1109/TC.2007.103756:6(769-784)Online publication date: 1-Jun-2007
https://dl.acm.org/doi/10.1109/TC.2007.1037
Maindorfer CMohamed KOttmann TDatta A(2007)A New Output-Sensitive Algorithm to Detect and Resolve Conflicts in Internet Router TablesProceedings of the IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications10.1109/INFCOM.2007.295(2431-2435)Online publication date: 1-May-2007
https://dl.acm.org/doi/10.1109/INFCOM.2007.295
Chang YLin Y(2006)Dynamic routing tables using simple balanced search treesProceedings of the 2006 international conference on Information Networking: advances in Data Communications and Wireless Networks10.1007/11919568_39(389-398)Online publication date: 16-Jan-2006
https://dl.acm.org/doi/10.1007/11919568_39
Lu HKim KSahni S(2005)Prefix and Interval-Partitioned Dynamic IP Router-TablesIEEE Transactions on Computers10.1109/TC.2005.8354:5(545-557)Online publication date: 1-May-2005
https://dl.acm.org/doi/10.1109/TC.2005.83

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents