r/bT ables - IP redundant trees for preplanned recovery in connectioning networks

5.2 Routing

5.2.4 r/bT ables

Themultipleroutingtablesproposalarriesahighostinmemoryusage,asthenumber

ofroutingtablesarediretlydependentonthenumberofnodesinthenetwork.Therefore,

this solutionisnotavalid optionin aonventional IP network. r/bTablesisasolution

forreduingthefootprintoftheIPRTmethodintheFIBstruture. Themain ideaisto

removeallnon-essentialroutesfrom thereoveryFIBswhileretaining thefuntionality

and propertiesof theredundanttrees. Thebasisfor themultiple routingtablesolution

is to view the upstream node of the failure as the root, and with this as a starting

point try to reover the tra using either its red or blue reovery tree. One of the

majordisadvantagesinthisapproahisthattherootisrequiredtoreahallothernodes.

ThusthereoveryFIBsoftherootnodeneedstoontainthenexthopforeahpossible

destination.

If oneisable toreversethissituationandusethedestinationastheroot,therewould

only be need for one entry in eah of the reovery FIBs, i.e. sine there is only one

possible destination instead of all other nodesexept the root, the FIB would be redued

aordingly.

Theredutionisbasedonthefollowingobservations.

•

^Every^nodeⁱⁿ ^the^network^has^its^own^unique^pair^of^red^and^blue^treeⁱⁿ^whih^it

•

^Consider^a^red ^and^blue ^tree ^pair^rootedⁱⁿ ^a^node⁽

S

^). ^In^both^trees, ^there^exist

pathsfrom

S

^to ^every^nodeⁱⁿ ^the^tree.

•

^If^the^trees^are^onstruted^from^a^topology^with^onlybidiretionallinks,thereexist areversepathforeverypath.

•

^In ^asingle-failuresituation

S

^should ^be^able^to ^reah^anyoperationalnodeeither by itsredorbluetree. Giventhereversepaththe opposite shouldalso holdtrue;

in afailuresituation,anyoperationalnodeshould beabletoreah

S

^either ^by

S

^'s

redorblue tree,provided

S

^isoperational.

•

^Every^nodeⁱⁿ^the^network^isrepresentedexatlyonein eah tree.

•

^Every^node,^exept

S

^,^has^exatly^one^parentⁱⁿ ^eah^tree.

The voltagerule ensuresthatanode isrepresentedat mostone in eah tree,i.e. if

anodeis enountered morethan oneit must have obtainedmorethan onevoltagein

thetreeandthusbreak theordering thevoltageruleimposesonthenodes. Ifanodeis

notinthetreethiswouldmeanthatthenetworkdoesnotomplywiththeonnetivity

requirements,e.g. thenetwork issegmentedorone-edge-onneted,andthat the IPRT

methodouldnothavebeensuessfullyapplied tothetopology.

Theresultingtopologies,aftertheRTalgorithmhasompletedtheomputation,are

twotrees. If,forexample,anode

Y

^has^more^than^one^parent,^the^voltage^rule^ould^not

havebeenenforedasthevoltageofanodemayonlytakeuponasingleredandasingle

blue value, and by following theloop nodes are enountered morethan one and thus

breakthedesendingorasendingvoltagerulefortheredorbluetreerespetively. Thus,

thereversepathfromanyofthehildrenoftherootnodeisunambiguousandloop-free.

The redundant tree algorithm requirethevoltagefound in thered and blue tree to

be monotoni inreasing and dereasing, respetively. Traversingthe trees from a leaf

node will hange the redtree to inreaseand the blue treeto derease. Let

X 6= S

^be

an arbitrary vertex that is removed from the graph and let another node

Y 6= S

^. ^In

this example

Y

^may^still ^reah

S

ⁱⁿ ^either ^the ^red ^or^the ^blue ^tree. ^Sine ^the ^verties

areorderedoneofthefollowingpropertiesmustbetrue;either

v(Y )

v(X)

^or

v(Y )

v(X)

^. ^F^or ^the ^rst^ase

S

^may ^be ^reahed ^through ^the ^red ^tree ^as^it ^provides ^parents

whohavevoltagesthataremonotoniinreasing. Fortheoppositediretionthebluetree

