Study of a Class of Partially Ordered Service Stra

StudyofaClassofPartiallyOrderedServiceStrategiesforaSystemofTwoDiscrete-TimeQueuesIoannisStavrakakisySophiaTsakiridouzyDept.ofElectricalandComputerEngineeringNortheasternUniversityBoston,MA02115zDept.ofElectricalandComputerEngineeringQueen’sUniversityKingston,OntarioK7L3N6,CanadaAbstractAdiscrete-timesystemoftwoqueuesservedaccordingtodistinctpoliciesisstudiedinthispaper:onequeuereceives1-limitedservice;theotherisservedaccordingtosomepolicyfromtheintroducedclassof(statedependent)policiesS.ClassScontainstraditionalservicepoliciesaswellasad-hocpolicies.ApartialperformanceorderingofpoliciesinSisderivedwhichcanbeusefulindesigningad-hocpolicieswithimprovedperformancecomparedtothatoftraditionalpolicies.Someexamplesofad-hocpoliciesinSarepresentedandnumericalresultsarederivedtoillustratethepotentialforeciencyprovidedbyservicepoliciesinS.ResearchsupportedinpartbytheNationalScienceFoundationundergrantNCR-9011962andbytheAdvancedResearchProjectAgency(ARPA)underGrantF49620-93-1-0564monitoredbytheAirForceOceofScienticResearch(AFOSR).ThisworkwasconductedwhiletheauthorswerewiththeDepartmentofElectricalEngineeringandComputerScienceoftheUniversityofVermont,Burlington,VT05405,USA.1IntroductionDiscrete-timequeueingsystemshavewidelybeenadoptedforthestudyofpacketcommunicationnetworks,wherepacketprocessesaredescribedintermsofdiscrete-timestochasticpointprocesses.Theservicepoliciesassociatedwithsuchsystemsmodeltheprotocolsthatgoverntheavailabilityofnetworkresourcestothepackets,usersorclassesofusers.Thedistributednatureofanetworkingsystemand/orthediversiedservicerequirementsofthesupportedusersnecessitatethedevelopmentofsophisticatedresourceallocationprotocolsmodeledintermsofqueueingsystemsundervariousservicepolicies.Examplesaretheexhaustive,gatedandlimitedservicepolicieswhichhavebeenstudiedextensively,primarilyincontinuoustime,inthecontextofpolling[1,2],andvacationsystems[3],andtheconsistentgated/limitedpolicy[4]whichhasbeenappliedforthestudyoftheDQDBnetwork[5,6].Adiscrete-timesingleserverqueueingsystemconsistedoftwoqueuesisconsideredinthispaper.Oneofthequeuesreceives1-limitedservice,theotherisservedaccordingtoapolicycontainedinaversatileclassofstate-dependentservicepoliciesS.Thisclasscontainssomeofthewell-knownservicepoliciesaswellasnewad-hocpolicieswhichmayprovideforimprovedperformancecomparedtothatundertraditionalpolicies.Thesystemstudiedinthispapermaybeconsideredasavariantofatwo-queueasymmetricpollingsystemwith1-limitedserviceatonequeueandserviceaccordingtoapolicyinSattheother.Whenbothqueuesreceive1-limitedservicethesystemoperatesunderanalternatingservicepolicy,whichhasbeenanalyzedincontinuoustime,[7].Acontinuous-timetwo-queuemodelwithmixedexhaustiveandlimitedserviceshasbeenstudiedin[8].Adiscrete-timemodelwithgatedand1-limitedserviceshasbeenanalyzedin[4].ThesystemconsideredinthispapermayalsobedescribedintermsofaGI/D/1innitequeuewithservervacations.Thevacationperioddistributiondependsontheoccupancyofthequeuewhichisservedduringthevacation.ThequeueingmodelandanalysisdevelopedinthispaperarealsoapplicabletoasystemwithvacationperioddistributionsthatdependonthestateofaMarkovprocesswhichevolvesindependentlyofthesystem,[9].Thisstate-dependentvacationmodelisdierentfrommostofthosepresentedinthepast,forexample[10]and[11],inthefollowingaspect:theprocesswhosestatedeterminestheoccurrenceanddistributionofvacationperiodsisexternaltothequeueunderstudy.Theanalysisisbasedonmatrixanalytictechniquessimilartothoseappliedforthestudyofthevacationmodelin[12].1ThedetaileddescriptionofthequeueingsystemandauniedrepresentationoftheclassofservicepoliciesSarepresentedinthefollowingsection.InSection3,aqueueingmodelforthesystemisformulatedandanalyzed.ThejointprobabilitydistributionofthequeueoccupanciesisderivedbyapplyingmatrixanalyticmethodsandMarkovrenewaltheoryarguments.Section4presentsapartialperformanceorderingforpoliciesinS.SomenumericalresultswhichillustratetheeectofvariousservicedisciplinesontheperformanceofthesystemarepresentedinSection5.TheworkissummarizedinSection6.2DescriptionoftheQueueingSystem2.1IntroductionConsiderthediscrete-timequeueingsystemshowninFig.1.Thepacketservicetimeisassumedtobeconstantandequaltothesystemtimeunit(slot).Unlessotherwisestated,asuperscriptI(F)willindicateaquantityassociatedwithqueueQI(QF).ThecapacitiesofqueuesQFandQIareassumedtobeN1andinnite,respectively.LetnqIjoj0andnqFjoj0denotetheassociatedqueueoccupancyprocesseswithstatespacesRI=f0;1;2;:::gandRF=f0;1;:::;Ng.ThesystemservicedisciplineisdeterminedbythegeneralrulespresentedinSection2.2andtheadoptedservicepolicyinSpresentedinSection2.3.Abriefintroductiontotheservicedisciplineispresentedrst.Theserverneveridlesaslongasthereisservicetobeperformed.UponswitchingtoQF,theserverservesanumberofF-packets(packetsinQF)whichdependsonthenumberofpacketsfoundinQFandthenumberofpacketsleftinQI.IfthenumberofF-packetsservedcannotexceedthenumberofF-packetsalreadypresentinQFattheswitchinginstant,thenthisstate-policy(seeSection2.3)willbecalledgated.Otherwise,itwillbecallednon-gated