Seleting best FIB for storing Qbit

5.4 F orwarding

5.4.1 Seleting best FIB for storing Qbit

Theexatloationto plaeQbit informationmay inuenethenumberofneededtable

lookups in afailure situation. There aretwopossibilitieswhen storingthis information

-therstreoveryFIBto beaessedwhenafailurearise orthenormaloperationFIB.

None of them adds to the worst ase senario in number of lookups, but they might

hangethedistributioninnumberoflookupswithin theoriginalrange.

IftheinformationisstoredintherstaessedreoveryFIB,i.e. theredreoveryFIB

thentheaveragenumberoflookupsmightgrowwhenomparedtotheoriginalforwarding

proedure. Thisisbeausethequalityinformationintroduesasituationwheretherst

triedlookupmightyieldavalidresultthatatthesametimeisundesired. Thus,aseond

reoverylookupwouldhaveto beperformed,andthereisnoguaranteethat thislookup

wouldyieldanentrynotaetedbythefailure.

If theinformationisplaedin theFIBused fornormalinformationthis tablewould

growinsize. Theimpattheinreaseinsizewouldhaveonrealperformaneisdepending

onthe implementation oftheFIB andthe lookupproedure. However,whenthe

infor-mation is plaedin the normaloperationFIB the numberof lookups may be redued.

When afailure is deteted the best table is then alreadyknown and the rst reovery

lookup maytrythis table. If the rsthoiefails the nexttable would betried. With

thisapproahtheaveragenumberoflookupsshouldbeaboutthesameasfortheoriginal

forwardproedure. However,sinethelookupordermighthavebeenhangedtheaverage

numberof lookupsmightbe skewedwhen ompared to theoriginal proedure,but this

wouldbedepending onbothIPRT routingalgorithmsand topologies. I.e. this enables

thelookupproeduretotrythepreferredFIBrstandbydoingthisthehaneofgetting

avalidresultfromthersttriedreoverytablethatdoesnotyieldthepreferredreovery

pathisnon-existent.

Both solutions may be used with the r/bTable solution and only needs to use one

additionalbitindiatingeithertheredorbluetree. Foranimplementationinasimulator

thesameamountofmemoryisneededforallombinationsandthusonlythenumberof

lookupswillhavearealimpatonsimulationtime.

IPRT Implementation

The IPRT implementation is divided into two distint parts; the IPRT tree generator,

andtheextensions totheJ-simnetwork simulator. Thetreegeneratorisused tomimi

partsoftheIPRTroutingprotool,andisresponsibleforreatingthereoverytopology

foreahnodeinthenetwork.TheJ-simextensionsusethesepre-alulatedtopologiesto

populatetheFIBsateahnode,andin additionprovidethemodulesneededtosimulate

IPRTenablednetworks.

ThereasonforseparatingthesimulationenvironmentandtheIPRTtreegeneration,

wasinitially to provide an easier start on the programming assignment for this thesis.

This approah allowed the graphenvironmentto be tailored for IPRT tree generation.

Furthermore,severalmethodsformappingtheresultingtopologieswerereadilyavailable

in J-sim. Thus, this approah provided tried methods for representing topologies and

populating the FIBs, and was therefore less prone to failure. After the generator was

implemented, no big drawbaks were present, removing the need to merge the J-sim

implementation and the generator. Another advantage is that the reoverytrees of a

topology may be omputed one, and subsequently be used in an arbitrary number of

experiments,thusuttingthetimeneededtoprepareasimulatedsenario. Theseparated

environmentallowsthetreegeneratortobefreelyusedindependentlyofthesimulator.

Theimplementationhasfourgeneralrequirementstothetopologyandtheaddressing

sheme.

•

^The^networks^used^must^be^at ^least^two-vertex^onneted.

•

^The ^node^id ⁱⁿ ^the ^graphs,^and^the ^IP ^addressing^sheme^used ^during simulation, mustorrespondtoeahother.

•

^The^nodes^must^be^given^addresses^ranging^from ^zero^to

n − 1

•

^The^link^ost^must^benon-negative,andassignedinsuhamannerthatthelowest weightindiatesthelinkthat ismostlikelytobeused.

Thereasonsfortheserequirementswillbelariedinthefollowingsetions.

The IPRT tree generator is implemented as a standalone appliation using the Java

programminglanguage. Itsprimarytaskistoalulatetheredundanttreesofatopology.

In addition, theimplementation providesan optional apability to onsider QoSin the

tree generationproess. It mayuse link-weightwhen onstrutingtheyle and arhes

