article

Towards a logic for wide-area Internet routing

Authors:

Hari BalakrishnanAuthors Info & Claims

ACM SIGCOMM Computer Communication Review, Volume 33, Issue 4

Pages 289 - 300

https://doi.org/10.1145/972426.944767

Published: 27 August 2003 Publication History

Abstract

Interdomain routing is a massive distributed computing task that propagates topological information for global reachability. Today's interdomain routing protocol, BGP4, is exceedingly complex because the wide variety of goals that it must meet---including fast convergence, failure resilience, scalability, policy expression, and global reachability---are accomplished by mechanisms that have complicated interactions and unintended side effects. The complexity of wide-area routing configuration and protocol dynamics requires mechanisms for expressing wide-area routing that adhere to a set of logical rules. We propose a set of rules, called the routing logic, which can be used to determine whether a routing protocol satisfies various properties. We demonstrate how this logic can aid in analyzing the behavior of BGP4 under various configurations. We also speculate on how the logic can be used to analyze existing configuration in real-world networks, synthesize network-wide router configuration from a high-level policy language, and assist protocol designers in reasoning about new routing protocols.

References

[1]

AGARWAL, S., CHUAH, C., AND KATZ, R. H. OPCA: Robust interdomain policy routing and traffic control. In IEEE Openarch (New York, NY, April 2003).]]

[2]

ANDERSEN, D. G., BALAKRISHNAN, H., KAASHOEK, M. F., AND MORRIS, R. Resilient Overlay Networks. In Proc. 18th ACM SOSP (Banff, Canada, Oct. 2001), pp. 131--145.]]

Digital Library

[3]

ANDERSEN, D. G., FEAMSTER, N., BAUER, S., ANDBALAKRISHNAN, H. Topology Inference from BGP Routing Dynamics. In Proc. Internet Measurement Workshop (Marseille, France, 2002).]]

Digital Library

[4]

BARTAL, Y., MAYER, A., NISSIM, K., AND WOOL, A. Firmato: A novel firewall management toolkit. In IEEE Symposium on Security and Privacy (Oakland, CA, May 1999), pp. 17--31.]]

[5]

BEARD, D., ET AL. Known Threats to Routing Protocols. Internet Engineering Task Force, October 2002. http://www.ietf.org/internet-drafts/draft-beard-rpsec-routing-threats-00.txt.]]

[6]

BURROWS, M., ABADI, M., AND NEEDHAM, R. A logic of authentication. ACM Transactions on Computer Systems 8, 1 (February 1990), 18--36.]]

Digital Library

[7]

CANSTINEYRA, I., CHIAPPA, N., AND STEENSTRUP, M. The Nimrod Routing Architecture. Internet Engineering Task Force, August 1996. RFC 1992.]]

Digital Library

[8]

Cisco BGP commands. http://www.cisco.com/univercd/cc/td/doc/product/software/ios113ed/cs/csprtn1/csbgp.htm.]]

[9]

Cisco BGP Best Path Selection Algorithm. http://www.cisco.com/warp/public/459/25.shtml.]]

[10]

How BGP Routers Use the Multi-Exit Discriminator for Best Path Selection. http://www.cisco.com/warp/public/459/37.html.]]

[11]

DENNING, D. E. A lattice model of secure information flow. Communications of the ACM 19, 5 (May 1976), 236--243.]]

Digital Library

[12]

DUBE, R. A comparison of scaling techniques for BGP. ACM Computer Communications Review 29, 3 (July 1999), 44--46.]]

Digital Library

[13]

FARROW, R. Routing instability on the Internet. Network Magazine (March 4, 2002). http://www.networkmagazine.com/article/NMG20020304S0007/2.]]

[14]

FEAMSTER, N., AND REXFORD, J. Network-wide BGP route prediction for traffic engineering. In Proc. ITCOM (Boston, MA, August 2002).]]

[15]

GAO, L. On inferring automonous system relationships in the Internet. IEEE/ACM Transactions on Networking 9, 6 (December 2001), 733--745.]]

Digital Library

[16]

GAO, L., AND REXFORD, J. Stable Internet routing without global coordination. IEEE/ACM Transactions on Networking (December 2001), 681--692.]]

Digital Library

[17]

GOGUEN, J., AND MESEGUER, J. Unwinding and inference control. In Proc. IEEE Symposium on Security and Privacy (1984).]]

[18]

GOODELL, G., AIELLO, W., GRIFFIN, T., IOANNIDIS, J., MCDANIEL, P., AND RUBIN, A. Working around BGP: An incremental approach to improving security and accuracy in interdomain routing. In Proc. NDSS (San Diego, CA, February 2003).]]

[19]

GOVINDAN, R., ALAETTINOGLU, C., AND KANNAN VARADHAN, D. E. Route servers for inter-domain routing. Networks and ISDN Systems 30 (1998), 1157--1174.]]

Digital Library

[20]

GRIFFIN, T., AND WILFONG, G. An analysis of BGP convergence properties. In Proc. ACM SIGCOMM (Cambridge, MA, August 1999).]]

