Dynamic load balancing in WDM Networks

UNIVERSITY

OF TRENTO

DEPARTMENT OF INFORMATION AND COMMUNICATION TECHNOLOGY

38050 Povo – Trento (Italy), Via Sommarive 14

http://www.dit.unitn.it

DYNAMIC LOAD BALANCING IN WDM NETWORKS

Mauro Brunato, Roberto Battiti, Elio Salvadori

June 2002

Technical Report # DIT-02-0011

Dynamic Load Balancing in WDM Networks

Mauro Brunato Roberto Battiti Elio Salvadori

UniversitadiTrento,

DipartimentodiInformaticaeTelecomunicazioni, viaSommarive14,I-38050PantediPovo(TN),Italy

Email: brunato|battiti|salvador@dit.u nitn .it

June3,2002

Abstract

In this papernew load balancing techniques are proposed based on IP-like routing, where the forwarding mechanism is only driven by the destinationaddress. Theaimofthisworkistoconsidertheapplicability ofthisapproachinthecontextofopticalnetworks.

Theproposedalgorithm(RSNE|ReverseSubtreeNeighborhood Ex-ploration)implementsalocalsearchtechniquewherethebasicstepisthe modicationofasingleentryintheroutingtableofanode. Arandomized methodwithreduced computationalcomplexity (fRSNE| fastRSNE) is alsopresented andanalyzed. Bothschemesallowanincremental imple-mentationwherelocalsearchstepsarecontinuouslyperformed astraÆc conditionschange.

Experimentsunderstaticand dynamic(time varying)traÆc scenar-ios show a rapid reduction of the congestion. The performance of the incrementalschemewhiletrackingachangingtraÆc matrixis compara-bletothatobtainablethroughthecompletere-optimizationofthetraÆc, whiletherandomizedimplementationisparticularlyeÆcientwhenscaling propertiesareconsidered.



Inpresentdaysweexperienceanincreasingbandwidthdemand caused bythe exponential Internet growth and the introduction of communication-intensive applications. In this framework, techniquessuch as optical Wavelength Divi-sionMultiplexing(WDM)androutingschemessuchasGeneralizedMulti Pro-tocolLabelSwitching(G-MPLS)havebeenproposed. InWDMnetworks,each ber carries multiple independent data streams on dierent carriers in order to achieve complete spectrum utilization. Relevant eorts are beingspentto assignawavelengthtoeachdatastreaminsuchawaythatalltraÆcishandled in theopticaldomain, withoutanyelectrical processingontransmission[4].

Current advances in optical communicationtechnology arerapidly leading to exible, highly congurable optical networks. The near future will see a migration from the current static wavelength-based control and operation to moredynamic IP-orientedroutingandresource managementschemes. Future opticalnetworksdesignsshould probablybebasedonfastcircuitswitching,in whichend-to-endopticalpipesaredynamicallycreatedandtorndownbymeans ofsignalingprotocolsandfastresourceallocationalgorithms.

IPmodicationsarebeingproposed totakeQoSrequirementsinto account and tointegratetheIPprotocol within theopticallayer. At thesametime,a generalizedversionofMulti-protocolLabelSwitching(G-MPLS)isbeing devel-opedtoenablefastswitchingofvarioustypeofconnections,includingIPbased lightpaths. As soon asprotocol modications can ensure dierent QoS levels at theIP level, moreand more staticallyallocated traÆc can be transmitted on thedynamic portion of the network leading to anall optical and fully dy-namicG-MPLS controlledopticalcloud[21]. Inthis scenarioitisnecessaryto study theimpactof routingmechanismstypicalofthe IPworld, by analyzing thepossibleintegrationoflabelswitching techniques (MPLS)withthecurrent opticalswitchingarchitectures. Inaddition,itisimportanttostudycriteriaand algorithmstodecidewhenandhowlightpathallocationandreleaserequestsare generatedin thepresenceofdata traÆc.

Theoptimization in the usageof scarce resourcesin opticalnetworks with WDM technologyleadstotheproblemsofpacketrouting(inpacketnetworks) andofcreatingvirtualconnectionsbyconsideringbothroutingandwavelength assignment. Some seminal papers are [6, 19, 17, 1, 24]. A review of algo-rithmsfordesigningvirtualtopologiesdirectlyontheopticallayerispresented in [10]. The network evolution in terms of traÆc amount and exibility re-quirementsindicatesthat meshnetworksmustbeconsideredinsteadoftypical SDH/SONET-likering topologies, thus opening amore complex scenario. A novel heuristic approach for thedesign of WDM networks under static traÆc demands is described in [13]. The work [2] considers thephysical topologyas completelyassignedandexploitstheresourcesoftheopticallayerforthedesign ofthevirtualtopology. Heuristicsforthedesignofvirtualtopologies,basedon greedyprinciples[18]oronlinearprogramming[8]havebeenrecentlydiscussed. Routingthat takesinto accountthecombinedtopologyandresourceusage information attheIPandoptical layers[7],withconstraintsonthemaximum delayornumberofhops,isanareathatdeservesadditionalexploration. Paper [23]investigatesdistributedcontrolmechanismsforestablishingall-optical con-nectionsinawavelengthroutedWDMnetwork: anapproachbasedonlink-state routing,andonebasedondistance-vectorrouting. A novelalgorithmfor

inte-developedin[7]. Anotherfundamentalissuewhendesigningnetworkalgorithms istheirabilitytofunctionwiththelimitationsofadistributedenvironment,i.e. localanddelayedinformation. Work[11]considersthecasein whichnodes ex-plorealimitedportionofthesearchspacebyconsideringonlyacertainnumber oflinks alongapath.

Thetechnologicalcontextof ourproposalissummarized inSection 2,then theReverseSubtreeNeighborhoodExploration(RSNE)algorithmisintroduced in Section 3. In Section 4 a randomized implementation and an incremental implementationaremotivatedanddescribed. InSection5anILPformulationof theproblemisgiveninordertocomparetheproposedalgorithmswiththeactual optimum values, at least for small networks. Finally, in Section 6 simulation resultsareanalyzedbyconsideringboththestaticandthedynamictraÆccases.

