Link metris

Link metris may be used to inuene the path seletion of a routing protool when

several paths to a destination exists. By assoiating a ost to eah link, the network

resouresmay be utilized in a moreeientmanner, allowingthe routingprotools to

provideahigher quality ofservie to thenetwork. In this thesis, both theJ-sim stati

routingprotool,andtheIPRTtreegenerator,mayuselinkmetriswhenalulatingthe

paths. Furthermore,theybothusetheDijkstrashortest-pathalgorithm toalulatethe

paths.

Theroutingalgorithmgovernsthemetrivaluesthatmaybeused. WhenaDijkstra

shortest-pathalgorithms is used, the link ostmaynot be negative, asthis would keep

thealgorithmfromterminating. Furthermore,thelinkostmustbeofsuhanaturethat

thelinkmostlikelytobeused,isrepresentedthroughthesmallestvaluesinthedierent

link metrisofanetwork.

Oneofthebigproblemswhenusingmetris,isthatthedierentreoveryproedures

mightneeddierentmetristoperformasoptimallyaspossible. Theoptimalmetrisare

oftendenedthroughheuristis. InRTandthusinIPRT,thereisstillongoingresearhin

tryingtondgoodheuristis,butthisisnotpartofthegoalsforthisthesis. Nevertheless,

the useof metrismaygivean indiationof whether IPRT is ableto respond to them.

Thus, the thesis will inlude the metris obtained asa partof the network topologies,

eventhoughthereisnoguaranteethat theyusedwill produegoodresults.

There isnotneessarilyaonnetionbetweenthelink apaityandthelinkmetris.

Evenifthelinkapaityisnotsetaordingtotherealtopologiesusedinthisthesis,the

metrismay help ahieve orretresults. However, the metrisshould bederived from

therealtopologies,asamismathbetweenthelinkbandwidthandthemetrisusedwhen

reatingtheFIB,mightresultin thetra followingpathsnotintendedforheavyuse.

Whentraisgenerated,itformsanetwork-wideloadpattern,i.e. theloadfoundonall

links atagiventimeorinterval. Whenafailureoursin anetwork,thetra aeted

by thefailurewill bererouted -followingnewpaths in thenetwork andforming anew

network-wideloadpattern. HowwellIPRTisabletodistributethisgeneratedloadisof

importane whenevaluatingitsperformane.

Charateristisinthetraimposedonnetworksmayplayaruialroleinevaluating

theperformaneofreoveryshemes. Therearetwomajorinuenestotheperformane

andbehaviorofnetworksduring afailure; rstly, theamountand destinationsof tra

introdued in the network, and seondly, in what manner the tra is transported. In

thissetion,thesepropertieswillbeexaminedtoprovidesolutionsusedinthesimulation

senariosin thisthesis.

7.2.1 Transport layer protool

TheIPpaketstrutureisdesignedtoprovideaminimalsetofmehanismstotransport

train aonnetionlessenvironment,andhasprovenitself aversatilepaket

represen-tation,leavingthepreferredhoieof tradeliverymethods totheupperlayers. TCP

and UPDare twoommonlyknowntransport protoolsused to extendthe apabilities

of IP, andbothtransport protools are implementedin the J-sim simulator. Generally,

TCP is used to transport the majority of internet tra (72-94 %) while UDP is the

