Research On Routing Optimization In Large Scale Autonomous Systems

Increasing demands are being placed on the performance of IP networks. Routing optimization is an efficient and effective way to improve the network performance. However, it is challenging to optimize routing in large scale autonomous systems (ASes) due to the complexity of such systems.This dissertation investigates some essential problems of routing optimization in large scale autonomous systems, especially the problems of IBGP visibility, routing protocols running parameters optimization and IBGP robustness. In consideration of the relationship between the routing system, the data plane and the management plane, as well as the complex interaction between the internal gateway protocol and the border gateway protocol, we present some new algorithms and mechanisms to improve the network performance by using graph theory, probability theory and simulation methods.Route reflection is widely used as an alternative to full mesh IBGP sessions inside an autonomous system for scalability reason. However, it may cause the complete visibility problem. Although the IBGP configuration generated by the existing algorithm BGPSep guarantees the property of complete visibility, BGPSep does not reduce the number of IBGP sessions of the top level route reflectors. To solve the scalability and visibility problems of IBGP networks, we present two algorithms, namely BGPSepD and BGPSepS, for constructing IBGP configurations. In the observation that a lot of pendant vertexes exist in the IGP topologies of some large ASes, we conditionally remove some vertexes from the IGP graph. By applying the BGPSep algorithm to the remaining graph, we obtain the BGPSep_D algorithm. Then we prove that IBGP topologies generated by BGPSep_D hold the properties of complete visibility, loop-free forwarding and robustness to IGP failures. The performance of BGPSep_D is evaluated on several real-world backbone topologies. Experimental results show that the maximum degrees of the IBGP topologies generated by BGPSepD for these backbone IGP topologies can be reduced by about 9%-50%. However, the scalability of IBGP topologies produced by BGPSep_D depends on the characteristics of IGP topologies, hence not satisfactory in some ASes. To further improve the scalability of IBGP topologies, we present another IBGP topology construction algorithm called BGPSep_S, by taking into consideration the vertexes degrees, the vertexes separators and the shortest paths between vertexes in the underlying IGP graph. We also prove that BGPSep_S guarantees the properties of complete visibility and loop-free forwarding in normal situations. The experiments show that the maximum degrees of the IBGP topologies generated by BGPSep_S for several real-world backbone topologies can be reduced by 27%-68%, compared with full mesh and BGPSep. Different settings of routing protocols running parameters have different impact on the routing convergence, routing stability and robustness. An insight into their effects on the networks is the premise of appropriate setting of them. This dissertation models the effects of failures on networks. We discuss the reliability of IBGP sessions for analyzing how failures affect interdomain traffic. Then based on probability theory, we give quantitative relations between the time of traffic loss/shift and the influential factors: the main tunable parameters and the failure duration. The analysis results are validated by simulations. The results of analysis and simulations demonstrate that the characteristics of both IGP topologies and traffic should be considered in the selection of parameter settings. To solve configuration conflict, a potential profit loss model is presented and some suggestions on the configuration are given.There may be lots of IBGP topologies available for a large scale autonomous system. Different IBGP topologies may have different impact on network performance. Robust IBGP networks are very important to the stability and reliability of Internet. Although several metrics have been presented to measure the robustness of IBGP networks, they only considered the impact of route reflection networks on the control plane. A small number of routing changes may cause large traffic shifts. A robust network should have low sensitivity to traffic load variations. So we propose a new metric called TDR (Traffic Diversion Rate) to measure the impact of route reflection networks on the data plane. A new approach is presented to calculate the failure probability of IBGP sessions, a parameter in TDR, based on the probability distribution of IGP routing recovery time. With this TDR metric, we investigate the optimization problem of finding the most robust IBGP route reflection topologies, in which a cluster is allowed to have one or more redundant route reflectors and the maximum number of IBGP sessions that a router can have is limited. We discuss the relationship between the route reflectors redundancy and the robustness of topologies, and give the lower bound of the optimization. In the case that there is a redundant route reflector within each cluster, we give the solvability conditions for the optimization problem and show that the problem in general is NP-hard. Simulations show that with the optimal route reflection topology that minimizes TDR, the network loses or shifts much less traffic than with the optimal route reflection topologies found according to other metrics.In summary, the performance of IP networks can be improved by optimizing IBGP topologies and routing protocols running parameters. Our research results are valuable to design high performance routers and to run high performance networks. They are also meaningful to the research on new network architectures and new routing protocols.