Asymptotic behavior of generalized processor shari

CentrumvoorWiskundeenInformaticaAsymptoticbehaviorofgeneralizedprocessorsharingwithlong-tailedtrafficsourcesS.C.Borst,O.J.Boxma,P.R.JelenkovicProbability,NetworksandAlgorithms(PNA)PNA-R9916December31,1999ReportPNA-R9916ISSN1386-3711CWIP.O.Box940791090GBAmsterdamTheNetherlandsCWIistheNationalResearchInstituteforMathematicsandComputerScience.CWIispartoftheStichtingMathematischCentrum(SMC),theDutchfoundationforpromotionofmathematicsandcomputerscienceandtheirapplications.SMCissponsoredbytheNetherlandsOrganizationforScientificResearch(NWO).CWIisamemberofERCIM,theEuropeanResearchConsortiumforInformaticsandMathematics.Copyright©StichtingMathematischCentrumP.O.Box94079,1090GBAmsterdam(NL)Kruislaan413,1098SJAmsterdam(NL)Telephone[phone]Telefax+31205924199AsymptoticBehaviorofGeneralizedProcessorSharingwithLong-TailedTrafficSourcesSemBorst∗,∗∗,†,OnnoBoxma∗,∗∗,PredragJelenkovi´c‡∗CWIP.O.Box94079,1090GBAmsterdam,TheNetherlands∗∗DepartmentofMathematics&ComputingScienceEindhovenUniversityofTechnologyP.O.Box513,5600MBEindhoven,TheNetherlands†BellLaboratories,LucentTechnologiesP.O.Box636,MurrayHill,NJ07974,USA‡DepartmentofElectricalEngineeringColumbiaUniversityNewYork,NY10027,USAABSTRACTWeanalyzetheasymptoticbehavioroflong-tailedtrafficsourcesundertheGeneralizedPro-cessorSharing(GPS)discipline.GPS-basedschedulingalgorithms,suchasWeightedFairQueueing,haveemergedasanimportantmechanismforachievingdifferentiatedquality-of-serviceinintegrated-servicesnetworks.Undercertainconditions,weprovethatinanasymptoticsenseanindividualsourcewithlong-tailedtrafficcharacteristicsiseffectivelyservedataconstantrate,whichmaybeinterpretedasthemaximumfeasibleaveragerateforthatsourcetobestable.Thus,asymptotically,thesourceisonlyaffectedbythetrafficcharacteristicsoftheothersourcesthroughtheiraveragerate.Inparticular,thesourceisessentiallyimmunefromexcessiveactivityofsourceswith‘heavier’-tailedtrafficcharacteristics.ThissuggeststhatGPS-basedschedulingalgorithmsprovideaneffectivemechanismforextractinghighmultiplexinggains,whileprotectingindi-vidualconnections.1991MathematicsSubjectClassification:60K25(primary),68M20,90B12,90B22(secondary).KeywordsandPhrases:GeneralizedProcessorSharing(GPS),long-tailed,queuelengthasymptotics,regularvariation,subexponential,WeightedFairQueueing(WFQ).Note:WorkofthefirsttwoauthorscarriedoutinpartundertheprojectPNA2.1“Commu-nicationandComputerNetworks”.11IntroductionStatisticaldataanalysishasprovidedconvincingevidenceoflong-tailed(subexponential[20])trafficcharacteristicsinhigh-speedcommunicationnetworks.Earlyindicationsofthelong-rangedependenceofEthernettraffic,attributedtolong-tailedfilesizedistributions,werereportedin[29].Long-tailedcharacteristicsofthescenelengthdistributionofMPEGvideostreamswereexploredin[21,26].Theseempiricalfindingshaveencouragedtheoreticaldevelopmentsinthemodelingandqueue-inganalysisoflong-tailedtrafficphenomena.Despitesignificantprogress,however,thepracti-calimplicationsarenotyetthoroughlyunderstood,inparticularissuesrelatingtocontrolandprioritymechanismsinthenetwork.Togainabetterunderstandingofthoseissues,thepresentpaperanalyzesthequeueingbehavioroflong-tailedtrafficsourcesundertheGeneralizedPro-cessorSharing(GPS)discipline.Asadesignparadigm,GPSisattheheartofcommonly-usedschedulingalgorithmsforhigh-speedswitches,suchasWeightedFairQueueing,seeforinstanceParekh&Gallager[32,33].Abasicapproachintheanalysisoflong-tailedtrafficphenomenaistheuseoffluidmodelswithlong-tailedarrivalprocesses(e.g.On/Offsourceswithlong-tailedOn-periods).Fluidmodelsarecloselyrelatedtotheordinarysingle-serverqueue,thusbringingwithinreachtheclassi-calresultsonregularly-varying(Cohen[18])orsubexponential(Pakes[31],Veraverbeke[35])behavioroftheserviceandwaiting-timedistributionintheGI/G/1queue.Thoseresultsareimmediatelyapplicableinthecaseofasinglelong-tailedarrivalstream,seeBoxma[10]andChoudhury&Whitt[16].Theyarealsoofusewhenasinglelong-tailedstreamismultiplexedwithexponentialstreams,seeBoxma[11],Jelenkovi´c&Lazar[24],andRolskietal.[34].Thequeueinganalysisoffluidmodelswithmultiplelong-tailedarrivalstreamsisfundamentallymoredifficultduetothecomplexdependencystructureintheaggregatearrivalprocess,seeforinstanceHeathetal.[22].Recently,Agrawaletal.[2]obtainedinterestingpartialresults.GeneralboundswerederivedinChoudhury&Whitt[16].Boxma[11]andJelenkovi´c&Lazar[24]studiedthelimitingprocessobtainedbymultiplexinganinfinitenumberofOn-Offsourceswithregularly-varyingandsubexponentialOn-periods,respectively.WerefertoBoxma&Dumas[14]foracomprehensivesurveyonfluidqueueswithlong-tailedarrivalprocesses.SeealsoJelenkovi´c[23]foranextensivelistofreferencesonsubexponentialqueueingmodels.Asmentionedabove,theimpactofprioritymechanismsonlong-tailedtrafficphenomenahasreceivedrelativelylittleattention.Somerecentstudieshaveinvestigatedtheeffectoftheschedulingdisciplineonthewaiting-timedistributionintheclassicalM/G/1queue,seeforinstanceAnantharam[3].ForFCFS,itiswell-known[18]thatthewaiting-timetailisreg-ularlyvaryingofindex1−νifftheservicetimetailisregularlyvaryingofindex−ν.ForLCFSpreemptivere