ouldbeusedas itprovidesparentswhohavevoltagesthataremonotonidereasing.

The r/bTablemethodsolvesthelast-hopproblem. Considertheroot node

S

^,ⁱⁿ ^the

redtree ithasavoltage equalto zero,and in theblue treeithasavoltageequal

v max

Furthermore,imaginethatalink betweenaneighbornode,

Y

^,^and^the^root^node,

S

^,^has

failed. If

Y

^want^to^send ^tra^to

S

^over^the^failed ^link,^one^of^the^following^properties

mustbetrue;either

v(Y )

v(S red )

^or

v(Y )

v(S blue )

^. ^Thus,^tra ^from

Y

^to

S

^may

bereoveredusing eithertheredorbluepathasshownintheformerparagraph.

These propertiesensurethat thereexists aloop-freeanduniquepathfrom eahleaf

nodeto

S

^,^and^that^all^the^paths^from^the^parents^are^proper^sub-paths^of^its^hildren's

paths. I.e. the pathfrom aroot of asubtree towards

S

^is independent ofthe starting pointinitssubtree.

By only onsidering the paths from the hildren towards the root of eah tree the

size ofeah orrespondingFIBmaybereduedtoonlyontainoneentryindiatingthe

next-hop onthe path towardsthe root and itsdiretly attahed hosts and subnets. In

an IP paket the destination address is always present, and from this information it is

possibleto determine whih pairof red and blue reoverytrees the destination is root

nodeof. Furthermore,sineallnodesarepresentinboththeredandbluetrees,andthat

apathisguaranteedinaseofasingle-failure,theupstreamnodeofthefailuremayuse

atleastoneofthesetreestoreoverthetraaetedbythefailure.

An example from a syntheti topology is shown in Figure 5.2. Only the red and

blue treewhere node Ais rootis shown forsimpliity, andthered andblue diretional

arrowsshow thenext hopfrom anode following thered orblue tree towardsthe root.

Furthermoreitisshownasituationwhere nodeBhasfailed andasituation wherenode

C has failed. In both situations the root node is reahable trough the red or the blue

tree,forfailureonBorCrespetively.

Figure5.2: Twodierentfailuresinar/bTableenablednetwork

The union of the reovery FIBs reated from the red trees, and a union of all the

reoveryFIBsreatedfromthebluetreeswillprovidewithaompleteredFIB(rTable)

destinationisnotinthetree,itisnotpossibletoreovertraboundforthatdestination.

Thisunionof thereoveryFIBsisnotneessaryfortheproedure tofuntion properly,

but allowsthe signaling to use less resoures. This is beause the marked paket only

needs to ontain a reovered bit and abit indiating whih of the reoverytables is

to be used. With the multiple redued routingtables the marking needs morebits to

indiatewhat tabletouse.

Inther/bTablemethodthedestinationwillditatewhatpairofredundanttreesare

used as basis for the path a reovered IP datagram use. Normally the destination of

an arbitraryIP paket would notbe arouter in the network but rathera hostor

sub-network attahed to an egress (last-hop) router. Thus, if the r/bTableapproah is to

beused, theview alsoneeds to inorporate a bindingbetweenall possible destinations

andtheirrespetiveegress(last-hop)routers. I.e. when apairof redandblue treesare

omputed for anarbitrary routerin thenetwork the treeswould need to be assoiated

withallthepossibleneighbordestinationsexeptdestinationswhothemselvesarerouters

in the sameAS. There is almost no additionalomputational ost assoiated with this

bindingrequirementasthenumberofiterationsoverthetreegenerationalgorithmdoes

notinrease.

The observations seen from the multiple routing tables solution are still valid for

this method as the redand blue tables yield avalid routingtable that maybe usedin

onjuntionwith anormaloperationFIB orbyitself. ByonatenatingtheFIBsthe

ost andoriginal topologyview islost and therefore thereoverymethod still needs to

relyonaroutingprotooltoobtainthefulltopologyviewneededwhenonstrutingthe

redundanttrees. Howeverthissolutionwouldrequirepakets tofollowadierentset of

reoverypathswhenatwowayommuniationis used. ThereasonforthepathsA

→

andB

→

