A_Short_Introduction_to_Queueing_Theory

AShortIntroductiontoQueueingTheoryAndreasWilligTechnicalUniversityBerlin,TelecommunicationNetworksGroupSekr.FT5-2,Einsteinufer25,10587Berlinemail:[e-mail]21,1999Contents1Introduction31.1Disclaimer............................................31.2ScopeofQueueingTheory...................................31.3BasicModelandNotation...................................41.4Little’sLaw...........................................62MarkovianSystems92.1TheM/M/1-Queue.......................................92.1.1Steady-StateProbabilities...............................102.1.2SomePerformanceMeasures.............................122.2TheM/M/m-Queue......................................142.2.1Steady-StateProbabilities...............................142.2.2SomePerformanceMeasures.............................142.3TheM/M/1/K-Queue.....................................152.3.1Steady-StateProbabilities...............................152.3.2SomePerformanceMeasures.............................162.4AcomparisonofdifferentQueueingSystems........................173TheM/G/1-System193.1SomeRenewalTheoryResults.................................193.2ThePASTATheorem......................................213.3TheMeanResponseTimeandMeanNumberofCustomersintheSystem/Pollaczek-KhintchineMeanValueFormulas...............................213.4DistributionoftheNumberofCustomersintheSystem..................233.5TwoExamples..........................................263.5.1TheM/M/1Queue...................................263.5.2TheM/D/1Queue...................................263.6DistributionoftheCustomerResponseTimes........................274QueueingNetworks284.1Notation.............................................304.2ProductFormNetworks....................................314.2.1TheJacksonTheoremforOpenQueueingNetworks...............324.2.2TheGordon-NewellTheoremforClosedQueueingNetworks..........3314.3MeanValueAnalysis......................................33AProbabilityGeneratingFunctionsandLinearTransforms36A.1ProbabilityGeneratingFunctions...............................36A.2LaplaceTransform.......................................382Chapter1Introduction1.1DisclaimerThisscriptisintendedtobeashortintroductiontothefieldofqueueingtheory,servingasamod-ulewithinthelecture“LeistungsbewertungvonKommunikationsnetzen”ofProf.AdamWoliszfromtheTelecommunicationNetworksGroupatTechnicalUniversityBerlin.Itcoversthemostim-portantqueueingsystemswithasingleservicecenter,forqueueingnetworksonlysomebasicsarementioned.Thisscriptisneithercompletenorerrorfree.However,weareinterestedinimprovingthisscriptandwewouldappreciateanykindof(constructive)commentor“bugreports”[e-mail]hematicaldetailsareomitted,insteadoften“intuitive”(orbetter:prosaic)argumentsareused.Mostoftheformulasareonlyusedduringaderivationandhavenonumbers,however,theimportantformulasarenumbered.Theauthorwastoolazytoannotateallstatementswithareference,sincemostofthematerialcanbefoundinthestandardliterature.1.2ScopeofQueueingTheoryQueueingTheoryismainlyseenasabranchofappliedprobabilitytheory.Itsapplicationsareindifferentfields,e.g.communicationnetworks,computersystems,machineplantsandsoforth.Forthisareathereexistsahugebodyofpublications,alistofintroductoryormoreadvancedtextsonqueueingtheoryisfoundinthebibliography.Somegoodintroductorybooksare[9],[2],[11],[16].Thesubjectofqueueingtheorycanbedescribedasfollows:consideraservicecenterandapopu-lationofcustomers,whichatsometimesentertheservicecenterinordertoobtainservice.Itisoftenthecasethattheservicecentercanonlyservealimitednumberofcustomers1.Ifanewcustomerar-rivesandtheserviceisexhausted,heentersawaitinglineandwaitsuntiltheservicefacilitybecomesavailable.Sowecanidentifythreemainelementsofaservicecenter:apopulationofcustomers,theservicefacilityandthewaitingline.Alsowithinthescopeofqueueingtheoryisthecasewheresev-eralservicecentersarearrangedinanetworkandasinglecustomercanwalkthroughthisnetworkataspecificpath,visitingseveralservicecenters.1Sincequeueingtheoryisappliedindifferentfields,alsothetermsjobandtaskareoftenusedinsteadcustomer.Theservicecenterisoftennamedprocessorormachine3Asasimpleexampleofaservicecenterconsideranairlinecounter:passengersareexpectedtocheckin,beforetheycanentertheplane.Thecheck-inisusuallydonebyasingleemployee,however,thereareoftenmultiplepassengers.Anewlyarrivingandfriendlypassengerproceedsdirectlytotheendofthequeue,iftheservicefacility(theemployee)isbusy.ThiscorrespondstoaFIFOservice(firstin,firstout).Someexamplesoftheuseofqueueingtheoryinnetworkingarethedimensioningofbuffersinroutersormultiplexers,determiningthenumberoftrunksinacentralofficeinPOTS,calculatingend-to-endthroughputinnetworksandsoforth.QueueingTheorytriestoanswerquestionslikee.g.themeanwaitingtimeinthequeue,themeansystemresponsetime(waitingtimeinthequeueplusservicetimes),meanutilizationoftheservicefacility,distributionofthenumberofcustomersinthequeue,distributionofthenumberofcustomersinthesystemandsoforth.Theseq