QoS - IP redundant trees for preplanned recovery in connectioning networks

8.3 Disussion

8.3.4 QoS

ThissetionaimstodisussIPRTsabilitytosupportQoSrouting,i.e. theobservedeet

ofQoSQbitandIPRTsabilityto respondto theuseoflink-ostand howthis inuene

theload-distribution.

0 1e+06 2e+06 3e+06 4e+06 5e+06 6e+06

0 2 4 6 8 10 12

bps

link number

Reconverged IPRT

Figure8.20: Abilene,notratoorfromfailednodewithatostonlinks

0 1e+06 2e+06 3e+06 4e+06 5e+06 6e+06 7e+06

0 2 4 6 8 10 12

bps

link number

Reconverged IPRT

Figure 8.21: Abilene,notrato orfromfailed nodewithostonlinks

Qbit

In the IPRT design hapter it was shown that Qbit ould be populated with QoS

in-any inuene on the results gathered from the simulations, with the exeption of the

ost239network. Inost239,it didreduethe averagelengthofthe reoverypath, and

furthermore, it wasshown that the redutionin reoverypath-length didnot inuene

theworst-aselink-loadinthenetwork(seeFigure8.18and8.19).

The reason for the low benet obtained from using QoS Qbit in terms of better

performanemaybearesultofseveralirumstanes.

•

^Beause^of^therequirementofadegreeofthreeormoreonthenumberoflinksonly asubsetofthenodesin thenetwork maypotentiallybenetfrom QoSQbit.

•

^The^redundant^trees^are^generatedⁱⁿ^suh^a^way^that^the^yle^and^arhes^are^tried

kept to a minimum length. Thus a greater amount of links are used and makes

it more likely that one of the paths follows the path used for routing in normal

operation. AgoodexampleonthiseetisfoundinthesimulationwiththeGeant

topology where thelog les showedthat there were noirumstanes where both

reoverypathswereavailableduring afailure.

•

^The ^topologyrequirementsthat needs to be fullled to provide QoSQbit is very similartothesenarioswhereQbitforwardorretionneedstobeutilized. F

urther-more, beause deetion wasused, the basisfor setting and loking aQbit entry

werebasedonwhether ornotitwaspotentiallyneededandthusthismethod may

inlude falsepositives.

•

^When ^the ^Qbit information was alulated equal ost paths was tagged with a third-olor and always interpreted as a free seletion resulting in the red path

beinghosen.

The author does still believe that the use of QoS Qbit may potentially benet the

performaneof IPRT. However,given theirumstanesused in thesimulationsin this

thesis, it is lear that the ost of alulating the QoS Qbit is not justied in terms of

betterperformane.

Cost

Fromthe results it may beobserved that theIPRT method is generallyapable of

re-spondingtohangesin link-ost.

Onewaytoobservethehangesinlink-ostistoonsiderthemedianobainedfromthe

measurementsdone onthetopologies. An exampleanbefoundin the abilene(Figure

8.13and 8.12)in links 4,6, 8,9and 10 oruninett (Figure 8.17and 8.16)in links 3,5,

6,17 and27. Inboth these examplesthemedian in there-onvergedsimulationshas a

learhangein thelink-loadandin bothexamplesIPRTisabletofollowthehanges.

InTable8.4onemayobservethat themedian totalloadshowastableaveragewhen

ostisintroduedingeantanduninett. Asmorelinksareusedtotransferpaketsbetween

used. However,inbothgeantanduninettitmayalsobeobservedanelevatedperentage

valuein maxlinkinreaseandadereasein perentagevaluesinminimumlinkinrease.

This gives an indiation that IPRT and the re-onverged reovery paths diers more,

omparedtothatofaatlink-ost,whenusingtheostspeiedbythetopology. Inthe

abilene topology this situation is reversed - providing more losely related paths when

link-ostisintrodued.

The reason for observing the dierenes between geant oruninett and abilene may

stem from theIPRT tree generation. In theabilene topologythe link ost enabledthe

pathsobtainedin there-onvergedsenariotomoreloselyrelatetotheIPRTreovery

paths as the topologyprovide only small variations in the trees. In asimilar manner,

thegeantoruninettre-onvergedsenariosusinglink-ostprovidedpathsthatIPRTwas

not exible enoughto fully respond to the hanges. However, beause IPRT is a loal

reoveryproedure,it isexpetedthat thereoverymethod maynotbeableto provide

anoptimalsolutionwhenomparedtoare-onvergedsenario. Anotherreasonforsome

ofthelinkstobeutilized,evenifithasalowost,maystemfromthewaytheredundant

