Research On IP Fast Rerouting Method With Next Hop Cost Decrease Criterion

With the population of Internet and rich and colorful applications in Internet, IP traffic has substituted the place of voice traffic and becomes the dominant service carried by telecom networks. And more and more real time voice and video traffic is transferred in Internet, the stricter performance requirements have been put forward on Internet network survivability.This thesis has investigated the problem of network survivability, especially the IP fast rerouting scheme with alternate interfaces method. In Chapter One, we survey and analyze the key topics of network survivability, which include the survivability of SDH/SONET network, optical ASON networks, pure IP networks, MPLS networks and multilayer networks.With stronger ability of the router, IP networks (Internet) improve the survivability mainly in two directions. One does not change the current connectionless, packet, the shortest path forwarding mode, while "patch" the routing protocols with a poor recovery results, such as long recovery time and low recovery ratio. Second introduce a new layer of MPLS (Multi-protocol Label Switching), using the connectivity of MPLS to enhance survivability, with the high operation and maintenance costs.Latest two new methods are appeared --Valiant Load Balancing (VLB) and IP Fast Reroute(IP FRR).In Chapter Two, detailed analysis have been put on the mechanism, limit and possible improvement of the two methods. And with the inspiration of reroute of Road Network in case of failures, we find the possible new idea of using Shortest Path Forward metrics as a direction-sense means to avoid routing-loop.Road network and the Internet are similar in many aspects, such as "connectionless, packet and self-routing along the shortest path". With the road(line in Internet) or junctions(node in Internet) failures in Road Network, automobiles (pedestrian) will deviate temporarily from the original (shortest path) routes, but follow a simple a principle of "direction unchanged", in which they will return to "direction" to destination as soon as possible. As to the Internet, which is the measure of correct "direction" to the destination in the failure?This paper put forward the "Next Hop Cost Decrease(NHCD)" as the corresponding "direction" in Road Networks in case of network failures. Namely, with the NHCD rule, the original router deflects to the candidate router not in the shortest-path. If the cost to destination of the next node in shortest path of the candidate router is not more than corresponding cost of the original router, this deflection is route loop-free.In Chapter Three, a new loop-free criterion-- "Next-Hop Cost Decrease(NHCD)" is put forward, it is different with LFA method in RFC5286. NHCD method has been proven to be loop-free.This paper put forward an algorithm which can find out the Shortest Path First (SPF) interface and NHCD alternate interfaces at the same time.Some initial simulation and analysis results have been done in Chapter Four. With the simulation and comparison between NHCD and LFA in RFC5286, we find that though the failure coverage ratio of NHCD method is somewhat lower than that of LFA method (40%VS46.9%). However as to the LFA rule, the NHCD method has following unique advantages, and is easier to be deployed in the real network.(1) NHCD can deal with link failure and node failure at the same time.(2) NHCD can deal with simultaneous failures, not the single failure in LFA(3) NHCD can be used with other rules to improve the recovery ration, such as ECMP(Equal-Cost Multiple Path) rule(4) NHCD has a lower algorithm complexity than LFA Based on the above characteristics, NHCD method can be used in the normal case to decrease the traffic congestion. So with NHCD ability, routers can deal with the network congestion and failures automatically with the improved route protocols. And these can be gradually deployed, that means not all routers should have the ability of NHCD at the same time.Therefore, in Chapter Five, we put forward and analyze the Alternate Interface Protocol (AIP) based on the NHCD rule, which can simultaneously deal with the fast reroute and fast traffic engineering. We give an integrated loop-free alternate interfaces selection rule with some conditions, the details of the algorithm, related protocols, basic operations of AIP and some application advices.This dissertation includes the following creative contents.(1) On selection criterion of alternate interfaces in shortest-path-first (SPF) network, a new "Next-Hop Cost Decrease" criterion is proven to be loop-free with "Next-hop strictly SPF forwarding" condition. The detailed comparison and simulation with the LFA method in RFC5286 are also put forward.(2) And it is proven to be loop-free to use "Strictly decreasing cost" criterion and "Next-hop strictly decreasing cost" criterion together with the rules of "Next-hop SPF forwarding" and "Can not receive deflection traffic when in AIP state" Some detailed application advices on loop-free alternate interfaces selection rule are presented too.(3) The Alternate Interface Protocol (AIP) which can simultaneously deal with the network recovery and traffic grooming based on the "Next-Hop Cost Decrease(NHCD)" criterion is put forward. The alternate interface algorithm based on the extension of Dijkstra shortest path algorithm is presented too. We analyze manual configuration method and give the detailed protocols and basic operations of AIP.