Schedulability criterion and performance analysis of coordinated schedulers

SchedulabilityCriterionandPerformanceAnalysisofCoordinatedSchedulers

ChengzhiLiandEdwardW.Knightly

DepartmentofElectricalandComputerEngineering,RiceUniversity

6100SMainStreet,Houston,TX77005,USA(chengzhi@rice.edu,knightly@rice.edu)Inter-servercoordinatedschedulingisamechanismfordownstreamnodestoincreaseorde-creaseapacket’spriorityaccordingtothecongestionincurredatupstreamnodes.Inthispaper,wederiveanend-to-endschedulabilityconditionforabroadclassofcoordinatedschedulersthatincludesCJVCandCEDF.Incontrasttopreviousapproaches,ourtechniquepurposelyallowsflowstoviolatetheirlocalpriorityindexeswhilestillprovidinganend-to-enddelaybound.Weshowthatunderasimplepriorityassignmentscheme,coordinatedschedulerscanoutperformWFQschedulers,whilereplacingper-flowschedulingoperationswithasimplecoordinationrule.Finally,weillustratetheperformanceadvantagesofcoordinationthroughnumericalex-amplesandsimulationexperiments.1.INTRODUCTION

Inthepastdecade,therehasbeengreatprogressinthedesignofpacketschedulingalgo-rithms,includingservicedisciplineswhichachieveperformanceisolation[19,25],qualityofservicedifferentiation[9,12,18],andscalablecore-statelessimplementation[4,22,27].

Simultaneously,newtheoreticaltoolshavebeendevisedtoanalyzetheperformanceprop-ertiesofsuchmulti-classschedulers.Forexample,exactdelayboundsforEarliestDeadlineFirst(EDF)andStrictPriority(SP)schedulersarederivedin[17].Moreover,multi-nodedelayboundshavebeendevelopedfornetworksofelementscharacterizedbyservicecurvesusing“networkcalculus”[3,8,21],anapproachwhichencompassesandgeneralizespreviousresultsfornetworksofWeightedFairQueueing(WFQ)servers[20]andrate-controlledservers[14,25].Ingeneral,suchtechniquesprovideschedulabilityconditions,i.e.,constraintsthat,ifsatisfied,ensurethatallpacketsofallflowswillmeettheirrespectivedelayboundswithoutviolationorloss.

Recently,aclassofschedulershasbeenstudiedwhichemploycoordinationofprioritiesamongnodes[2,15,28].Aschedulerthatemployscoordinationcangiveapackethigherorlowerpriorityatdownstreamnodesdependingonwhetherthepacketwasservicedlateorearlyatupstreamnodes.ThisintuitivelyappealingconcepthasbeenappliedinanumberofservicedisciplinesproposedintheliteratureincludingFIFO+[6]andGlobalEDF[5].Moreover,suchschedulershavepotentialapplicationstofuturemulti-servicenetworkssincetheycanprovideend-to-endservicesusingsimple,workconserving,per-nodeschedulingalgorithmsthatdonot

requireper-flowoperations.Indeed,itwasshownin[15]thatcorestatelessservicedisciplinessuchasCore-statelessJitterVirtualClock(CJVC)[23]canalsobeexpressedbyasimplecoor-dinationmechanism.

Thegoalisthispaperistoprovideaschedulabilityconditionandanalyticalframeworkforcoordinatedschedulers.Ourapproachrepresentsafundamentaldeparturefromprevioustech-niquesintwoways.First,ourschedulabilityconditionallowspacketstoviolatelocalper-nodeconstraints,whilestillensuringdelayboundsaresatisfiedend-to-end,i.e.,bythefinalhop.Al-lowingsuchlocalviolationsiscrucialtoexploitingthekeymulti-nodepropertyofcoordinatedschedulers.Consequently,techniquesthatrequireallpacketstosatisfytheirlocalconstraintsateachnodetoensureend-to-endschedulabilitycannotbeapplied.Second,previoustechniquesrelyoneitherper-flowtrafficre-shaping[14,25]orper-flowscheduling[3,8,20,21](suchasinWFQ)toderivemulti-nodeschedulabilityconditions.Incontrast,weconsiderascenarioofwork-conservingserverswithnoper-flowoperations,andthereforeachievethecore-statelesspropertydefinedin[22].

