Dynamic Traffic Grooming in WDM Mesh Networks Usin

AbstractAsourfiber-opticbackbonenetworksmigratefrominterconnectedSONETringstoarbitrarymeshtopology,trafficgroomingonWDMmeshnetworksbecomesanextremelyimportantresearchproblem.(Trafficgroomingreferstotheproblemofefficientlypackingasetoflow-speedconnectionrequestsontohigh-capacitychannels.)Toaddressthisproblem,weemployanew,genericgraphmodelfordynamictrafficgroominginWDMmeshnetworks,whereconnectionsarriveoneatatimeandholdforrandomtimedurations.Thenoveltyofthismodelisthat,byonlymanipulatingtheedgesofanauxiliarygraphcreatedbythemodelandtheweightsoftheseedges,themodelcanachievevariousobjectivesusingdifferentgroomingpolicies,whiletakingintoaccountvariousconstraintssuchastransceivers,wavelengths,wavelength-conversioncapabilities,andgroomingcapabilities.Basedontheauxiliarygraph,wedevelopadynamictraffic-groomingalgorithmwhichemploysthesimpleshortest-pathcomputationmethodtosolvethetraffic-groomingproblem.Differentgroomingpoliciescanbeimplementedbydifferentweightfunctionsassignedtotheedgesintheauxiliarygraph.Weproposefourfixedgroomingpolicies,whoseperformanceiscomparedinvariousnetworkscenarios.WealsodevelopanAdaptiveGroomingPolicy(AGP),inwhichtheweightsoftheedgesaredynamicallyadjustedaccordingtothecurrentnetworkstate,andourresultsshowthatitoutperformsthefixedgroomingpolicies.KeywordsOpticalnetwork,meshnetwork,WDM,dynamictrafficgrooming,graphmodelI.INTRODUCTIONWavelength-divisionmultiplexing(WDM)isakeyapproachtoincreasethebandwidthofanopticalnetwork[1].AsWDMtechnologycontinuestomature,thereexistsalargegapbetweenthecapacityofaWDMchannel(e.g.,OC-48,orOC-192,orOC-768)andthebandwidthrequirementofatypicalconnectionrequest(e.g.,STS-1,OC-3,OC-12,etc.).Inordertousethenetworkresourcesefficiently,low-speedtrafficstreamsneedtobemultiplexedandswitchedontohigh-speedlightpaths,whichisalsoknownastraffic-groomingproblem[2].Thetraffic-groomingproblemcanbeformulatedasfollows[3].Givenanetworkconfiguration(includingphysicaltopology,whereeachedgeisaphysicallink;numberoftransceiversateachnode;numberofwavelengthsoneachfiber;andthecapacityofeachwavelength)andasetofconnectionrequestswithdifferentbandwidthgranularities,suchasOC-12,OC-48,etc.,weneedtodeterminehowtosetuplightpathstosatisfytheconnectionrequests.Becauseofthesub-wavelengthgranularityoftheconnectionrequests,oneormoreconnectionscanbemultiplexedonthesamelightpath.∗ThisworkhasbeensupportedbytheNationalScienceFoundation(NSF)underGrantNos.NCR-9508239andANI-9805285,andbySprintAdvancedTechnologyLaboratories.DynamicTrafficGroominginWDMMeshNetworksUsingaNovelGraphModel∗∗∗∗+DepartmentofComputerScience,Univ.ofCalifornia,Davis,CA95616,USATel:[phone],Fax:[phone],Email:{zhuh,zhuk,mukherje}@cs.ucdavis.edu++SprintAdvancedTechnologyLaboratories,Burlingame,CA94010,USATel:[phone],Fax:[phone],Email:[e-mail]+,HuiZang++,KeyaoZhu+,andBiswanathMukherjee+Indynamictrafficgrooming,theconnectionrequestsarriveoneatatimewithdifferentstartingtimeandholdingperiod.Theobjectiveistominimizethenetworkresourcesusedforeachrequest,whichimplicitlyattemptstominimizetheoverallblockingprobability.Whenaconnectionrequestarrives,thenetworkoperatorshoulddeterminethefollowing:(1)Shouldthisconnectionberoutedonthecurrentsetoflightpaths,i.e.,virtualtopology,ifitispossibletodoso?Sometimes,itmaybebettertosetupanewlightpatheventhoughtheconnectioncanbecarriedonthecurrentsetoflightpaths.(2)Howtochangethevirtualtopologytoaccommodatetheconnection?i.e.,betweenwhichtwonodesshouldwesetupanewlightpath,ifany?Insomecases,wecansetupalightpathdirectlyfromthesourceofthetraffictothedestination.Inothercases,itmaynotbenecessaryorpossibletosetupthisdirectlightpath;instead,wemayneedtosetupsomeotherlightpath(s)androutetheconnectionontotheselightpath(s)and/orsomeexistinglightpaths.Differentdecisionsonthesequestionscanresultindifferentnetworkperformance.Thesedecisionsreflecttheintentionsofthenetworkoperator,andtheyarereferredtoasgroomingpolicies[4],[5].Byusingdifferentgroomingpolicies,anetworkoperatorcanachievevariousobjectives.Asthenetworkstatechanges,theoptimizationobjectivemayalsoneedtochange.Dynamicallyevolvingthegroomingpolicyaccordingtothenetworkstateisachallengefortrafficgrooming.A.PreviousWorkTrafficgroomingisanimportantandpracticalproblemfordesigningWDMnetworksanditisreceivingincreasingresearchattentionbothinacademeandinindustry.Theworkin[6]reviewsmostoftherecentresearchworkontrafficgroominginWDMringandmeshnetworks.PastresearcheffortsontrafficgroominghavemainlyfocusedonSONET/WDMringnetworks.ThemajorcostofsuchanetworkisconsideredtobedominatedbySONETadd-dropmultiplexers(ADMs).Therefore,minimizingthenumberofSONETADMshasbeentheobjectiveofstatictrafficgroominginrecentresearch.Thegeneraltraffic-groomingprobleminaSONET/WDMringnetworkisproventobeNP-complete[7],[8].Anoptimalalgorithmforasingle-hubringisproposedin[7]andseveraloptimalornear-optimalalgorithmsfortrafficgroomingandwavelengthassignmenttoreducethenumberofwavelengthsandSONETADMsareproposedin[9].Asanetworkdesignproblem,theauthorsin[10]attempttomini