Resilient interdomain routing with BGP: Protocols and reliability engineering

Interdomain routing is a key element in the global Internet routing infrastructure. We focus on modeling and improving the resilience of the Border Gateway Protocol (BGP), the de facto standard of the interdomain routing. Our research demonstrates that the robustness and the performance of interdomain routing can be increased by using appropriate configuration and extensions to the existing protocols.; First, we study the robustness of BGP sessions in temporarily failed or severely congested networks. We apply empirical and model-based approaches to systematically analyze impacts on BGP sessions, coming from (a) BGP behaviors, (b) TCP behaviors, (c) network failures, and (d) network congestion. For example, we show that the retransmission mechanism of TCP is too conservative for supporting BGP sessions; but we can properly configure and augment TCP to make BGP sessions much more robust in stressful network situations. Our results thus provide a guide for the precise configuration of network protocols to improve the BGP session robustness.; Second, we focus on the reliability modeling and topology optimization in Internal BGP (IBGP) route reflection networks, which can provide references for designing route reflection topologies. We characterize the resilience of IBGP networks with several reliability metrics, such as the connectivity of IBGP routers and the severeness of session loss. Based on these metrics, IBGP topologies are optimized for typical network failure scenarios. The topology optimization problems are systematically studied, including heuristic solutions, hardness, and other properties. Our experiments conclude that the resilience of IBGP route reflection networks can be significantly improved by configuring route reflection topologies properly.; In addition, we extend BGP for advertising interdomain QoS routing information which includes network resource availability, communication reliability, etc. This information can help to route and manage Internet traffic efficiently and reliably. We propose a series of statistical metrics which abstract QoS information into one or several probability intervals, so that the heterogeneous and dynamic information can be flexibly and precisely represented. Moreover, by capturing the statistical property in QoS routing information, these new metrics can highly decrease the message overhead in routing updates, thereby making the QoS advertising more scalable.