Some Qualitative Properties in Polling Systems

..UNITEDERECHERCHEINRIA-SOPHIAANTIPOLISInstitutNationaldeRechercheenInformatiqueetenAutomatiqueSophiaAntipolisB.P.10906561ValbonneCedexFranceTel.:93657777RapportsdeRechercheNo1596Programme1Architecturesparalleles,Basesdedonnees,ReseauxetSystemesdistribuesSOMEQUALITATIVEPROPERTIESINPOLLINGSYSTEMSEitanALTMANPanagiotisKONSTANTOPOULOSZhenLIUFevrier1992SomeQualitativePropertiesinPollingSystemsEitanALTMAN,PanagiotisKONSTANTOPOULOS,ZhenLIUINRIACentreSophiaAntipolis2004RoutedesLucioles06560Valbonne,FranceAbstractConsiderapollingsystemwithK1queuesandasingleserverthatvisitsthequeuesinacyclicorder.Thepollingdisciplineineachqueueisofgeneralgated-typeorexhaustive-type.WeassumethatineachqueuethearrivaltimesformaPoissonprocess,andthattheservicetimes,thewalkingtimesaswellastheset-uptimesformsequencesofindependentandidenticallydistributedrandomvariables.Forsuchasystem,weprovidesucientconditionsunderwhichthevectorofqueuelengthsisstable.Wetreatseveralcriterionsforstability:theergodicityoftheprocess,thegeometricergodicity,andthegeometricrateofconvergenceoftherstmoment.Theergodicityimpliestheweakconvergenceofstationtimes,intervisittimesandcycletimes.Next,weshowthatthequeuelengths,stationtimes,intervisittimesandcycletimesarestochasticallyincreasinginarrivalrates,inservicetimes,inwalkingtimesandinset-uptimes.Thestabilityconditionsandthestochasticmonotonicityresultsareextendedtothepollingsystemswithadditionalcustomerroutingbetweenthequeues,aswellasbulkandcorrelatedarrivals.Forpollingsystemswithmixedlimited,gatedandexhaustiveservicedisciplinesandwithoutset-uptimes,weprovethattheweightedsumofmeanwaitingtimesincreasesinthearrivalrate,intherstandsecondmomentsofthetheservicetimesandinthevariancesofthewalkingtimes.Thismonotonicityalsoholdswithrespecttothemeanwalkingtimesiftheyaredeterministicorifthereare\manyqueuesorthesystemisheavilyloaded.Finally,weprovethatthemeancycletime,themeanintervisittimeandthemeanstationtimesareinvariantundergeneralservicedisciplinesandgeneralstationaryarrivalandserviceprocesses.Keywords:Pollingsystem,stabilitycondition,monotonicity,stochasticcomparison,invariantquantities.11IntroductionTheaimofthispaperistoestablishsomebasicpropertiesofpollingsystemsundergeneralservicedisciplines.Thepollingsystemunderconsiderationconsistsofasingleserverwhichservescustomersfromdierentqueuesinacyclicorder.Theservicedisciplineineachqueueisofgeneralgated-typeorexhaustive-type.Intherstcase,whentheserverarrivesataqueue,thenumberofcustomersthatareservedisa(possiblyrandomized)functionofthenumberofcustomersinthatqueueatthearrivalinstantoftheserver.Thisincludesasspecialcasesthe(purely)gatedandthegated-limited.Intheexhaustive-typediscipline,serviceisgiveninaqueuetillthenumberofcustomersde-creasesbyanumberwhichisa(possiblyrandom)functionofthenumberofcustomersfoundbytheserveruponarrival.Thedecrementingserviceandtheexhaustiveservicearespecialcasesofthisservicediscipline.SuchgeneraldisciplineswererstintroducedbyLevy,SidiandBoxma[17].FourkindsofresultsareobtainedundertheassumptionthatineachqueuethearrivaltimesformaPoissonprocess,andthattheservicetimes,thewalkingtimesaswellastheset-uptimesformsequencesofindependentandidenticallydistributed(i.i.d.)randomvariables(RVs).Theseassumptionsarerelaxedfortheinvarianceresult.Therstresultisonthestabilityconditions.Forthegeneralpollingsystemdescribedabove,weuseFoster’scriteriontoobtainnewsucientconditionsfortheergodicityofthequeuelengths,aswellasforthegeometricergodicity(seedenitionine.g.[2,p.144]).Wealsoshowthattheergodicitythenimpliesthestationarityofthecycletimes,andthatthegeometricergodicityimpliesthegeometricrateofconvergenceoftherstmomentofthequeuelengths.Intheliterature,somegeneralsucientconditionsforstabilityofgatedandexhaustiveconditionswereobtainedbyZhdanovandSaksonov[29],wheretheinterarrivaltimesareallowedtobei.i.d.randomvariables.Kuehn[15]andGreorgiadisandSzpankowski[11]presentedthestabilityconditionforthelimitedservicediscipline.TheinterestedreaderisreferredtoTakagi[26]forfurtherreferences.Second,weanalyzethestochasticmonotonicityofthequeuelengths,thecycletimes,theintervisittimesandthestationtimeswithrespectto(w.r.t.)thesystemparameterssuchasthearrivalrate,theservicetimes,thewalkingtimesandtheset-uptimes.Weshowthatthequeuelengths,thecycletimes,theintervisittimesandthestationtimesarestochasticallyincreasinginarrivalrates,inservicetimes,inwalkingtimesandinset-uptimes.Thismonotonicityalsoholds2withrespecttothenumberofqueuesinthesystem.Alltheseresultsonthestabilityandmonotonicityareextendedtothesystemswithcustomerroutingandbulkandcorrelatedarrivals.Insuchacase,thecustomers,attheendofservice,mayberoutedtootherqueuesinthesystemorrejointhesamequeueforanotherportionofservice.PollingsystemswithsuchroutingmechanimsareanalyzedbySidi,LevyandFuhrmann[22]underthe(purely)gatedand(fully)exhaustiveservicedisciplines.WefurtherconsiderthecasewheretheexternalarrivalsofthecustomersarecontrolledbyasinglePoissonprocess.Atanarrivalepoch,arandomnumberofcustomersaresenttoeachofthequeues.Third,wees