Toward a Robust Internet Interdomain Routing.

Abstract

Robustness has always been one of themost important requirements in the design of the Internet infrastructure. This dissertation takes two directions toward enhancing the robustness of today’s Internet interdomain routing. On one hand, we propose reactive techniques to identify the cause and origin of each routing instability after its occurrence. On the other hand, we develop a proactive mechanism to enable the current interdomain routing protocol to tolerate certain types of failures. We first focus on the analysis of BGP dynamics from a single network’s perspective and develop a troubleshooting system that identifies in real-time from millions of daily BGP updates a few routing events that network operators can take direct actions upon to alleviate their impacts. There is serious lack of understanding of Internet routing resilience to significant and realistic failures such as those caused by the 2003 Northeast Blackout and the 2006 Taiwan earthquake. We systematically analyze how the current Internet routing system reacts to various types of failures by developing a realistic failure model, and then use it to pinpoint the reliability bottlenecks of the Internet. By focusing on the impacts of structural and policy properties, our analysis provides guidelines for future Internet design. We find that the current policy-driven interdomain routing greatly limits the Internet’s ability to maintain normal reachability under adverse conditions, and therefore, propose dynamic routing negotiation (DRN) to allow ISPs to temporarily relax routing policy restrictions when needed, to exploit the existing physical redundancy in the network topology. The increasing security concerns and emerging MPLS-like layer-2 technology make the traditional tools such as traceroute less capable of identifying the internal structure of networks, which is very important to diagnosis of network anomalies. To reduce the opaqueness of today’s networks, we propose a novel approach to discovering the resource sharing of each network based on the performance measurement between each pair of ingress and egress points in the network. Its performance and utility have been demonstrated via extensive simulations and Internet experiments.