Abstract
As the Internet takes an increasingly central rolein our communications infrastructure, the slow convergence ofrouting protocols after a network failure becomes a growingproblem. To assure fast recovery from page link and node failures inIP networks, we present a new recovery scheme called MultipleRouting Configurations (MRC). Our proposed scheme guaranteesrecovery in all single failure scenarios, using a single mechanismto handle both page link and node failures, and without knowing theroot cause of the failure. MRC is strictly connectionless, andassumes only destination based hop-by-hop forwarding. MRC isbased on keeping additional routing information in the routers,and allows packet forwarding to continue on an alternativeoutput page link immediately after the detection of a failure. It can beimplemented with only minor changes to existing solutions. Inthis paper we present MRC, and analyze its performance withrespect to scalability, backup path lengths, and load distributionafter a failure. We also show how an estimate of the trafficdemands in the network can be used to improve the distributionof the recovered traffic, and thus reduce the chances of congestionwhen MRC is used.
I. INTRODUCTION
In recent years the Internet has been transformed from aspecial purpose network to an ubiquitous platform for a widerange of everyday communication services. The demands onInternet reliability and availability have increased accordingly.A disruption of a page link in central parts of a network has the potentialto affect hundreds of thousands of phone conversationsor TCP connections, with obvious adverse effects.The ability to recover from failures has always been a centraldesign goal in the Internet [1]. IP networks are intrinsicallyrobust, since IGP routing protocols like OSPF are designedto update the forwarding information based on the changedtopology after a failure. This re-convergence assumes fulldistribution of the new page link state to all routers in the networkdomain. When the new state information is distributed, eachrouter individually calculates new valid routing tables.This network-wide IP re-convergence is a time consumingprocess, and a page link or node failure is typically followed by aperiod of routing instability. During this period, packets maybe dropped due to invalid routes. This phenomenon has beenstudied in both IGP [2] and BGP context [3], and has anadverse effect on real-time applications [4]. Events leadingto a re-convergence have been shown to occur frequently [5].Much effort has been devoted to optimizing the differentsteps of the convergence of IP routing, i.e., detection, disseminationof information and shortest path calculation, but the convergence time is still too large for applications with realtime demands [6]. A key problem is that since most networkfailures are short lived [7], too rapid triggering of the reconvergenceprocess can cause route flapping and increasednetwork instability [2].The IGP convergence process is slow because it is reactiveand global. It reacts to a failure after it has happened, andit involves all the routers in the domain. In this paper wepresent a new scheme for handling page link and node failuresin IP networks. Multiple Routing Configurations (MRC) is aproactive and local protection mechanism that allows recoveryin the range of milliseconds. MRC allows packet forwardingto continue over pre-configured alternative next-hops immediatelyafter the detection of the failure. Using MRC as afirst line of defense against network failures, the normal IPconvergence process can be put on hold. This process isthen initiated only as a consequence of non-transient failures.Since no global re-routing is performed, fast failure detectionmechanisms like fast hellos or hardware alerts can be usedto trigger MRC without compromising network stability [8].MRC guarantees recovery from any single page link or node failure,which constitutes a large majority of the failures experiencedin a network [7]. MRC makes no assumptions with respect tothe root cause of failure, e.g., whether the packet forwardingis disrupted due to a failed page link or a failed router.The main idea of MRC is to use the network graph andthe associated page link weights to produce a small set of backupnetwork configurations. The page link weights in these backupconfigurations are manipulated so that for each page link andnode failure, and regardless of whether it is a page link or nodefailure, the node that detects the failure can safely forward theincoming packets towards the destination on an alternate link.MRC assumes that the network uses shortest path routing anddestination based hop-by-hop forwarding.The shifting of traffic to links bypassing the failure canlead to congestion and packet loss in parts of the network [9].This limits the time that the proactive recovery scheme canbe used to forward traffic before the global routing protocol isinformed about the failure, and hence reduces the chance thata transient failure can be handled without a full global routingre-convergence. Ideally, a proactive recovery scheme shouldnot only guarantee connectivity after a failure, but also do so ina manner that does not cause an unacceptable load distribution.This requirement has been noted as being one of the principalchallenges for precalculated IP recovery schemes [10].

Download full report
http://simula.no/research/nd/publication...a_pdf_file