2 Adaptive routing and load balancing

Thepurpose ofLoadBalancinginWDM basednetworksisto reducethe con-gestionin thenetwork. Thecongestion isrelatedtodelaysin packet switching networks, and therefore reducing congestion implies better quality of service guarantees. In networks based on circuit switching (see for example the G-MPLS protocol), reducing congestion implies that a certain number of spare wavelengths are available oneverylink to accommodate future connection re-questsortomaintainthecapabilitytoreacttofaultsinrestorationschemes. In addition,reducingcongestionmeansreducingthemaximumtraÆcloadonthe electronic routersconnectedtothebers.

LoadbalancinginWDMnetworksconsistsoftwosubproblems:thelightpath connectivityandthetraÆcroutingproblem. Theroutingproblemhasitsorigin at thebeginning of the networking research, see [16] for a review of previous approachesto theproblem. Inparticular, adaptiverouting,that incorporates networkstateinformation intotheroutingdecisionisconsidered in [15]in the contextofall-opticalnetworks,whilepreviousworkonstate-dependentrouting withtrunkreservationintraditionaltelecommunicationsnetworksisconsidered in [14]. It is also known that ow deviation methods [5], although computa-tionallydemanding,canbeusedtondtheoptimalroutingthatminimizesthe maximumlinkloadforagivennetworktopology.

Because global changes of the logical topology and/or routingscheme can bedisruptivetothenetwork,algorithmsthatarebasedonasequence ofsmall steps (i.e., on local search from a given conguration) are considered. In [9] \branchexchange"sequencesareconsideredinordertoreachanoptimallogical congurationin small steps, upperandlowerbounds forminimum congestion routing are studied in [22] that also proposes variable depth local search and simulated annealing strategies. Strategies based on small changes at regular intervalsareproposed in[16].

Our technological context is that of dynamic lightpath establishment in wavelength-routed networks reviewed in [23]. We therefore assume a mecha-nism to assign resources to connection requests, that must be able to select routes, assign wavelengths and congure the appropriatelogical switches, see also[7]forintegratedIPandwavelengthroutingand[12]forablockinganalysis in thecontextofdestinationinitiated reservation.

ing strategies,where thenexthop at agivennode isdecided onlyby the des-tination of the communication. In particular, we consider a basic change in thenetworkthat aectsasingleentryin asingleroutingtable. Inthecontext of all-optical networks this is relevant for optical packet switching networks, or for circuit switching networks (e.g. based on G-MPLS) where the optical cross-connectsallowarbitrarywavelengthconversion.

Inthisarticlewebuildonourpreviouswork[3]. Newcontributionsinclude theintroductionandexperimentationofarandomizedversionofthealgorithm, a comparison with an ILP formulation and a largely extended experimental section.

Letus dene thecontextand thenotation. Byphysical topology wemean theactualnetworkcomposedofpassiveorcongurableopticalnodesandtheir ber connections. Thelogical topology is given by thelightpaths betweenthe electronic routers, determined bythe congurationof the OADMs and trans-mittersandreceiversoneachnode. ThetraÆcpatternisavailableasanNN matrix(N beingthe numberofnodesin thenetwork) T =(t

ij

) wheret ij

de-notes the number of lightpaths (or the number of traÆc load units) required fromnodeitonodej. Weassumethattheentriest

ij

arenon-negativeintegers and t

ij

= 0if i = j. A routing table is an array, associated to each node of thenetwork,containingthenext-hopinformation requiredfor routing. Inthe followingwe shall consider IP-likerouting, where the next hop is maintained foreachpossibledestination,regardlessoftheindex ofthesourcenode. Fora giventraÆcpatternandroutingtablesassociatedtothenodes,thesumofthe number of lightpathspassing through each link is called theload of the link. Finally,themaximumloadoneachlinkofapathiscalledthecongestionofthis path. Themaximumloadoneach linkof anetworkiscalled thecongestion of thenetwork.

TheLoadBalancingproblem canbedened asfollows.

LoadBalancing| Givenaphysical network withthelink costs andthetraÆcrequirementsbetweeneverypairofsource-destination (numberoflightpathsrequired),ndaroutingofthelightpathsfor thenetworkwiththeleastcongestion.

3 Local Search for the Load Balancing Problem

ThebasicideaofthenewLoadBalancingschemeisasfollows: startfrom the shortestpathroutingandthentrytominimizethecongestionofthenetworkby performingasequenceoflocalmodications. Foreachtentativemove,themost congested link is located, and partof itsload is re-routed along an alternate path.

Weshall beginwithsomedenitionsandexplanationsofthefunctions and variables. We maintain the set candidatePathSet containing paths that are candidate to replace those passing through the most congested links of the network. Thissetisemptied ateachiterationofthealgorithm.

Givenallroutingtables,everynoded identiesaspanning treeofthe net-work,namelythetreecomposedofalllinks that carrylightpathsaddressedto d (itis atree because ofthe destination basedrouting). Weare interestedin

2. <congestion,congestedLinkSet> calculateLoad(network,traÆc,rTable) 3. repeat

4. bestCandidateLoad +1 5. candidatePathSet ;

6. foreachlink<cFrom,cTo>2congestedLinkSet

7. foreachdestinationnodedestsuchthatrTable[cFrom][dest]=cTo 8. foreachsourcenodesrc 2routingTree(dest,cFrom)

9. removePartialLoad(src,dest)

10. foreachneighbornodenb2neighborhood(src)

11. vl loadonthecandidatepathfromsrctodestthroughnb 12. if(vl=bestCandidateLoad)