^A^to ^be^disjunt^is^beause^they^stem^from ^two^dierent^redundant^trees. ^With

themultipleroutingtablesolutionthisouldbeavoidedsinethissolutionprovideswitha

properFIBforeahofthegeneratedtopologies,andthusleavestheneessaryinformation

tobeabletoroute paketsbothwaysfollowingaFIBreatedfrom thesametopology.

The big advantagefor this solution is that it removes the dependeny between the

numberofFIBsandthenumberofnodesinthenetwork,andreplaesthememoryusage

assoiatedwiththismethodwithaonstantfator. Theresoureredutionisonlyfound

inmemoryusageastheomputationalresouresneededdoesnotdierfromthemultiple

routing table solution. I.e. alltrees need to be omputed and subsequently ashortest

path on the orresponding topology needs to be performed. However, this is still an

exellentredutioninthememory-footprintneededforIPRT.

The redution in stateinformation allow IPRT to be applied in a memory eient

way. Furthermore,siner/bTableallowIPRTtoguaranteethatonlytwoFIBsareneeded

to provideIP fastreoverymarkingpakets maybeimplemented. This allow IPRT to

provideaperpaketsignalingthatiseientinthermsoftraoverhead.Inthisthesis

ther/bTablemethodwillbeused torepresentthereoveryFIBs.

Theredundanttree method wasoriginallyintended forglobalreoveryina

onnetion-orientednetwork. ThemaingoalforIPfast-rerouteframeworkistoprovideloalreovery.

With redundanttrees, itispossibletoperformglobal reoverysineitis basedon a

senariowhereallthenodesinthenetworksharethesameviewofthereoverypaths. As

withallreoveryoperationsglobalreoveryhaveahigherpossibilitytoprovideashorter

reoverypaththanloalreovery.

However, to beable to support atrue global reoveryseveralsupport funtions are

needed. Thenodedetetingthefailureneedsatleasttoinformthesoureofeitheratwhat

omponentthefailurewasdisoveredorprovidethesourenodewiththeorretreovery

three, pathor topology. At thesoure node, a synopsisof the destinations aeted by

the failure must be maintained in a soft-state data struture. These two proedures

needsto berepeatedforeveryIP-prexaeted ofthefailure, sinetheredundanttree

method onlyguarantees reoverythrougheither the redortheblue tree. Furthermore,

thereoveredtraneedstobemaintainedin asoft-statetoavoidtheneedforasoure

nodeto relyonsignalingfrom theimmediateupstreamnodeof thefailureto revertthe

trabaktonormaloperation.

Even though there mightbe some gainin using a global reoveryin terms of path

lengththetotalostofmaintainingasoftstatedata-strutureofthetraneededtobe

reverted to reoveryoperationand theost of hekingeveryIP paketfor theneed of

reoverymaybe fargreater than thebenets in redued totalload in the network. In

addition, IPRTreoverymethod is intendedto work asabuer betweenfailure and

re-onvergene.Thus,thetimespantheglobalreoverywouldbeoperationalandeetive

wouldbe evenfurtherdiminished. This makesitunaeptableto utilizeglobalreovery

forIPRT.

5.3.1 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

^traverse^the^failed^node

F

^during failure-freeoperation. Furthermore,during a failure

R1

^may^freely^hoose^between^either ^the^red^or^the^blue ^reovery^path. ^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 ^exat^proedure,^where^the^healthy^reovery^path^is^identied^by^omputation

•

^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 ^a^link ^dierent^from ^the^available ^red

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

v(R1) > v(F )

^, ^thus ^it^is ^by^hane ^if^the^red ^path^provides ^a^working^reovery^path. ^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 ^have^been^higher^than

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.

5.3.2 Representing the loal reovery path orretion

When thepaths that maybe aeted bya singlefailure a seond time are known, the

informationmustbemadeavailabletotheforwardproedure. Sinethesituation where

areoverypath inludes the failed node asanintermediate node requires thenext-hop

onbothreoverypathstobeoperational,theforwardingproedure needsto be ableto

makeaninformeddeision. Theideapresentedhereistoletapairofbitsindiatewhih

reoverypathishealthy.

In document IP redundant trees for preplanned recovery in connectioning networks (sider 42-0)