Research On The Stability Of Internet Inter-Domain Routing

The Border Gateway Protocol, BGP, is currently the de-facto standard for inter-domain routing in today's Internet. BGP is a path-vector protocol that allows each Autonomous System to override distance-based metrics with policy-based metrics when choosing best routes to achieve their own economic objectives. With the Internet evolving into a business Public Telecommunication Infrastructure, the BGP is playing a more important role in it.As the core protocol of the Internet control layer, BGP will directly influence the stability and efficiency of inter-domain routing. This dissertation concentrates on intra-domain route oscillation, convergence delay, route inflation and inter-domain route oscillation, which are all concerned with inter-domain routing stability. This dissertation aims at making followed contributions:1. Proposed a new algorithm eliminating BGP intra-domain route oscillation. Starting from Stable Path Problem (SPP), the dissertation proposes a new model, Dynamic Stable Path Problem (D-SPP), by introducing a time-variability factor to describe dynamic of this problem. With this model the conclusion is drawn that the time-variability of permitted path and ranking function is root cause of the route oscillation. According to the result, a new algorithm is given which eliminates the time-variability of ranking function to avoid persistent route oscillations in a network using one-level Route Reflection. Compared with others, it is more reasonable and will not increase the network traffic.2. Improved the BGP convergence time. It was noticed that sometimes it takes BGP a substantial amount of time and messages to converge and stabilize following the failure of some node in the Internet. The reduction in the convergence latency of BGP plays a major role in providing QoS and highly available services on the Internet. The dissertation proposes a new algorithm that eliminates the problem pointed out and substantially reduces the convergence time and communication complexity of BGP. The basic concept of the algorithm is: confirm and discard the ASes through which the destination is unreachable, the ASes whose routes to the destination have changed are suspected and trust the stable ASes. Compared with others, the algorithm is more reasonable and will not increase the network traffic.3. Proposed a price mechanism to control BGP route inflation. Today's Internet is a loose federation of independent network providers, each acting in their own self interest. With the ISPs forming with peer relationship under this economic reality, it was proved that the "hot potato" routing is the main cause of BGP route inflation. A price mechanism is needed to avoid this routing policy. The dissertation first proves that a simple continuous price mechanism will result in arbitrarily high global welfare loss, and then proposes a discrete threshold price mechanism. With the mechanism, the welfare loss can be eliminated, and both peers will partly abandon "hot potato" routing.4. Proposed an approach to seeking BGP policy confliction based on secure multi-party computation. BGP is a path-vector protocol that allows each Autonomous System to override...