Thecontributionofthispaperisasfollows.First,wedevelopanend-to-endschedulabilityconditionforabroadclassofcoordinatedschedulersthatincludesCoordinatedEDF(CEDF)andCJVC.Ourkeytechniqueistointroduceavirtualpartitionofthetrafficintoessential,andnon-essentialtraffic,whereonlytheformertrafficcanimpedeapacketinmeetingitsdelaybound.Withthisconcept,wederiveaboundontheessentialtrafficatdownstreamnodesandshowthatdistortionoftheessentialtrafficisconfinedtowithinanarrowrange.Inotherwords,weshowthatcoordinationlimitsdownstreamdistortionanalogoustothewayper-flowtrafficreshapingeliminatesdistortion.

Second,westudytheproblemofassigninglocalpriorityindexes.Weshowthatwithaparticularassignmentscheme,coordinatedschedulerscanachievenotonlythesameend-to-enddelayboundasWFQ,butalsothetighterend-to-enddelayboundthanWFQ,yetwithoutper-flowpacketforwardinginthenetworkcore.Inotherwords,weestablishthatanysetofflowsthatcanbescheduledinWFQnetworkscanalsobescheduledincoordinatedschedulingnetworks.

Finally,weillustrateandquantifythepracticaladvantagesofcoordinatedschedulingwithasetofnumericalexamplesandns-2simulationexperiments.WefirstdeviseasimpleexamplewiththreeflowstoillustratethatcoordinatedschedulerscanachievealowerdelayboundthanWFQschedulers.WethenusesimulationsofexponentialandParetoon-offtrafficflowsanda6-nodenetworktoillustratestatisticaldifferencesbetweencoordinatedscheduling,EDF,andWFQ.

Theremainderofthispaperisorganizedasfollows.InSection2,weprovidebackgroundandaprecisedefinitionofinter-servercoordination.InsectionSection3,wedevelopakeytoolformulti-nodeanalysisandshowhowtoboundtheessentialtrafficatdownstreamnodes.InSection4,weusethistrafficboundtoprovideaglobalschedulabilitycriterionfornetworksusingcoordinatedscheduling.Next,inSection5,westudypriorityindexassignmentanditsre-lationshiptoWFQ.Finally,inSection6,wecomparecoordinatedandnon-coordinatedservicedisciplinesusingnumericalexamplesandsimulations,andinSection7weconclude.

2.BACKGROUNDONINTER-SERVERCOORDINATION

Inthissection,weprovideaformaldefinitionofcoordinationamongservers.Wethenillus-tratethegeneralityofthedefinitionbydescribinghowservicedisciplinesfromtheliterature,namelyCEDFandCJVC,canbecharacterizedasexamplesofcoordinatedschedulers.2.1.DefinitionandProperties

Definition1(CoordinatedNetworkScheduling)Consideraserverwhichservicespacketsinincreasingorderoftheirpriorityindexes.AschedulerpossessestheCNSpropertyif

(1)

whereisthepriorityindexassignedtothepacketofflowatitshop;isthetimewhenthepacketofflowarrivesatitsfirsthop;andaretheincrementofthepriorityindexofthepacketofflowatthecorrespondinghops;()isdeterminedwhenthepacketoftheflowarrivesatitsfirsthopand,where.

ThekeypropertyoftheCNSdisciplineisthatthepriorityindexofeachpacketatadown-streamserverdependsonitspriorityindexatupstreamservers,whichinturndependsonitsentrancetimeintothenetwork.Therefore,ifapacketviolatesitspriorityindexatanupstreamserver,downstreamserverswillincreasethepacket’spriority,therebyincreasingthelikelihoodthatthepacketwillmeetitsend-to-enddelaybound.Similarly,ifapacketarrives“early”duetoalackofcongestionupstream,downstreamserverswillreducethepriorityofthepacket,en-ablingotherpacketstobeservicedaheadofit.Thus,eventhoughthedistributedserversoperateindependently,thepriorityindexofeachpacketiscommunicateddownstreamviainsertionofalabelintothepacketheader(e.g.,asdescribedin[22])sothattheservers(virtually)coordinatetoprovideanend-to-endservice.

2.2.CJVCandCEDF

