skip to main content
10.1145/1402958.1402964acmconferencesArticle/Chapter ViewAbstractPublication PagescommConference Proceedingsconference-collections
research-article
Free access

Shedding light on the glue logic of the internet routing architecture

Published: 17 August 2008 Publication History

Abstract

Recent studies reveal that the routing structures of operational networks are much more complex than a simple BGP/IGP hierarchy, highlighted by the presence of many distinct instances of routing protocols. However, the glue (how routing protocol instances interact and exchange routes among themselves) is still little understood or studied. For example, although Route Redistribution (RR), the implementation of the glue in router software, has been used in the Internet for more than a decade, it was only recently shown that RR is extremely vulnerable to anomalies similar to the permanent route oscillations in BGP. This paper takes an important step toward understanding how RR is used and how fundamental the role RR plays in practice. We developed a complete model and associated tools for characterizing interconnections between routing instances based on analysis of router configuration data. We analyzed and characterized the RR usage in more than 1600 operational networks. The findings are: (i) RR is indeed widely used; (ii) operators use RR to achieve important design objectives not realizable with existing routing protocols alone; (iii) RR configurations can be very diverse and complex. These empirical discoveries not only confirm that the RR glue constitutes a critical component of the current Internet routing architecture, but also emphasize the urgent need for more research to improve its safety and flexibility to support important design objectives.

References

[1]
100x100 Clean Slate Project. www.100x100network.org.
[2]
4D Project. www.cs.cmu.edu/~4D.
[3]
NSF FIND Program. www.nets-find.net.
[4]
XORP. www.xorp.org.
[5]
Cisco. Using OSPF in an MPLS VPN Environment, 2002.
[6]
Cisco. BGP Best Path Selection Algorithm, 2006.
[7]
Cisco. EIGRP MPLS VPN PE-CE Site of Origin, 2006.
[8]
Cisco. OSPF Design Guide, 2006.
[9]
Cisco. OSPF Redistribution Among Different OSPF Processes, 2006.
[10]
Cisco. Redistributing Routing Protocols, 2006.
[11]
N. Feamster and H. Balakrishnan. Detecting BGP Configuration Faults with Static Analysis. In Proc. NSDI, 2005.
[12]
A. Feldmann and J. Rexford. IP Network Configuration for Intradomain Traffic Engineering. In IEEE Network Magazine, 2001.
[13]
T. G. Griffin and J. L. Sobrinho. Metarouting. In Proc. ACM SIGCOMM, 2005.
[14]
F. Le and G. Xie. On Guidelines for Safe Route Redistributions. In Proc. ACM INM Workshop, 2007.
[15]
F. Le, G. Xie, and H. Zhang. Understanding Route Redistribution. In Proc. IEEE ICNP, 2007.
[16]
F. Le, G. Xie, and H. Zhang. Instability Free routing: Beyond One Protocol Instance. Technical Report CMU-CS-08-123, May 2008.
[17]
D. Maltz, G. Xie, J. Zhan, H. Zhang, G. Hjalmtysson, and A. Greenberg. Routing design in operational networks: A look from the inside. In Proc. ACM SIGCOMM, 2004.
[18]
S. Misel. Wow, AS7007! www.merit.edu/mail.archives/nanog/1997-04/msg00340.html.
[19]
V. Paxson. End-to-end routing behavior in the Internet. In Proc. of ACM SIGCOMM, 1996.
[20]
I. Pepelnjak and J. Guichard. MPLS and VPN Architectures. Cisco Press, 2000.
[21]
Ratul Mahajan et al. Mutually Controlled Routing with Independent ISPs. In Proc. NSDI, 2007.
[22]
E. Rosen, P. Psenak, and P. Pillay-Esnault. OSPF as the Provider/Customer Edge Protocol for BGP/MPLS IP Virtual Private Networks (VPNs). RFC 4577, 2006.
[23]
J. W. Stewart. BGPv4: Inter-Domain Routing in the Internet. By Addison-Wesley, 1999.
[24]
T. V. Lakshman et al. The SoftRouter architecture. In Proc. ACM HotNets Workshop, 2004.

Cited By