trees are built. In the implementation used in this thesisthe tree generation needs to

followstritrules,andmaynotalwaysbeabletofreelyhoosebetweenallavailablelinks.

Even though IPRT is generally apable of responding to the use of link-ost, more

workneedstobedoneinordertoobtainknowledgeonhowtoongureandutilize

link-ostinaIPRTenablednetwork.Thisisapparentfromthelink-load,where somefailure

senariosdoresultinautilizationoflinksthat shouldhavebeenavoided.

Conlusions and future work

IPRTisbasedontheredundanttreeapproahpresentedbyMedardet.al[1℄,extendedto

providearesoureeientwaytopopulatethebakupForwardInformationBase(FIB)

and furthermore, the mehanisms needed to utilize this information in the forwarding

proedure. Byreversingtheredundanttreesobtainedforthetreegeneratorandusethe

root asadestination,IPRTis ableto provideIP fast reoveryusing tworeoveryFIBs

and guaranteefull overage ofall failures. Furthermore,IPRTmaybetheonly IP fast

reoveryproeduretoprovideaxedrequirementinadditionalstateinformationneeded

attherouters.

Themain goalofthethesishasbeensolved:

•

^BysupplementingtheFIBusedfornormaloperationwiththetwoadditional reov-eryFIBs,namedr/bTable,andusetunnelingorIP headermarkingforidentifying

reoveredpakets,IPRTis abletoo-existwithnormalroutingprotoolsin times

offailure-freeoperation.

•

^In^order^to^provide^loal ^reovery^,^IPRT^uses^Qbits,^a^bit^indiating^what^reovery

FIB is preferred in a reovery situation, to be able to identify a reovery path

unaeted of failure. The data-struture holding the Qbit information may be

merged with the FIBs or be self-ontained as an addition to the reovery FIBs.

The Qbits may be populated through means of a probabilisti algorithm that is

able to identify and mark the needed paths in a fast way, or through use of an

exat proedure that requires moreCPU usage but avoid theuse of deetion in

theforwardingproedure (seesetion5.3.1). However,theexatproedureshould

beused inorder to dereasetheadditionalloadassoiatedwith theuseofIP fast

reovery.

•

^Beause ^the^reovery^FIBs^areself-ontainedtheyare unaetedbyanypotential re-onvergene.

One ofthe strongest assetsof IPRTis the ability to provide 100% overage with a

minimalonstantamountofextrastateinformationineahrouter. Thismaybeahieved

throughuseofther/bTablesolutionforpopulatingthereoveryFIBs. Inomparisonto

layerstoprovideIP fastreoverynoguaranteesmaybegivenontheupperbounds.

Beause IPRTmayidentifyand orretlyforwardpakets basedononlytheolorof

thereoverypathandthedestination,itgainsanadvantageinstateinformationneededto

providethesignalingmehanism. Byguaranteeingthatonlytwobitsneedstobesetinthe

IPheadertoorretlyforwardareoveredpaketIPRTitmaybeeasiertoaommodate

forIP headers tobeused assignal-arriersin areal implementation. Thisouldenable

IPRT to be used without tunneling and thus avoid the inreased overhead in network

loadandpossiblepaket fragmentationassoiatedwiththeuseofIPenapsulating.

The ability to provide low additional state information is ahieved at the ost of

inreased amountsof alulations when ompared to RRL. To beable to populate the

r/bTableeahnodeinthenetworkneedstoperformanumberofshortestpathtree(SPT)

alulationsequalto twotimes thenumberofnodesin thenetwork. RRL also requires

oneadditionalSPT omputation perlayer,but thenumberof layersneeded byRRL is

onsiderablelowerthanthenumberofredundanttreesneededtopopulatether/bTables

inIPRT.Atthepresenttimethebestknownalgorithmforgeneratingapairofredundant

treeshasarun-timeof

O(n + v)

^[27℄.

TheQbitsmayprovideQoSproperties,howeverthemehanismsandsituationswhere

this may be fully utilized is not yet understood to a full extent; other approahes to

generatetheredundanttreesmaybenetfromQoSQbittoalargerdegreethanobserved

in thisthesis.

IPRTisabletoprovidewithagoodload-distributioninfailuresituation,andprovides

goodpotentialintheabilitytorespondtoQoSlink-ost. Inthepresentimplementation,

there are situations that reate hot-spots on ertain links. However, the eet may be

minimizedbypopulatetheQbitin suh awaythat deetionmaybedisabled.

9.1 Future work

Themain disadvantageofIPRT isthenumberofomputationsneededto reateallthe

redundanttrees. Futurework should inlude aninvestigation ifitispossibleto provide

inremental alulationsof the trees. If this is possible, it ould strengthen IPRT as a

ontestantamong theIP fastreroutereoveryproedures.

In this thesis, IPRT wasimplementedwith a stati routingapproah. Future work

ould inlude researh onhowIPRTmay interat with areal routingalgorithm

imple-mentation asOSPForIS-IS. Inaddition, it ouldproveinterestingto learnhow IPRT

maybeimplementedinahierarhial,segmentedorarearoutingenvironment. Another

topi that is to some extent related to this kind of routing environment is to provide

reoveryofmultihomeddestinations. IPRTmayprovidewithanenvironmentwherethis

ouldbesolved,andfuture workouldinlude aresearhinthis area.

thelink-ost. Work hasbeendonein this areabyXue et.al[16℄[17℄, howeverthe eet

from usingthesealgorithmsarenotknown. Furthermore,IPRTmayoperatefreeofthe

routingprotoolused fornormalroutingandouldpotentiallygainfrom usingseparate

link-ostsorlink-metris. Apossiblepathtofollowistodynamiallyupdatethemetris

as the trees are built, gradually inreasing the ost of the links inluded in the tree.

Another approah may beto investigate ifthe Qbitsmaybe used to spreadthe tra

moreevenlyduringspeifailures. I.e. trytobalaneusedoutgoinginterfaesthrough

use of Qbitsgivenaspei neighbornode failure. This ould be doneloally oneah

nodeastheuseofQbitonlygovernstheolorofthereoverypath.

Anothertopiforfutureworkmaybetoinvestigatetheabilitytowithstandn-failure

situations. Theproedureusedto providesinglefailureIP fastreoverywithIPRTmay

beusedtoprotetagainstfailuresthatareoherent. However,itisantiipatedthatother

approahesapartfromRTmustbeusedto generatetheappropriatetrees,andrun-time

ofsuhanalgorithmmaybeofimportane.

[1℄ Muriel Medard, Steven G. Finn, and Rihard A. Barry. Redundant trees

for preplanned reovery in arbitrary vertex-redundant or edge-redundant graphs.

IEEE/ACM Transations onNetworking,7(5):641652,1999.

[2℄ AndrewM.Odlyzko.Internettragrowth: souresandimpliations.volume5247,

pages115.SPIE,2003.

[3℄ G.Iannaone, C. Chuah, R. Mortier, S. Bhattaharyya,and C.Diot. Analysis of

linkfailuresinanipbakbone. InPro. ofACMSIGCOMMInternetMeasurement

Workshop2002,Marseille, Frane,Nov2002.

[4℄ C. Labovitz,A. Ahuja, and F. Jahanian. Experimental study of internet stability

and wide-area bakbonefailures. Tehnial Report CSE-TR-382-98, University of

Mihigan,1998.

[5℄ A. Markopoulou,G.Iannaone, S. Bhattaharyya,C.Chuah, and C.Diot.

Char-aterizationoffailuresin anip bakbone,2004.

[6℄ AnindyaBasu and JonRieke. Stability issuesin ospfrouting. InSIGCOMM'01:

Proeedings of the 2001 onferene on Appliations, tehnologies, arhitetures, and

protools for omputerommuniations, pages225236,NewYork,NY, USA,2001.

ACMPress.

[7℄ P.Franois,C.Filsls,J.Evans,andO.Bonaventure. Ahievingigponvergenein

largeip networks,2005.

[8℄ MurielMédard,StevenG.Finn,and RihardA.Barry. Wdmloop-bakreoveryin

meshnetworks. InINFOCOM,pages752759,1999.

[9℄ R. Bartos and M. Raman. A heuristi approah to servie restoration in MPLS

networks,2001.

[10℄ Ciso Systems In. Enhaned interior gateway routing protool white paper:

http://www.iso.om/warp/ustomer/103/eigrp-to .html,2003.

[11℄ G.Malkin. RIP version2. RFC2453, Internet EngineeringTaskFore,November

1998.

[12℄ E. W. Dijkstra. A note ontwoproblemsin onnexion with graphs. Numer. Math,

[14℄ A.KhannaandJ.Zinky. Therevisedarpanetroutingmetri. SIGCOMMComput.

Commun.Rev.,19(4):4556,1989.

[15℄ BernardFortzandMikkelThorup. InternettraengineeringbyoptimizingOSPF

weights. InINFOCOM(2),pages519528,2000.

[16℄ Guoliang Xue, Li Chen, and K. Thulasiraman. Qos issues in redundant trees for

protetioninvertex-redundantoredge-redundantgraphs. IEEEInternational

Con-fereneon Communiations,5:27662770,2002.

[17℄ Guoliang Xue, Li Chen, and K. Thulasiraman. Quality-of-servie and

quality-of-protetionissuesinpreplannedreoveryshemesusingredundanttrees. IEEE

Jour-nalonSeletedAreasinCommuniations, 21(8):13321345,Otober2003.

[18℄ A. F. Hansen, A. Kvalbein, T. Cii, S. Gjessing, and O. Lysne. Resilient routing

layersfor reoveryin paket networks. InBob Werner, editor, International

Con-fereneonDependableSystemsandNetworks(DSN2005). IEEEComputerSoiety,

2005.

[19℄ StewartBryantand MikeShand. Ip fastrerouteframework. IETF InternetDraft,

draft-ietf-rtgwg-ipfrr-framework-05.txt, Marh2006. (WorkinProgress).

[20℄ A.F.Hansen,T.Cii,andS.Gjessing.Alternativeshemesforproativeipreovery.

Inxxx,editor,2ndConfereneonNextGenerationInternetDesignandEngineering,

Valenia, SpainApril 3-5,pages18.IEEE,2006.

[21℄ W.Simpson. Ipinip tunneling. RFC1853,InternetEngineeringTaskFore,1995.

[22℄ J.Postel. RFC791: InternetProtool. RFC791,InternetEngineeringTask Fore,

September1981.

[23℄ Stewart Bryant. Ip fastreroute using tunnels. IETF InternetDraft,

draft-bryant-ipfrr-tunnels-02,April2005. (Workin Progress).

[24℄ Stewart Bryant, Mike Shand, and Stefano Previdi. Ip fast reroute using not-via

addresses. IETF Internet Draft, draft-bryant-shand-ipfrr-notvia-addresses-02.txt,

Marh2006. (Workin Progress).

[25℄ Steven MCanne and Sally Floyd. ns Network Simulator.

http://www.isi.edu/nsnam/ns/http://www.isi.edu/nsnam/ns/.

[26℄ Hung-YingTyan. Design,Realization andEvaluation ofa Component-Based

Com-positionalSoftwareArhiteturefor NetworkSimulation. PhDthesis,2002.

[27℄ W. Zhang, G. Xue, J. Tang, and K. Thulasiraman. Linear time onstrution of

redundanttreesforreoveryshemesenhaningqopandqos.INFOCOM24thAnnual

JointConfereneoftheIEEEComputerandCommuniationsSoieties.Proeedings

IEEE,4:27022710,Marh2005.

[28℄ CisoSystemsIn. Multi-topologyis-iswhitepaper,2003.

loationforPrivateInternets.InternetEngineeringTaskFore: RFC1918,February

1996.

[30℄ MarinaFomenkovKen. Longitudinalstudyofinternettrain 1998-2003.

[31℄ ThomasKaragiannis,MartMolle,MihalisFaloutsos,andAndreBroido. A

nonsta-tionarypoisson viewofinternettra. InINFOCOM,2004.

[32℄ A.Kvalbein,T.Cii,andS.Gjessing.Routingeienywithlinkfailuresusing

mul-tipleroutingongurations.TehnialReport02-2006,SimulaResearhLaboratory,

2006.

[33℄ Pålitelighet og ytelse i informasjons- og kommunikasjonssystem. tapir akademisk

forlag,2003.

[34℄ A.Kvalbein,A.F.Hansen,T.Cii,S.Gjessing,andO.Lysne.Fastipnetwork

reov-eryusingmultipleroutingongurations.InZhiliZhangArturoAzorra,JoeTouh,

editor,INFOCOM2006,pagesxxyy,Barelona,SpainApril2329,2006.IEEE.

APPENDIX A

Appendedto thethesisisaCD-ROM ontainingthefollowinghightlights:

•

^Readme^le

•

^Soure ^ode^for^IPRT^Tree^Generator

•

^Soure ^ode^for^IPRT^J-sim^extentions

•

^Soure ^ode^for^J-sim^1.3^v3

•

^Simple^example^explaining^how^to^simulate ^an^IPRT^enabled^networkⁱⁿ ^J-sim

•

^Topologies^and^tra ^matrixes^usedⁱⁿ^this ^thesis

The Readmelemaybefoundat theroot of theCD- speifyingfurther usageand

ontent.

In document IP redundant trees for preplanned recovery in connectioning networks (sider 95-105)