AnexampleofcoordinatedschedulingisCore-statelessJitterVirtualClock.CJVCwaspro-posedin[23]asamechanismforachievingguaranteedservicewithoutper-flowstateinthenetworkcore.CJVCuses“dynamicpacketstate”tostoreinformationineachpacketheadercontainingtheeligibletimeofthepacketattheingressrouterandaslackvariablethatallowscorerouterstodeterminethelocalpriorityindexofthepacket.Forawork-conservingvariantofCJVC,thepriorityindexofpacketofflowatnodeisgivenby:

(2)

whereflow-packetsizeandreservedbandwidtharegivenbyandrespectively,andis

theslackvariableassignedtothepacketofflowbeforeitentersthenetwork.Furthermore,itcanbeverifiedthatand

In[1,2,5],coordinationwithinthecontextofEDFwasstudied.WerefertosuchschedulersasCoordinatedEarliestDeadlineFirst(CEDF)ifthepriorityindexesareassignedas

(3)

isaconstant(expectedlocaldelayclearlyexpressibleintheformofEquation(1),where

bound)determinedforthehopofflow.Itisneededtopointoutthatinthiscase,

and.

OurtheoreticalresultsaddressallschedulerssatisfyingtheCNSdefinition,andthroughoutthispaper,weuseCEDFandCJVCasexampleservicedisciplines.Discussionofothersched-ulerscanbefoundin[15,27].

2.3.Example

ConsiderthesimpleexampleofFigure1inwhichthreepacketsofflowarrivetothenetworkatrespectively,andtraversetwohopswith.Intheexample,allpacketshaveidenticalsize,thelinkspeedis1packetpertimeunit,andcrosstrafficexistsatbothhops.Atthefirsthop,thesethreepacketsareassignedpriorityindexes(deadlines)of5,6,and7respectively,bybothCNSandEDF.Supposefurtherthatthesethreepacketsdepartfromthefirsthopattimes3,4,and10respectively,sothatthethirdpacketmissesitslocaldeadlineby3timeunitsduetocrosstrafficwithhigherpriority.Accordingtothearrivaltimesatthesecondhop,thesethreepacketsareassignedpriorityindexesof8,9,and15byEDF,whereastheindexesare10,11,and12forCNS.Intheexample,withfurthercrosstrafficatthesecondhop,thethirdpackethashigherpriorityintheCNSnetworkthantheEDFnetwork,andthereforeisabletomeetbothitslocaldelayboundandglobaldelaybound.Incontrast,intheEDFnetwork,thethirdpacketmeetsitslocaldelayboundatthesecondhop,butisnotableto“catchup”,andmeetitsend-to-enddelaybound.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 200 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 200 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20Packet Arrival Eventδ = 5 msecδ = 5 msecPacket Arrival Eventδ = 5 msecPacket Arrival Event0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 200 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 200 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20Packet Priority IndexPacket Priority IndexPacket Priority Index0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 200 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 200 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20Packet Departure EventPacket Departure EventPacket Departure Event(a)CNSandEDFattheFirstHop(b)EDFattheSecondHopFigure1.IllustrationofCoordination

(c)CNSattheSecondHop

Thissimpleexampleillustrateshowdistributedserverscanbeforcedto(virtually)coordinatepriorityindexestoimprovethelikelihoodofsatisfyinganend-to-enddelayconstraint.3.TRAFFICCHARACTERIZATIONINDOWNSTREAMNODES

Inmulti-nodenetworkswithouttrafficre-shaping,trafficcharacteristicsaredistortedatdown-streamnodesascomparedtotheirpropertiesatthenetworkentrance.Inthissection,wederiveaburstinessboundforarrivingtrafficatdownstreamnodes,whichweuseasabasisforderivingaglobalschedulabilitycriterioninthenextsection.

3.1.PreliminariesLetdenotethetotalarrivaltrafficofflow-atitsduringtimeinterval.Moreprecisely,wehave

hop(denotedasserver

)(4)

2

.Ignoringisthetimewhentheflow-packetwithsizearrivesatserverwhere

thepropagationdelay,thedeparturetrafficofflowfromserveristhearrivaltrafficofflowtoserver.Tosimplifynotation,weusetodenotethedeparturetrafficofflowfromserveraswellasthearrivaltrafficofflowtoserver.Asin[7],wecallanon-negativeandnon-decreasingfunctionasthesourcetrafficenvelopeofflowif,

(5)

Wealsoassumethatthenetworkisstableiffor

,

(6)