othersigniantontributor(5-27%)[30℄. Theprotoolsdierinthemannertheydeliver

pakets,and thisdierene mayinuene theobtainedresults, orthemanner in whih

thesimulationsareonduted.

ThemainfeatureoftheTCPtransportprotoolisto providemehanismsforthe

re-liabledeliveryofpakets. OneoftheseisTCPslowstart,whihadjuststhetransmission

rateinaordanewiththepereivedapabilitiesofthenetworkandthereeiver. When

apaketisinitiallyaetedbyafailure, itwillneedto bere-routedusing analternative

pathtoreahthedestination. Ifthepaketneedstotraversemorelinksaordingtothe

newpath,thismayresultinatemporaryhangeintheratethesenderreeives

aknowl-edgements. This may leadTCP to interpet the hange in thereply rateas ongestion,

orlossofpakets,triggeringtheTCPslowstartmehanism. Initial testswiththeJ-sim

TCPimplementationrevealedthat theTCPstreamsdidgointo TCPslowstartduring

asimulatedfailure-eventhoughreoverymehanismswerepresent.

TheapproahusedbyUDPdoesnotdiermuhfromarawIP deliveryprotool,as

itprovidesabesteort deliveryshemeofpakets, that is,noguaranteesare madeas

todelivery. TheUPDprotoolprovidesanoptiontouseaslow-startmehanism,butthis

mehanismwill notbeusedin this thesis. Aordingly, whenUDPis usedto transport

pakets in a network experiening failure, the sender is not informed whether delivery

wassuessful. This enablesany soureusing UDPas transport protool to send at a

onstantrate,regardlessoftheonditionofthenetworkitself.

duringfailure. TratransportedusingTCPwillexperieneaTCPslowstart,wherethe

sending rateisredued toaminimum foraperiod. Foraperiodfollowingimmediately

afterthefailure,theloadwillbeunaeted,asreoveredpaketstraversethenewpathto

theirdestination. Furthermore,after thesouresintiatetheTCPslowstartmehanism,

thelengthoftheperiodduringwhihtraisrestoredtoitsfullsendingrate,dependson

boththetimeneededfortheJ-simTCPimplementationtoitselfrestorethetransmission

rateaftertheTCPslowstart,andthepropagationtimeofapaketbetweeneahsoure

anddestination. TheimpatoftheTCPslowstartrelationwoulddependontheduration

ofthefailure. Furthermore,whenthefailureis prolonged,and noreoveryproedure is

oered,traboundforafailednodewillexperieneaseriesofTCPslowstarts,starving

thenetworkofthistra. ByusingUDPfortransport,thesimulationsenariobeomes

easiertoadministrate,asthetransmissionratedoesnotdependonthenetworkondition

ortheatualdeliveryofthepakets.

Considering the distributionof the transport protools used in the Internet, a

real-isti approah would be to utilize a ombination of TCP and UDP. However, by using

TCP,theonstrutionofasimulatedsenariobeomesmoreomplexbothto ongure

and to analyze. Byonly usingUDP, thesimulatedsenariomayrepresentaworst-ase

senario. Thisalsoremovesthedependenybetweenthedurationofthenode-failureand

theobtainedmeasurements,andshowstheresultsthat would be obtainedif thefailure

waslong-livedandalltrabound forafailed destinationwasusingUDP.

Forthisthesis,thetransportprotoolsusedwillbeeitherUDP,orapureIPsolution.

The reason for hoosing this approah is to enable measuring the generated loadin a

worst-asesenario,andtoprovideaneasyenvironmenttoanalyze.

7.2.2 Generating tra

There exists a number of ways to model the tra to be introdued into a network.

Generally,it is desirablethat thegenerated tra resemblesthat of areal-lifenetwork,

asthisgivesagoodfoundationforevaluationof atualperformane. However,properly

generatingtrathatresemblesthetrafoundintheInternetisatopithatisheavily

debated, withouta learonsensus. Thus, a model has been hosenwithout toomuh

disussiononalltheavailable options.

The tra introdued into thenetwork should be extensiveenoughto ensureto

a-urateveriationof network performane. E.g. ifatra generatoronly produesone

singlepaketeveryseonditwouldbehardtodetermineanyeetsintheloadpatterns.

Togeneratethenetwork-wideloadtwotehniquesareused:

•

^{Atra generatorbasedonthePoisson}distribution,togeneratetheloadbetween allsouresanddestinations.

•

^{A tra matrixis used to} individually sale theload of thetra generators,in

models may be used to aurately model Internet bakbone tra on sub-seond time

sales. Furthermore, the artiles states that simulations may get suiently aurate

resultsbyvaryingthearrivalrateofaPoissonproess. InJ-sim,severaltragenerators

areavailable,and forthisthesis, aPoissontra sourefrom theJ-simpakagewill be

used.

The tra will be weighted aording to a tra matrix made to mimi the

load-distributionfound in eah individualnetwork [32℄. The tra matrixdesribesthe

de-mand between all soures and destinations, but it does not desribe how the tra is

routed, northe amount of tra to begenerated. Theuse of atra matrix provides

manyfeaturesnotoveredinthisthesis. Commonly,thetramatrixwouldbesaledto

maththegeneratedloadtothelinkapaity. However,inthisthesis,itisonlyusedfor

generatingaredibleloadpatternbetweensouresanddestinations,asthelinkapaity

ofthenetworkmodelleddoesnotreetatualapaity. Thisisbeausethegoalforthis

thesis doesnot inlude determining the best loaddistribution IPRT is ableto provide,

butratherto determineifIPRTisabletodistributeloadatall.

In the thesis,atotal loadgenerated by allsoures ombinedwill bespeied. This

enablestheJ-simtrageneratorutility,desribedintheIPRTimplementationhapter,

toalulatetheaverageloadgeneratedbyallPoissonsoures. Furthermore,thedierent

tra souresaresaled aordingto atra matrix,whih speiesarelativeratioof

the amountof tra bound between everysoure/destination pair in a given network.

This enablesthetrato resemblethenetwork-wideloadpattern that oldpotentially

bepresentin thetopologies.

7.3 Failure models

The failure model used in thesimulator governsthe resultsthat are possibleto obtain

from the simulated senarios and the time needed to simulate all possible failures. In

a real network, failures may originatefor amultitude of reasons, diering in sale and

severity. Theymaybeeitherphysialorlogial,andarisefromeitherexternalorinternal

auses. An exampleofanexternalphysialerrorouldbeaable ut,whileaninternal

logialerrorouldbeausedby anerroneousonguration. Furthermore,notallerrors

ourbyaident,butarerathertheresultofplannedservieevents-hardwareupgrades

or largeonguration hanges, for example. However, in this thesis, asimpler

failure-senario resembling severe physial error will be used - simulating a omplete failure,

wherethefailedentityeasesoperation.

Thefailuremodelsthatmaybeusedinlude:

•

^{Nodefailure, themodelwhihprovidesthemost}omprehensivefailures,asanode failure alsoentailsafailureonalladjaentlinks ofthenode.

•

^{Link failure, whih produeasub-set ofthe failures generatedin the node failure}

model. It allowsthe nodes to remainoperational,and retain funtionality on all

operationallinks.

as it entails a failure on all adjaent links of the failed node. Beause IPRT has been

designed to withstand node failure, this property should be veried in the simulated

senarios. Nodefailureshould also bethefailure model that providesthefastest aess

toafullveriationoftheIPRTmodel. However,byusingnodefailureastheonlyfailure

model,thelast-hopproblem maynotbeonrmedinthesimulator. Thisisbeausethe

last-hopproblem dealswithhowtoreovertrawhenthenodeimmediatelyupstream

ofthefailureisthelast-hopnodebeforereahingthedestination address,andtheause

offailureisunknown.

The linkfailure modelwill produeasubsetoffailuresgenerated inthenodefailure

model. It maynotbeusedto verify theIPRTmethod, asit isnotapableof providing

anenvironmentwhere trameanttoavoidaspeinodeiseasilydeteted. Todetet

suh tra would require additional information in the reovered paket, and spei

detetionlogiwouldberequiredinthedispather. However,byusingthisfailuremodel,

itmaybeshowninthesimulatedenvironmentthattheIPRTmethodsolvesthelast-hop

problem.

It would bepossibletoutilize aombinationofthetwofailure models, toshowthat

IPRT isapable toreovertrawhen anodefailure ispresent,and tosolvethe

last-hopproblem whenalink failureispresentatthedestinationnode. However,thiswould

requirealargeinreaseinthenumberofsimulationsenarios.

Beauseofadesiretokeepthenumberofsimulationsdown,andthatithasbeenshown

in theorythatIPRTisapableofsolvingthelast-hopproblem,thenodefailuremodel

will be used in this thesis. Furthermore, if IPRT is apable of providing fast reovery

during all possible node failures, there are no good reason for it to not be apable of

solvingthelast-hopproblem.

7.4 Modeling re-onverged senarios

The re-onverged results are not modelled aurately in aordane to a real senario.

However,themodelensuresthat thefailednodein thenetworkisnotusedto generate,

reeive,orforwardanytra. Thedierenesmaybefoundinthewaytheroutingtables

arereated.

•

^{Theroutingtablesusedin the}re-onvergedsenarioontainanentrytothefailed node.

Toensurethat thefailednodeisnotusedasanintermediatenodeforanytra,the

adjaentlinksaregivenaveryhighostwheninitializingthesenario. Theostissetso

high that theshortest-pathstatiroutingalgorithmdoesnotuse thenodein anypath,

exeptwherethefailednodeisthedestination.

When simulatingthe re-onvergedsenarios, thefailed nodeis failed with thesame

delivered.

To verify the behaviorof the re-onverged model, the overage of the re-onverged

senariomay be tested. It shouldprovidefull overagewhen exludingthefailed

desti-nation.

7.5 Performing measurements

When performing measurements ona simulated senario,some hanges in the network

statemayneedatransientperiod. Morepreisely,aperiodduringwhihthestatehange

fundamentally alters the network behavior, introduing a duration where some time is

neededforthenetworktoreahanewequilibrium. Duringthisperiod,anymeasurements

ouldpotentiallyprovidedatathatmayskewtheresultsinanunrealisti diretion. For

example,if theJ-sim TCPimplementationwasto beused fortransport, anode failure

would result in a TCP slow start of the soures aeted by the failure, lowering the

throughput of a network immediately following the failure. Furthermore, during this

post-failureperiod, there will beatime spanwhere the tra aetedby thefailure is

being rerouted, and beause of the propagation time, there will be a delay before the

eetofthefailuremaybeseeninthelink-loadofthelinksdownstreamofthefailure. If

themeasurementsarebasedonthispost-failureperiod,theymaynotprovideanaurate

pitureoftheatualinuene ofthestatehangeonthenetwork.

In the simulated experiments with IPRT, the main fous is the duration between

failure and subsequent re-onvergene. It has been shown that the IP re-onvergene

maybereduedtosub-seondresponsetime [7℄. However,an importantmotivation for

implementingIP fastreovermehanisms,isto providethere-onvergene proesswith

more time to properly respond to the failure, and thus, the duration of the reovery

proedureshould beonsideredalargerinterval.

To ensure that the results obtained from the simulation are orret, the duration

betweenfailureandre-onvergeneshouldberunmorethanone. Thereareseveralways

ofahievingthis,butaommonlyusedapproahistouseasimulationtehniquenamed

setioning[33℄. Thismethodallowsasinglesenariotoountasaseriesofindependent

runs, by running the same senariofor a magnitude longer than the original duration

the simulation was intended to run for. This is done by splitting the simulation into

a series of disrete periods where measurementsare performed, and furthermore desist

from measuring for ashort intervalbetweenthe periods, in order to makethe disrete

measured periods independent. By using this tehnique, less total time is required for

thetransientperiod, i.e., theperiod fromsystemstartupuntil astable stateisreahed,

whileitisstillpossibleto providearangeofindependentmeasurements.

Experiments

In this hapter, the experiments will be desribed and the results obtained from the

simulatedsenarioswillbeshown,followedbyadisussionoftheresults.

Themain goaloftheexperimentsistoshowthat theIPRTmehanismmaybeused

for reoveryin onventional IP networks. Thus, an important partof the experiments

is to showthat no paket aetedby asinglenode failure, exluding thetra sent to

thefailednode,islost duringthedurationofthefailure. Furthermore,asub-goalofthe

experimentsistoshowtoshowhowtheIPRTmethodperformsintermsofreoveryand

howthemethodaetsthenetwork-wideload.

8.1 Experiment desription

Inthissetion, theexperimentsandtheiraimswill bepresented. Furthermore,in these

experiments,theIPRTspeiparametersthatwillbevariedinludewhatosthasbeen

used, when the reoverytrees have been generated, the use of QoSinformation in the

Qbittables,andtheuseofdeetionin theforwardingproedure:

•

^{Eitherthetreesmaybeonstrutedusingaatostonalllinksorusethelink-ost}

speiedobtainedfromthetopology. Byusingatheostobtainedfromthe

topolo-gies it maybepossibleto see if thealgorithm used in the IPRT tree generatoris

abletorespondto hangesinlink-ost.

•

^{Qbit maybeused for}optimization, i.e. seletingthebest outgoinginterfae, and guaranteeing a orret forwarding proedure using loal reovery, i.e. seleting a

valid reoverypath. Whenreferringto Qbit in this hapter it isthe QoS

respon-sibilities that are referred. Thus, the Qbit tables are always populated with the

information neededto ensureorretforwarding,butdoesnotinludetheQoS

in-formationunlessexpliitstatedotherwise.

•

^TheQbitinformationresponsibleforprovideaguaranteedsuessfulloalreovery proedure is omputedwiththe probabilistiapproah(see setion5.3.1),making

it neessaryto support deetion, i.e. requirethe forwardingproedure to move

reovered tra from the red to the blue path is a failure is enountered twie.

By turning o deetion, it may prove that the reoveryFIBs represent a valid

onguration forforwardingwithoutdeetion, i.e. aset oftrees that ouldhave

beenomputedfromtheexatproedureto populate theQbitinformation. Thus,

enabletheexperimentsto inlude anassertiononthe eetsof usingdeetionin

enabletheexperimentsto inlude anassertiononthe eetsof usingdeetionin

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