Chinese Journal of Computers   Full Text
Title	A Framework and Critical Algorithm of Interdomain Egress Selection Optimization Based on Link States
Authors	LIU Ya-Ping GONG Zheng-Hu HE Jun-Feng
Address	(School of Computer, National University of Defense Technology, Changsha 410073)
Year	2007
Issue	No.11(1963—1971)
Abstract &   Background	Abstract With the rapid development of Internet, interdomain routing becomes more important. Interdomain egress selection optimization is one of the important problems in the research of interdomain routing protocol. Current mechanisms of interdomain egress selection are often inflexible or ineffective with ignoring many factors such as routing stability, network dynamics, the demand of real time, traffic engineering and so on. This paper proposes and evaluates a framework to facilitate efficient selection of Border Gateway Protocol (BGP) egress for Autonomous System (AS) when Interior Gateway Protocol (IGP) link state changes. It can provide a flexible means for AS to optimize routing according to their multiple goals. Based on control rules and current link state, every BGP router can select appreciate egress points online. The framework is extensible, flexible, and robust. A critical algorithm based on link failures is applied to illustrate the main idea of the framework. Simulation results demonstrate that this solution is feasible and expressive for the network administrators. keywords BGP; traffic engineering; routing stability; routing optimization background The research problem of this paper is the egress selection optimization problem which is one of the important problems in the research of interdomain routing protocol. Presently, the most common egress selection algorithm that we used in transit AS(Autonomous System) is hot-potato algorithm. However, the hot-potato algorithm has two main problems: First, a small intradomain link change may be easy to trigger big problem of BGP(Border Gateway Protocol) routing stability. Second, it is not easy to support traffic engineering. Prior research has considered a range of possible techniques. Teixeira proposed a TIE (Tunable Interdomain Egress Selection) mechanism in 2005. Bressoud developed heuristic solutions to determine an optimal selection of outgoing links and associated border routers in 2003. Uhlig proposed a multiple objectives evolutionary algorithm to solve the potential conflicting nature of the traffic engineering objectives in 2004. There are many other techniques what are not listed here. However, current mechanisms of interdomain egress selection are often inflexible or ineffective with ignoring many factors such as routing stability, network dynamics, the demand of real time, traffic engineering and so on. In this paper, the authors propose and evaluate a framework to facilitate efficient selection of BGP (Border Gateway Protocol) egress for AS(Autonomous System) when IGP(Interior Gateway Protocol) link state changes. The research belongs to the project of "Theory of Switching and Routing for the Next Generation Internet", supported by the National Basic Research Program (973 Program) of China under grant No.2003CB314802. The project aims at creating new switching and routing mechanism for the next generation Internet to achieve scalability, security, controllability of the network. The work of this paper is an important part of the interdomain routing optimization, which researches how to select interdomain egress point optimally. The authors are working towards research of the fuzzy switching and interdomain routing optimization. More than 20 papers are published in the magazines and important international conferences. Three of them have been included in SCI (Science Citation Index), such as the paper titled "A Routing Optimization Algorithm for BGP Egress Selection". And eight of them have been included in EI (The Engineering Index), such as the paper titled "A Tunable Interdomain Egress Selection Algorithm Robust to Transient Link Failures". The others have been included in core magazines of china. Moreover, they are applying for a patent.