whereisthenumberoftotalserversinthenetworkandisthesetofallflowsservedbyserverandisthecapacityofserver.Accordingto[20,24],acyclicnetworksorcyclicnetworkswithringtopologyarestableifInequality(6)issatisfied.

3.2.VirtualPartition

Here,wedefineessentialtraffic3asafundamentalnotionforanalysisofcoordinatedsched-ulersthatenablesustoaccuratelyboundthequeueingdelayexperiencedbythetraffic.Inparticular,foragiventime,allarrivingtrafficofserverarrivingincanbevirtuallydecomposedaccordingtowhetherornotitspriorityindexislargerthan.Asonlytheportionoftrafficwithpriorityindexsmallerthanorequaltotimeaffectsthetimewhentrafficwithpriorityindexisserved,werefertothistrafficasessentialtraffic,whichweformallydefineasfollows.

Definition2(EssentialTraffic)Theessentialarrivaltrafficofflowattimerelativeto()atserverisdefinedasthetotalflow-trafficwithpriorityindexnolargerthanarrivingatserverin,i.e.,

(7)

Asanexample,forthetrafficwiththearrivalpatterndescribedinFigure1(a),somevaluesofitsessentialtrafficaregivenas:if;if;

if;if.

Foraserverwithpriorityscheduling,oneofitsimportantcharacteristicsisthevoidtimebeforeagiventime,andrelativeto(),denotedbyanddefinedas

and

(8)

whereisthetotalamountoftraffic,withpriorityindexsmallerthanorequalto,queueingatserverattime.Inotherwords,voidtimereferstothelargesttimelessthansuchthatthereisnotrafficbackloggedwithpriorityindexsmallerthanorequalto.Noticethatforaninitiallyidlenetwork,thevoidtimeisguaranteedtoexist.

3.3.BurstinessBoundattheIngressServer

Tocomputetheboundsofqueueingdelayssufferedbythetrafficatserverattime,weonlyneedtoconsidertheessentialtrafficarrivingin.Thisisbecauseisthelasttimebeforethatthereisnotrafficwithpriorityindexsmallerthanorequaltoqueueingatserver.Theenvelopeoftheessentialtrafficofaflowinsuchanintervalisdefinedasfollows.

Definition3(EssentialTrafficEnvelope)Anon-negative,non-decreasingfunctioncalledtheessentialtrafficenvelopeofflow-trafficatitshopif,

is(9)

where

and

isdefinedinEquation(8).4

Sincetheessentialtrafficatadownstreamserverdependsonthecorrespondingessentialtrafficattheingressserver(i.e.,thenetworkentrance),wefirstprovideanupperboundfortheessentialtrafficenvelopeattheingressserver.

Lemma1Anessentialtrafficenvelopeofflowatitsfirsthopisgivenby:

(10)

Proof:See[16].

BasedonLemma1,wehave

theschedulabilitycriterioninthenextsection.

,whichwillbeusedtoderive

3.4.DownstreamServers

Attheoutputofamultiplexer,atrafficflow’scharacteristics(suchasitstrafficenvelope)aredistorted.Withoutadditionalmechanismssuchasper-flowre-shaping,thisdistortioncanbecomemoresevereateachDownstreamnode.Wenowshowthatundercoordinatednetworkschedulers,thedistortionoftheessentialtrafficislimitedduetocoordinationitself.Thatis,aflow’sdistortionislimitedbydownstreammechanismstocatchuplatepacketsanddelayearlypackets.Recallthatweonlyconsiderstablenetworks,sothatthequeueingdelayisbounded(see[20]).

Lemma2Ifeachflow-packethasnotmisseditspriorityindexesatserverbymorethan,thenanessentialtrafficenvelopeofflowatits)isgivenby

