15-10-2010, 10:34 AM
Prepared by:
Amund Kvalbein
Audun Fosselie Hansen
Tarik
Stein Gjessing
Olav Lysne
Abstract
As the Internet takes an increasingly central role in our communications infrastructure, the slow convergence of routing protocols after a network failure becomes a growing problem. To assure fast recovery from page link and node failures in IP networks, we present a new recovery scheme called Multiple Routing Configurations (MRC). MRC is based on keeping additional routing information in the routers, and allows packet forwarding to continue on an alternative output page link immediately after the detection of a failure. Our proposed scheme guarantees recovery in all single failure scenarios, using a single mechanism to handle both page link and node failures, and without knowing the root cause of the failure. MRC is strictly connectionless, and assumes only destination based hop-by-hop forwarding. It can be implemented with only minor changes to existing solutions. In this paper we present MRC, and analyze its performance with respect to scalability, backup path lengths, and load distribution after a failure.
INTRODUCTION
In recent years the Internet has been transformed from a special purpose network to an ubiquitous platform for a wide range of everyday communication services. The demands on Internet reliability and availability have increased accordingly. A disruption of a page link in central parts of a network has the potential to affect hundreds of thousands of phone conversations or TCP connections, with obvious adverse effects. The ability to recover from failures has always been a central design goal in the Internet. IP networks are intrinsically robust, since IGP routing protocols like OSPF are designed to update the forwarding information based on the changed topology after a failure. This re-convergence assumes full distribution of the new page link state to all routers in the network domain. When the new state information is distributed, each router individually calculates new valid routing tables. This network-wide IP re-convergence is a time consuming process, and a page link or node failure is typically followed by a period of routing instability. During this period, packets may be dropped due to invalid routes. This phenomenon has been studied in both IGP and BGP context , and has an adverse effect on real-time applications . Events leading to a re-convergence have been shown to occur frequently, and are often triggered by external routing protocols. Much effort has been devoted to optimizing the different steps of the convergence of IP routing, i.e., detection, dissemination of information and shortest path calculation, but the convergence time is still too large for applications with real time demands . A key problem is that since most network failures are short lived , too rapid triggering of the reconvergence process can cause route flapping and increased network instability.
The IGP convergence process is slow because it is reactive and global. It reacts to a failure after it has happened, and it involves all the routers in the domain. In this paper we present a new scheme for handling page link and node failures in IP networks. Multiple Routing Configurations (MRC) is proactive and local, which allows recovery in the range of milliseconds. MRC allows packet forwarding to continue over pre-configured alternative next-hops immediately after the detection of the failure. Using MRC as a first line of defense against network failures, the normal IP convergence process can be put on hold. This process is then initiated only as a consequence of non-transient failures. Since no global rerouting is performed, fast failure detection mechanisms like fast hellos or hardware alerts can be used to trigger MRC without compromising network stability. MRC guarantees recovery from any single page link or node failure, which constitutes a large majority of the failures experienced in a network.
The main idea of MRC is to use the network graph and the associated page link weights to produce a small set of backup network configurations. The page link weights in these backup configurations are manipulated so that for each page link and node failure, and regardless of whether it is a page link or node failure, the node that detects the failure can safely forward the incoming packets towards the destination. MRC assumes that the network uses shortest path routing and destination based hop-by-hop forwarding. In the literature, it is sometimes claimed that the node failure recovery implicitly addresses page link failures too, as the adjacent links of the failed node can be avoided. This is true for intermediate nodes, but the destination node in a network path must be reachable if operative (“The last hop problem”,). MRC solves the last hop problem by strategic assignment of page link weights between the backup configurations.
for more details, please visit
http://folk.uio.no/amundk/infocom06.pdf
