article

Free access

Routing on longest-matching prefixes

Editor: Simon S. Lam Authors:

Willibald Doeringer,

Günter Karjoth,

Mehdi NassehiAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 4, Issue 1

Pages 86 - 97

https://doi.org/10.1109/90.503764

Published: 01 February 1996 Publication History

PDF eReader

References

[1]

A. Anderson, "On the balance property of Patricia tries: external path length viewpoint," Theoretical Comput. Science, vol. 106, no. 2, pp. 391-393, Dec. 1992.]]

Crossref

Google Scholar

[2]

J. Aoe, K. Morimoto, and T. Sato, "An efficient implementation of trie structures," Software Practice & Experience, vol. 22, no. 9, pp. 695-721, Sept. 1992.]]

Crossref

Google Scholar

[3]

ATM Forum, PNNI Draft Specification, 1995. Version 94-0471R10.]]

Google Scholar

[4]

S. Bradner and A. Mankin, The recommendation for the IP next generation protocol, RFC 1752, NIC, 1995.]]

Crossref

Google Scholar

[5]

D. Comer, lnternetworking with TCP/IP. Principles, Protocols and Architecture. Englewood Cliffs, NJ: Prentice-Hall, 1989.]]

Crossref

Google Scholar

[6]

W. Doeringer et al., "Multiprotocol transport networking: a software declaration of application independence," IBM Systems J., vol. 34, no. 3, Sept. 1995.]]

Crossref

Google Scholar

[7]

W. Doeringer, D. Dykeman, M, Peters, H. Sandick, and K. Vu, "Efficient, real-time address resolution in networks of arbitrary topology," in Proc. 1st LAN Conf., 1993, pp. 183-191.]]

Google Scholar

[8]

W. Doeringer and M. Nassehi, "A new standard for address resolution," submitted to IEEE Commun. Mag. Special Issue Enterprise Networking, 1995.]]

Google Scholar

[9]

5. A. Dundas lII, "Implementing dynamic minimal-prefix tries," Software Practice & Experience, vol. 21, no. 10, pp. 1027-1040, Oct. 1991.]]

Crossref

Google Scholar

[10]

G. H. Gonnet and R. Baeza-Yates, Handbook of Algorithms and Data Structures. Reading, MA: Addison-Wesley, 1991.]]

Crossref

Google Scholar

[11]

ISO/IEC, Intermediate System to Intermediate System Inter-Domain Routeing Exchange Protocol, 1992, DIS 10747.]]

Google Scholar

[12]

ISO/OSI, Network Service Definition, Addendum 2: Network Layer Addressing, 1988, DIS 8348, Add.2.]]

Google Scholar

[13]

OSI Routeing Framework, 1989, DIS 9575.]]

Google Scholar

[14]

Intermediate System to Intermediate System Intra-domain Routeing Protocol for Use in Conjunction with the Protocol for Providing Connectionless-mode Network Service (1SO 8473), 1990, DIS i 0589.]]

Google Scholar

[15]

P. Kirschenhofer, H. Prodinger, and W. Szpankowski, "Do we really need to balance Patricia tries?" in Proc. ICALP, Lecture Notes Comput. Science 317, 1988, pp. 302-316.]]

Crossref

Google Scholar

[16]

~. "On the balance property of Patricia tries: external path length viewpoint," Theoretical Computer Science, vol. 68, no. 1, pp. i-18, Oct. 1989.]]

Crossref

Google Scholar

[17]

D. E. Knuth, "Optimum binary search trees," Acta inJbrmatica, vol. 1, pp. 14-25, 1971.]]

Google Scholar

[18]

The Art of Computer Programming, vol. 3. Sorting and Searching. Reading, MA: Addison-Wesley, 1991.]]

Google Scholar

[19]

K. Lougheed and Y. Rekhter, Border gateway protocol (BGP), RFC 163, NIC, 1990.]]

Crossref

Google Scholar

[20]

T.X. Merrett and B. Fayerman, "Dynamic Patricia," in Proc. Int. Conf. Foundations Data Org., Kyoto, Japan, 1985, pp. 13-20.]]

Google Scholar

[21]

D. R. Morrison, "Patricia--practical algorithm to retrieve information coded in alphanumeric," J. ACM, vol. 15, no. 4, pp. 515-534, Oct. 1968.]]

Crossref

Google Scholar

[22]

P. Robinson, Suggestion for a new class of IP addresses, REX? 1375, NIC, 1992.]]

Crossref

Google Scholar

[23]

T.-B. Pei and C. Zukowski, "Putting routing tables in silicon," IEEE Network Mag., pp. 42-50, Jan. 1992.]]

Google Scholar

[24]

R. Perlman, lnterconnections: Bridges and Routers. Reading, MA: Addison-Wesley, 1992.]]

Crossref

Google Scholar

[25]

W. Pugh. "Skip lists: a probabilistic alternative to balanced tries," Commun. ACM, vol. 33, no. 6, pp. 668---676, June 1990.]]

Crossref

Google Scholar

[26]

Y. Rekhter, "Forwarding database overhead for inter-domain routing," ACM Comput. Commun. Rev., vol. 23, no. 1, pp. 66-81, Jan. 1993.]]

Crossref

Google Scholar

[27]

D. D. Sleator and R. E. Tarjan, "Self-adjusting binary tries," J. ACM, vol. 32, no. 2, pp. 652--686, July 1985.]]