ofatree,andfurthermore,itmaybeonguredto omputeQoSQbitinformation.

The IPRT tree generator isimplemented in asimple manner, followingthe original

RTalgorithm asloselyaspossible. Asit is meantto beused oine, itdoesnot fous

onahievingoptimized run-time. Thus, optimal run-timeis traded forsimpliity and a

tidyode-base. Toprovideaneasywaytohangebetweendierentseletion-algorithms

should theneedarise, themethods arekeptasmodularized aspossible. TheIPRTtree

generatorontainsseverallasses,shownin Table6.1.

TheoreresponsibilitiesfortheIPRTtreegeneratorare:

•

^Create ^a^graphrepresentationoftheoriginalnetwork.

•

^Generate^a^series^of^redundant^tree^pairs,^so^that^every^node^beomes^the^root^node

ofaredandbluetree.

•

^For^eah^node,^generate^Qbitinformationneededtoensureasuessfulloal reov-eryproedure.

•

^Present^the^reated^reovery^trees^and^Qbit^tables^so^that^they^may^be^easily^utilized

in theJ-simenvironment.

Theresponsibilitiesaredesribedin moredetailinthefollowingsetions.

Class Desription

Node Usedtorepresentthenodesinthenetwork.

Link Usedtorepresentthelinksin thenetwork.

Graph Administrationoflinksand nodes.

RTGen Mainlass.

Qbit UsedforreatingQbitinformation.

CreateTreesQoS Usedforreatingredundanttrees.

VerifyTrees Usedtoverifypropertiesoftheredundanttrees.

NodeOrder Usedforsortingandomparingnodes.

FileHandler Usedforreadingandwritingles.

Djikstra Djikstraimplementation.

Table6.1: RTGenlasses

WhentheIPRTtreegeneratorstarts,itsrstresponsibilityistoreateagraph

represen-tationofthenetworkfromaninputtopology. Thisgraphisusedprovidethefoundation

from whih the redundant trees may be generated. Furthermore, at a later stage, the

graphenvironmentis used to representthe redundant trees. Inthis setion, the initial

mappingof theoriginalgraphandtheoptionsoeredwill bepresented.

TheIPRTtreegeneratormodelsthenetworkbyrepresentingbothlinksandnodesas

objets. Thisapproahgivesagoodrepresentationofthenetwork,and allowsarbitrary

amountsofinformationtobeassoiatedwithbothlinksandnodes. Furthermore,an

ad-jaenylistrepresentationisusedtoonnetthenetworkentities. Thelistrepresentation

foresanysearhforagivennodeorpropertyto iteratethelistfrom thetop. However,

it is notaeted by any deline in onnetivity, and is the preferreddata struture for

anygraphthathassparseonnetivity,e.g.

|e| < |v ² |

^. ^However,^the^amount^of^nodes^to

beusedinthenetworksthattheIPRTtreegeneratoristoompute,isnotbigenoughto

haveanygreatinueneontheseletionofthedatastruture. Nevertheless,alinkedlist

representationwasusedintheimplementation,asthisisthestandardforlowonnetivity

graphs.

The implementation only supports one link between any given pair of nodes. This

is donetoprovideaneasiergraphenvironmentfortheIPRTtreegeneration algorithm.

Furthermore,itwasnotneeded morethanone link betweenanynodes in the topology

usedtoondut theexperiments.

Speifying link-ost

Themostimportantoption,thatmaybespeiedwhenreatingtheinitialgraph

repre-sentationof the network,ishow thelink-ost is represented. Depending on thehoie,

this will, atalater stage,deideiftheredundanttreeswill bereatedaordingto the

link-ost speiedbytheinput topology, andthus showthe ability ofIPRT to respond

totheuseoflink-ost.

Whenmappingtheoriginalnetwork,theIPRTtreegeneratorprovidestheoptionof

usingthelink-ostspeiedbytheinputtopology,ortoignorethis information,andset

aat oston all links. Thedefault behaviorof the generatoris to use aatlink-ost.

Beause of limitations in the IPRT seletion-algorithm, the weight used to represent

the link-ost must be non-negative. Furthermore, it is assumed that the link-ost is

symmetri,i.e. theostofalinkdoesnotdependonwhihdiretionthelinkistraversed.

Thereasonforhoosingthisapproah,wasalsotoprovideaneasierenvironmentforthe

IPRTtreegenerationalgorithm.

6.1.2 Creating the redundant trees

Theredundanttreesreatedinthisimplementationsupportreoveryoftraausedby

asingle nodefailure. Furthermore,the treegeneration proess honoursthelink weight

