Toward interdomain traffic engineering for availability and performance

People are increasingly relying on the Internet for individual user needs, business transactions and government interactions. Applications using the Internet for data transport typically require one or more of the following properties: low latency transport to enable "real-time" communication, high bandwidth transport to enable efficient transfer of large amounts of data, stable transport to enable long term and reliable communication. However, traffic loads introduced by applications are constantly changing and the resources available to the network are finite. Thus to maintain efficient, stable, congestion-free paths, network engineering is needed. This is still an unsolved problem in the interdomain setting. As the Internet has grown in the number of networks or domains that connect to it and the number of interconnections between these domains, the need for interdomain network engineering has become more urgent.; This dissertation addresses the following question: How can we increase the availability of and reduce congestion in the Internet without compromising the scalability, stability and performance of the hardware and protocols that underly it?; In particular, we focus on the scenario of a network with connections to multiple Internet Service Providers (ISPs). If a connection to an ISP is heavily congested, it is very difficult today for an operator to remedy the situation even if other ISP connections are not loaded. We want solutions to this problem to scale to all traffic on the Internet. We do not want to improve the performance of individual application flows at the expense of others. The more interconnected the Internet becomes, the more likely a change in one part of it will impact the rest. Solutions must scale with this growth while maintaining network stability. However, the Internet today is comprised of a variety of hardware and protocols. Any solution should co-exist with the deployed infrastructure. There are a variety of challenges for solving this interdomain problem---lack of global knowledge, global scale of the problem, lack of predictability of the paths that traffic takes, distributed control, and stability.; The general methodology for the dissertation is to measure and collect network data, develop algorithms to analyze the data and make observations. We have collected and analyzed large amounts of operational data across different network providers. This includes routing data, traffic data, router configurations and router loads. We have characterized various interactions between different components of network operation. This dissertation presents several results and makes several contributions: (1) Business relationships between networks can impact the paths of traffic flows. This dissertation proposes a novel algorithm to deduce these relationships. (2) We examine how interdomain routing instability can impact router infrastructure. Despite unusually high activity during network attacks, there is little discernible impact on the infrastructure. (3) We examine how changes in interdomain routing impact network performance in a "tier-1" ISP. Even though there is significant routing instability, less than 0.03% of traffic is affected due to certain properties of the instability. (4) Changes in intradomain routing can impact network performance across network boundaries. Over 60% of destinations or over 70% of traffic can be affected by this problem. Our work improves existing algorithms for intradomain network engineering by 20% in network utilization.