View all
  • (2019)Survey of Consistent Software-Defined Network UpdatesIEEE Communications Surveys & Tutorials10.1109/COMST.2018.287674921:2(1435-1461)Online publication date: Oct-2020
  • (2019)Scalable Rule Enforcement in SDN through Separate User Identifiers2019 IEEE 9th Annual Computing and Communication Workshop and Conference (CCWC)10.1109/CCWC.2019.8666494(0962-0968)Online publication date: Jan-2019
  • (2018)Tactical Router Interoperability: Concepts and ExperimentsMILCOM 2018 - 2018 IEEE Military Communications Conference (MILCOM)10.1109/MILCOM.2018.8599687(647-654)Online publication date: Oct-2018
  • Show More Cited By

Index Terms

  1. Shedding light on the glue logic of the internet routing architecture

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    SIGCOMM '08: Proceedings of the ACM SIGCOMM 2008 conference on Data communication
    August 2008
    452 pages
    ISBN:9781605581750
    DOI:10.1145/1402958
    • cover image ACM SIGCOMM Computer Communication Review
      ACM SIGCOMM Computer Communication Review  Volume 38, Issue 4
      October 2008
      436 pages
      ISSN:0146-4833
      DOI:10.1145/1402946
      Issue’s Table of Contents
    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]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 17 August 2008

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. route redistribution
    2. route selection
    3. routing glue logic

    Qualifiers

    • Research-article

    Conference

    SIGCOMM '08
    Sponsor:
    SIGCOMM '08: ACM SIGCOMM 2008 Conference
    August 17 - 22, 2008
    WA, Seattle, USA

    Acceptance Rates

    Overall Acceptance Rate 462 of 3,389 submissions, 14%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)85
    • Downloads (Last 6 weeks)8
    Reflects downloads up to 13 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2019)Survey of Consistent Software-Defined Network UpdatesIEEE Communications Surveys & Tutorials10.1109/COMST.2018.287674921:2(1435-1461)Online publication date: Oct-2020
    • (2019)Scalable Rule Enforcement in SDN through Separate User Identifiers2019 IEEE 9th Annual Computing and Communication Workshop and Conference (CCWC)10.1109/CCWC.2019.8666494(0962-0968)Online publication date: Jan-2019
    • (2018)Tactical Router Interoperability: Concepts and ExperimentsMILCOM 2018 - 2018 IEEE Military Communications Conference (MILCOM)10.1109/MILCOM.2018.8599687(647-654)Online publication date: Oct-2018
    • (2017)Automatically Repairing Network Control Planes Using an Abstract RepresentationProceedings of the 26th Symposium on Operating Systems Principles10.1145/3132747.3132753(359-373)Online publication date: 14-Oct-2017
    • (2017)MINOSProceedings of the ACM Turing 50th Celebration Conference - China10.1145/3063955.3063996(1-10)Online publication date: 12-May-2017
    • (2017)SFP: Toward a scalable, efficient, stable protocol for federation of software defined networks2017 IEEE SmartWorld, Ubiquitous Intelligence & Computing, Advanced & Trusted Computed, Scalable Computing & Communications, Cloud & Big Data Computing, Internet of People and Smart City Innovation (SmartWorld/SCALCOM/UIC/ATC/CBDCom/IOP/SCI)10.1109/UIC-ATC.2017.8397408(1-6)Online publication date: Aug-2017
    • (2017)Correctness of Routing Vector Protocols as a Property of Network CyclesIEEE/ACM Transactions on Networking10.1109/TNET.2016.256760025:1(150-163)Online publication date: 1-Feb-2017
    • (2017)Shedding light on the complexity of enterprise routing design: A case study2017 3rd IEEE International Conference on Computer and Communications (ICCC)10.1109/CompComm.2017.8322543(214-218)Online publication date: Dec-2017
    • (2016)Efficient network reachability analysis using a succinct control plane representationProceedings of the 12th USENIX conference on Operating Systems Design and Implementation10.5555/3026877.3026895(217-232)Online publication date: 2-Nov-2016
    • (2016)Fast Control Plane Analysis Using an Abstract RepresentationProceedings of the 2016 ACM SIGCOMM Conference10.1145/2934872.2934876(300-313)Online publication date: 22-Aug-2016
    • 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

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media