of 9
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Shedding Light on the Glue Logic of the Internet Routing Architecture

Category:

Computers & Electronics

Publish on:

Views: 2 | Pages: 9

Extension: PDF | Download: 0

Share
Description
Shedding Light on the Glue Logic of the Internet Architecture Franck Le, Geoffrey G. Xie,DanPei,JiaWang and Hui Zhang arnegie Mellon University, Naval Postgraduate School, AT&T Labs - Research ASTRAT Recent
Transcript
Shedding Light on the Glue Logic of the Internet Architecture Franck Le, Geoffrey G. Xie,DanPei,JiaWang and Hui Zhang arnegie Mellon University, Naval Postgraduate School, AT&T Labs - Research ASTRAT Recent studies reveal that the routing structures of operational networks are much more complex than a simple GP/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 GP. 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. ategories and Subject Descriptors:.2.3 [omputer- ommunication Networks]: Network Operations network management General Terms: Design, Management, Measurement Keywords: glue logic, route redistribution, route selection 1. INTRODUTION Recent studies reveal that the IP routing design of operational networks, particularly that of large enterprise networks, is far more complex than previously understood by the networking community [17], [15]. Not only many distinct instances of IGP and GP protocols are frequently configured in the same network at the same time, but these routing protocol instances or routing domains also 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. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. SIGOMM 08, August 17 22, 2008, Seattle, Washington, USA. opyright 2008 AM /08/08...$5.00. A domain 1 (OSPF) domain 3 (RIP) G F E H D domain 2 ( 20) Figure 1: An example enterprise network. are often linked together not by GP. Instead, routes are exchanged between different routing domains via route redistribution options configured on individual border routers connecting these domains. Figure 1 illustrates such a design. The network consists of three routing domains, each of which runs a different routing protocol: OSPF, or RIP. This topology may result from a merger of companies or may derive from administrative reasons. The routing domains are physically connected by border routers,, and E. For example, instantiates both an OSPF routing process and an routing process to exchange routing information with other routers of the respective domains. y default, processes of different routing protocols do not exchange routing information and consequently the internal routers in the OSPF domain (e.g., router A) have no visibility of the destinations inside the domain (e.g., router D). Route redistribution provides a simple solution to this reachability problem by allowing routes to be imported from one routing process (e.g., process on router ) into another process on the same router (e.g., OSPF process on router ). For this simple network, full reachability can be achieved by just setting up mutual route redistribution on both and E. In such a setting, route selection, the procedure that a router uses to rank routes from different routing protocols and select one of them to put into the forwarding table, plays an equally important role in the integration of routing protocols. For example because of the route redistribution configurations on routers and E, router receives two routes to router D: one from OSPF and the other from RIP. Route selection provides the operator of this network a mean to customize the preference order between the paths --D and -F -E-D. learly for the example network above, the per router route selection and redistribution procedures provide the required glue logic between the three routing domains and as such constitute a building block of the IP routing design that is separate from the routing protocols used. In the rest of the paper, we will refer to the combination of route 39 Report Documentation Page Form Approved OM No Public reporting burden for the collection of information is estimated to average 1 hour per response, including the time for reviewing instructions, searching existing data sources, gathering and maintaining the data needed, and completing and reviewing the collection of information. Send comments regarding this burden estimate or any other aspect of this collection of information, including suggestions for reducing this burden, to Washington Headquarters Services, Directorate for Information Operations and Reports, 1215 Jefferson Davis Highway, Suite 1204, Arlington VA Respondents should be aware that notwithstanding any other provision of law, no person shall be subject to a penalty for failing to comply with a collection of information if it does not display a currently valid OM control number. 1. REPORT DATE AUG REPORT TYPE N/A 3. DATES OVERED - 4. TITLE AND SUTITLE Shedding Light on the Glue Logic of the Internet Architecture 5a. ONTRAT NUMER 5b. GRANT NUMER 5c. PROGRAM ELEMENT NUMER 6. AUTHOR(S) 5d. PROJET NUMER 5e. TASK NUMER 5f. WORK UNIT NUMER 7. PERFORMING ORGANIZATION NAME(S) AND ADDRESS(ES) Naval Postgraduate School Operations Research Department Monterey, A PERFORMING ORGANIZATION REPORT NUMER 9. SPONSORING/MONITORING AGENY NAME(S) AND ADDRESS(ES) 10. SPONSOR/MONITOR S ARONYM(S) 12. DISTRIUTION/AVAILAILITY STATEMENT Approved for public release, distribution unlimited 11. SPONSOR/MONITOR S REPORT NUMER(S) 13. SUPPLEMENTARY NOTES SIGOMM08, August 1722, 2008, Seattle, WA, The original document contains color images. 14. ASTRAT Recent studies reveal that the routing structures of operational networks are much more complex than a simple GP/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 GP. 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. 15. SUJET TERMS 16. SEURITY LASSIFIATION OF: 17. LIMITATION OF ASTRAT SAR a. REPORT unclassified b. ASTRAT unclassified c. THIS PAGE unclassified 18. NUMER OF PAGES 12 19a. NAME OF RESPONSILE PERSON selection and route redistribution procedures simply as the glue logic. In some scenarios, GP can be used as an alternative solution to the glue logic. For example, in the network shown in Figure 1, one can use GP as the route selection and redistribution mechanisms between the three routing domains. However, the functionalities of the glue logic can not be solely supported by GP. For example, the route selection and redistribution mechanisms are still needed when exchanging routing information between OSPF and GP. Thus, the glue logic was introduced as a software enhancement by router vendors (rather than a standard protocol). Furthermore, the glue logic is independently configured per router and its safety properties have not been under much scrutiny by the research community. Vendors try to mitigate this problem by publishing templates for configuring the glue logic and pointing out common pitfalls of route redistribution configurations through simple examples [10], [9]. Misconfigurations of route redistribution (e.g., injecting routes from GP into OSPF and then back into GP) can easily result in persistent forwarding loops between multiple domains. Such misconfigurations have long been suspected by the operational community as one of the more likely root causes of the long-lived loops observed in [19] and IP prefix hijacks [18]. In fact, one recent study [15] has established that the glue logic introduces a wider range of safety challenges than GP. Given the documented safety concerns, one would expect operators to increasingly choose GP 1 or a similar protocol over the glue logic for joining routing domains. However, according to our interactions with the operators as well as messages posted on relevant bulletin boards, the use of the glue logic seems still very prevalent. A simple explanation for this phenomenon might be that the glue logic is relatively easier to configure and to deploy than GP since this latter requires the configuration of igp/egp sessions and the running of GP processes at every router. Instead, the glue logic only necessitates configurations at the border routers. There is, however, another much more interesting hypothesis to consider: the glue logic may offer important features to the operators which are not possible with current routing protocols alone. Put it more directly: the glue logic could be a fundamental building block of the Internet routing architecture. We believe it is essential to evaluate this hypothesis and get it right. If the glue logic is fundamental, then the research community should confirm it as soon as possible and begin to address its safety problems with the same intensity as we did for GP. A recent paper has presented simple scenarios to show that the glue logic indeed can be used to meet critical operational requirements such as domain backup [14]. In this paper, we take a first step toward a definite answer regarding whether the glue logic is a fundamental building block of IP routing design, based on empirical data. Specifically, we study the use of route redistribution in about 1600 operational networks to test the following hypotheses: 1. Route redistribution is used widely in operational networks. 2. Route redistribution is not used simply to interconnect routing protocols, but also as a powerful tool for achieving important design objectives which cannot be achieved with routing protocols (including GP) alone. 3. ecause of the high vulnerability of route redistribution to routing instabilities and the lack of standard solution to ensure its safety, the route redistribution configurations in the wild are adhoc and complex. 1 GP is known to have its own safety issues. However, GP is better understood and has less concerns than the glue logic. We extended the method proposed in [17] so that we were able to precisely identify routing instances and their interconnections from a network s router configuration files. In particular, we made the following major contributions in this paper: (1) We developed a complete model and associated tools for characterizing interconnections between routing instances based on analysis of router configuration data. (2) We analyzed and characterized router configurations of over 1600 operational networks ranging from large tier-1 ISP networks, enterprise networks, to campus networks. (3) We demonstrated that the route redistribution is indeed a critical building block of the current Internet routing architecture by confirming the above three hypotheses through empirical analysis. (4) We found that route redistribution is often used by operators to achieve efficient routing and partition healing. (5) We argued that the limitation of existing vendors support leads to increased complexity in network configurations and potential instability concerns. Thus, there is an urgent need for a standard solution to ensure safety of route redistribution. (6) We discussed the potential role of the glue logic as the Internet architecture evolves to its next generation. The rest of the paper is organized as follows. Section 2 provides an overview of the route selection and redistribution processes in the current Internet routing architecture. We present our characterization methodologies of route selection and redistribution in Section 3. Section 4 describes the operational networks configurations we analyzed in this paper. Section 5 presents our findings regarding the prevalence of route redistribution. Section 6 describes the patterns our method unearthed and the rationales behind them. Section 7 looks at the complexity of the route redistribution configurations. Section 8 interprets the results and discusses the limitations of the study. Section 9 summarizes related works. Finally, Section 10 concludes our study. 2. AKGROUND ON ROUTE SELETION AND REDISTRIUTION This section presents important properties of route selection and route redistribution. First, we introduce some terminologies. A router may be running multiple routing protocols. For example, router from Figure 1 is running both OSPF and. In fact, some vendors even allow routers to run multiple processes of the same routing protocol (e.g., OSPF routing process 100, OSPF routing process 200, etc.) We refer to each of these processes as a routing process. The routing processes at a router are by default independent: they do not exchange routing information among themselves. For example, the OSPF routing process at router in Figure 1 has its own set of routes, and so does the routing process. Two routing processes, belonging to different routers but running the same routing protocol and exchanging routing information through it, are said to pertain to the same routing instance. Inthe rest of the paper, we assign a unique identifier to each routing instance (e.g., 1, 2,...). Each of the domains 1, 2 and 3 in Figure 1 is a routing instance. We use router . routing instance to denote the routing process belonging to routing instance at router . For example, in Figure 1,.1 represents the OSPF process at router. As such,.1, A.1 and.1 belong to the same routing instance (1: OSPF), and.2, D.2 and E.2 belong to a different routing instance (2: 20). As explained in the previous section, route selection allows operators to rank the routes received from multiple routing processes at a router, and to select the most preferred one: in fact, each routing protocol is assigned a default administrative distance (AD) value. This parameter is an integer number. A route received from a rout- 40 ing process inherits the AD value of that routing process and the route with the lowest AD value is preferred. The AD value can be overridden per routing process and per prefix. The route with the lowest AD value is installed in the router s forwarding table and used to forward the traffic. It is often called the active route. Then, route redistribution allows operators to redistribute a route from a source routing process to a target routing process on the same router. It is important to note that a route is advertised in the target routing process only if the route is active (i.e., the route is the one used to forward the traffic) [15]. 3. METHODOLOGY We have followed the general white-box reverse engineering approach first used in [17] to analyze the configuration data and evaluate the three hypotheses. We collect RR usage statistics by simply tallying the RR commands in the configuration files. The identification of design patterns and the examination of configuration complexity are much more involved, requiring the construction of a graph model of the routing instances for each network, and the extraction of the route redistributions between the routing instances as well as the associated policies. ecause the recognition of design patterns is achieved through a manual inspection of the derived graphs, we focus on a few large networks for this specific task. Finally, we verify the identified design patterns and our understanding of the rationales behind the patterns with the operators whenever possible. [17] also presented three graph models of routing processes and routing instances and a methodology for distillingthem from a network s configuration files. However, those models do not have sufficient details for our purpose. They do not model the critical AD parameter. They do not model how routing instances are interconnected (e.g., through one or multiple interconnection points). They do not model the directions of the route propagations. We address these limitations by extending the routing instance graph model to include the details of all the border routers, their routing processes, and the route redistribution options defined between the routing processes. The algorithm used by [17] for determining the routing instances boundaries also has some limitations as discussed in details in the sub-section below. In the following, we first describe the way we identify and extract the routing instances of a network from its routers configurations. Then, Section 3.2 focuses on how we determine and represent the interconnections between the routing instances. Finally, Section 3.3 discusses the impact of incomplete network configurations. 3.1 Determination of routing instances Our goal is to identify the routing instances present in a network from its routers configuration files. We formerly defined a routing instance as a collection of routing processes, each residing on a distinct router, that run the same routing protocol and exchange routing information through the protocol. While verifying whether two routing processes run the same routing protocol is easy, determining whether they exchange routing information can be intricate. Subtle parameters can have profound impacts on whether two routing processes are able to exchange routing information. The methods used by [17] for determining the boundaries of routing instances do not consider them. The following describes such parameters and scenarios illustrating the difficulties: For each routing process (e.g., RIP, OSPF process 20, 30, etc.), a router interface can be either active or passive. This status modifies the behavior of the router. A RIP routing process on an interface that is passive still receives and processes the advertisements from RIP processes on other routers but does not send any announcement out. The difficulty to determine whether two routers exchange routing information is exacerbated by the fact that these commands can actually have different consequences for each routing protocol. In OSPF, the passive status prevents the formation of an adjacency and therefore sto
Search Related
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks