连接缓冲管理和行程安排 forDifferentiated 服务

JoBS:JointBufferManagementandSchedulingforDifferentiatedServices?J¨orgLiebeherrandNicolasChristinComputerScienceDepartment,UniversityofVirginia,Charlottesville,VA22904,USAfjorg,[e-mail]managementandpacketschedulingispresentedforprovidinglossanddelaydifferentiationfortrafficclassesatanet-workrouter.Thealgorithm,calledJoBS(JointBufferManagementandSchedul-ing),providesdelayandlossdifferentiationindependentlyateachnode,withoutassumingadmissioncontrolorpolicing.Thenovelcapabilitiesoftheproposedalgorithmarethat(1)schedulingandbuffermanagementdecisionsareperformedinasinglestep,and(2)bothrelativeand(wheneverpossible)absoluteQoSre-quirementsofclassesaresupported.Numericalsimulationexamples,includingresultsforaheuristicapproximation,arepresentedtoillustratetheeffectivenessoftheapproachandtocomparethenewalgorithmtoexistingmethodsforlossanddelaydifferentiation.1IntroductionQuality-of-Service(QoS)guaranteesinpacketnetworksareoftenclassifiedaccordingtotwocriteria.Thefirstcriterioniswhetherguaranteesareexpressedforindividualend-to-endtrafficflows(per-flowQoS)orforgroupsofflowswiththesameQoSre-quirements(per-classQoS).Thesecondcriterioniswhetherguaranteesareexpressedwithreferencetoguaranteesgiventootherflows/flowclasses(relativeQoS),orwhetherguaranteesareexpressedasabsolutebounds(absoluteQoS).EffortstoprovisionforQoSintheInternetintheearlyandmid-1990s,whichre-sultedintheIntegratedServices(IntServ)servicemodel[3],focusedonper-flowab-soluteQoSguarantees.However,duetoscalabilityissuesandalaggingdemandforper-flowabsoluteQoS,theinterestinInternetQoSeventuallyshiftedtorelativeper-classguarantees.Sincelate1997,theDifferentiatedServices(DiffServ)[2]workinggrouphasdiscussedseveralproposalsforper-classrelativeQoSguarantees,e.g.,[4,17].WiththeexceptionoftheExpeditedForwardingservice[11],proposalsforrelativeper-classQoSdiscussedwithintheDiffServcontextdefinetheservicedifferentiationqualitatively,inthesensethatsomeclassesreceivelowerdelaysandalowerlossrate?ThisworkissupportedinpartbytheNationalScienceFoundationthroughgrantsNCR-9624106(CAREER),ANI-9730103,andANI-0085955.cSpringer-Verlag20012J¨orgLiebeherrandNicolasChristinthanothers,butwithoutquantifyingthedifferentiation.Recently,researchstudieshavetriedtostrengthentheguaranteesofrelativeper-classQoS,andhaveproposednewbuffermanagementandschedulingalgorithmswhichcansupportstrongernotionsofrelativeQoS[6,7,15,16].Probablythebestknownsucheffortistheproportionalser-vicedifferentiationmodel[6,7],whichattemptstoenforcethattheratiosofdelaysorlossratesofsuccessivepriorityclassesberoughlyconstant.Fortwopriorityclassessuchaservicecouldspecifythatthedelaysofpacketsfromthehigher-priorityclassbehalfofthedelaysfromthelower-priorityclass,butwithoutspecifyinganupperboundonthedelays.Inthispaper,weexpresstheprovisioningofper-classQoSwithinaformalismin-spiredbythenetworkcalculus[5].Wepresentarateallocationanddroppingalgorithmforasingleoutputlink,calledJointBufferManagementandScheduling(JoBS),whichiscapableofsupportingawiderangeofrelative,aswellasabsolute,per-classguaran-teesforlossanddelay,withoutassumingadmissioncontrolortrafficpolicing.Theal-gorithmoperatesasfollows.Uponeacharrival,apredictionismadeonthedelaysofthecurrentlybackloggedtraffic.Then,theserviceratesallocationtoclassesareadjustedtomeetdelayrequirements.Ifnecessary,trafficfromcertainclassesisselectivelydropped.Auniquefeatureofthepresentedalgorithmisthatrateallocationforlinkschedulingandbuffermanagementareapproachedtogetherinasinglestep.TheJoBSalgorithmprovidesdelayandlossdifferentiationindependentlyateachnode.End-to-enddelaysandend-to-endlossratesarethusdependentontheper-nodeguaranteesoftrafficandonthenumberofnodestraversed.Thispaperisorganizedasfollows.InSection2wegiveanoverviewofthecur-rentworkonrelativeper-classQoSguarantees.InSections3and4,wespecifyouralgorithmforbuffermanagementandrateallocation.InSection5weproposeaheuris-ticapproximationofthealgorithm.InSection6weevaluatetheeffectivenessofouralgorithmviasimulation.InSection7wepresentbriefconclusions.2RelatedWorkDuetospaceconsiderations,welimitourdiscussionstotherelevantworkonschedulingandbuffermanagementalgorithmsforrelativeservicedifferentiation.Scheduling.Themajorityofworkonper-classrelativeservicedifferentiationsug-geststousewell-knownfixed-priority,e.g.,[17],orrate-basedschedulingalgorithms,e.g.,[9].Onlyafewschedulingalgorithmshavebeenspecificallydesignedforrelativedelaydifferentiation.TheProportionalQueueControlMechanism(PQCM,[15])andBacklog-ProportionalRatescheduler(BPR,[6])arevariationsoftheGPSalgorithm[18].Bothschemesusethebacklogofclassestodeterminetheservicerateallocation,andbearsimilaritytotheschedulingcomponentofJoBS,inthesensethattheydynam-icallyadjustservicerateallocationstomeetrelativeQoSrequirements.Differentfromtherate-basedschedulersdiscussedabove,theWaiting-TimePri-orityscheduler(WTP,[7])implementsawell-knownschedulingalgorithmwithtime-dependentpriorities([12],Ch.3.7).Likewise,theMean-DelayProportionalscheduler(MDP,[16])usesadynamicprior