Digital Library

[21]

GRIFFIN, T., AND WILFONG, G. A safe path vector protocol. In Proc. INFOCOMM (March 2000).]]

[22]

GRIFFIN, T., AND WILFONG, G. Analysis of the MED oscillation problem in BGP. In Proc. ICNP (Paris, France, November 2002).]]

Digital Library

[23]

GRIFFIN, T., AND WILFONG, G. On the correctness of IBGP configuration. In Proc. ACM SIGCOMM (Pittsburgh, PA, August 2002).]]

Digital Library

[24]

GRIFFIN, T. G., AND PREMORE, B. J. An experimental analysis of BGP convergence time. In Proceedings of the 9th International Conference on Network Protocols (ICNP 2001) (Riverside, CA, November 2001).]]

Digital Library

[25]

GRIFFIN, T. G., SHEPHERD, F. B., AND WILFONG, G. The stable paths problem and interdomain routing. IEEE Transactions on Networking 10, 1 (2002), 232--243.]]

Digital Library

[26]

KENT, S., LYNN, C., MIKKELSON, J., AND SEO, K. Secure border gateway protocol (S-BGP) - real world performance and deployment issues. In Proc. NDSS 2000 (2000).]]

[27]

LABOVITZ, C., AHUJA, A., BOSE, A., AND JAHANIAN, F. Delayed Internet Routing Convergence. IEEE/ACM Transactions on Networking 9, 3 (June 2001), 293--306.]]

Digital Library

[28]

LABOVITZ, C., MALAN, G. R., AND JAHANIAN, F. Origins of Internet routing instability. In Proc. Infocom (New York, NY, March 1999), pp. 218--226.]]

[29]

MAHAJAN, R., WETHERALL, D., AND ANDERSON, T. Understanding BGP misconfiguration. In Proc. ACM SIGCOMM (Aug. 2002), pp. 3--17.]]

Digital Library

[30]

MAO, Z. M., GOVINDAN, R., VARGHESE, G., AND KATZ, R. Route Flap Damping Exacerbates Internet Routing Convergence. In Prof. ACM SIGCOMM 2002 (Pittsburgh, PA, August 2002).]]

Digital Library

[31]

MAUCH, J. Odd UUNet BGP announcements for interior netblocks. http://www.merit.edu/mail.archives/nanog/2002-04/msg00653.html, April 2002.]]

[32]

MCPHERSON, D., GILL, V., WALTON, D., AND RETANA, A. Border Gateway Protocol (BGP) Persistent Route Oscillation Condition. Internet Engineering Task Force, August 2002. RFC 3345.]]

Digital Library

[33]

MYERS, A. C., AND LISKOV, B. A decentralized model for information flow control. In Proceedings of the 16th ACM Symposium on Operating Systems Principles (SOSP) (Saint-Malo, France, October 1997), pp. 129--142.]]

Digital Library

[34]

PERLMAN, R. Network Layer Protocols with Byzantine Robustness. PhD thesis, Massachusetts Institute of Technology, October 1988. MIT-LCS-TR-429. http://www.lcs.mit.edu/publications/specpub.php?id=997.]]

[35]

REKHTER, Y., AND LI, T. A Border Gateway Protocol 4 (BGP-4). Internet Engineering Task Force, 1995. RFC 1771.]]

Digital Library

[36]

SUBRAMANIAN, L., AGARWAL, S., REXFORD, J., AND KATZ, R. H. Characterizing the Internet hierarchy from multiple vantage points. In Proc. IEEE INFOCOM (New York, NY, June 2002).]]

[37]

TODD, J. AS number inconsistencies. http://www.merit.edu/mail.archives/nanog/2002-07/msg00259.html, July 2002.]]

[38]

VARADHAN, K., GOVINDAN, R., AND ESTRIN, D. Persistent route oscillations in inter-domain routing. Computer Networks 32, 1 (2000), 1--16.]]

[39]

WANG, L., ET AL. Observation and analysis of BGP behavior under stress. In Proc. ACM SIGCOMM Internet Measurement Workshop (Marseille, France, November 2002).]]

Digital Library

[40]

WOBBER, E., ABADI, M., BURROWS, M., AND LAMPSON, B. Authentication in the Taos operating system. In Proceedings of the 14th ACM Symposium on Operating System Principles (SOSP) (Asheville, NC, December 1993), pp. 256--269.]]

Digital Library

Cited By

Siddiqui MMontero DSerral-Gracià RMasip-Bruin XYannuzzi M(2015)A survey on the recent efforts of the Internet Standardization Body for securing inter-domain routingComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2015.01.01780:C(1-26)Online publication date: 7-Apr-2015
https://dl.acm.org/doi/10.1016/j.comnet.2015.01.017
Ruiz JBarnett G(2014)Who owns the international Internet networks?The Journal of International Communication10.1080/13216597.2014.97658321:1(38-57)Online publication date: 17-Nov-2014
https://doi.org/10.1080/13216597.2014.976583
Hallé SVillemaire RCherkaoui O(2012)Logical Methods for Self-Configuration of Network DevicesFormal and Practical Aspects of Autonomic Computing and Networking10.4018/978-1-60960-845-3.ch008(189-216)Online publication date: 2012
https://doi.org/10.4018/978-1-60960-845-3.ch008
Show More Cited By

