BGP Egress Selection Optimization Based On Traffic Load Balance

With the rapid development and broad application of Internet, interdomain routing and traffic engineering become more and more important. Interdomain egress selection optimization is one of the hot research topics in the area of interdomain routing and traffic engineering, for, multihoming is often used by large enterprises and stub Autonomous Systems (AS) as a means of Internet connection. Many domestic as well as international research institutions have carried on quite a lot research works on interdomain egress selection optimization, and have made some valuable achievements so far. However, we argue that the modeling theory, computing framework, key technologies, and implementation mechanism in this research area are far from well developed, with new issues and open problems keep on emerging.To address several problems in interdomain egress selection optimization, we present a model, BGP-ESOM (BGP Egress Selection Optimization Model Based on Traffic Demand) based on traffic demand and framework, BGP-RCS (BGP Routing Control Service), based on traffic load balance for transit AS. We start our research from the general framework of BGP-RCS, and then focus on the following key technologies: optimization on the static stage, optimization on the dynamic stage and dynamic traffic detection. Our work outperforms the existing solutions both in reducing the running time of interdomain egress selection optimization and improving the routing stability with traffic load balancing. Comparing with other routing optimization architectures, BGP-RCS has many advantages, including good global optimization, real-time selection of BGP egress, distributed egress selection, system robustness and little modification to BGP. The contributions of this dissertation are as follows:1. Model and framework for interdomain egress selection optimization. Based on the analysis of relationship and interaction between interdomain routing protocol and intradomain routing protocol, BGP-ESOM model composing of static optimization stage and dynamic optimization stage is proposed. The corresponding BGP-RCS framework is designed on the BGP-ESOM model, which can reflect the objective of traffic engineering on the static stage of the problem, the objectives of variability, robustness and real-time decision on the dynamic stage of it with the change of routing, topology and traffic. The BGP-RCS framework is a feedback control system, which composes of four parts: egress selection optimization in static stage, egress selection optimization in dynamic stage, negotiation process between domains, and dynamic detection of traffic change to decide the occasion of optimization recomputation. In this dissertation, we focus on the static egress selection optimization algorithm, the dynamic egress selection optimization algorithm, the dynamic traffic detection algorithm, and the implementation of BGP-RCS prototype. 2. The static egress selection optimization algorithm for interdomain egress selection optimization. In the BGP-RCS framework, we convert the BGP egress selection problem into IGP engineering based on traffic demand in the static stage. The main drawback of the typical algorithm for this problem is its long execution time. To reduce the execution time, a bottleneck prediction algorithm, BAF(Bottleneck Area Forecast Algorithm), is proposed to preprocess optimization in static stage by reducing search space at first. Then a BGPEOpt(BGP Egress Optimization Algorithm) algorithm is proposed to reduce the execution time of the typical algorithm by leveraging the .characteristics of cut link in the topology graph to reduce the frequency of recomputing traffic demand. Further more, mediate results are used in the iterative process to reduce the time of computing the IGP shortest distances from a source node to other nodes. Experimental results indicate that the running time of BGPEOpt reduced 7%~30% with the similar link utilization comparing to that of typical algorithms.3. The dynamic egress selection optimization algorithm for interdomain egress selection optimization. The typical BGP egress selection algorithm in dynamic statge has some disadvanges of complex computation of parameters, ignoring some useful factors, to name a few. We propose three algorithms, ATIE(Adaptive Tunable Interdomain Egress selection algorithm), RTF_TIE(Tunable Interdomain Egress selection algorithm Robust to Transient link Failures) and BGP-RO-ES(BGP Route Optimization for Egress Selection based on Link States), respectively. The main idea of ATIE is that it simplifies parameters in typical algorithm-TIE and the value of parameter can change with the change of traffic load to satisfy different purpose of balance between traffic engineering and routing stability. The RTF_TIE focuses on the relationships among IP link failure duration, routing stability and traffic engineering. We define the new metrics of routing stability and traffic engineering on time axis at first. Due to most link failures are transient link failures, the main idea of RTF_TIE is that interdomain egress selection should be robust to transient link failures. The BGP-RO-ES uses the characteristics of ATIE and RTF_TIE. It also adds multiple constraints defined by network administraror (e.g. the cost of maintaining lightweight tunnels inconsistency with the forwarding path) and provides direct traffic engineering control used by network administrator. Simulation results show that these algorithms are more effective on routing stability, traffic engineering, control flexibility and complexity of computation.4. The dynamic traffic detection algorithm for interdomain egress selection optimization. Based on the demand of traffic change detection in the BGP-RCS framework, two new and easy-to-measure metrics are proposed, the excursion of mean value of max link utilization and the excursion of standard variability of max link utilization. We present the determinant criteria of recomputing the static egress selection optimization algorithm. The typical periodic method to measure and collect link traffic and flow traffic for dynamic traffic change detection suffers from many drawbacks, such as too many objectives to be measured, massive data to be saved, and higher frequency of measurement. In this dissertation, we propose a dynamic traffic detection algorithm, PCAD(Principle Component Analysis Detection Algorithm), composing three-level measure structure based on PCA(Principle Component Analysis) to overcome the above drawbacks. The PCAD algorithm reduce the number of measuring links by making use of PCA to analyze the relativity among link traffics in space and time with respect to the control the selection of key links to measure. Simulation results show that PCAD has higher recognition probability and lower error rate with reducing the number of measuring links and the frequency of measurement effectively.5. Design and implementation of BGP-RCS prototype. Based on the studies on the key technologies stated above, a BGP-RCS prototype in NetWatcher is designed and implemented focusing on the details of RCS (Routing Control Service) composing of U profile, O profile and M profile, followed by a description of the relationship between objectives in all kinds of situations in the network.To sum up, we present well-evaluated solutions in this dissertation for some key issues of interdomain egress selection optimization. We believe that our contributions make a nice groundwork for future research and engineering on interdomain egress selection optimization both in theory and practice.