Monotonie-et-stabilite-des-syst`emes-de-polling

MonotonicityandstabilityofperiodicpollingmodelsChristineFricker1,M.RaoufJabi2Abstract.Thispaperdealswiththestabilityofperiodicpollingmodelswithmixedservicepolicies.Theinterarrivalstoallqueuesareindependentandexpo-nentiallydistributedandtheserviceandtheswitch-overtimesareindepen-dentwithgeneraldistributions.Thenecessaryandsucientconditionforthestabilityofsuchpollingsystemsisestablished.Theproofisbasedonthestochasticmonotonicityofthestateprocessatthepollinginstants.Thestabilityofonlyasubsetofthequeuesisalsoanalyzed,and,incaseofheavytrac,theorderofexplosionofthequeuesisgiven.1INRIA,domainedeVoluceauB.P.105,78153LeChesnayCedex,France2TilburgUniversityP.O.Box90153,5000LETilburg,TheNetherlandsiMonotonieetstabilitedessystemesdepollingChristineFricker1,M.RaoufJabi2Resume.Cepapieretudielesproprietesdestabilitedesmodelesdepollingperiodiquesavecdespolitiquesdeserviceheterogenes.Lesprocessusd’arriveeauxlesd’attentesontdePoisson.Lesservicesetlestempsdepassaged’uneleal’autresontdesvariablesaleatoiresindependantesdedistributiongenerale.Laconditionnecessaireetsusantedestabilitedecesmodelesestetablie.Lapreuvesebasesurlaproprietedemonotoniedecesmodelesauxin-stantsd’arriveeduserveurauxles.Lastabilited’unsousensembledeslesd’attenteestetudieeetdanslecasd’unmodeleavechauttrac,lavitessed’explosiondelatailledeslesd’attenteestdonnee.1INRIA,domainedeVoluceauB.P.105,78153LeChesnayCedex,France2TilburgUniversityP.O.Box90153,5000LETilburg,TheNetherlandsiiMONOTONICITYANDSTABILITYOFPERIODICPOLLINGMODELSC.Fricker1,M.R.Jabi2;z1INRIA,DomainedeVoluceauBP.105,78153LeChesnayCedex,France2TilburgUniversityP.O.Box90153,5000LETilburg,TheNetherlandsAbstractThispaperdealswiththestabilityofperiodicpollingmodelswithmixedservicepolicies,wheretheinterarrivalstoallqueuesarein-dependentandexponentiallydistributed,andwheretheserviceandtheswitch-overtimesareindependentwithgeneraldistributions.Thenecessaryandsucientconditionforthestabilityofsuchpollingsys-temsisestablished.Theproofisbasedonthestochasticmonotonicityofthestateprocessatthepollinginstants.Thestabilityofonlyasub-setofthequeuesisalsostudied,and,incaseofheavytrac,theorderofexplosionofthequeuesisgiven.Keywords:pollingsystem,stability,markovchain,stochasticmonotonicity,heavytrac.1IntroductionThispaperdealswithperiodicpollingsystemswithmixedservicepoliciesandoccurrenceofswitch-overtimes.Insuchsystems,theserverattendstozThisworkwassupportedinpartbyaFellowshipoftheNetherlandsOrganizationforScienticResearchNWO-ECOZOEK.1thequeuesaccordingtoapollingtableinacyclicway.Thequeuesmaybeservedatdierentstagesinacycle.Eachstageisruledbyaservicepolicy,notnecessarilythesameforallthestagesinacycle.Particularly,thesamequeuemaybeservedaccordingtodierentpoliciesatdierentstages.Weconsidergeneralservicepoliciessatisfyingsomepropertiesspeciedlater;thesepropertiesaresatisedbythemainservicepolicies,liketheexhaustive,thegatedandthesemi-exhaustivepoliciesintheirpureandstochasticallylimitedversions,andthetime-limitedpolicywithoutpreemption.Thestabilityconditionforsuchsystemsisknownforalongtime(Eisen-berg[1972],Kuehn[1979]).Recently,Georgiadis&Szpankowski[1992]ad-dressedthestabilityofastrictlycyclicpollingmodelservedbythel-limitedgatedpolicyatallqueues.However,nocompleteproofhasbeenprovideduptonow,atleastforperiodicsystemswithmixedservicepolicies.Thepollingsystemissaidtobestableifitadmitsastationaryregimewithintegrablecycletime.Thenecessaryandsucientconditionforthestabilityofthesystemisestablishedstraightforwardly.Forthesucientpart,theproofisessentiallybasedonthestochasticmonotonicityoftheMarkovchainrepresentingthestateofthesystematthepollinginstants.Thispropertyisinterestinginitself,and,toourknowledge,hasnotbeennoticeduptonow.Ourmainresultisthefollowingnecessaryandsucientconditionforthestabilityofthepollingsystem:+max(j=Gj)S1whereSisthemeanofthetotalswitch-overtimeinacycle,=Pjjjisthetotaltracloadofthesystem,jisthearrivalratetoqueuej,andGjisthemeanofthemaximalnumberofcustomersthatmaybeservedpercycleinqueuej(j=Gj=0ifGj=1;seeSections3and4formoredetails).Thisanalysisallowstogivethestabilityconditionforonlyasubsetofthequeues,whenthewholesystemisnotstable.Inparticular,incaseofheavytrac,theorderinwhichthequeuesbecomeunstableisgiven,providingsomeinsightintheworkingofthepollingsystem.Ourmethodextendstonondeterministicroutingoftheserverbetweenthequeues,likethemarkovianroutingforexample(Fricker&Jabi[1992])Thepaperisorganizedasfollows.InthenextSection,wedescribethemodel.Section3isdevotedtoaformaldenitionofservicepoliciesandtoaclassicationofthem.InSection4,thecrucialstochasticmonotonicityof2theMarkovchainrepresentingthestateofthesystematthepollinginstantsisprovedanddominantsub-systemsaredened.InSection5,thenecessaryandsucientconditionforthestabilityofthesystemisestablishedandthestabilityofonlyasubsetofthequeuesisstudied.2ModelDescriptionWeconsiderthefollowingmodel.Apollingsystemwithcinnitebuerqueues,indexedbyj2f1;2;:::;cg,isservedbyasingleserver.Theserverattend