Abstract—This paper presents a load balancing method to improve network utilization when static routing algorithms are employed. Static routing algorithms can generally be reduced to a path assignment problem with the aim of minimizing a cost function: i.
QoS-AwareRoutingSchemesBasedonHierarchicalLoad-BalancingforIntegratedServicesPacketNetworks
C.Casetti,R.LoCigno,M.Mellia
DipartimentodiElettronica,PolitecnicodiTorino,Italy
E-Mail:casetti,locigno,mellia@polito.it
Abstract—Thispaperpresentsaloadbalancingmethodtoimprovenet-workutilizationwhenstaticroutingalgorithmsareemployed.Staticrout-ingalgorithmscangenerallybereducedtoapathassignmentproblemwiththeaimofminimizingacostfunction:i.e.,maximizingnetworkrevenues.Unfortunatelytheproblem,whenmultipleconstraintssuchasdifferentQoStraf cclassesarepresent,iscomputationallyintractable.Loadbal-ancingmethodsareheuristicsthatallowtheidenti cationoflocalminimaofthecostfunctionthathopefullyareclosetotherealoptimum.
Theloadbalancingmethodweproposeisbasedonlyonstaticinfor-mationabouttheaveragetraf cloadofeachtraf crelation:apieceofinformationwhichcaneasilybeattainedintelecommunicationnet-works.Thepath-selectionstrategyisde nedintermsofSetTheoryanditsperformanceisevaluatedviasimulationbycomparisonagainststandardMinimum-Hoppathselections.Simulationresultsshowthatlowprioritytraf cbene tssigni cantlyfromthemorebalancedloadobtainedwithoursolution.
I.INTRODUCTION
Integrated-ServicesPacketNetworks(ISPN)areemergingasoneofthenewchallengesinnetworkingresearch.ISPNisnotyetacompletelyde nedterm:theassumptioninthisworkisthatwedealwithapacket-switchednetworksupportingtwoormoretraf cclassesdifferentiatedbytheirrequiredQualityofService(QoS).NextgenerationInternetwillbe(hopefully)anISPN,butAsynchronousTransferMode(ATM)networksareISPNsaswell,withtheadditionalconstraintofhandlingonly xed-sizepacketsnamedcells.
RoutingstrategiesplayanimportantroleinISPNs,sinceitisexpectedthattheyhavewide-areacoverageandtheyarehighlymeshed.QoS-awareroutingtakesintoaccountalsothecharac-teristicsoftheconnectionthatisbeingroutedthroughthenet-work,inordertoexploitnetworkresourcestotheirfullextent.Traditionally,routingstrategieshavebeendividedintostaticanddynamicones.Dynamicroutingstrategies[1],[2],[3]areveryappealingfortheircapacitytodealwithunpredictablechangesintraf cpattern;however,inverylargenetworks,theysufferfromthestaleinformationproblem:routingdecisionsaretakenonestimatesofthenetworkconditionthatmaybeeitherwrongorout-of-dateandthismayinduceinef cientnetworkexploitationand,ultimately,evennetworkoscillationandcol-lapse[4].Staticroutingstrategiesaregenerallynotbasedonthenetworkload,butontopologicalpropertiesofthenetwork,suchasthenumberofcrossednodes,thelengthandthecapacityofthelinks,andsoforth.Agoodexampleofdifferentstaticrout-ThisworkwassupportedinpartbyaresearchcontractbetweenCSELTandPolitecnicodiTorinoandinpartbytheItalianGovernmentthroughtheMin-istryforUniversityandResearch(MURST)andthroughtheNationalResearchCouncil(CNR).
ingstrategiescanbefoundin[5].Inourworkwefocusonstaticroutingstrategies,leavingforfutureresearchacomparisonwithdynamicones.
Theperformanceofstaticroutingalgorithmscanbeenhancedmakinguseofsomestatisticalknowledgeofthetraf c,suchasthelong-termaverageofthetraf cofferedtothenetworkfromnodetonode.Inanycase,theaimofanystaticrout-ingalgorithmistheidenti cationofthesetofroutes,forany
,thatoptimize(oratleastenhance)sourcedestinationpair
thenetworkperformance.Theidenti cationoftheoptimalsetofroutesisgenerallyaNP-Completeproblemwhenmultipleconstraintsarepresent[6],[7],henceapproximationsorheuris-ticsareneededtoobtainroutingalgorithmswithgoodperfor-manceinISPNnetworks,especiallyifmultipleserviceclassesarepresent.
Ourworkintroducesaload-balancingheuristicsthatcanbehierarchicallyappliedtodifferenttraf cclassesforthede ni-tionoftheroutesetstobeusedbyalternate-path(primary-pathonlycanbeseenasaspecialcase)routingschemes.AlternateroutesaresequentiallyprobedastheCAC(ConnectionAdmis-sionControl)functiondeniesallocationonthechosenpath.WepointoutthatroutingandCACfunctionsarenottightlycoupled,sothat,forinstance,astaticroutingalgorithmcanbecoupledwitheitherastaticCAC(e.g.,peakorequivalentbandwidth)orwithadynamicCACbasedontraf cmeasures.
Theremainingpartofthepaperisorganizedasfollows:Sec-tionIIgivesaformalde nitionoftheproblem,inordertoallowageneralandtheoreticalanalysis;SectionIIIdescribesthepathsselectionalgorithmsusingtheformalismde nedinSectionII;SectionIVdescribesthescenariochosenforresultscomparison,andSectionVpresentsthenumericalresultsobtainedbysimu-latingtheabovescenario;SectionVI, nally,closesthepaperwithhintsontheprosecutionofthework.
II.SETTHEORYPROBLEMFORMULATION
ALGORITHMDESCRIPTION
AND
Letusconsideranetwork,whereisthesetof
and.nodesandisthesetoflinks,andlet
1
thesetofallpossibleloop-freepaths,andWedenoteby
thesetofallpossible1loop-freepathsbetweentheby
sourcenodeandthedestinationnode.Obviously
.Letbeagenericpath,andbethei-th
bethesetofallpathfromsourcetodestination.Letalso