setion themethod used to reate thetreesis reviewed. Theimplementationhas three

maintasksitattends to:

•

^It ^must^ensure^that ^all^nodes^is^the^root ^of^a^pair^of^red^and^blue^trees^and^inform

theuserifthis fails.

•

^It^isresponsibleforidentifyingtheylesandarhesthatformtheredundanttrees.

•

^It^must^guarantee^that^the^trees^are^generatedⁱⁿ^a^orret^fashion^aording^to^the

voltagerule.

To reate all the redundant trees, the proess iterates throughall the nodes in the

network and uses eah node as the root of a red and blue reoverytree. If it at any

stage failsto buildthetree pairs,theomputationwill behalted,andanerror message

produed.

When reatingeahindividual pair of redundanttrees, the IPRT algorithm tries to

follow the original RT algorithm as losely as possible, i.e. the redundant trees are

generated by growing them in a series of stages. Furthermore, the algorithm used in

IPRTisimplementedinagreedymanner,wherethealgorithm,ateahstage,hoosethe

shortestyleandsubsequentlyarhesavailable.

Theseletion-algorithmused,i.e. thealgorithmthathoosestheyleandthearhes,

is asimple implementation of the Dijkstra algorithm that onsiders theweight oflinks

whensearhingfortheshortestpathtree. Thisalgorithmwashoseninordertokeepthe

lengthoftheyleandarhestoaminimumateahstage. Furthermore,itisimplemented

in suh a manner that it is able to avoid any nodes that are already ontained in the

redundanttreesgeneratedatthisstage.

A andidate node indiates a node that is not in the tree itself, but whih has a

neighborontainedin thetree,i.e. itisanodeattheborderofanodealreadyaddedto

thetrees andthus astrongandidate to be inorporatedin theredundant treesat this

stage.

To generate the initial yle, the andidate nodes are identied. Furthermore, a

shortest-pathtreeisgeneratedforeahandidatenode. Inthisshortestpathalulation,

the root is avoided and is thus not inluded in the searh. Subsequently, eah tree is

hekedtondthepaththatprovidesthesmallestostbetweenanytwooftheandidates,

inluding the ost needed to reah the root node from eah tested pair of neighbors.

The shortest of these paths is subsequently used asa basis for the initial yle. If no

path isfound betweenthe andidate nodesit is onsidered afailure, and theexeution

is halted and an error-message produed. This approah guarantees that if the initial

yle is found, it ontains at least two nodes in addition to the root node. A possible

optimizationouldbedereasingthenumberofshortestpathtreealulations. However,

additiontoalulatingtheshortestpathtreesfromeahandidatenode,eahandidate

is individually examined to determine ifit has twoormoredistint neighbors that are

ontained in the redundant trees. By adding this last hek, the arhes may ontain

oneormorenodesin addition to the startand end nodes, that are alreadypartof the

redundanttrees.

When assigning the voltages, the maximum voltage is derived from the number of

nodes in thenetwork. Furthermore,thevoltagesassigned are distributed evenlywithin

a voltage range. The voltage range is onstrained by the highest of the two voltages

obtained from the head and tail of the yle or arh, and the voltage assigned to the

tree that is immediately beneath the rst. With this approah, the worst possible

as-signmentsenarioentailsthat arhesof minimalsizeisaddedin suhafashion thatthe

available voltagerange is utin half with eahnew added arh. Toounterthis eet,

theimplementationrepresentsthevoltagesusing adoublerepresentation. Additionally,

arelativelylargemaximumvoltage isused. If thevoltage rangeshould proveto betoo

small to be represented,the implementation will haltthe tree generation,and produe

anerrormessage. Othervalidapproahesmighthavebeentoprovideamaxvoltagethat

ouldbeprovenlargeenoughgiventheworst-asesenario,orto rearrangethevoltages,

should theneedarise. Ifthevoltageswere toberearranged,itwouldbeimportantthat

the ordering ofthe nodes waskeptintat. However,the worst-asesenariois unlikely

tohappeninpratie,andtheimplementedapproahhasproventobeadequateforthe

topologiesused inthisthesis.

Byutilizingthisgreedyapproahtoonstrutthetrees,theimplementationprovides

anapproximationtotheoptimalsolutionforeahpairofreoverytrees. Thereasonfor

hoosing this approah, is that it might resemble an approah that ould be pratial

to implement in a real-life routingprotool. In this manner, the greedy approah will

providewithresultsthataremorerealisti.

6.1.3 Calulating Qbit information

