Design and Implementation of an Inherently Anomaly-free Internal BGP Routing
The iBGP Route Server Architecture
1st Edition
Published on 1. November 2011
Book
Paperback/Softback
XXVI, 196 pages
978-3-89863-248-5 (ISBN)
Description
Abstract
In a globally interconnected world, the Internet as one of the central communication platforms becomes more and more important. Companies centralize services and network their remote offices with leased lines, replace POTS by VoIP connections, and supersede business trips by video conferences. Private individuals pass more and more spare time in social networks, share photos and videos, and replace classical broadcast media by corresponding web-based services. All of these services and applications cause a significant growth of the global load to be forwarded. Independent of whether stationary or portable end devices are used, this traffic has to pass through the Internet Backbone.
Technically speaking, the Internet Backbone is a network of interconnected Autonomous Systems. To implement interconnectivity and reachability between the Autonomous Systems, network traffic has to be routed. Today, the exchange of global routing information is realized by means of the Border Gateway Protocol (BGP). External BGP is used to exchange data on available paths between Autonomous Systems, while internal BGP is used to spread the known paths within a system. In the Internet Backbone, internal BGP is usually implemented by means of Route Reflection and AS Confederations. However, while usable and performant alternatives are not available, both concepts require to apply restrictive and unwanted design network rules to avoid routing anomalies: Without further restrictions, serious problems like forwarding loops, oscillating best path selections, and non-deterministic behavior can appear. Due to the significant load growth in the Internet Backbone, restrictive network design rules do not provide a long term solution. They complicate the expansion of Autonomous Systems, make Network Operators inflexible, and conflict with optimized network designs. But even if this problem is well-known by operators, router manufacturers, and the research community, productively usable solutions are not available yet. This unsatisfactory situation outlines the starting point for the research activities discussed in this thesis.
The research carried out in the context of this thesis pursues two major objectives. Firstly, the anomalies which may appear in the internal BGP routing, their root causes, and the un- derlying flaws in the protocols and the architectures shall be studied and understood. By applying a graph theoretical model of the routing information exchange, the situations that cause anomalies are formally specified and classified: Necessary conditions for the occurrence of internal BGP routing anomalies are identified. By showing how to avoid conditions with- out affecting the semantics of the internal BGP, a theoretical framework for an inherently anomaly-free internal BGP routing is provided.
Knowing how anomalies in the internal BGP routing can be inherently avoided, adequate implementations are necessary to prevent their appearance in productively used systems. As the workarounds used today are problematic for large Autonomous Systems found in the Internet Backbone, architecture concepts for this class of systems seem to be most urgent. Hence, developing an implementation of the theoretical framework that matches the require- ments of ISPs and large carriers defines the second primary objective. Special requirements of this group of Network Operators affect the efficiency, reliability, scalability, and the interoper- ability of the routing information exchange. These requirements are met by the iBGP Route Server architecture. A close cooperation with the network engineers of Deutsche Telekom AG, a large ISP in Germany, guarantees a productively usable solution. This course of ac- tion resulted in scientifically well-founded concepts and solutions, which are tailored to the real life conditions in production systems.
In a globally interconnected world, the Internet as one of the central communication platforms becomes more and more important. Companies centralize services and network their remote offices with leased lines, replace POTS by VoIP connections, and supersede business trips by video conferences. Private individuals pass more and more spare time in social networks, share photos and videos, and replace classical broadcast media by corresponding web-based services. All of these services and applications cause a significant growth of the global load to be forwarded. Independent of whether stationary or portable end devices are used, this traffic has to pass through the Internet Backbone.
Technically speaking, the Internet Backbone is a network of interconnected Autonomous Systems. To implement interconnectivity and reachability between the Autonomous Systems, network traffic has to be routed. Today, the exchange of global routing information is realized by means of the Border Gateway Protocol (BGP). External BGP is used to exchange data on available paths between Autonomous Systems, while internal BGP is used to spread the known paths within a system. In the Internet Backbone, internal BGP is usually implemented by means of Route Reflection and AS Confederations. However, while usable and performant alternatives are not available, both concepts require to apply restrictive and unwanted design network rules to avoid routing anomalies: Without further restrictions, serious problems like forwarding loops, oscillating best path selections, and non-deterministic behavior can appear. Due to the significant load growth in the Internet Backbone, restrictive network design rules do not provide a long term solution. They complicate the expansion of Autonomous Systems, make Network Operators inflexible, and conflict with optimized network designs. But even if this problem is well-known by operators, router manufacturers, and the research community, productively usable solutions are not available yet. This unsatisfactory situation outlines the starting point for the research activities discussed in this thesis.
The research carried out in the context of this thesis pursues two major objectives. Firstly, the anomalies which may appear in the internal BGP routing, their root causes, and the un- derlying flaws in the protocols and the architectures shall be studied and understood. By applying a graph theoretical model of the routing information exchange, the situations that cause anomalies are formally specified and classified: Necessary conditions for the occurrence of internal BGP routing anomalies are identified. By showing how to avoid conditions with- out affecting the semantics of the internal BGP, a theoretical framework for an inherently anomaly-free internal BGP routing is provided.
Knowing how anomalies in the internal BGP routing can be inherently avoided, adequate implementations are necessary to prevent their appearance in productively used systems. As the workarounds used today are problematic for large Autonomous Systems found in the Internet Backbone, architecture concepts for this class of systems seem to be most urgent. Hence, developing an implementation of the theoretical framework that matches the require- ments of ISPs and large carriers defines the second primary objective. Special requirements of this group of Network Operators affect the efficiency, reliability, scalability, and the interoper- ability of the routing information exchange. These requirements are met by the iBGP Route Server architecture. A close cooperation with the network engineers of Deutsche Telekom AG, a large ISP in Germany, guarantees a productively usable solution. This course of ac- tion resulted in scientifically well-founded concepts and solutions, which are tailored to the real life conditions in production systems.