搜索
ApproximationAlgorithmsforMulticonstrainedQuality-of-ServiceRouting∗MeongchulSongSartajSahniComputer&InformationScience&EngineeringUniversityofFlorida{msong,sahni}@cise.ufl.eduAugust3,2005AbstractWeproposesixnewheuristicstofindasource-to-destinationpaththatsatisfiestwoormoreadditiveconstraintsonedgeweights.Fiveoftheseheuristicsbecomeǫ-approximationalgorithmswhentheirparametersareappropriatelyset.Theperformanceofournewheuris-ticsiscomparedexperimentallywiththatoftworecentlyproposedheuristicsforthesameproblem.Keywords:Qualityofservicerouting,intervalpartitioning,approximationalgorithm,heuristic.1IntroductionInunicastquality-of-service(QoS)routing,wewishtofindapathfromasourcevertextoadestinationvertexofanetwork.Thispathmustsatisfyspecifiedconstraints.Typicalconstraintsfallintooneoftwocategories–linkandpath[1].LinkconstraintslimittheuseofcertainedgesofthenetworkinconstructingaQoSroutewhilepathconstraintsapplytoentiresource-to-destinationpaths.Bandwidthisthemostcommonexamplecitedforalinkconstraint.TheQoSpathweseekmayberequiredtoprovideaminimumbandwidth.Tomeetthisrequirement,eachlink(oredge)oftheconstructedsource-to-destinationroute/pathmustprovidethismuchbandwidth.Themostcommonlycitedexamplesofpathconstraintsarecost,delayanddelayjitter.Althougheachedgeorlinkhasacost/delay/delay-jitterassociatedwithit,theQoSconstraint∗Thisresearchwassupported,inpart,bytheNationalScienceFoundationundergrantITR-03261551isonthesumofthevaluesforeachedgeonthepathratherthanonthevalueforanindividualedge.Inthispaper,weareconcernedwithpathconstraintsonly1.TheproblemofdeterminingaQoSroutethatsatisfiestwoormorepathconstraints(forexam-ple,delayandcost)isknowntobeNP-hard[5].Hencethefocushasbeenonthedevelopmentofpseudopolynomialtimealgorithms,heuristicsandapproximationalgorithmsfortheconstructionofmulticonstrainedQoSpaths[1,3,9,12].Inthispaperwefocusonheuristicsandapproxima-tionalgorithmsformulticonstrainedQoSpaths.WebegininSection2byformulatingpreciselythevarietyofthemulticonstrainedQoSpathproblemwestudyhere.Inthissectionwealsointroduceournotationandreviewrelatedwork.InSection3,weproposesixnewheuristics.Fiveofthesebecomeapproximationalgorithmswhentheirparametersareproperlyselected.Theperformanceofoursixnewheuristicsisexperimentallycompared,inSection4,withthatofthelimitedgranularityandlimitedpathheuristicsproposedbyYuan[19].2Preliminaries2.1ProblemFormulationOurnotationandterminologyarefromYuan[19].WeassumethatthecommunicationnetworkisrepresentedbyaweighteddirectedgraphG=(V,E),whereVisthesetofnetworkverticesornodesandEisthesetofnetworklinksoredges.Weusenande,respectively,todenotethenumberofnodesandlinksinthenetwork,thatis,n=|V|ande=|E|.Weassumethateachlink(u,v)ofthenetworkhask1non-negativeweightswi(u,v),1≤i≤k.Thenotationw(u,v)isusedtodenotethevector(w1(u,v),···,wk(u,v)),whichgivesthekweightsassociatedwiththeedge(u,v).Letpbeapathinthenetwork.Weusewi(p)todenotethesumofthewisoftheedgesonthepathp.wi(p)=X(u,v)∈pwi(u,v)Bydefinition,w(p)=(w1(p),···,wk(p)).Inthemulticonstrainedpath(k-MCP)problem,wearetofindapathpfromaspecifiedsource1Wenotethatlinkconstraintsareusuallyeasytoworkwith;whenconstructingtheQoSpath/route,simplyignoretheedgesthatviolatethelinkconstraint.2vertexstoaspecifieddestinationvertexdsuchthatwi(p)≤ci,1≤i≤k(1)ThecisarespecifiedQoSconstraints.NotethatEquation1isequivalenttow(p)≤c,wherec=(c1,···,ck).AfeasiblepathisanypaththatsatisfiesEquation1.Therestrictedshortestpath(k-RSP)problemisarelatedoptimizationprobleminwhichwearetofindapathpfromstodthatminimizesw1(p)subjecttowi(p)≤ci,2≤i≤kAnalgorithmisanǫ-approximationalgorithm(orsimply,anapproximationalgorithm)fork-MCPiffthealgorithmgeneratesasourcetodestinationpathpthatsatisfiesEquation1wheneverthenetworkhasasourcetodestinationpathp′thatsatisfieswi(p)≤ǫ∗ci,1≤i≤k(2)whereǫisaconstantbetween0and1.2.2RelatedWorkBoththek−MCPandk−RSPproblemsfork1havebeenthesubjectofintenseresearch.BothproblemsareknowntobeNP-hard[5]andseveralpseudopolynomialtimealgorithms,heuristicsandapproximationalgorithmshavebeenproposed[1,13,18].Jaffe[9]hasproposedapolynomialtimeapproximationalgorithmfor2-MCP.Thisalgorithm,whichusesashortestpathalgorithmsuchasDijkstra’s[16],replacesthetwoweightsoneachedgebyalinearcombinationofthesetwoweights.Thealgorithmisexpectedtoperformwellwhenthetwoweightsarepositivelycorrelated.ChenandNahrstedt[2]usetheroundingstrategyofSahni[15]toarriveatapolyno-mialtimeapproximationalgorithmfork-MCP.KorkmazandKrunz[10]proposearandomizedheuristicthatemploystwophases.InthefirstphaseashortestpathfromeachvertxofVtothedestinationvertexdiscomputedforeachofthekweightsaswellasforalinearcombinationofallkweights.Thesecondphaseperformsarandomizedbreadth-firstsearchforasolutiontothek-MCPproblem.Yuan[19]hasproposedtwoheuristicsfork-MCP–limitedgranularity3andlimitedpath.Byproperlyselectingtheparametersforthelimitedgranularityheuristic,thisheuristicbecomesanapproximationalgorithmfork-MCP.[6,7,11,14]developpseudopolynomialtimealgorithms,heuristics,andapproximationalgo-rithmsfork-RSP.2.3ExtendedBellman-FordAlgorithmThisisanextensionofthewe