|Abstract:||Interdomain routing is a key element in the global Internet routing infrastructure. A resilient interdomain routing framework is required, in order to deliver reliable and dependable data communication services. However, because the existing routing system has evolved to a large scale and legacy protocols have been widely deployed, building a resilient interdomain routing framework is challenging.
In this thesis, we focus on modeling and improving the resilience of the Border Gateway Protocol (BGP). BGP is the de facto standard of Internet interdomain routing and is used in tens of thousands of Internet routers. It is prohibitively expensive and difficult to build a new interdomain routing protocol from scratch in the near future. Thus, we take an evolutionary approach to improve the reliability of BGP routing. Our research demonstrates that the robustness and the performance of interdomain routing can be increased by understanding the network routing and transport protocols rigorously and by further engineering the protocol stack system appropriately.
Specifically, our investigation on the resilience of BGP falls into three aspects: robustness of BGP sessions, reliability of internal BGP (IBGP) networks, and advertising interdomain QoS routing information. First, we study the robustness of BGP sessions in temporarily failed or severely congested networks. We apply empirical and model-based approaches. These approaches allow us 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 the existing 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 IBGP route reflection networks, which provides references for designing route reflection topologies, especially in the transition from the fully meshed topologies to route reflection IBGP. 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, BGP is a natural medium 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. For example, using interdomain QoS routing information, we can better control resource reservation and traffic engineering processes to make the Internet routing more stable. In order to advertise QoS routing information by BGP, 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.