UC San Diego

The Internet's routing architecture was designed to have a clean separation between the intradomain and interdomain routing protocols. However, the appropriate "division of labor" between these two tiers becomes unclear when an Autonomous System (AS) has interdomain routes to a destination through multiple border routers--a situation that is extremely common today because neighboring domains often connect in several locations. Unfortunately, this evolution in Internet structure has made it increasingly susceptible to unforeseen interactions between the two routing protocols. We believe that the current mechanism of early-exit or hot potato routing--where each router in an AS directs traffic to the "closest" border router based on the intradomain distances--is convoluted, restrictive, and sometimes quite disruptive. This thesis improves the robustness of IP networks by revisiting the interaction between intradomain and interdomain routing protocols. First, it analyzes the influence of intradomain routing changes on BGP routing (the interdomain routing in the Internet today). We found that some intradomain routing changes trigger a significant number of BGP updates. In fact, these BGP routing changes are responsible for the largest traffic variations. Applications such as voice over IP, streaming, and gaming are particularly sensitive to these instabilities. As a result, the development of guidelines and tools for the design and configuration of networks that minimize the impact on BGP are important tasks for achieving network robustness. We address these challenges using an analytic model of routing interaction that incorporates metrics to evaluate network sensitivity to intradomain changes. Our model identifies vulnerabilities in the network and can be used by network administrators to engineer more robust networks. Finally, we propose a simple change to router's BGP decision logic to implement a flexible mechanism for selecting egress points for traffic. This mechanism allows network administrators to satisfy diverse goals, such as traffic engineering and robustness to equipment failures. We present two example optimization problems that use integer -programming and multicommodity-flow techniques, respectively, to tune our mechanism to satisfy network- wide objectives. Experiments with traffic, topology, and routing data from two backbone networks demonstrate that our solution is both simple (for the routers) and expressive (for the network administrators)