LM CCN Section 3.2: Queuing Theory
Computer and Communication Networks
Queuing Theory John Easton
1
Learning Objectives
! Queuing theory
– Modelling queues
2
Queuing Models
! As we’ve seen, network delay is largely determined by the packet arrival rate, and the internal delay of the NEs
! We can use the same principles to model queues
! The figure shows the basic elements of a queuing system
! In particular, we will focus on:
– Arrival process – Service time
3
1
LM CCN Section 3.2: Queuing Theory
Arrival Process
! We have seen that the arrival rate is given by: 𝜆=1
𝐸[𝜏]
! 𝐸[𝜏] may be described one of many processes, in particular:
– Deterministic: inter-arrival times all equal the same constant value
– Exponential: inter-arrival times are exponential random variables withmean𝐸 𝜏 =”! ⇒𝑃 𝜏>𝑡 =𝑒#$/&[(] =𝑒#”$ for𝑡>0
! For exponential inter-arrival times, the number of arrivals in time interval t, 𝐴(𝑡), is given by a Poisson random variable:
(𝜆𝑡)! “#$
𝑃𝐴𝑡 =𝑘 = 𝑘! 𝑒 for𝑘=0,1,⋯
4
Service Time
! Queue resources known as “servers” – They serve customer requests
! Time to serve each customer is known as the service time, 𝑋
! The flow through the queuing system is known as the processing capacity (or service rate), 𝜇, and is given by:
𝜇 = 1 customers / second 𝐸[𝑋]
5
Classifying Queue Models
! Queues are classified / denoted by:
! Multiplexer models: M/M/1/K, M/M/1, M/G/1, M/D/1 ! Trunk models: M/M/c/c, M/G/c/c
! User activity: M/M/∞, M/G/∞
Arrival Process / Service Time / Servers / Max Occupancy
Inter-arrival times, 𝜏
Service times,
𝑋
M = Exponential
M = Exponential
1 server
K customers
D = Deterministic
D = Deterministic
c servers
Unspecified if unlimited
G = General
G = General
infinite
Arrival rate:
𝜆 = 1/𝐸[𝑇]
Service rate:
𝜇 = 1/𝐸[𝑋]
6
2
LM CCN Section 3.2: Queuing Theory
Queuing System Variables
N(t) = number of packets in system Nq(t) = number of packets in queue Ns(t) = number of packets in servers T = total delay
W = waiting time X = service time
From Little’s theorem:
𝐸𝑁 =𝜆1−𝑃+ 𝐸𝑇
𝐸𝑁, =𝜆1−𝑃+ 𝐸𝑊 𝐸 𝑁- = 𝜆 1 − 𝑃+ 𝐸 𝑋
Offered (traffic) load 𝜌 = 𝜆𝐸 𝑋 = *” Erlangs (rateatwhich“work”arrivesatthesystem)
Carriedload=𝐸𝑋𝜆1−𝑃+ =𝜌(1−𝑃+) (average rate at which system does “work”
Utilisation=& ./ = ” 1−𝑃+ 0 *0
(average fraction of servers in use)
7
M/M/1/K Basic Multiplexer Model
! Poisson arrival process & exponential service time
! Processing rate is 𝜇 = 𝑅/𝐸[𝐿] packets/second assuming:
– Avg. packet length is 𝐸 𝐿 bits/packet
– Transmission line speed is R bits/second
! Max K packets allowed in system before overflow
– K-1 in buffer
– 1 in processor
! If 𝜆 > 𝜇 the system will loose packets
! If 𝜆 < 𝜇 the system will be able, on average, to process all
packets offered
– May loose occasional packets due to traffic peaks
– May loose packets following long consecutive service
times (long packets)
8
Derivation of Occupancy
Probabilities in M/M/1/K
! What can happen to the system in the next Δ𝑡 seconds? – There could be 0, 1, or >1 arrivals
– There could be 0, 1, or >1 departures
! As the inter-arrival times in the M/M/1/K model are exponential, it can be shown that:
– 𝑃1arrivalinΔ𝑡 =𝜆Δ𝑡+𝑜Δ𝑡
– 𝑃 0arrivalinΔ𝑡 =1−𝜆Δ𝑡+𝑜(Δ𝑡)
– For a small Δ𝑡 these imply only 1 arrival or no arrivals are likely
! As service times are also exponential, the same holds for departures vs. continuation of service beyond Δ𝑡
– 𝑃 1departureinΔ𝑡 =𝜇Δ𝑡+𝑜(Δ𝑡)
– 𝑃 0departureinΔ𝑡 =1−𝜇Δ𝑡+𝑜(Δ𝑡)
9
3
LM CCN Section 3.2: Queuing Theory
Derivation of Occupancy
Probabilities in M/M/1/K (Cont.)
! By combining the probabilities, we can estimate the probability of state changes in the system, e.g.:
𝑃[0 arrival, 0 departure in 𝛥𝑡] = {1 − 𝜇Δ𝑡 + 𝑜(Δ𝑡)}{1 − 𝜆Δ𝑡 + 𝑜(Δ𝑡)} =1− 𝜆+𝜇 Δ𝑡+𝑜(Δ𝑡)
! Similarly, it can be shown that: 𝑃1arrival,0departurein𝛥𝑡 =𝜆Δ𝑡+𝑜(Δ𝑡) 𝑃0arrival,1departurein𝛥𝑡 =𝜇Δ𝑡+𝑜(Δ𝑡)
10
Derivation of Occupancy
Probabilities in M/M/1/K (Cont.)
! From transition probabilities, we can form a state transition diagram for occupancy (represent as a state machine)
! N(t) can be seen to increase by one in the next Δ𝑡 seconds with probability 𝜆Δ𝑡, and decrease by 1 in the next Δ𝑡 seconds with probability 𝜇Δ𝑡
! The probability on the slings can be seen to be the probability of no change in state (i.e. 𝑃[0 arrivals, 0 departures in Δ𝑡])
! If the system is stable (does not grow to inf.), then long-term transition rate from n to n+1 must equal long-term transition rate from n+1 to n
11
Derivation of Occupancy
Probabilities in M/M/1/K (Cont.)
! Let 𝑝1 represent probability of n customers in the system, then 𝑝1 is also the time the system is in state n of the state transition
– Therefore 𝑝1 𝜆Δ𝑡 is the transition rate from state n to state n+1
– 𝑝12!𝜇Δ𝑡 is the transition rate from n+1 to n
! In steady state, these must be equal:
𝑝/01𝜇𝛥𝑡 = 𝑝/𝜆𝛥𝑡
! Implying:
𝑝 / 0 1 = 𝜇𝜆 𝑝 / 𝑛 = 0 , 1 , ⋯ , 𝐾
! Continuing to apply the same logic recursively gives: 𝜆 /01
𝑝/01 = 𝜇 E𝑝2 =𝑝/𝑝2 𝑛=0,1,⋯,𝐾
12
4
LM CCN Section 3.2: Queuing Theory
Derivation of Occupancy
Probabilities in M/M/1/K (Cont.)
! To find 𝑝3, we use the fact that all state probabilities must total 1: 1=𝑝2 +𝑝1 +𝑝3 +⋯+𝑝/ 𝑛=0,1,⋯,𝐾
𝜆𝜆3𝜆4 =𝑝2 1+𝜇+ 𝜇 +⋯+ 𝜇
! Recalling that 𝜌 = *” , we can restate this in terms of load: =𝑝2 1+𝜌+𝜌3+⋯+𝜌4
! Which finally gives us an expression for the probability of no customers in the system / the system being idle:
𝑝=1−𝜌
2 1 − 𝜌401
13
Derivation of Occupancy
Probabilities in M/M/1/K (Cont.)
! The probability of n packets being present in the system is then: (1 − 𝜌)𝜌/
𝑃𝑁𝑡 =𝑛 =𝑝/=1−𝜌401 for𝑛=0,1,⋯,𝐾
! The probability of blocking / packet loss in an M/M/1/K system is the same as the probability of K packets (buffers and processor are full), therefore:
𝑃5677 =𝑝4 =(1−𝜌)𝜌4 1 − 𝜌401
! The expected number of packets is: 𝐸𝑁= 𝜌 −(𝐾+1)𝜌401
1 − 𝜌 1 − 𝜌401
14
Average Delay and Loss
Performance of M/M/1/K
! From the preceding probabilities and Little’s formula it is possible to derive the following expression for the expected delay:
𝐸𝑇= 𝐸[𝑁]
𝜆(1 − 𝑃5677)
! From it, we can see that the average delay and loss performance of the M/M/1/K model are completely determined by:
– The ratio of the arrival and service rates (𝜌)
– The maximum system occupancy (K) embodied in 𝑃4566
15
5
LM CCN Section 3.2: Queuing Theory
M/M/1 – An Infinite Queue
! If you assume an infinite queue (an M/M/1 model), the following hold:
𝐸𝑁=𝜌
(1 − 𝜌)
𝐸𝑇 =𝐸[𝑁]= 1
𝜆 𝜇(1 − 𝜌)
𝐸𝑊 =𝐸𝑇 −𝐸[𝑋]= 𝜌 𝜇(1 − 𝜌)
! Note that where arrival / service times are random, perfect scheduling is not possible, so the system cannot operate at 𝜆=𝜇
16
The Effects of Scale on M/M/1
! Is it more efficient to have m independent multiplexers, or one combined system with combined input / output / processing bandwidth?
! 𝐸 𝑇6789:9$7 = !/* (!#<)
! 𝐸 𝑇05>+?17@ = !/>* = ! 𝐸 𝑇6789:9$7
(!#<) >
! The combined system performs better. Why? – Consider the idle time for the processors
17
M/M/1 and Average Packet Delay
! We earlier used a sum of NE delays to model total delay in a network
! If you assume a router can be modelled as an M/M/1 multiplexer, and that the service times of each packet at each multiplexer in the network are independent (not strictly true), you can use loads for the same trick:
𝐸𝑇/8$=L1 𝜌9
9 𝜆/8$ 1−𝜌9
! This can be used to select transmission speeds in packet- switched networks.
– See Kleinrock, L., Communication Nets: Stochastic Message Flow and Delay, McGraw-Hill, New York, 1964 for details
18
6
LM CCN Section 3.2: Queuing Theory
M/M/1/K Example
! Assume a M/M/1/K model ! Network gateway
– 4Mbps
– Packet size 1000 bytes
– Arrival rate of 250 packets/second
! What is the probability of overflow with 12 buffers?
19
M/M/1/K Example (Cont.)
! Arrival rate 𝜆 = 250pps ! Service rate:
– 4000000/8 = 500000bytes/sec
! Probability of n packets in gateway:
𝑝 = (1 − 𝜌)𝜌1 1 1 − 𝜌C 2 !
– 500000/1000 = 500 pps ! Probability of overflow:
– 𝜇 = 500pps !Load𝜌=” =AB3 =0.5
𝑃4566 = 𝑝C = (1 − 0.5)0.5!A 1−0.5!D
= 0.000122
* B33
! Mean packets in gateway: 𝜌 (𝐾 + 1)𝜌C2!
! Average delay: 𝐸[𝑁]
𝐸𝑁 =1−𝜌− 1−𝜌C2!
𝐸𝑇 =𝜆(1−𝑃4566)
0.5 13×0.5! D =1−0.5−1−0.5!D =0.9984
0.9984 =250(1−0.000122)=0.00399
20
M/M/c/c – The Telephone
Exchange Model
! M/M/c/c models can be used to model systems that handle trunk connections for many users
! If all trunks are busy, new calls are blocked
– No waiting is allowed (just like a telephone switchboard)
! Design involves selecting a number of trunks such that blocking probability is kept below a desired threshold
! The blocking probability 𝑃+ for a system with c trunks and offered load 𝜌 is given by the Erlang B formula:
𝑃 = 𝜌0 /𝑐! where k!=1×2×3×⋯×(k−1)×k
+ ∑0 (𝜌E/𝑘!) EF3
21
7
LM CCN Section 3.2: Queuing Theory
M/M/c/c – The Telephone Exchange Model (Cont.)
Figure from Garcia, A. L., & Widjaja, I. (2000). Communication networks. Ed. McGraw Hill.
22
M/M/c/c – The Telephone
Exchange Model (Cont.)
! Erlang B is valid for any service time distribution
– e.g.thesameformcanbeusedwithM/G/c/cmodels
! 𝑃+ as given by Erlang B is equivalent to 𝑃[𝑁 𝑡 = 𝑐]
! Analysis of the network in M/M/c/c is identical to M/M/1/K except
in the departure rate:
– In M/M/1/K departure rate when 𝑁 𝑡 = 𝑛 is 𝜇 – In M/M/c/c departure rate when 𝑁 𝑡 = 𝑛 is 𝑛𝜇
! This leads to a subtlety different state transition diagram
23
Summary
! Queuing theory
– Modelling queues
24
8