Index Terms

Towards a logic for wide-area Internet routing
1. Networks
  1. Network protocols

Recommendations

Towards a logic for wide-area Internet routing
FDNA '03: Proceedings of the ACM SIGCOMM workshop on Future directions in network architecture

Interdomain routing is a massive distributed computing task that propagates topological information for global reachability. Today's interdomain routing protocol, BGP4, is exceedingly complex because the wide variety of goals that it must meet---...
Improving internet-wide routing protocols convergence with MRPC timers
CoNEXT '09: Proceedings of the 5th international conference on Emerging networking experiments and technologies

The behavior of routing protocols during convergence is critical as it impacts end-to-end performance. Network convergence is particularly important in BGP, the current interdomain routing protocol. In order to decrease the amount of exchanged routing ...
Stable internet routing without global coordination

The Border Gateway Protocol (BGP) allows an autonomous system (AS) to apply diverse local policies for selecting routes and propagating reachability information to other domains. However, BGP permits ASs to have conflicting policies that can lead to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGCOMM Computer Communication Review

ACM SIGCOMM Computer Communication Review Volume 33, Issue 4

October 2003

93 pages

ISSN:0146-4833

DOI:10.1145/972426

Issue’s Table of Contents

FDNA '03: Proceedings of the ACM SIGCOMM workshop on Future directions in network architecture
August 2003
100 pages
ISBN:1581137486
DOI:10.1145/944759
Conference Chair:
John Wroclawski
MIT LCS

Copyright © 2003 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 August 2003

Published in SIGCOMM-CCR Volume 33, Issue 4

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
887
Total Downloads

Downloads (Last 12 months)61
Downloads (Last 6 weeks)7

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Siddiqui MMontero DSerral-Gracià RMasip-Bruin XYannuzzi M(2015)A survey on the recent efforts of the Internet Standardization Body for securing inter-domain routingComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2015.01.01780:C(1-26)Online publication date: 7-Apr-2015
https://dl.acm.org/doi/10.1016/j.comnet.2015.01.017
Ruiz JBarnett G(2014)Who owns the international Internet networks?The Journal of International Communication10.1080/13216597.2014.97658321:1(38-57)Online publication date: 17-Nov-2014
https://doi.org/10.1080/13216597.2014.976583
Hallé SVillemaire RCherkaoui O(2012)Logical Methods for Self-Configuration of Network DevicesFormal and Practical Aspects of Autonomic Computing and Networking10.4018/978-1-60960-845-3.ch008(189-216)Online publication date: 2012
https://doi.org/10.4018/978-1-60960-845-3.ch008
Huadmai C(2011)Verification of routing policies by using model checking techniqueProceedings of the 6th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems10.1109/IDAACS.2011.6072863(711-716)Online publication date: Sep-2011
https://doi.org/10.1109/IDAACS.2011.6072863
Risson JMoors T(2006)Survey of research towards robust peer-to-peer networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2006.02.00150:17(3485-3521)Online publication date: 5-Dec-2006
https://dl.acm.org/doi/10.1016/j.comnet.2006.02.001
Llorens CSerhrouchni A(2005)Mesurer la sécurité d’un réseau d’un opérateur de télécommunicationA methodology to measure the security level of a data provider networkAnnales Des Télécommunications10.1007/BF0321985760:11-12(1439-1465)Online publication date: Dec-2005
https://doi.org/10.1007/BF03219857
Qadir JHasan O(2015)Applying Formal Methods to Networking: Theory, Techniques, and ApplicationsIEEE Communications Surveys & Tutorials10.1109/COMST.2014.234579217:1(256-291)Online publication date: Sep-2016
https://doi.org/10.1109/COMST.2014.2345792
García Clemente FMartínez Pérez GGómez Skarmeta A(2009)Multi-layer framework for analysing and managing routing configurationsComputers and Electrical Engineering10.1016/j.compeleceng.2009.01.00135:5(634-643)Online publication date: 1-Sep-2009
https://dl.acm.org/doi/10.1016/j.compeleceng.2009.01.001
Llorens CSerhrouchni A(2007)Security Verification of a Virtual Private Network over MPLSNetwork Control and Engineering for QoS, Security and Mobility, IV10.1007/978-0-387-49690-0_27(339-353)Online publication date: 2007
https://doi.org/10.1007/978-0-387-49690-0_27
Jaggard ARamachandran V(2006)Robust Path-Vector Routing Despite Inconsistent Route PreferencesProceedings of the Proceedings of the 2006 IEEE International Conference on Network Protocols10.1109/ICNP.2006.320220(270-279)Online publication date: 12-Nov-2006
https://dl.acm.org/doi/10.1109/ICNP.2006.320220
Show More Cited By

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents