Enabling loal reovery

It is possibleto utilize theIPRT informationto provideloal reovery. This is beause

eah node in the network has its own pair of redundant trees and IPRT is therefore

apable to reover tra bound for anydestination througheither thered or the blue

tree. Furthermore, sinetra bound for anyarbitrary destination may be reovered,

the reovery may be performed regardlessof the soure. This also holds true for the

r/bTablesolutionsineallpossibledestinationsare presentin boththe rTableandthe

bTable. However, theuse of aseparate routing table for normaloperationintrodue a

problem;

•

^{In a failure situation, the immediate upstream node may experiene a situation}

where it has the option to reover tra using either the red or the blue path.

However, beause aseparate routingtable is used for forwardingin afailure-free

requiresthenodeinitiatingthereoverytohaveanodedegreeofatleastthreeand

furthermore, neighbors thatare presentin therealtopologythat arenotadjaent

nodesin thereoverytrees.

Consider thesituation shown in Figure 5.3. In this examplethe tra from soure

node

R1

^{traversethefailednode}

F

^during failure-freeoperation. Furthermore,during a failure

R1

^{mayfreelyhoosebetweeneither theredortheblue reoverypath. However,}

iftheredpathishosenthereoveredtra would enounterthesamefailureaseond

timewhenbeingforwardedfromrouter

R2

^.

Figure5.3: A nodewithdierentIPRTneighborsandrealneighbors

To ounter this problem someadditional omputation is needed in the IPRT

rout-ing proedure to be ableto tell whih routes arevalid optionsin a reoveryproedure.

Thisinformationmaybepre-alulatedandmadeavailable tothereoveryproedurein

advaneofanyfailure.

Twopossiblesolutionsaredesribed:

•

^{An exatproedure,wherethehealthyreoverypathisidentiedbyomputation}

•

^A probabilistiproedure,wherepotentiallyaetedreoverypathsareidentied The exat proedure is implementation dependant but logially eah node needs to

beveriedtohekifthefailure-free,i.e. default,next-hoptowardstherootisontained

amongtheredorbluenext-hopofaredundanttreepair. Ifthisisnottrue,thealgorithm

mayneedto traversetheredandblue pathin ordertoverifywhih,ifany,ofthepaths

areaetedbysuh afailure.

Another,andprobabilisti,approahtotheproblem,that requireslessomputation,

is to use a dierene in the set of neighbor nodes found in the real topology and the

neighbors found in a pair of redundant trees to result in suessful identiation of a

Furthermore,apositiveidentiationresultsinadefaultrouteseletionregardlessofwhat

path orpathsprovidesavalid reoverypath. However,theforwardingproedure must

support to move reoveredtra between the red and blue path; assume that the red

FIBis alwaysseleted in suh reoverysituations, and theonlyvalid hange of oloris

from red to blue. Furthermore, assume that a node

F

^{has failed and that the failure}

is aetingtra forwardedfrom node

R1

^{,using alink dierentfrom theavailable red}

and blue next-hops. At this stage there is no easy way of evaluating voltages, i.e, if

v(R1) > v(F )

^{, thus itis byhane ifthered pathprovides aworkingreoverypath. If}

thereoveredtraenounters thesamefailureaseond timebeingforwardedfrom

R2

thevoltageofthedierentnodesmustbe

v(F ) < v(R2) < v(R1)

^{. Beause}

v(F ) < v(R2)

thebluepathmustalwaysprovideafailure-freepathtothedestination. Thisisbeause

ifthesameerrorwasenounteredathird time

v(F)

^{must havebeenhigherthan}

v(R2)

^,

whihisimpossiblein aordanetothevoltagerule. Thisshowsitispossibleto deet

reoveredtrafrombetweenthetwoolors. Howeverthedeetionshouldonlybedone

onetoounterthepossibleloopsthatmayarisefrom multipleonurrentfailures.

Theprobabilistiproeduremayresultinundesirablebehavior;inreasingthenetwork

loadanddeethealthyreoveredtraintheeventofmultipleonurrentfailures. The

use of deetion may result in longer reovery-paths. E.g. pakets bound for a failed

destination will be reoveredat the last hop, furthermore, if theyuse the red reovery

FIBtheywillbedeetedwhentheyaretrieddeliveredtothefaileddestinationaseond

time. Whena reoveredpaket traverse an inreased number of links it generate load

at more links and thus inrease the total load in the network. Furthermore, multiple

onurrentfailuresmayprovideaproblem. Thisisbeausethemethodmaynotbeable

to distinguishbetweentwo dierent failures. Consider somereoveredtra following

a red path. If one assumes that the red path wasthe orret hoie for the reovered

tra, i.e. the red pathprovides apath unaeted bythe rst enountered failure. If

this tra were aeted by a seond failure, the forward proedure would deet the

tratothebluepath. Thismayleadtoasituationwherethetramayloopbakand

enountertherstfailureagain. Thus,addingtothetotalamountoftrawithoutbeing

ableto aomplishasuessfulreovery. Inaddition, thedeetionroutingaddsto the

omplexityoftheforwardproedure,asadditionaldeisionsbeomeavailable. However,

thedeetion mayenablepaketstobesuessfullyreoveredfromaseondfailure, i.e.

the newblue reoverypath doesnotneessarily equalthe reverse redpath, but this is

outside the sope of this thesis. In addition, the deetion proedure does enable the

IPRT method to operate in a transparentmanner in the presene of ECMP routingif

desired,butthis isoutsidethesopeofthethesis.

The exat proedure does enable the reovery proedures to pik the orret, i.e.

failure-free,reoverypathatrsttry. Thus,thisapproahdoesnothaveanegative

im-pat on the length of areoverypath. In addition, this proedure trades omputation

that is more omplexduring the routingproedure to enablethe use of asimpler

for-wardingproedure. I.e.,Deetionroutingmaybeusedeveniftheorretreoverypaths

are known in advane to get thebenets of a possible betteroverage during multiple

needs to verify their own next-hopsin eah redundanttree set. Thus, thetime needed

to ompute the aeted reovery paths may not be of signiane if ompared to the

deetion approah. However,thegainofusingthis mehanisminadistributed fashion

variesbetweenthevariouslinkdegreesofthenodesin agiventopology.

In document IP redundant trees for preplanned recovery in connectioning networks (sider 46-49)