hop(server

(11)

where

.

Proof:See[16].

Thislemmacharacterizesakeypropertyofcoordinatedschedulers,namelythataflow’strafficcharacteristicsareminimallydistortedatdownstreamservers.Specifically,ifisaconstantfor,wecanusethesameessentialtrafficenvelopetoevaluatethelocalqueueingdelaysufferedbyflowateachserveralongitspath.

4.END-TO-ENDSCHEDULABILITYCRITERION

Inthissection,wederiveageneralend-to-endschedulabilitycriterionforcoordinatedsched-ulers.Inourapproach,weallowpacketstoviolatetheirlocalpriorityindexesandexploitthecoordinationpropertytoobtainanend-to-enddelaybound.Moreover,sincepriorityindexesarenotrequiredtobeequivalenttodelaybounds,theapproachprovidesflexibilityinassignmentoflocalpriorityindexeswhichwefurtherexploitinthenextsection.

4.1.ARecursiveConditionforViolatingPackets

ForanisolatedEDFscheduler,theschedulabilitycondition(nopacketviolatesitspriorityindex)hasthoroughlybeendiscussedinseveralpapers,e.g.,[13,17,11].However,whentheschedulabilityconditioncannotbeensatisfied,itisimportanttoknowwhatistheboundfortheamountoftimebywhichpacketsmisstheirdeadlines(priorityindexes),speciallyforcoordi-natedschedulersthatallowpacketstoviolatetheirlocaldeadlines.BasedonthekeypropertyofcoordinatedschedulersexploitedinLemma2,weprovideaconditionforboundingthetimebywhichpacketsmisstheirlocaldeadlines(priorityindexes).

Theorem1Ifeacharrivingpacketatserverhasnotmisseditspriorityindexesattheprevi-5

,thenforousserverbymorethansuchthatfor

agivenflow,itspacketswillmisstheirpriorityindexatserverbyatmostif

,

(12)

where

,

,and

.

Proof:See[16].If,,and,Equation(12)istheschedulabilityconditionprovidedin[17].Thus,Theorem1isageneralizationoftheschedulabilityconditionforanisolatedEDFscheduler.

4.2.End-to-EndDelayBounds

SincetheschedulabilitycriteriongiveninEquation(12)decouplesthepriorityindexfromthedelaybound,thefollowingcorollarycanbeusedtocomputetheend-to-enddelaybound.Corollary1Giventhepriorityindexincrementassignmentsand(and

)foreachflow,iftheconditionsofTheorem1aresatisfiedforeachflowateachserver,thentheend-to-endflow-packetdelayisboundedby

(13)

Proof:See[16].

ObservethatthemaximumqueueingdelayofEquation(13)hasthreecomponents.Thefirsttermhastwointerpretationswhichweillustratebyexamples.IfthenetworkperformsCEDFasinEquation(3),thenisaconstantandrepresentsthelocaldelayboundattheingressnode.Alternatively,ifthenetworkperformsCJVC,then

i.e.,itisthemaximumpacketsizedividedbytheguaranteedrate,plusthemaximumamountoftimeaflow-packetarrivingbeforeitspreviouspacketpriorityindex.Thesecondtermisthesumoftheupperboundsofthelocalpriorityindexesfromthesecondtofinalhop.Thethirdtermrepresentsthedelaybywhichpacketsareallowedtoviolatethepriorityindexatthefinalhop.AswewillshowinSection5,thereisflexibilityinhowtoassignallthreeofthesecomponentstoobtaindifferentend-to-endperformanceproperties.

4.3.LeakyBucketFlows

Iftheessentialtrafficenvelopesattheingressserversareboundedbyaffinefunctions,theschedulabilitycriterionofTheorem1canbesimplified.Thisscenarioarisesforbothleakybucketregulatedtrafficaswellasvirtualleaky-bucketsmoothersasdescribedinSection5.1.Corollary2Ifeachflowhasand

thenInequality(12)inTheorem1canbesimplifiedas:ifforany

forwith

,,

where

6

,

,and

.

Proof:See[16].

Inthenextsection,weapplythissimplifiedschedulabilitycriteriontoassignpriorityindexesatdownstreamservers.

5.PRIORITYINDEXASSIGNMENTFOREND-TO-ENDSERVICE

Inthissection,wedevelopaparticularpriorityindexassignmentschemeandshowthatunderthescheme,coordinatedschedulerscanachievethesameend-to-enddelayboundasWFQ.

5.1.AtIngressServers

Supposetheingressnodeservicespacketsaccordingtothevirtualclockservicediscipline[10,26].Thenthepriorityindexincrementsattheingressserverare

fromthevirtualserverwithcapacity

isthedeparturetimeofthepacketofflow

,accordingtoDefinition3andLemma1,

(15)

If

,thenaccordingtoTheorem2in[10],

(17)

Noticethatinthiscase,

(19)

Proof:See[16].

Noticethattheend-to-enddelayboundinEquation(19)isthesameasthatforWFQ[20]andVC[10].Itisneededtopointoutthat,withcoordinationandtheabovesimplepriorityindexassignments,Theorem2plusasimpleexampleprovidedinthenextsectionistoourknowledgethefirstproofthatcore-statelessschedulerscanoutperformWFQschedulers.

Finally,weobservethatcoordinatedschedulerscanemployheterogeneouslyallocatedper-nodepriorityassignmentsinordertobetterutilizenetworkresources.Forexample,flowscouldallocatealessstringentpriorityindextoheavilyloadednodes.Ageneralassignmentschemeremainsanimportantissueforfuturestudyincoordinatedschedulersaswellasotherservicedisciplines.

6.COORDINATIONVS.NON-COORDINATION:NUMERICALEXAMPLESANDSIM-ULATIONS

Table1

TrafficParametersandPriorityIndexAssignment.flow1

flow2flow3

.Thetrafficparametersandthepriorityindexassignmentsare

summarizedinTable1.

Sinceeachpacketdoesnotsufferthequeueingdelayatitsfirsthop,

andtheparametersthatareneededwhencheckingthescedulabilityforflowsat

server1aregiveninTable2.

Table2

ParametersforServer1.

,weneedtoverify

(20)

and

(21)

Toverifyflow-2packetswillmisstheirpriorityindexesatserver1nomorethanweneedtocheck

,

(22)

UsingtheparametersgiveninTable1andTable2,itiseasytoverifyInequalities(20)(21)(22).

Similarly,usingtheparametersgiveninTable1andTable3,itiseasytoverifyflow-1packetswillmisstheirpriorityindexesatserver2nomorethan

ThenaccordingtoCorollary1,wehavethefollowingend-to-enddelayboundsthatcanbeguaranteedbytheCNSdiscipline.

forflow1,mustbe.Hencethebandwidths(weight)reservedforflow2atserver

1andflow3atserver2mustbezero.Therefore,inthiscase,WFQdegeneratestothestrictpriorityservicediscipline(flow1hasthehighestpriority).Accordingtotheresultprovidedin[17],theminimumdelayboundsguaranteedbythestrictpriorityservicedisciplinetoflows2and3are

6.2.SimulationExperiments

Throughoutthispaper,wehavefocusedonschedulabilityconditionsforcoordinatedsched-ulers.Here,weusens-2simulationstoillustratepotentialperformanceimprovementsfromcoordinationnotonlyinthemaximumend-to-enddelay,butalsoinstatisticaldelayproperties.

Server 1Server 2Server 3Server 4Server 5Server 6Path for target trafficPath for background traffic Figure3.SimulationTopology

WeconsiderasimpletandemnetworktopologyasdepictedinFigure3.Alllinkcapacitiesare10Mb/sec,packetlengthsare100bytes,andpropagationdelaysare0.Thereareseveralflows(varyingfrom25to60)enteringthenetworkfromthefirstserverandexitingfromthelastserver.Theseflowshavethelongestpathandarechosentobethetargetclassforanalysis.Inaddition,eachserveralsoservestwoclassesofcrosstrafficconsistingof125flowswhichtraverseasinglerouterandthenexitthenetwork,and125flowsthattraversetworoutersandthenexit.Thecrosstraffichasthesamecharacteristicsasthetargettraffic.

99% Percentile End-to-End Delay (msec)25020015010050WFQCNS99% Percentile End-to-End Delay (msec)30030025020015010050EDFCNS275280285290295300305310275280285290295300305310Number of Flows at Each ServerNumber of Flows at Each Server(a)ComparisonofCNSandWFQFigure4.ExponentialOn-OffTraffic

(b)ComparisonofCNSandEDF

WesimulatebothexponentialandParetoon-offflowswithon-rateKb/sec,meanontime312msecandmeanofftime325msecandParetashapeparameter1.9.Theincrementofthepriorityindexateachserveris1msecforthetargettraffic,3msecforthecrosstrafficwitha2-hoppath,and6msecforcrosstrafficwitha1-hoppath.Wecomparethe99-percentileend-to-enddelayexperiencedbythetargettrafficfornetworkswithCNS,EDF,andWFQschedulers.ThesimulationresultsaredepictedinFigures4and5.Eachpointinthefigurerepresentstheresultofa200secondns-2simulationrun,withaveragesreportedovermultiplesimulations.Thefigureshowsthe99.9-percentileoftheend-to-enddelaydistributionofthetargettrafficasafunctionofthenumberofflowspassingeachserver.

Wemaketwoobservationsregardingthefigures.First,coordinationhasreducedthe99-percentileend-to-enddelayexperiencedbythetargettraffic:forexample,inFigure4,wheneachserversupports295exponentialon-offtrafficflows(45targetflowsand250crosstraffic

flows),theend-to-enddelayexperiencedbythetargettrafficis40msecforCNS,66msecforWFQ,and51msecforEDF.ThereasonforthisisthatinaCNSnetwork,packetswhichsufferexcessivequeueingdelaysatupstreamnodeshaveanopportunityto“catchup”atadownstreamnode,byhavingahigher(relative)priorityindex.Incontrast,inEDForWFQnetworks,eachroutertreatspacketslocallyaccordingtotheirarrivaltime,withoutregardtowhetherthisarrivaltimeislateorearly.

Second,whentrafficismorebursty,e.g.,forParetoon-offtraffic,theadvantageofCNSoverWFQorEDFisevenmorepronounced.Forexample,inFigure5,wheneachserversupports295Paretoon-offtrafficflows(45targetflowsand250crosstrafficflows),theend-to-enddelayexperiencedbythetargettrafficis52msecforCNS,111msecforWFQ,and109msecforEDF.Thereasonforthisisthattheheavy-tailedburstdurationsofthistrafficplaceaheavierburdenontheschedulerduringperiodsofoverload.Throughinter-servercoordination,CNScanbetterdistributethisoverloadamongnetworknodesandreduceaflow’send-to-enddelay.

99% Percentile End-to-End Delay (msec)25020015010050WFQCNS99% Percentile End-to-End Delay (msec)30030025020015010050EDFCNS275280285290295300305310275280285290295300305310Number of Flows at Each ServerNumber of Flows at Each Server(a)ComparisonofCNSandWFQFigure5.ParetoOn-OffTraffic

(b)ComparisonofCNSandEDF

7.CONCLUSION

Inthispaper,wederivedanend-to-endschedulabilitycriterionforaclassofworkconservingservicedisciplinestermedcoordinatedschedulers.Exploitingthecoordinationproperty,weshowedthatthe“essentialtraffic”foraflowincursonlyminimaldistortionatdownstreamnodes.Moreover,weshowedthatpacketscanbeallowedtoviolatelocalpriorityindexes(suchaslocaldeadlines)andstillsatisfyanend-to-endrequirementby“catchingup”withhigherprioritydownstream.Wethendevisedapriorityassignmentschemeandshowedthatunderthescheme,coordinatedschedulerscanoutperformWFQschedulers.Finally,wepresentednumericalandsimulationresultstoquantifytheperformancegainsofcoordination.REFERENCES

1.M.Andrews.Probabilisticend-to-enddelayboundsforearliestdeadlinefirstscheduling.InProceedingsof

IEEEINFOCOM2000,TelAviv,Israel,March2000.

2.M.AndrewsandL.Zhang.Minimizingend-to-enddelayinhigh-speednetworkswithasimplecoordinated

schedule.InProceedingsofIEEEINFOCOM’99,NewYork,NY,March1999.

3.J.LeBoudec.Applicationofnetworkcalculustoguaranteedservicenetworks.IEEETransactionsonInfor-mationTheory,44(3):1087–96,May1998.

4.Z.Cao,Z.Wang,andE.Zegura.Rainbowfairqueueing:Fairbandwidthsharingwithoutper-flowstate.In

ProceedingsofIEEEINFOCOM2000,TelAviv,Israel,March2000.

5.T.Chen,J.Walrand,andD.Messerschmitt.Dynamicpriorityprotocolsforpacketvoice.IEEEJournalon

SelectedAreasinCommunications,7(5):632–3,19.

6.D.Clark,S.Shenker,andL.Zhang.Supportingreal-timeapplicationsinanintegratedservicespacketnetwork:

Architectureandmechanism.InProceedingsofACMSIGCOMM’92,pages14–26,Baltimore,Maryland,August1992.

7.R.Cruz.Acalculusfornetworkdelay,partsIandII.IEEETransactionsonInformationTheory,37(1):114–

141,January1991.

8.R.Cruz.Qualityofserviceguaranteesinvirtualcircuitswitchednetworks.IEEEJournalonSelectedAreas

inCommunications,13(6):1048–1056,August1995.

9.C.DovrolisandP.Ramanathan.Acaseforrelativedifferentiatedservicesandtheproportionaldifferentiation

model.IEEENetwork,13(5):26–35,September1999.

10.N.FigueiraandJ.Pasquale.Anupperboundondelayforthevirtualclockservicediscipline.IEEE/ACM

TransactionsonNetworking,3(4):399–408,August1995.

11.V.Firoiu,J.Kurose,andD.Towsley.EfficientadmissioncontrolforEDFschedulers.InProceedingsofIEEE

INFOCOM’97,pages310–317,Kobe,Japan,April1997.

12.S.FloydandV.Jacobson.Link-sharingandresourcemanagementmodelsforpacketnetwork.IEEE/ACM

TransactionsonNetworking,3(4):365–386,August1995.13.L.Georgiadis,R.Gu´erin,andA.Parekh.Optimalmultiplexingonasinglelink:Delayandbufferrequire-ments.IEEE/ACMTransactionsonInformationTheory,43(5),1997.14.L.Georgiadis,R.Gu´erin,V.Peris,andK.Sivarajan.EfficientnetworkQoSprovisioningbasedonpernode

trafficshaping.IEEE/ACMTransactionsonNetworking,4(4):482–501,August1996.

15.C.LiandE.Knightly.Coordinatednetworkscheduling:Aframeworkforend-to-endservices.InProceedings

ofIEEEICNP’00,Osaka,Japan,November2000.

16.C.LiandE.Knightly.Schedulabilitycriterionandperformanceanalysisofcoordinatedschedulers,2001.

TechnicalReport(http://www.ece.rice.edu/networks/publications.html).

17.J.Liebeherr,D.Wrege,andD.Ferrari.Exactadmissioncontrolfornetworkswithboundeddelayservices.

IEEE/ACMTransactionsonNetworking,4(6):885–901,December1996.

18.T.Nandagopal,N.Venkitaraman,R.Sivakumar,andV.Bharghavan.Relativedelaydifferentationanddelay

classadaptationincore-statelessnetworks.InProceedingsofIEEEINFOCOM2000,TelAviv,Israel,March2000.

19.A.ParekhandR.Gallager.Ageneralizedprocessorsharingapproachtoflowcontrolinintegratedservices

networks:thesingle-nodecase.IEEE/ACMTransactionsonNetworking,1(3):344–357,June1993.

20.A.ParekhandR.Gallager.Ageneralizedprocessorsharingapproachtoflowcontrolinintegratedservices

networks:themultiplenodecase.IEEE/ACMTransactionsonNetworking,2(2):137–150,April1994.

21.H.Sariowan,R.Cruz,andG.Polyzos.SCED:ageneralizedschedulingpolicyforguaranteeingquality-of-service.IEEE/ACMTransactionsonNetworking,7(5):669–684,October1999.

22.I.Stoica,S.Shenker,andH.Zhang.Core-StatelessFairQueueing:Ascalablearchitecturetoapproximatefair

bandwidthallocationsinhighspeednetworks.InProceedingsofACMSIGCOMM’98,Vancouver,BritishColumbia,September1998.

23.I.StoicaandH.Zhang.Providingguaranteedserviceswithoutperflowmanagement.InProceedingsofACM

SIGCOMM’99,Cambridge,MA,August1999.

24.L.TassiulasandL.Georgiadis.Anywork-concervingpolicystabilizestheringwithspatialre-use.IEEE/ACM

TransactionsonNetworking,4(2):205–208,April1996.

25.H.ZhangandD.Ferrari.Rate-controlledservicedisciplines.JournalofHighSpeedNetworks,3(4):3–412,

1994.

26.L.Zhang.Virtualclock:Anewtrafficcontrolalgorithmforpacketswitchingnetworks.InProceedingsof

ACMSIGCOMM’90,pages19–29,Philadelphia,PA,September1990.

27.Z.Zhang,Z.Duan,andY.Hou.Virtualtimereferencesystem:Aunifyingschedulingframeworkforscalable

supportofguaranteedservices.IEEEJournalonSelectedAreasinCommunications,18(12):2684–2695,December2000.

28.K.Zhu,Y.Zhuang,andY.Viniotis.Achievingend-to-enddelayboundsbyEDFschedulingwithouttraffic

shaping.InProceedingsofIEEEINFOCOM’01,Anchorage,Alaska,April2001.