Network Sensitivity to Intradomain Routing Changes

The Internet's routing architecture was designed to have aclean separation between the intradomain and interdomain routingprotocols. However, the appropriate "division of labor" between these twotiers becomes unclear when an Autonomous System (AS) has interdomainroutes to a destination through multiple border routers -- a situationthat is extremely common today because neighboring domains often connectin several locations. Unfortunately, this evolution in Internet structurehas made it increasingly susceptible to unforeseen interactions between thetwo 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 designand configuration of networks that minimize the impact on BGP areimportant tasks for achieving network robustness. We address thesechallenges using an analytic model of routing interaction thatincorporates metrics to evaluate network sensitivity to intradomainchanges. 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 toimplement a flexible mechanism for selecting egress points fortraffic. This mechanism allows network administrators tosatisfy diverse goals, such as traffic engineering and robustness toequipment failures. We present two example optimization problems thatuse integer-programming and multicommodity-flow techniques,respectively, to tune our mechanism to satisfy network-wideobjectives. Experiments with traffic, topology, and routing data fromtwo backbone networks demonstrate that our solution is both simple(for the routers) and expressive (for the network administrators)