Crossref

Google Scholar

[28]

W. Szpankowski, "How much on the average is the Patricia trie better?" in Proc. Allerton Conf., 1986, pp. 314-323.]]

Google Scholar

Cited By

View all

Murugesan SSk N(2017)A Novel Range Matching Architecture for Packet Classification Without Rule ExpansionACM Transactions on Design Automation of Electronic Systems10.1145/310595823:1(1-15)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1145/3105958
Hager SBendyk DScheuermann B(2017)Matching circuits can be smallJournal of Parallel and Distributed Computing10.1016/j.jpdc.2017.05.004109:C(42-49)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1016/j.jpdc.2017.05.004
Song TYuan HCrowley PZhang BSolis ICarzaniga ARamakrishnan K(2015)Scalable Name-Based Packet ForwardingProceedings of the 2nd ACM Conference on Information-Centric Networking10.1145/2810156.2810166(19-28)Online publication date: 30-Sep-2015
https://dl.acm.org/doi/10.1145/2810156.2810166
Show More Cited By

Index Terms

Routing on longest-matching prefixes
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems

Recommendations

Routing Protocols: RIP and BGP Rbsw05e
Dynamics of hot-potato routing in IP networks

Despite the architectural separation between intradomain and interdomain routing in the Internet, intradomain protocols do influence the path-selection process in the Border Gateway Protocol (BGP). When choosing between multiple equally-good BGP routes, ...
Dynamics of hot-potato routing in IP networks
SIGMETRICS '04/Performance '04: Proceedings of the joint international conference on Measurement and modeling of computer systems

Despite the architectural separation between intradomain and interdomain routing in the Internet, intradomain protocols do influence the path-selection process in the Border Gateway Protocol (BGP). When choosing between multiple equally-good BGP routes, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 4, Issue 1

Feb. 1996

136 pages

ISSN:1063-6692

Editor:
Simon S. Lam
Univ. Texas, Austin

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 February 1996

Published in TON Volume 4, Issue 1

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

34
Total Citations
View Citations
1,027
Total Downloads

Downloads (Last 12 months)46
Downloads (Last 6 weeks)4

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Murugesan SSk N(2017)A Novel Range Matching Architecture for Packet Classification Without Rule ExpansionACM Transactions on Design Automation of Electronic Systems10.1145/310595823:1(1-15)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1145/3105958
Hager SBendyk DScheuermann B(2017)Matching circuits can be smallJournal of Parallel and Distributed Computing10.1016/j.jpdc.2017.05.004109:C(42-49)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1016/j.jpdc.2017.05.004
Song TYuan HCrowley PZhang BSolis ICarzaniga ARamakrishnan K(2015)Scalable Name-Based Packet ForwardingProceedings of the 2nd ACM Conference on Information-Centric Networking10.1145/2810156.2810166(19-28)Online publication date: 30-Sep-2015
https://dl.acm.org/doi/10.1145/2810156.2810166
Pong FTzeng N(2012)Concise lookup tables for IPv4 and IPv6 longest prefix matching in scalable routersIEEE/ACM Transactions on Networking10.1109/TNET.2011.216715820:3(729-741)Online publication date: 1-Jun-2012
https://dl.acm.org/doi/10.1109/TNET.2011.2167158
Hwang HAta SMurata MLee DFdida SPartridge CChoi YFriedman TMoon SRaychaudhuri D(2010)Frequency-aware reconstruction of forwarding tables in name-based routingProceedings of the 5th International Conference on Future Internet Technologies10.1145/1853079.1853093(45-50)Online publication date: 16-Jun-2010
https://dl.acm.org/doi/10.1145/1853079.1853093
Pong FTzeng N(2010)SUSEIEEE/ACM Transactions on Networking10.1109/TNET.2009.202208518:1(81-94)Online publication date: 1-Feb-2010
https://dl.acm.org/doi/10.1109/TNET.2009.2022085
Hsiao YChen MHsiao YSu HChu Y(2009)A fast update scheme for TCAM-based IPv6 routing lookup architectureProceedings of the 15th Asia-Pacific conference on Communications10.5555/1803074.1803264(779-783)Online publication date: 8-Oct-2009
https://dl.acm.org/doi/10.5555/1803074.1803264
Lin DHamdi M(2009)Compress the route table stored in TCAM by using memory filterProceedings of the 15th international conference on High Performance Switching and Routing10.5555/1715730.1715742(76-81)Online publication date: 22-Jun-2009
https://dl.acm.org/doi/10.5555/1715730.1715742
Raj ASuganthi M(2008)Hardware implementation of an efficient internet protocol routing filter designInternational Journal of Computers and Applications10.1080/1206212X.2008.1144189030:2(124-128)Online publication date: 1-Mar-2008
https://dl.acm.org/doi/10.1080/1206212X.2008.11441890
Kim KSahni S(2007)Efficient Construction of Pipelined Multibit-Trie Router-TablesIEEE Transactions on Computers10.5555/1191544.119170756:1(32-43)Online publication date: 1-Jan-2007
https://dl.acm.org/doi/10.5555/1191544.1191707
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

Routing Protocols: RIP and BGP Rbsw05e

Dynamics of hot-potato routing in IP networks

Dynamics of hot-potato routing in IP networks

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations