7.5 Performing measurements
8.2.1 Coverage
Table8.2and8.3showstheoverageofIPRTandRRL withthedierentparameters.
Network Link-ost Qbit Coverage
The tests wasrepeatedone with forward deetion, i.e. the abilityto move tra
from theredtotheblue path,turned o. Theoverageobtainedfromthis testwasthe
Abilene no 100%
Cost239 no 100%
Geant no 100%
Uninett no 100%
Table8.3: RRL reoveryoverage
furthertestingwithdeetionturnedointheforwardingdeisionseventhoughthetrees
werenotinitiallygeneratedtosupportthisusage. Thismaybedonebeauseithasbeen
shownthat thereoveryFIBsusedrepresentvalidongurationsforforwardingwithout
deetion. I.e. it hasbeenshownin theoveragesetionthat theyprovidewith 100%
overagewithoutdeetionturnedon.
8.2.2 Path-length
The graphsfound in Figure 8.5, 8.6, 8.7, 8.8, 8.9, 8.10 and 8.11 showthe distribution
of path-lengthsaetedby afailure. The path-lengthisameasurementonthe amount
of links apaket must traverseto get from the soureto the destination. InIPRT the
reoverypathisdetermined bytheredundanttrees ofwhihthe destinationis theroot
node of, thegeographialposition of the node initiating thereoveryand whih of the
redundant trees areavailable for thisnodeto use. Thus, A
→
B andB→
A are disjuntpathsandtreatedassuh-eventhoughtheymightfollowthesamelinks.Pathsunaeted
byfailurearenotinludedin thegraphs.
0 0.1 0.2 0.3 0.4 0.5
0 2 4 6 8 10
percent
path length
Original Reconverged IPRT IPRT QoS Qbit
Figure8.5: Abilene,withlink-ostenabled
0 0.1 0.2 0.3 0.4 0.5
0 2 4 6 8 10
percent
path length
Original Reconverged IPRT IPRT QoS Qbit RRL
Figure8.6: Abilene,withatlink-ost
0 0.1 0.2 0.3 0.4 0.5
0 2 4 6 8 10
percent
path length
Original Reconverged IPRT IPRT QoS Qbit
Figure8.7: Geant,withlink-ost enabled
0 0.1 0.2 0.3 0.4 0.5
0 2 4 6 8 10
percent
path length
Original Reconverged IPRT IPRT QoS Qbit RRL
Figure8.8: Geant,withatlink-ost
0 0.1 0.2 0.3 0.4 0.5
0 2 4 6 8 10 12
percent
path length
Original Reconverged IPRT IPRT QoS Qbit
Figure8.9: Uninett, withlink-ostenabled
0 0.1 0.2 0.3 0.4 0.5
0 2 4 6 8 10 12
percent
path length
Original Reconverged IPRT IPRT QoS Qbit RRL
Figure8.10: Uninett, withatlink-ost
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
0 1 2 3 4 5 6 7
percent
path length
Original Reconverged IPRT IPRT QoS Qbit RRL
Figure8.11: Cost239,withatlink-ost
ThegraphsfoundinFigure8.12,8.13,8.14,8.15,8.16,8.17,8.18and8.19showthemedian
throughputinludingthe97.5and2.5perentilemeasuredateahlink. InthetestsUDP
wasusedasatransportprotoolmakingthemeasuredvaluesmimiaworst-asesenario.
Inadditionthetrabetweeneahsoureanddestinationnodewasweightedaording
totopologyspei tramatrixes.
TheresultsobtainedfromrunningthesimulationswithQoSQbitareomittedasthey
didnotdierfromtheresultsobtainedwithoutQoSQbitturnedon.
Notethatthere-onvergedresultsinludetrafromsouressendingtratofailed
nodes. Thistraisdroppedatthelast-hopbeforeitreahthefailednodes.
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 IPRT no deflect
Figure8.12: Abilene,with atlink-ost
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 IPRT no deflect
Figure 8.13: Abilene,withlink-ost enabled
0 1e+06 2e+06 3e+06 4e+06 5e+06 6e+06
0 5 10 15 20 25
bps
link number
Reconverged IPRT IPRT no deflect
Figure 8.14: Geant,withatlink-ost
0 1e+06 2e+06 3e+06 4e+06 5e+06 6e+06
0 5 10 15 20 25
bps
link number
Reconverged IPRT IPRT no deflect
Figure 8.15: Geant,withlink-ostenabled
0 1e+06 2e+06 3e+06 4e+06 5e+06 6e+06
0 5 10 15 20 25 30
bps
link number
Reconverged IPRT IPRT no deflect
Figure8.16: Uninett,withatlink-ost
0 1e+06 2e+06 3e+06 4e+06 5e+06 6e+06
0 5 10 15 20 25 30
bps
link number
Reconverged IPRT IPRT no deflect
Figure8.17: Uninett,withlink-ostenabled
0 1e+06 2e+06 3e+06 4e+06 5e+06 6e+06
0 5 10 15 20 25
bps
link number
Reconverged IPRT IPRT no deflect
Figure8.18: Cost239,withatlink-ost
0 1e+06 2e+06 3e+06 4e+06 5e+06 6e+06
0 5 10 15 20 25
bps
link number
Reconverged IPRT IPRT no deflect
Figure8.19: Cost239,withatlink-ostandQoSQbit
8.3.1 Coverage
Of the results obtained from the simulation runs, the overage results show the most
importantfeatureofIPRT.BothIPRTandRRLareprovenapableofdelivering100%
overage,whih isanexellentresultonsidering thismaybethesinglemostimportant
property to legitimate the use of extra resoures in a network in order to provide IP
fastreroutereovery. However,IPRTis abletoprovidethisoverageusing asmall and
onstant amount of additional state information. In these tests RRL needed between
twoand seven reoveryFIBs (see g. 8.1) while IPRTused aonstantamount of two
additionalFIBs.
BeauseithasbeenprovenintheorythattheIPRTmethodshouldbeabletoprovide
100 % overage, the results seems to verify that the IPRT simulator model has been
implementedorretly. Sinenodefailurehasbeenusedastheonlyfailure-modelinthis
thesis,ithasnotbeenshowninthesimulatorthattheIPRTsolvethelast-hopproblem.
However,followingdiretlyfrom thetree-generation proess itis proven in theory that
IPRT does solve this problem without the need of any additional funtionality in the
IPRTmodel.
8.3.2 Path-length
Theresultsobtainedfromthepath-lengthtestsshowsthatIPRTisapableofdelivering
shortreoverypaths. Thisisanimportantpropertybeausethenumberoflinksusedto
forwardthepaketsinuenediretlyonthetotalamountofloadgeneratedinanetwork.
When thenumber of links used to forwarda paket inreasethe total loadinrease as
thepaketgenerateloadonalllinks ittraverse.
Thegraphsshowthatallnormaltra aetedbyafailurehasapath-lengthoftwo
or more. This is beause the measured paths show the path-length of tra aeted
by failure that is bound for an operationalnode. Beause the destination needs to be
downstream of the failure to beaeted bythe failure, the path-lengthneeds to be at
leasttwohops. Insomeirumstanes,whenlinkosthasbeenenabled,thepath-length
after a re-onvergene beomes only one hop. This is beause the re-onverged tra
thenfollowsapathwithhigherost.
Furthermore, it may be observed that the routes obtained after a re-onvergene
are shorter than the reovery paths obtainedfrom both RRL and IPRT. This may be
explained from thefat that are-onvergenemaybeompared to thebest result that
aglobalreoveryouldprodue. Furthermore,bothRRLandIPRTneedsto implement
a loal reoveryproedure resulting in paths that may need to baktrak upstream of
thefailure. Inaddition,bothRRLandIPRTareusingrestritedsub-topologiestoroute
paketsaetedbythefailureasaresultofthelayerreationortreereationneededto
guaranteefulloverage.
ofreoverypath-lengthdistribution. However,thetestresultshould onlybeonsidered
togiveindiationsontherelativeperformaneofIPRT.RRLwasnottweakedtoobtain
goodresults,andthenumberoflayerswassettotheminimumnumberoflayersthatthe
layergeneratorouldprovideforeahtopology. Furthermore,RRLouldusemorelayers
toprovidewithshorterreoverypaths.
8.3.3 Load distribution
In this setion, IPRTs general ability to distribute load is analyzed. In addition, it is
shownthattheuseofdeetion,i.e. theabilitytomoveaIPRTpaketwithaREDFIB
ID to aBLUE FIB ID,doesinreasethe loadin some worst-asesenarios andshould
beavoided. TheQoSspei properties,i.e. theabilityto respondtolink-ostand QoS
Qbit,aredisussedinthenextsetion.
The measurementsobtained from the post-failureload-distribution experiment give
information on several aspets of the IPRT reovery proedure. The most important
observationsarelistedanddisussedbelow.
•
IPRTisgenerallyapabletofollowtheloaddistributionobtainedatre-onvergene.•
Themedian loadisgenerallyhigherwhenIPRTisused(seeg. 8.4).•
InsomefailuresituationsIPRTinreasethemaximumloadonspeilinkssignif-iantly.
Inthemeasurementsobtainedfromsimulatingthere-onvergedstatein thenetwork,
thefailed nodes havetra bound for them. Thus, the amountoftra introduedin
the network does notdier between the IPRT reoverysenariosand the re-onverged
senarios.
In thesenarioswhere IPRT reoveryis used, onlythetra aetedby thefailure
is rerouted by the IPRT reoveryproedure. In most failure situations the tra will
beunaeted bythe failure, allowingthetra to beforwardedaordingto theFIBs
obtained from the normal routingproedure. Whenre-onvergene is used, the routes
willbeverysimilartothenormalroutingtable,asonlytheshortestpathsaetedbythe
simulatedfailurearealtered. Thusitmaybeexpetedthatmostofthetraintrodued
inthenetworkwillfollowthesamelinksandthustoagreatextentallowtratofollow
thesamepathsin bothfailure-freeand failed situations. This isalso validwhen ostis
usedasthelink-ostisnotaltered,exeptforwhenthere-onvergeneissimulated,and
thenonlylinksaetedbythefailurearealtered.
Theredundanttreesaregeneratedtoprovidewithreoverypathsthatarelosetothe
shortestpathavailable. Thus,itislikely,thatthereoverypathsfollowthere-onverged
shortest pathin a losemanner. However, beause theIPRT redundant treegenerator
asmallextent,besomedeviationfrom theshortestpathatmosttimes.
Thepathsfoundinther/bTablesarebasedoneahindividualnodespairofredundant
trees. ThisshouldenableIPRTtoprovidegoodspreadoftradownstreamofafailure.
However, in this implementation itis partly governedby hane. I.e. if there is alink
with low ostdownstreamof the failure andlink-ost is used, it is ahigherprobability
thatthelinkwillbeinludedinalltrees. However,beauseoftheredundantpropertiesof
theredandbluepathsthelinkwillprobablynotbeinludedinalltheavailablereovery
pathsdownstreamofthefailure.
Network Link-ost Deet avg totalin min linkin max link in
Abilene
Table8.4: IPRTmedian throughputompared tore-onvergedvaluesontotalloadand
link-levelload(*doesnotinludemeasurementswherere-onvergedlink-loadiszero)
The general inrease in the median load when IPRT is used, is aused by the fat
that IPRT is using aloal reoverystrategy. Whenusing a loal reoverystrategythe
lengthofthereoverypathsusuallyontainsmorehopsthanifaglobalreoverystrategy
is used. It is apparent from the path-length experiments that this is valid for IPRT.
Beausemorelinksareusedtoforwardthetraasinglepaketthathasbeensubjetof
reovery,is bound to generatemoreloadasmorelinks are usedtotransportthepaket
toitsdestination.
Furthermore,someload-spikesmay be observedin theresults from thesimulations.
Itmaybeobservedthatitisduring onlyafewofthefailuresituationsthat aload-spike
ispresentbeauseofthedeviationbetweenthemedianvalueandthehighperentile. An
exampleonsuhspikesmaybeseenin Figure8.12and8.13onlink 2(onnetingnode
1and 2) and link 3(onneting node3 and4), similar examplesare alsopresentin all
theother topologies. There areseveral reasonsto whythespikesome to presene but
tra bound for failed nodes are subjet for the reovery proedures of IPRT.
Furthermore,theinitial yle used whengenerating the redundanttrees follows a
shortestpath startingandending in therootnode. This approahmakesit likely
that the reovered tra destined to the failed node to be ontained in a near
geographialproximityofthefailednodeandthusreatingahot-spot oftra.
2. Whenreoveredtraenountersafailurefortheseondtime,i.e. reoveredtra
withthefailednodeasdestination,thetrafollowingaredpathistriedreovered
aseondtime. Inthesimulationsusedheretheonlytrathatis subjetforthis
deetion is the tra bound for the failed node, thus inreasing the hot-spot
eet. Generally, the amount of tra that is deeted equal to half the tra
bound for the failed destination. This may be observed from the measurements
performedwithdeetionturnedo.
The observed eet from these two irumstanes are further inreased by the
re-onvergedsenariostraboundforthefailednodeisnottriedreovered.Inaddition,the
tramatrixusedtovarytheloadgeneratedbythetrageneratorsontainvariations
intheamountoftraboundforanodeandafewofthetrageneratorsgeneratesan
aboveaverageheavyload.
To verify the ndings the simulation of the Abilene topology, where the example
load-spikes were shown, was repeated and the results may be seen in gure 8.20 and
8.21. However,in these experimentsall trabound forafailednode wasprunedfrom
thenetwork. I.e, thetra generatorssending tra tothe failed destinationwerenot
installed. Thus, the results obtained from these simulations ontains less tra than
thepreviousonduted experiments,andmaynotbeompareddiretly totheprevious
showngraphs. Furthermore,theresultsdoesnotshowanauratepitureof howIPRT
would perform as thetra should betried reovered. I.e., the upstreamnodeshould
presumethatallfailuresarelink-failures,asthisapproahistheonlyapproahthatmay
guarantee100%overageofallfailures,i.e. thelast-hopproblem. However,theresults
obtainedhereseemtoonrmthelaimthatthereoveryofpaketsboundforthefailed
nodeisresponsiblefortheload-spikes.
The observedinreaseinloadmakesit learthat theprobabilistiapproahto
pop-ulate theQbittables -inorder toensureloalreovery,is apoorhoie. Thedeetion
resultin ainreasein link-loadwhen thedestination nodehas failed. Thus, thebetter
hoiebetweentheprobabilistiandexatapproah,isthelatterapproah-eventhough
thishoierequiresasmallinreaseinomputationalrequirements.
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.
•
Beauseoftherequirementofadegreeofthreeormoreonthenumberoflinksonly asubsetofthenodesin thenetwork maypotentiallybenetfrom QoSQbit.•
Theredundanttreesaregeneratedinsuhawaythattheyleandarhesaretriedkept 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. Further-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 pathbeinghosen.
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
link-ostinaIPRTenablednetwork.Thisisapparentfromthelink-load,where somefailure