13. candidatePathSet candidatePathSet [{<src,dest,nb>} 14. elseif(vl<bestCandidateLoad)

15. bestCandidateLoad vl

16. candidatePathSet {<src,dest,nb>} 17. restorePartialLoad(src,dest)

18. if(candidatePathSet 6=;)

19. <src,dest,nb> pickRandomElement(candidatePathSet) 20. rTable[src][dest] nb

21. <congestion,congestedLinkSet> calculateLoad(network,traÆc,rTable) 22. elseexit

23. untilMAXITERiterationshavebeenperformed

Figure 1: theLocalSearchRSNEalgorithm.

identifying asubtreeofthis tree, andweusethefunction routingTree(d,r) re-turningthesubtreerootedinnoder oftheroutingtreehavingdestinationnode d. TheshadedtreeshowninFigure2isactuallyroutingTree(dest,cFrom), and itcontainsallnodeswhoselightpathsdirectedtodestination destpassthrough nodecFrom. ThefunctionshortestPathRouting(network)calculatestheshortest pathtreeforeachdestinationnodeandreturnsthecorrespondingsetofrouting tables as a matrix. rTable[n] is theroutingtable ofnoden, whose i-th entry rTable[n][i] is thenext-hop node index for lightpaths passingthroughnoden andwithdestination i.

Finally, function calculateLoad(network,traÆc,rTable) returns the network congestiongiventhenetworktopology,thetraÆcpatternandthecurrent rout-ingscheme. Thefunctionalsoreturnsthesetoflinkshavingmaximumloads.

Figure 1 shows a description of our Local Search algorithm used for the LoadBalancingproblem. IntherestofthepaperweshallrefertoitasReverse SubtreeNeighborhoodExploration (RSNE).

Theinitialization section(lines1{2) startsbygeneratingtheroutingtables bythe applicationof theShortest PathRoutingalgorithmto the specic net-work(the costsof alltheedgesareconsidered asuniform). Usingthefunction calculateLoad we initially calculate the load on each link of the network, the initial valueofcongestion (from which thelocal search algorithmstartsits re-searchoftheminimum)andtheset ofcongestedlinks congestedLinkSet. Then candidatePathSet isemptyat thebeginningofeach iteration.

Every iteration of the local search algorithm (lines 3{23) consists of two distinct parts. First, a set of alternate paths for part of the traÆc passing

Downstream

of

src − dest

src − dest

Alternate route (candidate)

Current route

(cFrom,cTo)

rooted at cFrom

Subtree of destination dest

using edge

dest

cTo

cFrom

Other destinations

src

Other most

loaded edges

src

neighbors

_nb

Figure 2: searchspaceforamoveoftheRSNEalgorithm.

through the most congested links is found (lines 6{17): then, once the most promisingcandidatemoveisselected,theroutingtablesofthenetwork(lines18{ 22)are correctedaccordingly,thenthe iterationstartsbyconsidering thenew congestedlinks.

Therstpartincludes thecoreof RSNEalgorithm. Refer toFigure 2fora visualreference. Weconsidereachcongestedlink in congestedLinkSet (loopat lines 6-17). Letusidentify thislink withitsendpoints(cFrom,cTo). Thenthe procedure iterates throughalllightpathsthatuse thatlink. Twonestedloops arepresent: therst(line7)scans theroutingtableofnodecFrom lookingfor alldestination nodesdest using that link. Thesecond (line 8) scansall nodes src whoselightpathsdirectedtodest runthroughcFrom. Thesenodesidentify thesubtreerootedin cFrom oftheroutingtreehavingdestinationdest.

Forevery(src,dest)pairwhoselightpathgoesthroughthelink(cFrom,cTo), wetrytoreroutesuchlightpathbyalteringtheroutingtableinsrc. Todothis, wetemporarilyremovetheloadofthelightpathfromthecurrentroute(function removePartialLoad atline 9)and iteratethroughalldownstreamneighborsnb of src calculating the maximum loadthat would becaused by re-routing the lightpath, provided that the new route does not end up in a cycle and that thecongestededgeisavoided. Thebest alternatepaths,intermsofmaximum load, arecollected into thecandidate set candidatePathSet. In particular, the currentminimumisstoredinbestCandidateLoad. Iftheloadobtainedafterthis traÆcre-routeisequaltobestCandidateLoad, thenthere-routeisaddedtothe candidate set(lines12-13),ifit issmaller,thecandidateset isre-initializedto the current re-route and its load is stored as the new best (lines 14-16). At theendofthealternate pathsresearch,thepartialloadassociatedtothepath

allowthesearchofnewpathswithdierentsourcenodessrc (line8).

InthesecondpartoftheRSNEalgorithm,iftheresultingset candidatePath-Set isnotemptythenonerandomsolutionisselectedfromit(line19),andthe routingtable ofthenetwork isupdated(line 20). Finally, anewvalueof con-gestion andtherelativesetofmostloadedlinks congestedLinkSet iscalculated againinorder tostartanewsearchofalternatepathsthroughthenetwork.

Note that the local search algorithm continues looking for better values of congestion until the set of candidate re-routes candidatePathSet is empty (line22),oruntilagivennumberofiterationshasbeenperformed(line23).

4 Algorithm properties and modications

As anestimateof theCPU timerequiredbythe algorithm,let usconsider its computational complexity of an iteration(lines 4{22)in terms of node visits, i.e. operationsonnodesofthenetwork. Indetail,acounterisincrementedfor eachnodeconsideredin thecandidatepathatline11. Theproposedalgorithm is composed of nestedcycles. Let n be the numberof nodes in the network; if dis thelargest nodedegree, thenumber ofedges is O(nd). The number of iterationsfor theloopat line 6isonly bounded bythe numberoflinks in the network. Each of the two nested loops at lines 7 and 8 may scan almost all nodes in the worst case. Function removePartialLoadmay need to operate on along path(the diameter of the network is potentially equalto n). Loop at line 10 is executed dtimes at most, and thepath checkat line 11 is again bounded by thenumberof nodes. Thenthe complexity of oneRSNEiteration is O(n

4 d

2

). So in the worst case, when d growslinearly 1

with n, the overall complexityofaniterationisO(n

6 ).

However,this isapessimistic, worst-casebound: experiments onnetworks modeledbyEulerdiskgraphs(seeSection6.2)suggestthatthenumberofnode visits(whilethealgorithmisexploringtheroutingsubtreeandcheckingthenew path)hasO(n

)empiricalcomplexitywithslightlyhigherthan2. However, simplications of thealgorithm shall beintroduced in the nextsubsections in ordertolowertheworst-casecomplexityofthealgorithmtoareasonablepower ofnandd.

4.1 Randomized version (fRSNE)

Computational complexityandscalabilityaretwomajorissuesin current net-workalgorithmresearch: algorithmsare requiredtoadapt todierentnetwork sizeswithoutexcessiveslowdown. Inthepresentcase,adrasticreductionofthe computationalcomplexitycanbe obtainedby reducingsomeoftheloops toa xed,smallnumberofrandomchoices. Axed-sizesubsetofthecongestedlinks canbeexploredbytheloopatline6,andaxednumberofrandomdestinations canbecoveredby theloop atline 7. The loopat line 8is basicallyasubtree exploration. Bylimitingthedegreeofthedescentthroughthistree,thenumber of source nodes that are explored canbereduced. Whenall these reductions

1

thishappensinmanyreal-worldcontexts: inInternetautonomoussystemsthereis evi-dence[20 ]ofastrongcorrelationbetweenthelogarithmsofnanddwithacoeÆcientnearto 0.95,sothatd=O(n

:95 ).

are performed together, thecomplexityof aniteration becomes O(n d) in the worstcase(O(n

3

)forunboundeddegree). ExperimentsonthesameEulerdisk graphshavereportedanO(n

)empiricalcomplexity(intermsof nodevisits), with 1:67.

In the following, the randomized version will be called fRSNE(e,d,s) (fast RSNEone edges,d destinationsperedgeanddegrees ofsourcesubtree explo-ration). AsshowninSection6,whencomparedto RSNE,performance degrada-tion of fRSNE(1,1,1)(the randomizedversionwhere one edge, one destination and just onesource subtreepath areconsidered) is almost negligiblein terms ofcongestion,whileaveragehoplengthandaverageedgeloadareonlyslightly increased.

4.2 Incremental version (I-RSNE)

Localsearchheuristicscanbeseenasstepwiserenementsofaninitialsolution byslightmodicationsofthesystemconguration. Inourcase,theRSNE algo-rithmstarts from ashortestpath routingschemeand changes at everystepa routingtable entry ofa singlenode in the matrix. Byperforming many such changes, thesystemstabilizestoalowcongestionconguration.

ThisiterativeschemeisappropriateforadynamicenvironmentwheretraÆc requirements evolve with time. In particular, if changes in the traÆc matrix are reasonably smooth

2

even a small number of steps of the RSNE algorithm in Figure 1 are suÆcient to keep the system in a suitable state as the traÆc matrixchanges. Ofcourse,onlylines2-23mustbeexecuted,becausewedon't want to restart from scratch by calculating the shortest path routing tables. Moreover,averylownumberofiterationsoftheouterloop(lines3-23)mustbe performedat each step,i.e. MAXITER mustbeverysmall to avoidexcessive traÆc disruption. In the following, we refer to the incremental algorithm as Incremental RSNEwithk outeriterationsperstep: I-RSNE(k).

Simulationsdiscussed in Section 6 showthat evena singleiterationof the algorithm yieldsgood resultsunder afairlygenerictraÆcmodel. Thenumber ofiterationsofthealgorithmisequivalenttothenumberofroutingtableentry modications in the systems. Thus, a very limited number of routing table entries must be modied astraÆc evolves in order to keep congestion at low levels. Moreover,I-RSNEisfullycompatiblewiththefRSNErandomizedscheme discussedabove,andexperimentsshowthattheperformanceofthecombination whichshallbecalled I-fRSNEdoesnotdegrade.

Asimilarapproachhasbeenproposedin[19],wherebranch-exchange meth-ods areproposedfor alocal searchheuristic. However,thetypeoflocal modi-cationisdierentfrom ourproposal.

4.3 Restricted Neighborhood Exploration (RNE)

A simplied versionof thealgorithm wasalsotested, which canbecalled RNE (RestrictedNeighborhoodExploration);itonlyconsidersnodecFromasa can-didateforre-routing,withnoexplorationofitsroutingTree (considerthe algo-rithm in Figure 1where theloopat lines 8{17 isexecuted only oncewith src

2

TheassumptionisreasonableeventhoughIPtraÆcisknowntobebursty: infact,traÆc requirementsare givenas an average over a certain amount of time, withsome marginal capacitylefttoaccommodatetraÆcpeaks.

fromthecongestedlinkwithasingleroutingtablechange. However,as simula-tionsinSection6show,suchpolicydoesnotcomparewellwithRSNEandfRSNE, probablybecausetoolargeamountsofloadaremovedateachstep,whilener modicationsaremoreappropriate.

5 ILP formulation

In order to compare the results of the proposed techniques with the actual optimum,thefollowingIntegerLinearProgramming(ILP)formulationcanbe used.

Letusconsiderthen-nodeorientedgraphG=(V;E)whereV =f1;:::;ng and E  V V. For each couple of nodes s;d2 V, s 6= d, let us dene the requestedtraÆcasT

sd .

Foreachi;j;s;d2V suchthat(i;j)2E ands6=d,thebinary owvariable F

ij sd

2 f0;1g is introduced; itsvalueis 1if and only ifdata from source s to destination dis routed throughedge (i;j). The usualset of ow conservation (solenoidal)constraintscanbeimposed(eachfamilyofconstraintsisidentied byanindexedlabelontheright):

X i (i;j)2E F ij sd X i (j;i)2E F ji sd = 8 > < > : 1 s=j 1 d=j 0 otherwise, (FLOW j sd )

oneequationforeachcombination ofj;s;d2V withs6=d. These constraints avoidimbalancesbetweentheincomingandoutgoing owatallnodeswiththe exceptionofthesourcesandthedestination d.

IProutingisdestination-driven,soanewfamilyofbinaryvariablesis intro-duced in order toconsider onlythe owdestination. Foreachd;i;j 2V such that(i;j)2E,letR

ij d

2f0;1gequalto1ifandonlyifedge(i;j)carriestraÆc

towardsdestinationd. ThisinformationcanbeextractedfromtheF ij sd variables byimposingR ij d

=1assoonasthereisatleastonesourcessuchthatF ij sd

=1. Thiscanbeobtainedbythefollowinglinearconstraints:

R ij d F ij sd ; (ROUTE ij sd )

one equation for every combination of indices s;d;i;j 2 V where s 6= d and (i;j)2E.

IProutingisachievedwhenforeverynodeandeverydestinationthereisat mostoneoutgoingedgecarrying owforthat destination, regardlessfrom the source. Thefollowingconstraintsimposethatlimit:

X i (i;j)2E R ij d 1; (IP i d )

oneequationforeveryi;d2V.

AfterimposingIProutingon thegraph,congestion mustbeminimized by introducing anewvariable F

max

F max  X s;d s6=d T sd F ij sd ; (LOAD ij )

forevery(i;j)2E.

Theproblemcan bestatedasfollows:

Minimize F max Subjectto 8 > > > < > > > : FLOW j sd 8s;d;j2V; s6=d ROUTE ij sd 8s;d;i;j2V; s6=d; (i;j)2E IP i d 8d;i2V LOAD ij 8i;j2V; (i;j)2E: (ILP)

This formulation will beused in the followingsection in order to test the RSNEheuristicagainstthe optimalvalueon smallnetworks, andagainst lower bounds determinedby theCPLEXoptimizerif theoptimumsearch couldnot becompletedbecauseoftimelimits.

6 Simulation results

SeveralexperimentshavebeenperformedinordertotesttheRSNEheuristicon dierentnetworksizes andtopologies,bothcomputergeneratedandreal, with staticanddynamictraÆcconditions.

6.1 Experimental setting

Shortest pathandtheproposedheuristicswere simulatedbyaC++ program, with someclassesdevoted to generatenetwork and traÆc instancesaccording tovarious models. Thefollowingnetwork modelswereconsidered:

 random graphs,parameterizedbythenumberofnodesand edgedensity, i.e. theprobabilityof anedgeto existforeverycoupleofnodes;

 Eulerdiskgraphs,parameterizedbythenumberofnodesandbyaradius r,wherenodesarescatteredinaunitsquare,andtwonodesareconnected ifandonlyiftheirdistanceislessthanr;

 real-world networks,withconnectionmatricesreadfromale.

TraÆcmodelsareof thefollowingtypes:

 static uniform matrices, where all non-diagonal entries have the same value;

 static random matrices, where all non-diagonal entries are taken by a uniformrandomdistributionbetweenagivenminimumandmaximum;

 dynamic random matrices, generated as follows (see [16] for a similar model): given two positive integers N and
, consider a sequence of N
+1 traÆc matrices (T 0 ;T 1 ;:::;T N
) where matrices T k
, k = 0;1;:::;N arerandom and independently generated, by choosing a ran-dommaximumvaluebetween10and100andcalculatingeveryentryasa

earinterpolationsoftheimmediatelyadjacentrandommatrices;in other words,givenh=0;:::;
1andk=0;:::;N 1,entryT

k
+h ij ofmatrix T k
+h iscomputedasfollows: T k
+h ij =round  1 h
 T k
ij + h
T (k +1)
ij  ;

 real-world traÆcmatrices,readfrom ale.

Togeneratepseudo-randomsequences,aMersenneTwisteralgorithmof pe-riod2

19937

1wasused 3

. Everyrandom-sensitiveobject(thegraphgenerator, thetraÆc generatorandtheheuristicroutingalgorithms)wasendowedwitha dierentinstance ofthegenerator,in orderto ensureindependenceand repro-ducibilityofinitialconditionsfordierentalgorithms.

The C++ program was also used to output problem instances to les in MPSformatinordertosolvethemviaalinearproblemoptimizer. CPLEX7.1 wasusedtosolvetheseinstances.

6.2 Empirical complexity tests

TheRSNEandfRSNEalgorithmshavebeentestedonrandomEulerdiskgraphs in order to obtain a measure of the growth of computational time (in terms of node visits per iteration) as the network size increases. Euler disk graphs wereselectedbecausetheyshowsomepropertiessimilartoreal-worldnetworks, suchaslocalconnectionschemesandalargernumberofmulti-hoppathswhen comparedwithcompletelyrandomgraphs. Moreover,bylettingthenumberof nodes nincreasewhile keepingtheradiusconstant, thedegreeis proportional ton, thusunbound.

Figure 3plotsthe numberof nodevisits againstthe size (in nodes)of the network: 10samplesforeachnetworksizehavebeengenerated,andbothRSNE andfRSNEhavebeentested. Least-squareslinearregressionhasbeencalculated onthelogarithmictransformsofthedatatoestimatethehighestexponentinthe dependenceformula. Ifvisthenumberofnodevisits,theresultingdependencies arev0:14
n

2:04

fortheRSNEalgorithmandv0:02
n 1:67

forfRSNE.Thus, eventhoughexperimentaldatashowalargevariability,thefRSNEalgorithmhas alowerasymptotic complexity in thecase considered aswell as amuch lower constantmultiplier.

6.3 Tests on static traÆc

ThersttestsoftheRSNEalgorithmaimatassessingitscapacitytooutperform thesimpleshortestpathschemein astatictraÆccontext.

The24-noderegionalnetworkpresentedin [24] andthetraÆc pattern pre-sentedin the samework havebeenchosenfor the rst staticsimulation. We executed 1000stepsof theRSNEandfRSNEschemes andcompared theresults withtheinitialshortestpathconguration.

3

Thecode,writtenbyMakotoMatsumoto(KeioUniversity,Japan)andTakujiNishimura (YamagataUniversity,Japan),isavailableat:

1

10

100

1000

10000

100000

10

100

Visited nodes

Nodes in the graph

RSNE samples

RSNE log-log fit

fRSNE samples

fRSNE log-log fit

Figure 3: numberof nodevisits in oneiteration of RSNEand fRSNEfor Euler diskgraphswithradius.3onaunit square.

Figure 4 shows how edge loads distribute under the three policies for a randomtraÆcmatrix. Loadvalueshavebeengroupedinclassesof20,andthe histogram representsthepopulationof each class. Themaximumloadforthe shortest path routingwas242, RSNEand fRSNEbothreduced it to 157 (RSNE found it at the26th iteration), obtaininga36%reduction. Theoverall shape oftheloaddistributionisnotmuchdierentinthethreecases,apartfromthe longertailin theshortestpathdistribution. Inparticular,thenumberof light-loaded edgesremainssimilar

4

, andtheaverageedge loadisincreasedby6.8%, from30.37 to32.42.

Anotherimportantvericationconcernedthedistributionofhoplengths. In thiscase,themaximumhoplengthof7hopswasleftunchangedbybothRSNE and fRSNEalgorithms, while a1.8% increasein theaverage hop length (from 2.77to2.82withRSNE) wasveried. Thisis unavoidable,becausetheshortest path routingminimizeshoplength bydenition,so it necessarilyoutperforms allotherschemes. However,theimbalanceisverysmall.

Figure 5 plots the best congestion value against the number of steps for onerunof theRNEandRSNEalgorithms;heretheNSFNETtopologywasused with a random traÆc pattern from 10 to 100 for each couple of nodes. It turnsoutthatthemorecomplete RSNEalgorithmoutperformsitssimplestRNE version,although thelatter seems to havea betterresult in its earlier phase: thisbehaviorshowsupinmanycases,probablybecausethealgorithmisforced to movelargerportions ofloadfromedge toedge, achievingtemporarybetter

4

Indeed,aschemewhichreducescongestionbutsubstantiallyincreasesthe loadofmany otheredgeswouldbeunacceptable.

000

000

111

111

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0

0

0

0

0

1

1

1

1

1

0

0

0

1

1

1

0

1

₀

₁

₀₀

00

00

11

11

11

00

11

0

1

00

11

000

111

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

0

0

0

0

0

0

0

1

1

1

1

1

1

1

0

0

0

0

0

1

1

1

1

1

0

0

0

0

0

0

1

1

1

1

1

1

00

00

00

11

11

11

0

1

₀₀

00

00

11

11

11

00

00

00

11

11

11

fRSNE

10

20

30

40

50

60

0

20

40

60

80

100

120

140

160

180

200

220

Number of edges in the class

Load class (lower value shown)

Shortest Path

RSNE

0

Figure4: distributionofedgeloadsforShortestPathrouting,RSNEandfRSNE.

results but ending up with a complex, non-improvable routing scheme. For clarity, only the rst 50 iterations are shown. However, the fRSNE scheme, showinganintermediatebehaviordue tothesmallestmovespaceateachstep, eventuallynds the samevaluesshown by the complete heuristic. Theabove simulation gavea maximum hop length equal to 7(i.e. a lightpathneeds to travel7linksfromsourcetodestination)ateachiteration. Thisistheminimum, becauseitalsoresultsfrom theshortestpathroutingassignmentthatinitiates allalgorithms.

Table1 showsthe resultsof acomparisonbetweentheshortest path algo-rithm,theRSNEtechniqueandthesolutionsprovidedbytheCPLEXoptimizer when the same instances were put in the ILP form. Every line reports the

Table1: comparison betweenalgorithms onsmall randomnetworks with60% density. Averagegureson10experimentspersize,intervalsareshown where ILPcouldnotndsolutioninscheduledtime.

Nodes ShortestPath RSNE ILP

5 333:83 312:41 312:24 6 379:05 348:91 340:12 7 345:86 263:98 [257:16;254:51] 8 416:03 325:24 [345:77;305:92] 10 374:87 254:88 [374:87;228:45] 12 463:10 249:99 [495:73;249:13]

650

700

750

800

850

900

950

1000

0

10

20

30

40

50

Network congestion

Time

RNE

RSNE

fRSNE

Figure5: behaviorofheuristicsduringasinglerun.

average of 10 experiments; a time limit of 10 minutes for each instance was imposed to CPLEX (runningon a1.5GHz PIII Linux machine with no other CPU-consuming tasks), and if the optimum was not found then the current feasible solutionand thelowerbound werereportedas theintervalwhere the optimum lies. Note that the RSNEalgorithm alwaysoutperformsthe shortest path routing, and when relatively large networks are considered the CPLEX integersolverneedsmuchmorethan 10minutesin orderto ndtheoptimum (weleta12-nodetestrunforthreedayswithoutimprovingtheestimatebefore thebranch-and-bound treecaused amemoryover ow).

Toallowabettercomparisonamongheuristics,aseriesofexperimentswere performed onrandom networks (Figures 6and 7) and on Euclidean disk net-works(Figure8).

Figures6,7and8havebeenobtainedbyaveraging50runsofthealgorithms foreachplottedbar,representingthe95%condenceintervalofthetruemean congestionvalue. InFigure6nodesizewasvariedfrom 10to50instepsof10, with aconstant50%edge density, anddisconnected networks were discarded. Figure 7 comparesalgorithms on randomnetworks with a constant size of 20 nodesanddierentdensitiesfrom40%to95%. Figure8hasbeenobtainedfrom thesameexperimentsonEulerdisknetworkswithradiusequalto.3(remember that pointsarerandomlyscattered throughoutaunitsquare). All graphsplot meancongestionvalues. Inallcases,thetwolowerlines,representingRSNEand fRSNE,arealmostequal,andthismotivatessupportoftherandomizedversion. Onthe otherhand,thesimplied RNEschemedoesnotshowasignicant per-formanceimprovementovershortestpathroutingin therandomnetworkcase. Its use, however, maybe motivated in the Euler disk case, where an average

200

400

600

800

1000

1200

1400

0

10

20

30

40

50

60

Network congestion

Graph size

Shortest path

RNE

RSNE

fRSNE

Figure6: congestiononrandomnetworksofdierentnodesize,50%edge den-sity. Random barsrepresentthe95%condence interval,thetwolowerplots, representingRSNEandfRSNE,arealmostequal.

43%congestionreductionisobtainedinthe50-nodescase.

Figure 6plots an interesting behavior: while edge congestion obtained by RSNE (or equivalently fRSNE) is almost constant, the shortest path result is linearlyincreasing. ThesamecanbeseeninTable1. Thiscanbeexplainedby considering that boththe overall traÆc requirementand the numberof edges increaseasthesquareofthenumberofnodes. Techniquesaimingatcongestion reduction are able to exploit this fact, while shortest path policies, which do not aim at congestion reductionastheir primary target, tend to crowd paths alongeventualshortcuts. Whilecongestioncanbedrasticallydecreased(upto 5.5timeson50nodes),theaveragehoplengthincreasesupto4%forRSNEand 5.7%forfRSNE.Likewise,increaseinaverageedgeloadhasbeendetectedupto 3.6%.

InFigure7,thecongestionreductionoperatedbyRSNEandfRSNEreachesits maximum(67%)at70%edgedensity,thenitbecomeslessandlesssignicant, andthedierentplotstendtothesamecongestionvalueasdensityapproaches 100%. Thisisobvious,asallpolicieswill useone-hoproutingonaclique. For thesamereason,allaveragehoplengthstendto1asdensityapproaches100%. The highestincrease(3.6% forRSNE,6% forfRSNE) hasbeendetected forthe lowestconsidereddensity,40%.

Figure8depicts amorerealisticsituation in which connection depends on distance. In this case condence intervals are much larger because topology is more variable. Clusters of nodes with few congested inter-cluster links can appear with signicant probability, aswell as uniformly distributed networks

100

200

300

400

500

600

700

800

900

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Network congestion

Graph density

Shortest path

RNE

RSNE

fRSNE

Figure7: congestiononrandomnetworksof dierentdensities,20nodes.

withbalancedloads.Alsointhiscasethehighestcongestionreductionoperated by RSNEand fRSNE(56%)isdetectedfor 50nodes. Theaveragehop lengthis increased in the worst case by 12%(from 2.6 to 2.92 for50 nodes), while the averageloadis11%higher.

In all cases considered in this section, a largeimprovement on congestion reductionhasbeenobtainedattheexpenseofaslightdegradationoftheother performanceindicesthathad beenconsidered,averagehoplengthandaverage load.

6.4 Tests on dynamic traÆc

The24-nodesnetworkalreadyconsideredforstatictraÆchasbeentestedwith traÆc evolvingin time. ThetraÆc evolutionpattern isthat discussed earlier. Thecomplete timespanis of1000time steps,withanewindependentmatrix every20stepsandlinearinterpolationonintermediatematrices.

Figure9reportstheresultsofthesimulationfortherst100steps. Asthe shortestpathoutcomeishighlyvariable,wechosetocalculate50shortestpath routingswithrandomtie-breakingpertimestep. Allrunswereexecutedoverthe sametraÆcpattern. Errorbarsrepresentthespanfromthelowesttothehighest congestion valueobtained. Theotherlinesrepresentonerun of RSNEwith full restartand100iterationsateachtimestep,onerunofI-RSNE(1)withjustone optimizingiterationpertimestepandonerunof I-fRSNEwithoneoptimizing iterationpertimestepandallparameterssetto1. Asexpectedfromstatictests, resultsachievedwiththeproposedtechniquesarealwaysbelowtheshortestpath range. Thefactthat incrementalimplementationsoccasionallyoutperformthe

0

1000

2000

3000

4000

5000

6000

7000

8000

9000

0

10

20

30

40

50

60

Network congestion

Graph size

Shortest path

RNE

RSNE

fRSNE

Figure8: congestiononEulerdisknetworksofdierentnodesizes,radius.3on aunitsquareuniformscattering.

static RSNE depends from the low number of iterations per step. An initial transient can be seen for the rst 10 steps, while the incremental algorithms descendfromtheirinitialshortestpathcongurationstolowercongestions.

These resultssuggestthat modifyinga singleentryin therouting table of asinglenodeateachstepisenoughtoadequatelyfollowthetraÆcpattern,at least withthis traÆc model, evenwith arestrictedrandomexplorationof the movespace.

While congestion is signicantly reduced, a slight increase in the average pathlengthhastobeexpected. Figure10representsthebehaviorofaveragehop lengthinthesameexperimentdescribedaboveonthecomplete1000-steptime span. Itcanbeobservedthat,whileallshortestpathcomputationsresultinthe samevalue(lowerhorizontalline),andtheincreaseofthestaticRSNEalgorithm remains around the same level (about 5%), the incremental policies tend to suerfromahigherdegradation(upto17.3%)duetoprogressiveabandonofthe shortestpathconguration. However,thisproblemcanbexedbytriggeringa shortest-pathrestartwhenevertheaveragehoplengthreachesagiventhreshold, orperiodically.

7 Conclusions

We proposed new Load Balancing algorithms for Optical Networks based on IP-likeroutingand Local Search, whereeverymovemodies asingle entryin theroutingtableofanode. Thecomparisonsbetweenthenewschemeandthe optimumsolutionsfound viaanILPsolvershowbothcalculationtimesavings

500

1000

1500

2000

2500

3000

3500

4000

4500

0

20

40

60

80

100

Network congestion

Time

Shortest path, highest and lowest in 50 runs

I-RSNE

I-fRSNE

RSNE

Figure9: congestionin anonlinesetting.

and comparableresultsof network congestion andof averagelength ofthe re-sultingroutes. TheincrementalschemeI-RSNEproducescongestionvaluesthat arealmostundistinguishablefromthoseoftheRSNEalgorithm. Therandomized schemecalledfRSNEhasasubstantiallyreducedcomplexityincomparisonwith RSNEand,again,verysimilarnalcongestionresults.

Manyextensions canbeenvisioned,in particular whenconsidering specic properties of the optical medium. At the moment these schemes could work properlyonOpticalPacketSwitchingnetworkswhereIP-likeroutingisassumed orinwavelengthrouted networkswherewavelength conversionat eachnodeis considered. Thecontextofnetworkshavinglinkswithdierentcapacitiesshould alsobeconsidered infutureextensions, aswellasmoregeneralrouting mecha-nisms(e.g. G-MPLS).Furtherinvestigationwilldeterminehowtherandomized versioncouldbeexploitedin adistributedenvironment,wherecomplete infor-mationisnotavailableateachnode,in ordertohaveafastimplementationon anasynchronousnetwork.

Acknowledgments

We would like to thank Imrich Chlamtac and Jason Jue of the University of Texasat Dallas, for theirinteresting andfruitful discussionswith the authors aboutthesubjectofthiswork. Wealsothanktheanonymousrefereesfortheir suggestionsthathelpedimprovingthequalityofourwork.

2.75

2.8

2.85

2.9

2.95

3

3.05

3.1

3.15

3.2

3.25

3.3

0

100

200

300

400

500

600

700

800

900

1000

Hops

Time

Shortest path

I-RSNE

I-fRSNE

RSNE

Figure10: averagehoplengthin adynamicsetting.

References

[1] DhiritimanBanerjeeand Biswanath Mukherjee. A practicalapproachfor routingandwavelengthassignmentinlargewavelength-routedoptical net-works.IEEEJournalonSelectedAreasinCommunications,14(5):903{908, June1996.

[2] S. Bregni, U. Janigro, and A. Pattavina. Optimal allocation of limited optical-layer-resourcesin WDM networks under static traÆc demand. In Globecom2001 Proceedings,pages25{29,SanAntonio, Texas,2001.

[3] Mauro Brunato, Roberto Battiti, and Elio Salvadori. Load balancing in WDM networks through adaptive routingtable changes. In E. Gregori, M. Conti, A.T. Campbell, G. Omidyar, and M. Zukerman, editors, Net-working 2002 Proceedings,LNCS2345.Springer,May2002.

[4] I.Chlamtac,A.Ganz,andG.Karmi. Lightpathcommunications: Anovel approach to highbandwidthoptical WANs. IEEE Transactions on Com-munications, 40(7):1171{1182,1992.

[5] L. Fratta, M. Gerla, and L. Kleinrock. The ow deviation method: An approach to store-and-forwardcommunicationnetworkdesign. Networks, 3:97{133,1973.

[6] Aura Ganz and Xudong Wang. EÆcient algorithm for virtual topology designinmultihop lightwavenetworks. IEEE/ACM Transactions on Net-working,2(3):217{225,June1994.

routing in IP over WDM networks. In Infocom 2001 Proceedings, pages 358{366,2001.

[8] RajeshM.KrishnaswamiandKumarNSivarajan. Designoflogical topolo-gies: Alinearformulationforwavelengthrouterswithnowavelength chang-ers. IEEE/ACMTransactions onNetworking,9(2):186{198,April2001.

[9] J.LabourdetteandA. Acampora. Logicallyrearrangeablemultihop light-wavenetworks. IEEE Trans.onCommun.,39:1223{1230,August1991.

[10] Emilio Leonardi, Marco Mellia, and Marco Ajmone Marsan. Algorithms for the topologydesign in WDM all-optical networks. Optical Networks Magazine, 1(1):35{46,January2000.

[11] LingLiandArunK.Somani.Dynamicwavelengthroutingusingcongestion andneighborhood information. IEEE/ACM Transactions on Networking, 7(5):779{786,1999.

[12] K.Lu,G. Xiao,andI.Chlamtac. Blockinganalysisof dynamiclightpath establishment in wavelength-routed networks. In ICC2002 Proceedings, volume5,pages2912{2916,2002.

[13] G.Maier,A.Pattavina,L. Roberti,andT.Chich. Static-lightpathdesign by heuristic methods in multiber WDM networks. In Opticomm 2000 Proceedings,pages64{75,Dallas,TX, 2000.

[14] D.Mitra,R.Gibbens,andB.Huang. State-dependentroutingon symmet-riclossnetworkswithtrunkreservations. IEEETransactions on Commu-nications,41(2):400{411,1993.

[15] AhmedMokhtarandMuratAzizoglu. Adaptivewavelengthroutingin all-opticalnetworks. IEEE/ACM Transactions onNetworking, 6(2):197{206, April1998.

[16] Aradhana Narula-Tam and Eytan Modiano. Dynamic load balancing in WDM packet networks with and without wavelength constraints. IEEE JournalofSelectedAreasinCommunications,18(10):1972{1979,Oct2000.

[17] R. Ramaswami and K. N. Sivarajan. Design of logical topologies for wavelength-routedopticalnetworks. InInfocom 1995 Proceedings,1995.

[18] D. A. SchupkeandD. Sellier. Lightpathcongurationoftransparentand staticWDMnetworksforIPtraÆc. InICC2001 Proceedings,2001.

[19] JadrankaSkorin-KapovandJean-FrancoisLabourdette.Onminimum con-gestionroutingin rearrangeablemultihop lightwavenetworks. Journalof Heuristics,1:129{145,1995.

[20] HongsudaTangmunarunkit,JohnDoyle,RameshGovindan,SugihJamin, ScottShenker,andWalterWillinger. DoesASsizedeterminedegreeinAS topology? ComputerCommunication Review,31(5),October2001.

[21] C. Xin,Y. Ye, T.S. Wang, and S. Dixit. Onan IP-centric control plane. IEEECommunications Magazine, 39(9):88{93,2001.

for minimum congestion routingin lightwave networks. InInfocom 1994 Proceedings,pages138{149,1994.

[23] H.Zang,J.P.Jue,L.Sahasrabuddhe,R.Ramamurthy,andB.Mukherjee. Dynamic lightpath establishment in wavelength routed networks. IEEE CommunicationsMagazine, 39(9):100{108,2001.

[24] ZhenshengZhang andAnthony S. Acampora. A heuristic wavelength as-signmentalgorithmformultihop WDMnetworkswithwavelengthrouting andwavelengthre-use.IEEE/ACMTransactionsonNetworking,3(3):281{ 288,June1995.