Soastoprovideaninsightintothecomplexityoftheloadbal-ancingalgorithmsweareproposing,weestimatedthatsortingallpossiblepathsofthenetworkinFigure2(approx.40,000paths)requiredjust2secondsonaPentiumII-266MHzwork-station.
ingandCACalgorithmsweredeployed,withoutpreventivelybalancingtheload(i.e.sortingthesetoftheavailablepathsonlybytopologicalcost).Figure3showsthecallblockingprob-abilitiesforguaranteedtraf cwhichwereestimatedasafunc-tionoftheoverallguaranteed-classloadofferedtothenetwork(inGb/s),whendifferentvaluesof,rangingfromapeak-rate
)toamorecharacterizationofvariable-bitratesources(
).Solidlinesrefertocurvesobtainedwith-relaxedone(
outloadbalancing,whiledashedlinesrefertotheloadbalancingalgorithm.
Itcanbeobservedthatbalancingguaranteedtraf cdoesnotimprovecalls’chancesofbeingadmittedtothenetwork,nordoesitleadtohigherblockingprobabilities.
IfwenowturnourattentionontothelowerQoStraf cclass,wecantryandgaugehowthecombinationofloadbalancingappliedtobothtraf cclassescan,ontheonehand,rationalizethedistributionofguaranteedtraf c,thusfreeingupresources,and,ontheother,ef cientlyallocatetheleftoverbandwidthtobest-efforttraf c.Tothispurpose,wede nedausers’“reward”astheratiobetweenthepeakbandwidththatabest-effortcallrequestsandtheactualaveragebandwidththatthecallhasbeenabletoexploitthroughoutitslife.Figures4and5reportsuchrewards,averagedoverallcallsthatwereactivatedduringthesimulation,fordifferentvaluesoftheadmissionparameter.Itcanbeseenthatarewardincrementashighas5%canbeachievedwhentheloadbalancingalgorithmisapplied.
V.NUMERICALRESULTS
Simulationswereruntoobtainanestimateofhowmuchbandwidthcanbesparedwhentheproposedload-balancingal-gorithmisused,withrespecttoasituationwherethesamerout-Ofcourse,thisisonlyanestimateofwhatthebest-effortconnectionsget,dependingontheactualpolicyusedbythenetworktoallocateresourcestoconnections;howeverregardlessofthepoliciesandtheperformancetheyattain,therelativemeritsofroutingschemesshouldnotbeaffected.
Acloserinspectionoftheresultsallowsustolinktherewardstotheactualpathschoiceasdeterminedbytheloadbalancingalgorithm.TableIdetailstheeffectivenessoftheloadbalancingalgorithmatlimitingthenumberoftimesnon-primary(andthusmoreresourcesconsuming)pathsarecheckedforadmissionofthehigher-QoScallsbeforeasuitablepathisfoundandthecallisroutedoverit.Expressedthroughpercentages,thesequanti-tiesalsoprovideuswithageneralindicationofthecallsetuptimeandofhowitcanbeconsiderablyshortenedwhenusingaload-balancingalgorithm.
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.
5
VI.CONCLUSIONS
0.90.850.8
Users reward
0.750.70.650.61.5
no lbwith lb5 Mb/s10 Mb/s
1.61.7
Load
1.81.92
Fig.4.Averagebest-effortusers’rewardasafunctionofguaranteed-classnet-workloadinGb/s-=0.4
0.90.850.8
Users reward
0.75
no lbwith lb5 Mb/s10 Mb/s
Thispaperhaspresentedaloadbalancingpathselectionalgo-rithmforstaticroutingstrategies,thatissuitedforhierarchicalimplementationinnetworksthatsupportmultipleQoStraf c.Theloadbalancingmetricwasbasedonlyontheminimumavailablebandwidthonthepath;howevermetricsthatarebasedalsoontheexpecteddelayand/ordelayvariationsarenotdif -culttobede nedandwillbestudiedinthefuture.
Theproposedsortingalgorithmwasimplementedandasim-ulationstudywascarriedoutonacomplex,meshedtopol-ogy,withtwotraf cclasses,inordertocomparetheproposedschemewithastandardMinimum-Hoppathselectionalgorithm,applyinganuncontrolledalternateroutingstrategytothepathsselected.Resultsshowthattheproposedstrategyallowsthelowertraf cclasstoobtainanincreasedshareofresources,whileobviouslynotaffectingthehigherclasstraf c.
Thetotaltraf cadmittedwithinthenetworkwasnotobservedtochangesigni cantly;howeveritmustbenotedthatonlyasingletopologywithuniformtraf cdistributionwasstudiedinthisearlystageoftheresearchandthesituationmightchangesigni cantlyifthetraf cloadisnotuniform.Futureresearchwillcoverthispoint.
ACKNOWLEDGEMENTS
TheauthorswishtothankGabrieleFavalessaandLucaMedicofortheircontributionstothesimulatorcode.
REFERENCES
0.70.650.61.5
1.61.7
Load
1.81.92
Fig.5.Averagebest-effortusers’rewardasafunctionofguaranteed-classnet-workloadinGb/s-=1
Path#1233Path#1233
Load=1.5Unbal.Bal.98.6599.980.630.010.320.0030.400.03Load=1.8Unbal.Bal.94.0099.092.750.521.370.121.880.27
TABLEI
Load=1.6
Unbal.Bal.97.3099.911.260.040.640.010.80.04Load=2.0Unbal.Bal.90.8396.464.232.002.010.472.931.07
PERCENTAGEOFTIMESAGUARANTEED-CLASSCALLISROUTEDOVER
FIRST-,SECOND-,THIRD-ANDGREATER-THAN-THIRD-CHOICEPATHS,
E.Crawley,R.Nair,B.Rajagopalan,H.Sandick,“AFrameworkforQoS-basedRoutingintheInternet”,Internet-Draft,July1998,workinprogress[2]Q.Ma,P.Steenkiste.“RoutingTraf cwithQuality-of-ServiceGuarantees
inIntegratedServicesNetworks”,InProceedingsofthe8thIEEE/ACMInternationalWorkshoponNetworkandOperatingSystemsSupportforDigitalAudioandVideo(NOSSDAV’98),pages115–126,England,July1998