The Qbit information alulatedin theimplementation maybe used for two purposes.

Firstly, it is to be used to ensure the provisioning of loal reovery. Seondly, it may

be used for seleting the shorter of two valid reovery paths when available. In the

implementation, thebits set to ensure orret forwardinghaspreedene overany QoS

optimizations. Both methods for populating the Qbit are optional, allowing for more

experimentationwithdierentongurations.

The Qbit has three states. Thetwo rst indiate if either the red orthe blue tree

provideswiththe shortestreoverypath,and whether theost towardsthe destination

isequalforbothreoverypaths. ThelaststateisnotneededtopopulatetheQbittable

orretly,but isused inthe implementation toenablethemeasurementofthe senarios

wherethismehanismisuseful.

In thedesign hapter,twooptions were presentedfor reatingtheQbit information

used to ensure a suessful loal reovery proedure: The Qbit information ould be

oraprobabilistiapproahthat fores theuseof theredpath,if theneighbortopology

ouldresultinareoverypaththattraversedthefailure. Inthisthesis,thelatterapproah

wasused.

Thereasonsforhoosingthislatterapproahweretwofold. Theimplementationofthe

statiroutingprotool intheJ-sim simulatorusesaspeializedandoptimized

shortest-pathrouteomputation,makingitdiulttoidentifytheshortestpathusedduringthe

simulationintheIPRTtreegenerator. Furthermore,thegraphrepresentationusedinthe

J-sim implementation diers from the representation used in the IPRT tree generator,

making it hard to map the outgoing interfaes to orrespond between the IPRT tree

generatorandtheJ-simLSDB.Thus,theimplementationofthetreegeneratorpopulates

theQbitbaseduponthepreseneofatopologyenvironmentthatpotentiallyouldresult

in an invalid reoverypath. It is antiipated that this approahmay provide lessthan

idealQoSQbitresults,astheimplementedapproahmayidentifyfalsepositives,reduing

theabilityto freelyonguretheQoSQbitforadditionalsoure/destinationpairs.

In ordertoalulate theQbitinformationused to ensureasuessfulloal reovery,

theimplementationiteratesthroughallpairsofredandbluereoverytrees. Foreahset

of trees, all the nodes are examined to see if the unionof neighbor nodes ontainedin

theredandblue tree,dierfromtheneighbornodespresentintheoriginal topology. If

therearemorenodespresentintheoriginaltopology,theredandbluereoverypathsto

therootnodearetraversedin ordertohekifanyofthemissingneighborsarepresent

inthesepaths. Ifmissingneighborsarefoundinbothpaths,theQbitissettofollowthe

red pathtowards theroot ofthe tree. If theyare present in onlyoneof thepaths, the

oppositeolorissetin theQbittable.

The method used for alulating the QoSQbit uses a shortest-pathalgorithm that

alulates the ostfrom theroot node to allother nodesin eah tree. Foreah pair of

redundanttrees,thenodesareexaminedto seeiftheostdiersbetweenthetwotrees.

If the Qbit is not already populated by the forwarding orretion method, it is set to

identifytheshortestpossiblepathtowardstherootofthetree.

6.1.4 Results

TheresultsobtainedbytheIPRTgeneratorarewrittentothreedierentles,separating

thetopologyrepresentations,Qbitsandlink-ost.

6.2 J-sim implementation

TheextensionstotheJ-simimplementationoveradiversityoftasks. However,themost

importantarethemethods thatsupportpopulatingmultiple FIBsat eahnode,i.e. the

routingprotool, and the ability to performreoveryand properlyforward tra both

stage provides themethods needed to ongure the simulatedenvironmentbefore the

simulation is started - suh as building the network, populating the FIBs, preparing

the tra generators,and sheduling failures. The nextstage,the Operational-stage,

providesmethodsfororretIPRTsimulationaordingtotheongurationsperformed

intheSetup-stage,suhasforwardingwithorwithoutIPRTreovery,simulatingfailures

andperformingmeasurements.

Many of the J-sim extensions implemented in this thesis are inspired by the J-sim

implementation of RRL. Most of the lass struture is gatheredfrom this

implementa-tion, andsomeof thelassesare used withonly minorhangesto variable names. The

hanges in variable nameswasintendedbothas anexeriseto enableunderstanding of

thestruture,andtoseparatethetwoimplementations. Theselassesareusedtosupport

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

5.4 F orwarding

5.4.1 Seleting best FIB for storing Qbit

•

•

•

n − 1

•

•

•

•

•

|e| < |v 2 |

•

•

•

|e| < |v ² |