排队论是专门研究带有随机因素

1、Queueing Theory2008 Queueing theory definitionsl(Bose) “the basic phenomenon of queueing arises whenever a shared facility needs to be accessed for service by a large number of jobs or customers.”l(Kleinrock) “We study the phenomena of standing, waiting, and serving, and we call this study Queueing

2、Theory. Any system in which arrivals place demands upon a finite capacity resource may be termed a queueing system.”l(Mathworld) “The study of the waiting times, lengths, and other properties of queues.”l排队论是专门研究带有排队论是专门研究带有随机随机因素，产生拥挤现象的优化理因素，产生拥挤现象的优化理论。也称为论。也称为随机随机服务服务系统。系统。 Applications of Queue

3、ing TheorylTelecommunicationslDetermining the sequence of computer operationslPredicting computer performancelOne of the key modeling techniques for computer systems / networks in generallVast literature on queuing theorylNicely suited for network analysislTraffic control lAirport traffic, airline t

4、icket saleslLayout of manufacturing systemslHealth services (eg. control of hospital bed assignments) Queuing theory for studying networkslView network as collections of queues lFIFO data-structures lQueuing theory provides probabilistic analysis of these queueslExamples: lAverage length (buffer) lA

5、verage waiting timelProbability queue is at a certain length lProbability a packet will be lost lUse Queuing models to lDescribe the behavior of queuing systemslEvaluate system performanceModel Queuing System Queuing System Queue Server Customers Time TimeArrival eventDelayBegin serviceBegin service

6、Arrival eventDelayActivityActivityEnd serviceEnd serviceCustomer n+1Customer nInterarrivalCharacteristics of queuing systems Kendall Notation 1/2/3(/4/5/6)nArrival DistributionnService DistributionnNumber of servers nTotal storage (including servers) (infinite if not specified) nPopulation Size (inf

7、inite if not specified) nService Discipline (FCFS/FIFO) DistributionslM: stands for Markovian / Poisson , implying exponential distribution for service times or inter-arrival times. lD: Deterministic (e.g. fixed constant) lEk: Erlang with parameter klHk: Hyperexponential with param. klG: General (an

8、ything) Poisson process & exponential distributionlInter-arrival time t (time between arrivals) in a Poisson process follows exponential distribution with parameter (mean)l无后效性无后效性 不管多长时间不管多长时间( t)已经过去，逗留已经过去，逗留时间的概率分布与下一个事件的相同时间的概率分布与下一个事件的相同1)()Pr(tEett fT(t)t1)(TEExampleslM/M/1: lPoisson arri

9、vals and exponential service, 1 server, infinite capacity and population, FCFS (FIFO)lthe simplest realistic queuelM/M/m/mlSame, but lm servers, lm storage (including servers)lEx: telephone Analysis of M/M/1 queuelGiven: : Arrival rate (mean) of customers (jobs) (packets on input link) m m: Service

10、rate (mean) of the server (output link) lSolve:lL: average number in queuing systemlLq average number in the queue “1”lW: average waiting time in whole systemlWq average waiting time in the queue “1/m m”M/M/1 queue model m m m1WqWLLqDerivation 012k-1kk+1.PoP1Pk -1PkmPkmPk +1mP1mP2P0mP1P1mP2PkmPk+1si

11、nce all probability sum to onePkkP0mkkP0mkP0k 0 1Solving W, Wq and Lq For stability, mean arrival rate must be less than mean service rate Utility factor 1m2,111,(1)(1)(1)qqnnLLWWPmmmResponse Time vs. Arrivalsm1WWaiting vs. Utilization00.050.10.150.20.2500.20.40.60.811.2W(sec) ExamplelOn a network r

12、outer, measurements show lthe packets arrive at a mean rate of 125 packets per second (pps) lthe router takes about 2 millisecs to forward a packet lAssuming an M/M/1 modellWhat is the probability of buffer overflow if the router had only 13 bufferslHow many buffers are needed to keep packet loss below one packet per million?ExamplenArrival rate = 125 ppsnService rate = 1/0.002 = 500 ppsnRouter utilization = / = 0.25nProb. of n packets in router =nMean number of packets in router =nn)25. 0(75. 0)1 (33. 057. 025. 01ExamplenProbab