Report

Introduction Definition M/M queues M/M/1 M/M/S M/M/infinity M/M/S/K 1 Queuing system A queuing system is a place where customers arrive According to an “arrival process” To receive service from a service facility Can be broken down into three major components The input process The system structure The output process Customer Population Waiting queue Service facility 2 Characteristics of the system structure λ μ Queue Infinite or finite Service mechanism λ: arrival rate μ: service rate 1 server or S servers Queuing discipline FIFO, LIFO, priority-aware, or random 3 Queuing systems: examples Multi queue/multi servers Example: Supermarket Blade centers orchestrator . . . Multi-server/single queue Bank immigration 4 Kendall notation David Kendall A British statistician, developed a shorthand notation To describe a queuing system A/B/X/Y/Z A: Customer arriving pattern B: Service pattern X: Number of parallel servers Y: System capacity Z: Queuing discipline M: Markovian D: constant G: general Cx: coxian 5 Kendall notation: example M/M/1/infinity A queuing system having one server where Customers arrive according to a Poisson process Exponentially distributed service times M/M/S/K K M/M/S/K=0 Erlang loss queue 6 Special queuing systems Infinite server queue μ λ . . Machine interference (finite population) S repairmen N machines 7 M/M/1 queue λ μ λ: arrival rate μ: service rate λn = λ, (n >=0); μn = μ (n>=1) Pn 0 1 ... n 1 0 1 ... n P0 Pn Pn P0 ; n n n P0 P0 P1 ... Pn ... 1 P0 (1 ...) 1 P0 1 2 8 Traffic intensity rho = λ/μ It is a measure of the total arrival traffic to the system Also known as offered load Example: λ = 3/hour; 1/μ=15 min = 0.25 h Represents the fraction of time a server is busy In which case it is called the utilization factor Example: rho = 0.75 = % busy 9 Queuing systems: stability λ<μ N(t) busy => stable system 3 2 1 1 λ>μ idle 2 3 4 5 6 7 8 9 10 11 Time Steady build up of customers => unstable N(t) 3 2 1 1 2 3 4 5 6 7 8 9 10 11 Time 10 Example#1 A communication channel operating at 9600 bps Receives two type of packet streams from a gateway Type A packets have a fixed length format of 48 bits Type B packets have an exponentially distribution length With a mean of 480 bits If on the average there are 20% type A packets and 80% type B packets Calculate the utilization of this channel Assuming the combined arrival rate is 15 packets/s 11 Performance measures L Lq Mean queue length in the queue space W Mean # customers in the whole system Mean waiting time in the system Wq Mean waiting time in the queue 12 Mean queue length (M/M/1) L E[n] nP n n0 n (1 ) n n0 (1 ) ( n n 1 n0 ) (1 ) ( )' n n0 (1 ) ( )' n n0 (1 )( L 1 1 )' 1 13 Mean queue length (M/M/1) (cont’d) Lq ( n 1) P n n 1 nP n 1 n P n n 1 L (1 P0 ) L (1 (1 )) L L Lq 14