IP redundant trees for preplanned recovery in connectioning networks

UNIVERSITY OF OSLO Department of Informatics

IP REDUNDANT TREES FOR

PREPLANNED RECOVERY IN CONNECTION- LESS

NETWORKS

Master thesis

Ole Kristoffer Apeland

1st November 2006

Mostnetworksareinherentlyproneto failures,and failuresdoouronaregularbasis.

New real-time servies, relying on ontinuous onnetivity, are regularly introdued on

the Internet -requiringnew demands to bemet, oftenextending beyond the Internet's

originaldesign goals. Traditionally,reoveryhasbeenoveredby theIP re-onvergene

proess, whih is a lengthy proess oering reoverytime in the range of seonds. In

this thesisIPRedundantTrees (IPRT),anewmethodfor providingIP fast reovery,is

introdued. It is based on theredundanttree approah presented byMedard et.al [1℄,

extendedtoprovidearesoureeientwaytopopulatethereoveryForwardInformation

Base (FIB) and furthermore, the mehanisms needed to utilize this information in the

forwardingproedure in order to provideloal reovery. IPRTis evaluatedthroughthe

use of graph theory in the initial design phases, and simulations on several real and

synthetiallygeneratednetworks. Theevaluationshowsthat oneofthestrongestassets

ofIPRTistheabilitytoprovide100%overagewithaminimalandonstantamountof

extrastateinformationin eahrouter.

Working with this thesis has been both interesting and hard work. I would espeially

liketothankmysupervisor,TarikCii,foronstantenouragementandvaluableinput,

andmywifeforherloveandpatienethroughthelonghours. I wouldalsoliketothank

AmundKvalbein,TommyAndréNykvist,Audun FosselieHansenandotherpeoplewho

ontributedommentstothiswork.Furthermore,Iwouldliketothankfamilyandfriends

forallhelpandsupport.

1 Introdution 1

1.1 Motivation . . . 1

1.2 Importantndings . . . 4

1.3 Organization . . . 5

2 Goals 6 3 Bakground 7 3.1 Classiationofreoverymehanisms. . . 7

3.2 IPRouting . . . 9

3.2.1 DistaneVetor. . . 10

3.2.2 LinkState. . . 11

3.3 DefaultRouteComputation . . . 12

3.3.1 Algorithmsandmetris . . . 12

3.3.2 Dijkstraalgorithm . . . 13

3.4 ConnetivityandMenger'stheorem . . . 13

3.5 RedundantTrees . . . 14

3.6 Relatedwork . . . 16

3.6.1 ResilientRoutingLayer(RRL) . . . 16

3.6.2 IPfastrerouteframework . . . 18

3.6.3 Lasthop. . . 20

4 Method 21 4.1 ChoosingtheenvironmenttomodelIPRT . . . 21

4.2 Simulators . . . 23

4.2.1 J-sim . . . 23

5 IPRT Design 25 5.1 Construtionofthetrees. . . 25

5.1.1 Introduingtheredundanttreealgorithm . . . 25

5.1.2 Importantproperties . . . 27

5.1.3 Observations . . . 30

5.2 Routing . . . 30

5.2.1 EnablingIPRTtoo-existinafailure-freeenvironment . . . 30

5.2.4 r/bTables . . . 36

5.3 Reovery. . . 40

5.3.1 Enablingloalreovery . . . 40

5.3.2 Representingtheloalreoverypathorretion . . . 43

5.3.3 Qualitybit(Qbit) . . . 44

5.4 Forwarding . . . 45

5.4.1 Seletingbest FIBforstoringQbit . . . 47

6 IPRT Implementation 49 6.1 IPRTTreegenerator . . . 50

6.1.1 Creatingthegraphs . . . 51

6.1.2 Creatingtheredundanttrees . . . 51

6.1.3 CalulatingQbitinformation . . . 53

6.1.4 Results . . . 54

6.2 J-simimplementation . . . 54

6.2.1 Routingprotool . . . 55

6.2.2 Forwarding . . . 57

6.2.3 Utilities . . . 58

7 Design of simulation senarios 60 7.1 Network . . . 60

7.1.1 Topology . . . 60

7.1.2 Linkapaity . . . 61

7.1.3 Linkmetris . . . 62

7.2 Tra . . . 63

7.2.1 Transportlayerprotool . . . 63

7.2.2 Generatingtra. . . 64

7.3 Failuremodels . . . 65

7.4 Modeling re-onvergedsenarios . . . 66

7.5 Performingmeasurements . . . 67

8 Experiments 68 8.1 Experimentdesription . . . 68

8.1.1 Coverageandmodel veriation . . . 69

8.1.2 Path-length . . . 70

8.1.3 Throughputandloaddistribution . . . 71

8.1.4 Topologies. . . 73

8.2 Results. . . 76

8.2.1 Coverage . . . 76

8.2.2 Path-length . . . 77

8.2.3 Loaddistribution . . . 81

8.3 Disussion . . . 86

8.3.1 Coverage . . . 86

8.3.2 Path-length . . . 86

8.3.3 Loaddistribution . . . 87

8.3.4 QoS . . . 89

9.1 Futurework . . . 94

Bibliography 96

10APPENDIX A 99

Introdution

1.1 Motivation

Over the years, the role of Internet has shiftedfrom sienti use towards ating as a

key ontributor in both business and rereational servies. As servies onverge and

are aommodated by the Internet, the soiety depends inreasingly on the reliability

of omputernetworks. An examplemaybe drawn from the healthare industry where

newserviessuhasTelemediineand remotediagnostishasstringentrequirementson

network reliability asany failure may haveserious onsequenes. The versatilityof the

InternetProtool(IP)ombinedwiththepopularityandvastdeploymentoftheInternet

has lead to amigration of servies traditionally losely tied to speialized distribution

network. Teleommuniation servies are now being integrated in omputer networks

through VoIP servies and by adding IP apabilities to existing distribution networks

suh as foundin UMTSreleases4 and5. Furthermore,television and radio ompanies

are starting to use Internet as a distribution hannel. It appears that an inreasing

numberof ommuniationsystemswillbeusingInternetasadistributionhannel.

By moving serviesfrom their old tehnologial platforms and introduing them to

theInternet,newdemandsneedtobemet,oftenextendingbeyondoriginaldesigngoals.

Old Internet servies suh as e-mail and web browsing require moderate onnetivity,

whereas many of thenewly introdued servies requireamoreontinuous onnetivity.

Thisplaesahigherdemand onthenetworkin termsofavailabilityandreliability.

With the inreasing popularity and task diversity of the Internet, there is a steady

and signiant growthin the volume of data transported [2℄. Ina high-speednetwork,

a failure may render information obsolete or data lost if the network laks the ability

to quikly reroute tra. Some appliations rely on a robust paket delivery servie,

however, reliability is alwaysdesirable and sometimes required. Due to theamount of

serviesaommodatedbytheInternetitispossiblethatasinglenodeorlinkfailuremay

beofnegativeonsequene. Thus,thegrowingnumberofservies,travolumeandthe

ever-inreasingdependenyontheInternetmagniestheonsequenesofanetworkfailure

andstrengthentheneedofreliableoperation.

networks. Sprint'sIPbakbonewasanalyzedandresultsshowthat20perentageofthe

links had aMeanTime BetweenFailure(MTBF) of lessthan1day, and 70perentage

of the links had a MTBF of less than 10 days [3℄. The failures may originate from a

multitude of reasonsand have various saleand severity. Theymay beeither physial

orlogial,and arise from either externalorinternal auses. An exampleof anexternal

physial errorouldbeaableut,whileaninternallogialerrorouldbeausedbyan

erroneousonguration. Furthermore,notallerrorsourbyaidentbutareratherthe

resultofpreplannedservieevents,e.g.hardwareupgradesorlargeongurationhanges.

Studies as [4℄ and [5℄, show that the single most ommon ause for failure originate

from sheduledmaintenanee.g. upgrades,installation orongurationhanges. Other

signiantontributorstofailurewerepoweroutages,linkfailuresandhardware(router)

failures,and ombinedtheseunsheduledfailures ontributetoabout80% ofallfailure

situations. Inaddition,itisshownthatmostfailuresareshortlived.

Beause mostofthefailuresareshortlived,itseemstobeagood ideatoimplement

reoverymehanismsthatareabletodealwithallfailuresituationswithoutreonguring

thewholenetwork.Inaddition,suhmehanismsmayatasabuerprovidingmoretime

forthenetwork toproperlyaddressthefailurewhenitislong-lived.

Assuring a robust network, routing infrastruturehas been in fous for quite some

timeandisawidelyinvestigatedarea. Nevertheless,formerreportshavebeentoalarge

degree foused on onnetion-oriented networks. However, solutions for traditional IP

networks are not absent. Historially, one of the main goals of the DARPA Internet

Arhiteturewasthat ommuniation must be ableto ontinue despite lossof network

omponents. This was realized throughfate-sharing betweenthe ommuniating hosts

anddynami distributedinteriorgatewayprotools (IGP).IGPLinkState(LS) routing

protools,suhasOSPForIS-ISarethemostadopted IGP.LSroutingprotools relies

onaperiodioodingofatopologyinformationfromeahrouterinthenetwork. These

messagesarethen usedtoform aglobalviewofthetopologyat eahrouterand further

omputethenexthopforthetra.

WhenalinkornodefailureoursinatraditionalIPnetworkawideIPre-onvergene

isinitiated. Duringthisre-onvergeneallroutersinthenetworkaremadeawareofthe

new topologyand subsequently realizedin theroutingtable of all routers. During this

period there may arise inonsistenies where routers disagree on the paths of pakets

asa onsequeneofthe transition,from the old routingtable to thenew, that may be

asynhronousbetweentherouters. Thismayleadtomiroloops,asituationwhere some

tra is sent bak and fourth between two routers in the network. Thus paket drop

mayoureither throughongestiononlinks suering frommiroloops,depletedtime-

to-live in IP headers, orrouterlogi refusing to forwardtra arriving onunexpeted

inominginterfaes. Traditionallythere-onvergeneperiodhasbeenatime-onsuming

proessintheorderofseonds. ForatraditionalIPnetworkwithanLSroutingprotool

the duration needed for the network to return to aoherent state, i.e. reovery time,

is equalto thetime neededto detetaloal topologyhange, e.g. link-is-down, ood a

dierentstepstowardsreovery.

Therearetwowaystodetetfailuresinanetwork;eitheratthelowerlevelorthrough

exhangeofHELLOmessages. Link-leveldetetionisthefastermethodofthetwo,butit

isoflimiteduseasitonlydetetlinkfailures,i.e. thelinkmaybereportedworkingeven

iftherouterlogihasfailed. Thetwomethods omplementeah otherintermsof fault

detetiontimeandthusbothmethodareusedtoidentifyfailures. HELLOmessagesmay

detetbothlink andnode failures but itsfault detetion timeis bound by theHELLO

intervals.Thedetetiontimeanbereduedbyreduingtheintervaltime. Byusingboth

approahes,the averagefailure detetiontimemaybekeptassmallaspossiblewithout

introduingexessiveamountsofHELLOmessagestothenetwork. Neverthelessfailures

maybe utuating,i.e. last for only ashort period of time, and reporting a failure to

soonortofrequentlyanleadtorouteapsandstabilityissues[6℄.

Therehasbeenproposalstoreduetheresponsetimebyreduingthequeuingdelaysof

theLSPtraanduseoptimizedoodingmehanisms(iteRFC4222). Theomputation

timehas alsobeenaddressedwith optimizationsin thealgorithms usedto omputethe

new routing tables i.e. inremental routing table updates. However, even with these

optimizations, the IGP onvergene proess might prove too slow for the new Internet

servies,anditislikelythattherequirementforreoverytimemightbeinseveralorders

lessoftheseahievements. ThewideIPre-onvergeneisinherentlyslowbeauseitonly

respondstoafailureafteritisdetetedandrequireseveryrouterinthenetworktorespond

tothefailure. Inareentstudy[7℄itwasshownthatitwaspossibletoahievesub-seond

reovery time, in the range of 0.3 - 1 seond. However, this required arefully tuned

parameters; The performane were dependent on the number of nodesin the network,

the topology, the link propagation delays and, when inremental routingtable updates

areused,thenumberofprexesinthenetwork.

Inordertomeetthenewdemandsin reoverytimenewmethodsneedto beutilized.

Proativereoveryprovidesareoverystrategy whereall thealternativebakup routes

arepre-alulatedinadvaneofanypossiblefailure. Itallowsthefailuretobeaddressed

loally withouttheimmediate need toinform otherrouters ofthe failureand thuspro-

longingtheperiodavailableto performthe timeonsuming globalfailure signalingand

path alulations. This allowsthedisruptiontime to bereduedto thetime needed to

detetthefailureandinvokethereoveryrerouting,whihisonsistentwithatimeframe

oftensofmilliseonds.

IETFhaspresentedsuhproativereoverymehanismsintheIPFast-RerouteFrame-

work, where the reovery is based on single or multi-hop repair paths. The solutions

presentedin the framework are similar to MPLS Fast Reroutebut themehanismsfor

providing the bakup routes in pure IP networks are neessarily verydierent. In ad-

dition, there has been some work lately on Multi Topology(MT) routing. Where the

design hasbeenfoused onreatingvirtualreovery-topologiesupon whih the routing

protoolsould at. The main ideabeingthat should alink fail oneould hoose from

oneof thevirtual topologiesandtheir routingtables notontainingthe failed link and

reroutethetra aordingtotheseletedtopology.

fousedonprovidingsolutionsfor onnetion-orientednetworks thereare relativelyfew

mehanisms that may address reovery in onnetionless networks. The dierene of

onnetion-orientednetworks,andonnetionlessnetworks,i.e. onventionalIPnetworks

isinessenehowapathisrepresented. Inonnetion-orientednetworksthesourerouter

havefullontrolonthepathapaketwillfollowthroughthenetwork,whileonnetionless

networkssharetheresponsibilityofdiretingapakettoitsdestinationamongallrouters

in thenetwork. Thus,thereoveryshemesdevelopedforthetwokindsofnetworkswill

relyoninherentlydierentmehanisms.

Oneofthesolutionsthat hasbeendevelopedtobeappliabletoonnetion-oriented

networksistheredundanttree(RT)modelpresentedbyMedardet.al. [1℄. Themethod

hasbeenpresentedinonjuntionwithbothWDM[8 ℄andMPLS[9℄.

The main ideaof theRT method isto onstrut twodireted trees, namedred and

blue, in suh a way that in ase of a single node or link failure a soure node is still

onnetedto alloperationaldestinations througheither thered orthe blue tree. Thus,

if apair of red an blue trees are generated for eah soure node in the network, every

sourenodemayreah allother operationaldestinations in thenetwork in theeventof

single-failures.

1.2 Important ndings

InthisthesisIPRedundantTrees(IPRT),anewmethodforproviding IPfastreovery,

isintrodued. ItisbasedontheredundanttreeapproahpresentedbyMedardet.al[1℄,

extendedtoprovidearesoureeientwaytopopulatethebakupForwardInformation

Base (FIB) and furthermore, the mehanisms needed to utilize this information in the

forwardingproedure.

TheoreofIPRTisther/bTables,thereoveryFIBsreatedbyaproeduretoextrat

onlyessentialroutesfromredundanttreeswhileretainingthefuntionalityandproperties

of thetrees. The proedure allowsanumberofFIBs equalto twotimes thenumberof

nodesinthenetworktobereduedtoaonstantadditionalstateequaltotwoadditional

FIBsateahnode. Thus,itreduesthefootprintoftheRTmethodintheFIBandmay

allowtheper-paketsignalingtoberesoureeetive.

Furthermore,anadditionaldata-struturenamedQbitisintroduedtosupportloal

reoveryin aonnetionlessenvironment. This isadata-struture that may be merged

withtheFIBsorbeself-ontainedasanadditiontotheFIBs. Itin additionto support

loal reoveryQbitbut may alsoallowthe forwardingproedure to hoose theshortest

reoverypath ifit is available. However, at this point theQoSproperties ofQbit is of

limiteduseasatheoretialgainisprovenbuttheeetsobservedinsimulationsprovide

onlyminimalgain.

The rest of thethesis is organizedin the followingmanner; Inthe bakgroundhapter

general reovery and routing strategies are introdued along with related work. The

main ontributions are found in the hapter named IPRT Design. In this hapter all

nessesarymodiationsanddesignhoisesneededforRTtobeappliabletoonventional

IP networks are identied and aounted for. Furthermore, the IPRT tree generator

and theextensions to theJ-sim network simulator neededin order to simulate IPRT is

desribedintheimplementationhapter. Inthesubsequenthapter,thenetworkmodels

key harateristis are identied and alternative methods are aounted for. This is

followed by a hapter where the experiments are desribed, the results obtained from

simulatingdierentIPRTenablednetworksareshown,andsubsequently,theresultsare

analyzed. Inthelast haptertheonlusionsarepresentedalongwithfuturework.

Goals

The prinipal goal for the thesis is to researh appliability of the RTmethod to on-

ventional IPnetworks. Weset threegoalsthat needto bereahediftheredundanttree

reoverymehanismistobeappliabletoonnetionlessIPnetworks:

1. TheIPRTmehanismneedstobeabletoo-existwithnormalroutingprotoolsin

timesoffailure-freeoperation.

2. The method needs to be able to support loal reoveryin a onnetionlessenvi-

ronment. This is beause the use of global reovery would generally be too slow

to ounter anyfailurebeforeIP re-onvergenenishes,andthusvoidtheuseof a

reoverymehanism.

3. The method needsto provideamehanismforpath representation, i.e. represent

the redundant trees. This path representation needs to be unaeted of the re-

onvergenesubsequenttoafailure.

Another goal of the thesis is investigate if the IPRT method may be applied in a

resoureeientway. Theoriginal RTmethod needs anumberof trees equalto twie

thenumberofnodesin anetworkto beableto providepreplannedreovery. Memoryis

averyexpensiveresoureintheroutersandthusitisagoaltotrytoreduethememory

footprintofthereoverymethod.

Furthermore,ifitanbeproventhat theRTmethodmaybeappliedin onventional

IP networks,asubgoalofthisthesisisto investigatetheperformaneoftheredundant

trees and see how the method ompares to alternative solutions. I.e. investigate the

lengthofrepairpathsandhowthereoverytraaetsthetraloaddistributionin

anetworkduring failure.

Bakground

Inthishapter,generalreoveryandroutingstrategiesareintroduedalongwithrelated

work. The dierent methods and approahes to ahieve self-healing networks are pre-

sentedand lassied. Furthermore,a short overviewof the IP routing algorithms, and

howtheymaybeonguredoralteredtoprovideabetterqualityofservie,isgiven. In

addition, the original Redundant Tree (RT) algorithm is presentedas well asMenger's

theorem, whih forms the foundation for the qualities found in the RT method. Re-

latedworkisalsopresented,introduingResilientRoutingLayersandtheIPfastreroute

framework.

3.1 Classiation of reovery mehanisms

There aremany dierentmethods and approahesto ahieveself-healingnetworks, but

theyareallgenerallylassiedbythreedierentriteria.

Criterion Shemes

Reovery

Protetion

Restoration

Computation

Distributed

Centralized

Sope

Global

Loal

Table3.1: Classiation

Themainriterion,lassifyingthedierentreoverymehanisms,isharaterizedby

atwhatstageareoveryisinitialized. Protetionshemesarebasedontheideaofhaving

pre-alulatedalternativepaths in advane of any failure, whereas restoration shemes

only alulate newpaths after afailure has ourred. As aresult, restoration methods

generally require more time to respond to a failure situation, onsequently adding to

registered in the network in advane.Thus, protetion shemes add to the state infor-

mation required in the nodes. Moreover, it is a higher omputational ost assoiated

withprotetionshemesbeauseofthealulationofalternativepathsregardlessoffail-

ures. With bothapproahesitmightbeneessaryto reserveadditionalresouresin the

network,e.g. bandwith. Theoretially, restoration may beable to avoidto reservethe

resouresin advane of afailure and rather adeptto spesi topologyafter the failure

hashappened. Howeverthenormalapproahforbothmethodsistohavetheadditional

resouresavailable in advane of afailure, e.g. byoverprovisioningrouter and link a-

paity. Consequently, thehoie betweenprotetionandrestorationshemes beomes a

tradeobetweenrouterstate,omputation,andreoveryspeed.

Theomputationofroutesanbeahievedeitherbyaentralizedshemeorbyadis-

tributedsheme. Bothmethodsshould oerthesameamountofonnetionsthatould

berestored. Centralizedshemesrelyonamastertoalulatetherouteforeveryrouter

in thenetwork,andallowforadediatedserver,andthus reduetherequiredomputa-

tionsin nodes. Themastermust maintainafullglobal knowledgeof thenetwork. This

knowledgeofthenetworktopologyandavailableresouresallowsforomplexalgorithms

tobedeployedandmayprovideanadvantageintermsofeientuseofresoures. How-

ever,theentralizedshemehasanimportantweakness;ifthemaster serverfails orget

speratedfrompartsofthenetwork-thewholeshememayfail. Inadditionthissolution

requirestheservertoreeiveperiodiandtimelyinformationonthepresenttopologyto

beabletoprodueaurateandorretresults. Distributedshemesaremoreadaptable

to failures in the network, and allowfor greater salability than a entralized sheme.

Themajordrawbakisthatdistributed shemesaremoreomplex. Distributedshemes

need to exhangemessagesin orderto havesuientinformation to oordinate there-

overy,and theonvergingof this informationneedsto beproven toensure stabilityin

thesystem. Aswithentralizedshemes, thedistributed approahmayprodueinferior

or inorret results if the deisions are based on inonsistent or stale information. In

addition,distributed systemaddstotheworkloadimposed onthenodes.

Bothentralizedanddistributedshemesmaybeusedinonjuntionwitheitherpro-

tetionorrestorationshemes. However,eveninallombinationarepossible,entralized

isoftenusedtogheterwithprotetionanddistributed areusedwithrestoration. Inen-

tralizedshemeseveryenquirytothemasterintrodueapotentialdelayassoiatedwith

retrievingtheinformation. Thisanaettheinitial setup-timeofaonnetionwhen a

protetionshemeisused, e.g. ifspeipathsare tobesignaledto thenodesfromthe

ingress node. Whenused with restorationshemesthe potential delay addsdiretly to

thetotalreoverytime,andthustheombinationislesssuitedforreovery. Distributed

shemes an be used in onjuntion with either protetion or restoration shemes. As

withentralizedshemesthereisapotentialdelaytogettheinformationassoiatedwith

distributed shemes,butbeauseofitsloal naturethedelayisofalesserdegree.

The last riteriondivides theshemes bythesopeof thereovery. Global reovery

requires the ingress node to havethe main responsibilityfor reoveryoperations, while

seondary path may or may not share nodes or links with the primary path. Global

reoveryutilizespathrerouting,whihroughlyimpliestearingdowntheoriginalprimary

pathandthenreestablishanewend-to-endroute. Thismethodhasaglobalnaturewhih

letsitspreadthealternativepathsovertheentirenetwork,andallowsforabetterresoure

utilization than loal reovery. Loal reoverylets the fault behandled by thenearest

upstream node of the faulty node or link. The onnetion is reestablished by routing

aroundaneighbornodeorlinktoavoidthenodeorlink presumed faulty. Furthermore,

link rerouting does not need to utilize signaling to the ingress node, and thus has the

potentialtooperateonasmallertimeframethanglobalreovery.

3.2 IP Routing

InatraditionalIPnetworkpaketsgenerallyneedtotraversemultiplenetworkelements

to reah the destination. Toaommodatethis movement,routers usea method alled

store-and-forwardtotransportthepakettothedestination. Inaddition,theresponsi-

bility ofdeterminingthepath isdistributed betweenalltheroutersin thenetwork. I.e.

whenapakettravelsfrom itssouretowardsthedestination, eahrouterloally deter-

minesthenext-hopofapaketandforwardsitaordingly. Thisdeisionisdoneforevery

paketsine thebest route mayhavehangedsinethepreviouspaket wasforwarded.

Tobeable toforwardpaketseah routermaintainsaforwardinformation base (FIB),

alsoreferredto asaroutingtable. Eah FIBontainsthenext-hopdestinationforeah

reahableIP prex in thenetwork. Routing isthe atof onstrutingand maintaining

theFIB,whileforwardingistheatofusingtheFIBtodeideandsubsequentlytransmit

thepakettowardsitsnexthop.

Therearetwomainwaystoprovideroutingfuntionalityinanetwork;troughmanual

ongurationorthroughanalgorithmiapproah. Insmallandsimplenetworks, itmay

bedesirabletoonstrutthepathsmanually. Thisstatiandentralizedapproahworks

wellin environmentswherethenetworktra ispreditableandthetopologyissimple.

Insmallnetworksthepathsmayberelativelyeasyto designandunderstand. However,

the method does not sale well as the FIBs may beome umbersome to maintain by

hand, as networks growin both size and omplexity, speially sine all hanges in the

networkortrapatternsneedtobeaddressedmanually. Todaymostroutingprotools

are automated through routingalgorithms whih are distributed and operate in a dy-

nami manner. Theprotoolsongure andadapt theFIBdynamially asdestinations

areadvertisedordisovered,andarethusmorerobustthanstatirouting. Inaddition,

dynami routingalgorithmsmayhavean adaptiveproperty where routingdeisionsre-

et hangesin otheraspetsthantopologyhangessuhashangesin tra patterns.

However,somestatiandentralizedaspetsarestillmaintainedtoaommodatetra

engineering.

Generally, alldynamiroutingprotoolsneedto performsomebasioperation. One

oftheseistoobservetheloalnetworkparameters. Theneededparametersdierbetween

theroutingprotools,but typiallyarouterneedsto advertiseitspreseneanddisover

it'sadjaentnode,e.g. ifthenodeisupordown. Othertypialnetworkparametersmay

inlude link utilization or link delay. The measurement may be ontinuous, triggered

or periodi depending on the desired resolution and response time of the metris and

states. The seond operationinvolvesdisseminationof this information throughoutthe

networkto leteahrouterreate aviewofthetopologyand otherdesiredpropertiesof

thenetwork. Theexatmethodused forarouterto informallroutersof it'sloalview

ofthetopologyisdependentoftheroutingprotool,butisoftenahievedthroughsome

periodiortriggeredreliableooding. Thisinformationisstoredateahrouter,typially

if a dediated data struture other than the FIB is used. Another operation involves

the route omputation. Based on the information gathered and the routing algorithm

used, the routers generate paths with minimum ost towards eah possible destination

(see setion3.3.1). Finally, ifneeded, therouters adapt the FIBto reet any hanges

disoveredfromthelastdisseminationproess.

Furthermorethedynamiroutingprotoolsaredividedintooneoftwomainfamilies

of routing protools; distane vetor (DV) and link state(LS). Of these twofamilies of

routingprotoolsusuallyLSisusedinonventional IPnetworks.

3.2.1 Distane Vetor

DistaneVetorroutingprotoolsrelyonthedistributedBellman-Fordalgorithmandthe

exhangeofasmallamountofinformation. RoutersrunningaDVprotoolareexpeted

tomaintainavetorofeahreahableIP-prexinthenetworkandtheirassoiatedost

andnext-hop. Furthermore,eah routermustmeasureitsloalnetworkparametersand

update their vetors aordingly. The ost is often a measurement of hop-ount, but

DV allows it to take on any form and there are implementations using other metris

than hopount[10℄. Todisseminate theinformation eah router sends theirvetorsto

their adjaent routers whom in turn heks the reeived vetorsagainst their own and

updates it if neessary. This tehnique gives theDV family of protools aloal view

ofthetopologywhere nonodeholdstheompleteviewofthetopology. Inaddition,the

onvergenetimebeomesdiretlyonnetedto thenetworkdiameter andthetimingof

theperiodimessages.

Theloal propertymakesDVprotoolssensitivetoomponentfailuresandinlined

to populating the routing tables with old and invalid route information. Consider a

networkwithanodeAand B,where Aisprovidingtheonlylink towardsasubnetwork

and B is a diret neighborof node A as shown in Figure 3.1. Given a failure on the

link towardsthesubnetwork,node Awould updateit's routingtable indiatingnolink

towardsthesubnetwork. NowsupposenodeBsendsoutitsvetorbeforeA.Awouldthen

inorretlylearnthatBhasaroutetothesubnetworkandupdate it'stable aordingly.

Thiswouldresultinaloopwheretheostofreahingtheunreahablesub-networkwould

inreasetowardsinnity.

Several proposals havebeenproposed to ounter theount-to-innity problem i.e.

results in a max-hop ount on the paths, and thus imposes a restrition on the max-

diameter of a network. Furthermore split-horizon provides with rules that minimizes

thehanesofloopingproblems,butonlypartiallysolvestheproblem. Overalltheshort-

omingmakesDV onlyusableforsmallnetworks.

3.2.2 Link State

In LinkState (LS) routingprotools eah routerin thenetwork is expeted to at least

identifyitsadjaentnodesanddistributethisinformationperiodiallyortriggeredtoall

other nodesin thenetwork. Theinformation isusually disseminated throughareliable

ooding mehanismproviding aguaranteed deliveryto all nodes. Thenodesstore this

informationinaLinkStateDatabase(LSDB).ThereliabledeliveryofmessagesandLSDB

provideallnodesin the network with asynhronizedglobalviewof thewhole network.

ThisenablesLSprotoolstoperformmoreomplexroutingalulations,makingiteasier

to alulatepaths thatare moresophistiated. Inaddition, alltheroutersomputethe

newpathsinparallel.

Whenafailureoursthismaytriggeranodetosendoutaprotooldataunit(PDU),

i.e. anIPpaketontainingLSroutinginformation,reetingthenewtopology. Although

miro-loopsmayourwhentheLSDBoftwonodesarenotsynhronizedtheyareshort

additionLSprotoolsprovidessolutionsforhierarhiroutingwhereanetworkaredivided

intoseveralsmallerzones,andthustheonvergenetimemayberedued.

ThemajordrawbakforLSprotoolsistheamountofCPUtimeneededtoompute

theroutingtables. Updatesarereeivedonaregularbasisandthusroutersspendmuh

time reomputing their FIB. However, muh work has beendone in this area, suh as

inrementalrouteomputationsandoptimizedalgorithms.

3.3 Default Route Computation

Inmanyoftodaysroutingprotoolstheshortest-pathlassofalgorithmsformsthefoun-

dation for route omputation. This lass of algorithms allows eah node to hoose the

pathsofminimumdistane basedontheroutinginformationolleted. Therearemany

implementationsonndingtheshortest-pathwherethemostknownaretheDijkstraand

theBellman-Fordalgorithms. Dijkstrais oftenusedwith LSprotools, e.g. OSPF [12℄,

whileBellman-FordiswidelyusedinDV protools,e.g. RIP [11℄.

3.3.1 Algorithms and metris

Someoftheshortest-pathalgorithmsmaybeusedinweightedgraphsandallowforboth

dynami and stati adaptationto hanges in thenetwork properties, e.g. may be used

fortraengineering. Aroutermayknowofseveraladjaentpathstoadestination,and

sometimes theshortest path does notalwaysutilize the network resouresin themost

eientway. A ommon approah to ahieveahigherquality ofservie in the routing

protools,isto assoiateaostwith eah linkin thenetworkandlettheroutingprool

omputetheshortestpathtoeahdestinationusingtheseostaslengthofthelink. The

ostofalinkisoftenderivedfromoneormoremetris. Themetrisusedaredependent

on the implementation of the routing protool but usually metrisas number of hops,

delay, available bandwidth, tra and reliability are used. An example may be found

in OSPF [13℄ where anetworkengineer maymanually assign aost toeah link in the

network. There are also possibilities to letthe routing protool automatily adapt the

ostas found in earlyARPAnet [14℄. However,in pratie,metrisare mostlyassigned

manuallyasautomatedassignmentmayindue routeapsorpooroverall performane.

Common metris

The mostommon routingmetriis path-length. This metriis often measuredin the

number of hops needed to reah the destination. However, it is also possible for net-

workadministratorsto assign weightstoeahlink in the network,where path-lengthis

measuredinthetotalweightofapath.

Anotherommonroutemetriisdelay. Thismeasuresthetimerequiredforapaket

totraversethepathfromsouretodestination. Delayisaetedbymanyaspetsinthe

aspetsofapath,itis aommonlyusedandveryusefulmetri.

Bandwidth isalsoausefulmetriasitmaytelltheavailableapaityof alink. E.g.

when onstruting paths a 100-Mbps Ethernet link would be preferable overan ISDN

line. However, if the faster link has a high load preferred seletion might be reversed

as a result of the load and time needed to aess the link. Thus, it may be useful to

measure available bandwidthinsteadof thetotallink apaity. Howeverthis requires a

moreativemeasurement, e.g. trough probing, andthe measuredresultsbeomesstale

after arelativelyshort period. Therefore, available bandwidthit is notwidely adapted

asametri,and usually over-provisioningare usedasaguarantee againstongestion.

Furthermore, there are ongoing researh to adept the weights on links to enhane the

networks ability to honorinreasing demands in tra and thus provide large parts of

thepotentialgainsoftraenginering throughdynamilyadapting weightonlinks[15℄.

3.3.2 Dijkstra algorithm

TheDijkstraalgorithm wasrstintroduedin 1959[12℄. It allowsforomputing short-

est path from a single soure to multiple destinations. In addition it may be used in

onjuntionwithnon-negativeweightedgraphs.

Thereareseveralimplementationsofthisalgorithm. Aommonimplementationisto

makethealgorithmndtheshortestpathfromasoureSto anyothernodein agraph

with nonnegative ars. This is doneby iterativelygrowingthe set of nodes ofwhih it

alreadyknowtheshortestpath. Ateahstepofthealgorithm,theunknownvertexwith

thesmallestdistaneis addedto thesetofknownverties. Thisvertex'sneighborsthen

gettheir distaneupdatedto equalthedistaneof thenode beingtreatedplusthelink

to eah neighborweight,but onlyifthis weightislowerthan theweightalready known

attheneighborverties. Thealgorithmthenloopsandproessthenextvertexnotinthe

knownset untilallareknown. TherunningtimeofthisalgorithmisO(n

2

).

3.4 Connetivity and Menger's theorem

Informally,agraphis anite setof vertiesonnetedbylinks allededges. Agraphis

onnetedifthereisapathonnetingeverypairofverties,andfurthermoretwoverties

areadjaentiftheyareonnetedbyasingleedge.

At minimum, the network needs to be link-redundant (two-edge onneted) if one

wantsto reoverfrom alink failure, andnode-redundant(two-vertexonneted) if one

wants to reover from a node failure; E.g. for a graph to be deemed link- or edge-

redundant,thegraphneedstobeonnetedafterremovingasinglegivenedgeorvertex,

respetively. Artiulationpoint,orsinglepointoffailure,isapointinthenetworkwhere

afailurewoulddisonnettwopartsofthenetwork. Failureinartiulationpointsannot

beremediedbyanyoftheprotetionorreoveryshemes.

Let G=(V,E) be a graph and A,B

∈

minimumnumberofvertiesneededtoberemovedtoseparateAfromBinGisequalto

themaximumnumberofnode-disjointA

→

neededto beremovedto separate Afrom Bin G isequalthethe maximumnumberof

edge-disjointA

→

Thisgivesusthatforanytwovertiesinavertexoredgeredundantgraphthereexists

atleastapairofvertexoredgedisjointpathsrespetively.

3.5 Redundant Trees

Theredundanttree(RT)modelpresentedbyMedardet.al. [1℄isapre-plannedprotetion

sheme for global reovery. The method is appliableto onnetion-orientednetworks,

and hasbeenpresentedin onjuntion with both WDM[8 ℄and MPLS[9℄. Furthermore,

RT utilizes aentralized approah for omputation of the reoverypaths, and may be

usedtoprotetagainstbothnodeandlinkfailures.

The main ideaof theRTmethod isto onstrut twodireted trees, namedred and

blue, in suh a way that in ase of a single node or link failure a soure node is still

onnetedto alloperationaldestinations througheither thered orthe blue tree. Thus,

if apair of red an blue trees are generated for eah soure node in the network, every

sourenodemayreah allother operationaldestinations in thenetwork in theeventof

single-failures.

TheoneptisshowninFigure3.2. Thisgureshowsativetwo-vertieonneted

network,andapairofredandbluetreeswhereAistherootnode. Theredundanttrees

in this exampleareonstruted tobeable towithstand asinglenode failure. If in this

example,nodeFwere tofail, theblue tree would onlyprovideonnetivity to nodesC

and D. However,withuse ofthe redtreenodeA would beableto reah theremaining

nodes,B,Eand G,and alsoprovideaseondoptiontoreah nodeD.Similarly,ifnode

Dweretofail, boththeredandblue treeswouldprovideonnetivityfornodeAtothe

remainingoperationalnodes.

Thetreesareonstrutedbygraduallygrowingtheonnetednodesfromthesoure

nodeS.InformallythisisdonebyonstrutingaylipathfromthesourenodeS. By

followingthepathinoppositediretions,onediretionforeahoftheredand bluetree,

thevertiesareaddedtotherespetivetree. Thelastlink intheyle,i.e. thelink that

leadsbak toS when followingtheyli path, isnotinluded in either tree. If notall

vertiesareinludedintheyletheRTmethodonstrutsanarh;apaththatstartand

endontheyle. Inthesamefashionastheylipaththearhistraversedin opposite

diretions,andappendedtotheredandbluetreein suhawaythat thelastlink onthe

pathis notinludedin thetree. Ifthere isstill nodesthatare notinluded, newarhes

areonstrutedin thesameway, startingon anodeinludedin thetrees,followingone

ormorenodesnotinludedandendingonanothernodealreadyinluded. Thealgorithm

TheRTapproahprovidessomemethodsforoptimizingtheperformane. Byhoosing

theyleand thearhesin dierentwaysthe pathsusedforreoverymaybealteredto

betterahieveadesiredbehavior.InthealgorithmspresentedintheoriginalRTartile[1℄,

the treesare grown in anarbitrary way. However, thereis an ongoingresearhby Xue

et.al [16℄[17℄to enablethemethodto makeinformeddeisionswhenseletingtheyle

and arhes, e.g. to minimizedelayor ostof reoverypaths. Inaddition, the researh

alsofousonoptimizetherun-timeoftheRTalgorithm.

If theredundanttreemodelisto beused toprotetagainstnodeorlink failuresthe

networktopologyneedstobenode-orlink-redundant,respetively.

The redundant tree approah is mainly foused on global reoveryin networks op-

erating in a onnetion-oriented manner. In [16℄ it is proposed to let one of the trees

representtheworkingpath, e.g. lettra followoneofthe treeswhenthe network is

notexperiening failures. Inaseof afailure, theaeted owsorpathsmaybemoved

totheotherthreebythesourenode.

3.6.1 Resilient Routing Layer (RRL)

TheResilientRoutingLayermodelpresentedin[18℄isbasedonaprotetionshemewith

pre-planned pathsforbothglobaland loal reovery. Themethod utilizesaentralized

omputation of the alternativepaths in the implementing phaseof the network,and is

usedforprotetionagainstbothnodeand linkfailure.

TheoreofRRListheutilizationofasimpleglobalabstrationreferredtoasrouting

layers. Eahlayerisasubsetof thenetworktopology,whihontainsallnodesbutonly

someofthelinksin thenetwork. Asafenodeisanodethatonlyhasonelinkinagiven

layer,and thatlayerisdened asthesafelayerofthenode. Everynodeinthenetwork,

ifnotoriginallydeemedanartiulationpointshouldbesafeinat leastonelayer.

Figure3.3: Anexamplenetwork. B)andC)representthelayersbasedonA)

two-vertex onneted or two-link onneted, respetively. In ontrast to RT, the RRL

method an still be utilized without modiations even if the network does not meet

these requirements, butthis leadsto asituationwhere RRL annotguaranteethe fault

tolerane for every node in the network. In addition, there are some requirements to

theoperationofthenetwork. Inonnetion-orientednetworks,eahnewlayerrequiresa

newsetof pathstobesignaled. Foraonnetionlessnetwork,thepaketheadershould

identify the urrent valid layer. In a failure situation, only pakets on route through

thefailed nodeor link should havetheirheaders updatedto avalid layer. Whenglobal

reoveryisused,theingressnodeshouldknowoftheentirerouteofthetraorpaket,

andwhat pathsareaetedbythefailure. Inloal reovery,theserequirementsarenot

neessaryasthenodewillknowifanyoftheadjaentlinksorneighbornodesaredown.

Inaddition,therestofthenetworkwill beroutedaordingtothefulltopology.

TheRRLshemelaysnoboundariesonhowtoproduethelayers. Howeverageneral

approahistoreduethenumberoflayersbymakingasmanynodesaspossiblesafeinthe

rstlayer,andfurthermorekeeptrakofartiulationpointsandsafenodes-andproess

the nodes by removing all adjaent links of a node but one. The nodes are proessed

untilallaresafe,i.e. tothepointwhenthegraphwill beomedisonnetedbyremoving

anotherlink. Thus, allremainingnodes havebeomeartiulationpoints. Subsequently,

the next layer is omputed, where the fous is to make nodes that were not safe or

originallydeemed artiulationpointssafe. Toattainmoreequalroutingperformanein

the dierent layers, a post-proessing of the layers is performed, where the goal is to

equalizethenumberofsafenodesineahlayer.

RRL oers two possibilities for optimizing the reovery topology. First, hoosing

whihnodesto besafein agiven layeranbe usedto reahadesired behavior. When

thenumberofsafenodesisreduedinasafelayer,morelinkswillbefreedtobeutilized

in thesame layer, and thus the average reoverypath-length is redued. This may be

usedinordertoreduethenumberofsafenodesinasafelayerofanodethatisexpeted

to fail often. Seond, RRL oers freedom in the number of layers that is to be used.

Withmorelayers,lesssafenodesmustresidueineahlayerandthusmorelinksarefreed

leadingtoaredutionintheaveragereoverypath-length.

RRL usesthreeimportantobservationswhenprotetingagainstnodefailures. First,

when a node is in a safelayer, it will notexperiene any transit tra. This leads to

the seond observation; wheneverasafelayerof a failed nodeis used, allnodes exept

the failed node areunaeted bythe failure. The third observation is that whenever a

node has failed all tra to that node is lost in any irumstane. Forlink failures, a

somewhatdierentapproahisneeded. Generally,asafelayerforalink isthesafelayer

ofadownstreamnoden. Thisruledoesnotomplyifthenaldestinationisnitselfand

thefailedlinkistheleaflinkofnoden. Tomendthis,oneantrytousethesafelayerof

thedetetingnode,but onlyiftheleaf link isunaeted. Ifthis fails, thenalsolution

is to usethedeteting nodesown safelayer,but deet thetra to anotherlink than

theleaflink. Thiswouldguaranteethetratoavoidthefailed link.

InternetEngineeringTaskFore(IETF)isastandardizationbodythatontributestothe

engineering and evolution of Internet tehnologies. Fast reoveryis animportant issue

in theInternet,and theRoutingArea Working Group(rtgwg), aworkinggroupwithin

IETF,isurrentlymappingtehnologiesandworkingonaframeworkforIP fastreroute

(IPFRR)[19℄.

The main goal in IPFRR is to provide a framework for mehanisms that protet

againstlink ornode failure in onnetionlessnetworks. The repairpaths should belo-

allydetermined,and furthermore,themehanismsshouldfousonsolvingfailuresthat

would requiremulti-hop repair paths. There are also some strongrequirementson the

funtionalityofthemehanismsdevelopedwiththisframework. Themehanismsshould

not impose anyonstraintson the network topology orassigned link ost. In addition

it should neverperformworse thanexisting router onvergene tehniques and provide

o-existenewithnon-IPfastrerouteapableroutersin thenetwork.

Repairpaths

Thereare severalsolutionsforprovidingrepairpathsin IPnetworks. InIPfastreroute

frameworktherearementionedthreegeneralways;EqualCostMultiPath(ECMP),loop

freealternatepathsandmulti-hoprepairpaths.

ECMPisgenerallyonsideredoneofthesimplerapproahesto providerepairpaths.

It is a routing tehnique originally developed for load balaning of the tra among

multiple equal ost paths. In this sheme, the router keeps trak of paths towards a

destinationwheretheostforeahalternativepathareequal. Thegatheredinformation

may subsequently be used to disperse the tra bound for aspei destination over

more links. This mehanism may also be used in a reoverysituation where one may

routealltraoverthepathsunaetedbythefailure. Thissolutionisverysimpleand

easy to use as it is ommon for networks to have ECMP shemes deployed. However,

the overage forthis solutionis not verygood beause equalostpaths are notalways

available.

To expand the overage of ECMP, loop-free alternate paths may be used. This is

a tehnique for rerouting pakets where the adjaent nodes have a path towards the

destinationthatisunaetedbythefailure. Generally,aloopfreealternatepathrequires

allthenodesinthenetworktoomputetheshortestpathtreesoftheirneighbors. Then,

for eah possible adjaentnodeor link failure, eah node uses theshortest path threes

to nd whih of the neighbor nodes that may havean unaeted path for all possible

destinations. The next-hop reovery neighbors are seleted in suh a way that loops

in thenetwork are avoided. Inaddition, thesheme proposes several optimizations on

theomputationoftheneighborshortestpathtreesandreoverypaths. This tehnique

extends the overage over the ECMP sheme but as ECMP, it does not provide full

overage. It isantiipated that ECMP and theloop-freealternate paths ombined an

provideabout80%overage[20℄[19℄,buttheexatperentagewilldependonthenetwork

providesthemostomplexprotetionagainst failure, but in return,it mayprovide full

overage.Inafailuresituationitmaybeneessarytoreroutethetraseveralhopsaway

fromthefailurebeforeanodewho'spathisunaetedbythefailureisfound. Multi-hop

repairpathsmayfurtherbelassiedintotwoategoriesdependingonwhatmehanisms

areneededtorepresentthereoverypaths. Furthermore,theapproahesarealsodivided

bythesignalingproedureneededtoguidethepaketalongtheseletedpaths.

Pre-omputed FIB

Withpre-omputedFIB,oneormorealternativeFIBsarepre-omputedinallrouters. In

afailuresituationthereoveryFIBareusedtoforwardIPpaket. Therearetwowaysof

signalingwhentohangetothealternativeFIB;1)It ispossiblefortherouterstoswith

to the alternative FIB by performing logial heks. If a paket arrives at an invalid

interfae,theroutermayforwardthis paket bythealternativeFIB.2)It ispossibleto

markeahindividualpaketandletthemarkedpaketindiatewhat FIBto use.

This solutionisusedin theRRL method.

Tunneling

Aseriesoftunnelingbasedapproaheshavebeenproposedin[19℄. Whatkindoftunnels

aretobeused,arenotdened,butIP-in-IPdesribedin[21℄isaommontehniquewhere

IP pakets are enapsulated in the payload of another IP paket where the destination

addressissetattheendofthetunnel. Attheendofthetunnel,thepayloadisextrated

andforwardedasusualtowardsthedestination. Oneoftheadvantagesoftunnelsisthat

they may be utilized without any hanges to the FIB, but as with soure routing the

workloadimposed onthenodesin thenetworkmaybeonsiderable.

In both IPv4 and IPv6, it is possible to support soure routing. This is a method

where the soure of an Internet datagram supply the routing information to be used

by the intermediatenodes in the forwarding proess. IPv4has a eld for strit soure

routingthattheingressnodeanuseto speify apathbasedonpre-omputedreovery

paths[22℄. However,thisshemeimposesaonsiderableworkloadonthenodes,asevery

router alongthereoverypathneeds to rewriteorupdate theIP header. Furthermore,

the solution may interfere with the ahieved throughput as the header size grows and

lessofthemaximumtransportationunit (MTU), i.e. thelargestallowedIPpaketsize,

is available for atual data. Inaddition, the IP header allowsthis eld to appear only

onein adatagram,and ismeantto beused bytherealsoureofthetra. Thus,the

methodmayforetheingressnodeto hekifapathhasbeenspeiedandhekifthe

speiedpathis violatedby addingthereoverypath, ifthisannot beguaranteedthe

datagramannotbedelivered,orthepaketneedstobetunneled.

The TUNNELS method [23℄ tunnels the tra around the failure terminating the

tunnelatanintermediatenode. Whenthepaketarrivesattheothersideofthefailure

it may be forwardedasthoughit had traversed thefailed link ornode. Nosignalingis

inaseparatedatastruture. Thisenablestheshemetonotaetthesizeorstrutureof

theFIB.Themethod maybeusedtoomputereoverypathsforeverypossiblefailure,

aslong asthe ost dened on the links are notasymmetri. When asymmetri ost is

used,100%overagemaynotbepossible.

Not-via [24℄is somewhat similar to the TUNNELS approah. Eah omponentin

thenetwork,i.e. node, interfaeof nodes andlinks, isassigned aspeial addressalled

the not-via address of a omponent. The nodes in the network broadast the not-via

addresses,i.e. eahnodebroadasttheaddressesofitsomponents. Inafailuresituation

thetraistunneled,asin[23℄,totheappropriatenot-viaaddressinsuhafashionthat

it avoidsthe not-via omponent. Apparently, this method is able to repairall possible

failures.

3.6.3 Last hop

Mostshemesaddressingbothlinkandnodefailuresneedtodealwiththelast-hopprob-

lem. The last-hopproblem arises when the node immediate upstream of the failure

isthe last-hopnode before reahing thedestinationaddress. Inthesesituations, it may

beimpossiblefor the node initiatingthe reoveryproedure to determineif the failure

originatefromanode-failureoralink-failure. However,thetrashouldbetriedreov-

eredone asthere is ahane that thenode is operational. In these situations, it may

be neessaryfor the reovery mehanism to distinguish between node and link failure.

This isbeauseif thefailure isatually anode-failureand it istreatedasalink-failure

itmayreate loopsin thenetwork. E.g. ifareoveryshemeweretosolvethelast-hop

problem bysendingtheinvolvedpaketstoanotherofthedestinationsneighbors,with-

out informing that it was tryingto solve the last-hopproblem and the failure was a

node-failure,thereipientnodewouldrepeattheproedure-possiblyleadingtolooping

ofthereoveredtra.

Method

InthishapterthemedhodandenvironmentusedtorealizeamodeloftheIPRTmethod

ispresented.

4.1 Choosing the environment to model IPRT

The use of models gives agreat freedom in the networks available for experimentation

as any real or imagined network may be freely modeled. It grants the opportunity to

freely experiment with ongurations on existing networks. In this way models may

aommodate for experimentingwith bothsenariosand ongurations that mightnot

have been possible in other irumstanes. For example by providing an environment

wherenetworktehnologiesmaybetestedwithoutinduingdisruptioninanoperational

ommerialnetwork.

Therearethreegeneralapproahestoonsiderwhenmodelinganewnetworkprotool.

Theutilization ofoneof theseapproahesshould notexludetheuse oftheotherones,

asthey mayomplementeah other. Theapproahesdierin how easily available the

models are, the results that may be obtained and the exibility they oer. The three

approahesarelistedbelow.

1. Mathematialanalysis

2. Testbedsandprototypes

3. Simulations

Theadvantageofusingamathematialmodelisthat theenvironmentthisapproah

provides, may be used to quikly produe results. This is espeially true in situations

where the problem area onsists of a ommon problem where a formula oralulation

methodisknowninadvaneofthemodel. Furthermore,itmightprovidealearoverview

of the environment, as well asparameters that governsthe results. The drawbaks of

usingamathematialanalysisisthatthemodelsmay,toalargeextent,needtosimplify

omplexsystems,thestatesneededtoproperlyrepresentthemodel,maygrowtoolarge

andrenderthisapproahunpratial.

One of the strongest assets of testbeds and prototypes is that they provide results

with a high degree of redibility. The use of testbeds or prototypes may be superior

to mathematial analysis when the problem area is omplex and simpliation of the

realsystemisimpossibleorundesirable. However,thisapproahmayrequireaomplex

development proess, where it might prove diult to verify or build the protool in

inrementalstages. Thus,thisisanapproahthatisoftenusedtoimplementandverify

theabilities ofa protool whererequirementsand behaviorhas matured. Furthermore,

beause the tests are run in a real environment, it might be diult to aess all the

neessarymeasurementsanditmightalsoinvolveexpensiveinstruments.

Simulationsanbeaveryexibleandeientmethodwhenanalyzing omplexsys-

tems. This approah an be used to model protools where the problem area is too

omplexto be testedin amathematialenvironmentand where aexible development

yle is needed. Furthermore,this approah provides theability to hoose the level of

abstration. This allows the simulated environment to better suit the desired level of

omplexity,andbyvaryinggranularity,itis possibletoaommodatebothdetailed and

high-levelsimulations. However,theresultsthatareobtainedfromasimulatorisusually

lessrediblethanthoseobtainedfrom testbedsorprototypes. Ifasimulatorwithanex-

istingframeworkanbeused,thismightsavedevelopmenttimeand,inaddition,remove

someof the need for simplied orstati assumptions onhigher and lowerlayersin the

network.

Inthisthesis,anewmethodforprovidingIPfastreoverywillbetrieddeveloped,and

thus, itis antiipated that therewill beaneedforamodelenvironmentthatis exible

and allows easyadaptation of newideas in the developmentyle. Some graphtheory

will be used in the initial designphases to be able to onvert the original RT method

to appliabletoonventionalIP networks. Furthermore,theproblem areais onsidered

to be omplexto be ompletely understood in aneasy orproperfashion when using a

mathematial model. Thus, a simulatedenvironmentwill be used to model, verify the

ndingsandmeasuretheperformaneoftheIPRT method. Thisenablestheevaluation

oftheperformaneandabilitiesofaIPRTasitinteratswithotherprotoolsinvarying

onditions. Thelevelofontrolmakesiteasytomeasureandinspetallstateinformation

ofthemodel,at anystageoftheexeution. Inaddition,itmayallowforarapidhange

in model propertiesbeause ofthe ontrolthat is provided overthe dierentaspets of

thesystem. Forexamplemaytopologieseasilybereplaedand method easilyadded or

dedutedfromthemodel.

Beause simulation is performed on models and assumptions and abstrations are

used, lessoftheatualeventsarefoundin thesimulation. Thus, simulationmaygivea

goodindiationonthe performane andorretnessof amodel, but guaranteesmay be

hardtogive.

Generally,networksmaybedesribedthroughstohastimodelswhere oneormoredis-

tinteventsaet thestateoromponentsin thenetwork. A varietyofsimulators spe-

ializeson spei aspets ofnetworksimulation. However,simulatorsaregenerally set

apartbyhowtheymodeltimeandhowtheymodelevents.

Time advane in asimulatormaybemodeledwith either anext-event oratime-

sliing approah, both using a disrete time. The time-sliing approah advanes the

simulationtimebymovingforwardat xedintervals,e.g. everyseond,regardlessofthe

ativitiesbeingsimulated. With thenext-event approah thetime is advaned to the

timesheduledbyeahevent. Inmostasesthenext-event mehanismismoreeient

and allows models to beevaluated morequikly. I.e. the simulator may jump diretly

from oneevent to the next sheduled event without aeting the overall results of the

simulation.

Furthermore,thewayhanges in systemstateouris alsodening for asimulator.

Itmaybemodeledthroughtheuseofevents,ativitiesorproesses. Theeventapproah

desribesahangeasanimmediatehangeinoneormorerelatedsystemvariables. The

ativitiesapproahissomewhatsimilartotheeventapproahbutusedurationtodesribe

hanges instates. Theproessapproahjoins olletionsofeventsorativitiestogether

to desribe thelife yle of anentity. Beause theeventsare disrete andordered it is

diultto model twoeventsthat overlapin timeandat thesametimemayinterat or

interferewitheahother.

The mostommonlyused approahis disrete-timeevent-drivensimulators. Aom-

monly known simulator that uses this approah is the network simulator also known

asns orns2[25℄. Anotherapproah,foundinJ-sim [26℄,isareal-timeproess-driven

approah to simulation. In suh systems, the evolution of asystem is dened by pro-

essestakingplaeatreal-timealongavirtualtime-axis. Eahproessisexeutedinan

independentexeutionontextandproessinterationismodeled,asitwouldhappenin

areal implementation. Furthermore,thereal-time proess-drivenapproahisan exten-

siontothedisrete-timeevent-drivenapproah. E.g.,theproess-drivenapproahisalso

event-driven. However,theinterationsbetweentheentities,i.e. proesses,areexpliitly

dened throughdependeniesandsynhronizationsbetweentheproesses.

InthisthesisJ-simwill beusedtoprovidethesimulatorenvironmentinwhihIPRT

will be implemented. The J-sim simulator is desribed in moredetail in the following

setion:

4.2.1 J-sim

J-simisaomponent-baseddisreteeventsimulatorwritteninJavathatmaybeusedfor

networksimulation. Itprovidesmanynetworkrelatedpakagesinludinganetworkpak-

age (INET Framework), wireless pakage, sensor network pakage, and a dierentiated

servie(Diserv)framework.

environment tries to mimi a blak-box approah to modeling often found in devel-

opmentof integratediruits. The dening propertiesof a blak-box is that bothits

purpose and the in/out signal pattern through pins or ports are fully speied. This

allows the omponents to mimi the behavior of real-world systems through message

passingand anindependentexeutionmodel. Thisisahievedbyallowingdataarriving

to aport of a omponentto be immediately proessed by that omponent in aninde-

pendentomputationontext. Inaddition,theACAallowsforafuntion allexeution

model whereaomponentmaysenddata to anotheromponent tobeomputedin the

sameomputationontextasthesender.

ThereareseveralreasonsforwhyJ-simwashoseninthisthesis. Itiswrittenpurely

inJava,andthus,providewithawell-knownprogrammingenvironment. Furthermore,it

provideswithallthebasiomponentsneededtosimulatenetworksandperformmeasure-

ments. Inaddition,SIMULAhasimplementedaversionoftheRRLreoveryproedure

in J-simthat ouldprovidewith bothagood foundationforinitial developmentandan

opportunitytotestbothRRL andIPRTundersimilaronditions.

IPRT Design

ThishapterontainsanoverviewoftheimportantdesignhoiesforimplementingIPRT

foronventionalIPnetworks. Ineahsetion,theproblemswillbeidentiedandpossible

solutionswillbepresented.

5.1 Constrution of the trees

TheoriginalRTwork[1℄presentstwodierentalgorithms;oneforlinkfailures,and one

fornodefailures. Bothofthealgorithmsfollowthebasiideaofgrowingtheredandblue

treesgradually byaddingnewredundantpaths. Furthermore,thealgorithms introdue

avoltagerule toensurethat theredundantpropertyofthetreepairisahieved. This

isdonebylettingtheruleimposeaompleteorderonthenodesasthetreesaregrownto

formapairofredandbluetrees. Thereareseveralattributesthatgoverntheperformane

andbehavioroftheIPRTtreeonstrution,wherethemainattributesarepathandyle

reation,and run-timeofthealgorithm.

5.1.1 Introduing the redundant tree algorithm

The Node-algorithm,shown in Algorithm 1, is designed to work with two-vertex-

onnetedgraphs. Itstartsbyaddingarandomlyhosenyle,ontainingthreeormore

nodes,fromthegraphwitharoot

S

redtreeandoneforthebluetree,suhthat

V blue = v max

V red = 0

yle in anarbitraryhosendiretion. Thevoltagesassigned are within theboundaries

of

v max

0

S

and red tree, in suh a way that the assigned voltages are dereasing and inreasing,

respetively. Subsequently,thetreesaregrownbyonnetingtwonodesalreadyassigned

to the trees, with one or more nodes not assigned; i.e. forming an arh starting and

endinginthetree. Thearhisthenorientedsothatthestartingnodeistheonewiththe

highervoltageofthetwonodesinthetrees. Followingadiretedpathfromthestarting

1:

j =

2: Choose any yle

(S, C ¹ , ..., C k , S)

≥

N 1

verties

{S, C ¹ , ..., C k }

v max > v(C ¹ ) > v(C k ) > 0

3:

A ^B 1 = {(S, C ¹ ), (C ¹ , C2), ..., (C k−1 , C k )}

A ^R 1 = {(S, C k ), (C k , C k−1 ), ..., (C ² , C 1 )}

4: while

N j 6= N

5:

j = j + 1

6: Chooseapath

P j = (X j, 0 , X j, 1 , ..., X j,L j ), L j ≥ 2

X j, 0 ∈ N j−1

X j,L j ∈ N j−1

v(X j, 0 ) > v(X j,L j )

If

X j,L _j = S

v(X j,L _j ) = 0

If

X j,0 = S

v(X j,0 ) = V

Theotherverties,

X j,i , i ≤ i ≤ L j

N j−1

7:

N j = N j−1 ∪ (X j,1 , ..., X j,L _j )

8: Orderthevertiesin

P j

v(X j,0 ) > v(X j,1 ) > ... > v(X j,L _j−1 ) > (v max )

where

v max = _y∈N ^max

j−1 (v(Y ) : v(Y ) < v(X j, 0 ))

9:

A ^B _j = A ^B _j−1 ∪ {(X j, 0 , X j, 1 ), (X j, 1 , X j, 2 ), ..., (X j,L _j−2 , X j,L _j−1 )}

A ^R _j = A ^R _j−1 ∪ {(X j,L _j , X j,L _j−1 ), (X j,L _j−1 , X j,L _j−2 ), ..., (X j,2 , X j,1 )}

10: endwhile

N j

j A ^B 1

j

A ^R 1

j S

P j

j L j

j X j,i

X

j

i

P j

v(X)

X

node, thearh istraversed. All nodes,exepttherstand last,areassigned voltagesin

adereasingmanner. Therstandthelastnodeonthearhisnotassignedvoltagesas

theyarealreadyinludedinthetrees,andhasthereforealreadybeenassignedvoltages.

Thenewnodesaregivenvoltageswithintheboundariesof

v(X j, 0 )

assignedtoanynodeinthetreethatdoesnotexeed

v(X j, 0 )

of

X j,L _j

X j, 0

redtree,through

X j,L _j

Fromthisnode,theyle

[A − B − E − F − C − A]

theirvoltagesaordingtolinetwo. Theredtreethusonsistsofinreasingvoltages,and

theblue dereasingvoltages,followingthethree-growthrulefoundinlinethreeandnine

in Algorithm1. Next, thearh

[E − G − F ]

6,thisbeomestheupperboundary. Thelowervoltage4,whihisownedbyE, beomes

thelowerboundary. Thus, Gisassignedavoltageof5. Eisthen addedto theredand

blue tree in aordaneto the voltage rule found in line 8. Thenext arh to be found

is

[C − D − B]

However,thelowerboundaryisvoltage6ownedbynodeF.ConsequentlyD isassigned

avoltageof7andaddedto theredandblue treesaordingly.

The Link-algorithm is verysimilar to theformerpresentedNode-algorithm. The

main dierene between thetwo, is that the link-failurealgorithm allows thearhes to

start and end at the same node. Thus, it beomes neessary to assign two voltages

to eah node and in this manner expand the voltage rule. The Link-algorithm may

potentiallyyieldshorterreoverypathsat theexpenseofintroduingartiulationpoints

intheredundanttrees. Thisisbeausemorelinksmaybefreelyusedwhenreatingtrees

with the Link-algorithm. However, the Link-algorithm is not required to produe

artiulationpointswhere noneareneeded. Itmaythereforebemadetoprotetagainst

nodefailurestotheextentallowedbythetopology. Thismaybedonebyrefrainingfrom

letting an arh start and end at thesame node asfar aspossible. However, this may

introdueabiggeromputationalostin thealgorithm.

The layout of topologies where the Node-algorithm and the Link-algorithm re-

spetivelymaysuessfullybeapplied,isinherentlydierent. ThisisbeausetheNode-

algorithmhasastriterrequirementontheonnetivityofthenetworksitmaybeapplied

to. TousetheNode-algorithm,thenetwork needsto beatleast two-vertex-onneted,

whereastheLink-algorithm onlyneedsthenetwork tobetwo-edge-onneted.

5.1.2 Important properties

Thereare severalattributesthatgoverntheperformaneandbehavioroftheIPRTtree

onstrution,andtheymayinueneresoureusagein bothroutingandforwarding:

•

•

•

Themannerofhowtheyleandthearhesareseleted,isofgreatimportanetothe

attributes oftheredundanttrees. Intheoriginal RT algorithms, e.g. Algorithm1, this

wasleftas anopenquestion. However,there hasbeensomeresearhinthisareabyXue

et. al. [27℄[16℄[17℄. Theirresultsshowthatthereationof ylesandarhesisvitalfor

IPRT to meet thedesired performane riteria. Agood examplemay behow thetrees

wouldperformwithashortest-pathversuslongest-pathseletionoftheyleandarhes;

Consideranodethathastwoneighbors,wherealinkhasfailedbetweentherootnodeand