CS计算机代考程序代写 chain capacity planning Erlang COMP9334

COMP9334
Capacity Planning for Computer Systems and Networks
Week 3A: Queues with Poisson arrivals (2)
COMP9334
1

Pre-lecture exercise
• You have a loaded die with 6 faces with values 1, 2, 3, 4, 5 and 6
• The probability that you can get each face is given in the table below
• What is the mean value that you can get?
Value
Probability
1
0.1
2
0.1
3
0.2
4
0.1
5
0.3
6
0.2
T1, 2021 COMP9334 2

Single-server queue
Arrivals
• Open,singleserverqueues
• Howtofind: • Waitingtime
• Responsetime
• Meanqueuelengthetc.
Departures
• Thetechniquetofindwaitingtimeetc.iscalledQueueing Theory
T1, 2021 COMP9334 3

Multiple server queue
Arrivals
Departures
1
2 3
• Open,multi-serverqueue
• Howtofind: • Waitingtime
• Responsetime
• Meanqueuelengthetc.
m
m servers
T1, 2021
COMP9334
4

What will you be able to do with the results?
Configuration 1:
processing speed = m p
Configuration 3:
Arrivals
Randomly
assign the arrivals into m queues
1
m
Configuration 2: Arrivals
1
m servers of speed p
m
T1, 2021 COMP9334
5
m servers of
Which configuration has the best response time?
speed p

Single Server Queue: Terminology
l
WS
Time spent waiting
T=W+S
Response Time T
= Waiting time W + Service time S
Note: We use T for response time because this is the notation in many queueing theory books. For a similar reason, we will use r for utilisation rather than U.
T1, 2021 COMP9334 6

Call centre analogy from Week 2B
• Consider a call centre
• CallsarearrivingaccordingtoPoissondistributionwithratel
• Thelengthofeachcallisexponentiallydistributedwithparameterμ • Meanlengthofacallis1/μ
Arrivals
Call centre:
m operators
If all operators are busy, the centre can put
at most n additional calls on hold.
If a call arrives when all operators and holding slots are used, the call is rejected.
• We solved the problems for
• (m=1andn=0),and(m=1andn=1)
• How about other values of m and n? What about response time?
T1, 2021 COMP9334 7

Kendall’s notation
• To represent different types of queues, queueing theorists use the Kendall’s notation
• The call centre example on the previous page can be represented as:
Inter-arrival distribution
is Markovian i.e. Exponential
M / M / s (/ B)
Service time distribution
is Markovian i.e. Exponential
Buffer Positions (wait room)
Number of servers
The call centre example on the last page is a M/M/m/(m+n) queue If n = ∞, we simply write M/M/m
T1, 2021 COMP9334 8

M/M/1 queue
Exponential Inter-arrivals (l)
Exponential Service time (μ)
Infinite buffer
One server
• Consider a call centre analogy
• CallsarearrivingaccordingtoPoissondistributionwithratel
• Thelengthofeachcallisexponentiallydistributedwithparameterμ • Meanlengthofacallis1/μ
Arrivals
• Queueing theory will be able to answer these questions: • Whatarethemeanwaitingtime,meanresponsetimeforacall?
Call centre with 1 operator
If the operator is busy, the centre will put
the call on hold.
A customer will wait until his call is answered.
T1, 2021 COMP9334 9

Little’s Law
• Applicabletoany“box”thatcontainssomequeuesorservers • Meannumberofjobsinthe“box”=
Mean response time x Throughput
• WewilluseLittle’sLawinthislecturetoderivethemeanresponsetime
• We first compute the mean number of jobs in the “box” and throughput
T1, 2021 COMP9334 10

M/M/1: State and transition diagram
• Wewillsolveforthesteadystateresponse
• Definethestatesofthequeue
• State 0 = There is zero job in the system (= The server is idle)
• State1=Thereis1jobinthesystem(=1jobattheserver,nojob queueing)
• State2=Thereare2jobsinthesystem(=1jobattheserver,1job queueing)
• State k = There are k jobs in the system (= 1 job at the server, k-1 job queueing)
• Thestatetransitiondiagram lll
l
..
μμ
0123…
μ
K-1
l
k
μ
μ
T1, 2021 COMP9334
11

l
0
μ
M/M/1 state balance:
ll
l
k
l
..
μμ
123…
μ
K-1
μ
T1, 2021
COMP9334
12

M/M/1 state balance: Exercise 1
l
1
μ
ll
l
..
μμ
l

μ
• Exercise:WritethestatebalanceequationforState1
k
023
μ
K-1
T1, 2021 COMP9334
13

M/M/1 state balance: Exercise 2
lll
l
..
μμ
0123…
μ
K-1
l
k
μ
μ
• Exercise: Write the state balance equation for magenta box, i.e. Rate of transiting out of the magenta box
= Rate of transiting into the magenta box
T1, 2021 COMP9334 14

l
0
l
1
μ
μ
State balance for State 1
State balance for State 1 and State 2 combined
Which state balance is easier to work with?
l
2
l

μ
l
..
μμ
3
K-1
k
T1, 2021
COMP9334
15

M/M/1 state balance: Relating P2 and P0
l
0
μ
l
1
μ
l
2
l

μ
l
..
μμ
3
K-1
k
T1, 2021
COMP9334
16

M/M/1 state balance: Relating P3 and P0
lll
l
..
μμ
0123…
μ
K-1
l
k
μ
μ
T1, 2021 COMP9334
17

M/M/1 state balance: Relating Pk and P0
In general
We have
T1, 2021 COMP9334 18

Solving for Pk
With and
Since
Arrival rate < service rate T1, 2021 COMP9334 19 r = utilisation = Prob server is busy = 1 - P0 = 1- Prob server is idle Exercise: Mean number of jobs Recall that and we have calculated that Determine the mean number of jobs in the system. Hint 1: Look at pre-lecture exercise 1. You can use the following formula to help you. T1, 2021 COMP9334 20 Mean number of jobs The mean number of jobs in the system = T1, 2021 COMP9334 21 M/M/1: mean response time l Little’s law: mean number of customers = throughput x response time Throughput is l (why?) T1, 2021 COMP9334 22 Mean waiting time = mean response time - mean service time We know mean response time (from last slide) Mean service time is = 1 / μ Exercise: M/M/1 mean waiting time l What is the mean waiting time at the queue? T1, 2021 COMP9334 23 Using the service time parameter (1/μ = 15ms) in the example, let us see how response time T varies with l Observation: Response time increases sharply when r gets close to 1 Infinite queue assumption means r ® 1, T®¥ T1, 2021 COMP9334 24 Non-linear effect on response time • The response time of an M/M/1 queue • Assuming the mean arrival rate is 10 requests/s • We will calculate the effect of service rate on response time • Complete the following table and see what you can conclude Service rate 11 22 Utilisation 𝛌/𝝁 10/11 = 0.909 10/22 = 0.454 Response time 1 0.08 • Doubling the service rate can sometimes reduce by response time by a factor more than 2. T1, 2021 COMP9334 25 Multi-server queues M/M/m Exponential 1 Inter-arrivals (l) Exponential Service time (μ) 2 All arrivals go into one queue. Customers can be served by any one of the m servers. When a customer arrives • If all servers are busy, it will join the queue • Otherwise, it will be served by one of the available servers Infinite buffer m servers T1, 2021 COMP9334 26 3 m A call centre analogy of M/M/m queue • Consider a call centre analogy • CallsarearrivingaccordingtoPoissondistributionwithratel • Thelengthofeachcallisexponentiallydistributedwithparameterμ • Meanlengthofacallis1/μ Arrivals Call centre with m operators If all m operators are busy, the centre will put the call on hold. A customer will wait until his call is answered. T1, 2021 COMP9334 27 State transition for M/M/m llll 0123.. μ 2μ 3μ mμ mμ mμ l l .. m m+1 T1, 2021 COMP9334 28 M/M/m • Followingthesamemethod,wehavemeanresponsetimeTis where T1, 2021 COMP9334 29 Multi-server queues M/M/m/m with no waiting room Exponential 1 Inter-arrivals (l) Exponential Service time (μ) 2 An arrival can be served by any one of the m servers. When a customer arrives • If all servers are busy, it will depart from the system No waiting Room or No buffer • Otherwise, it will be served by one of the available servers 3 m servers T1, 2021 COMP9334 30 m A call centre analogy of M/M/m/m queue • Consider a call centre analogy • CallsarearrivingaccordingtoPoissondistributionwithratel • Thelengthofeachcallisexponentiallydistributedwithparameterμ • Meanlengthofacallis1/μ Arrivals Call centre with m operators If all m operators are busy, the call is dropped. T1, 2021 COMP9334 31 State transition for M/M/m/m lll l l 0123.. μ 2μ 3μ (m-1)μ mμ Probability that an arrival is blocked = Probability that there are m customers in the system where “Erlang B formula” m-2 m-1 m T1, 2021 COMP9334 32 What configuration has the best response time? Configuration 1: processing speed = m p Configuration 3: Arrivals Randomly assign the arrivals into m queues 1 m Configuration 2: Arrivals 1 m servers of speed p m Try out the tutorial question! m servers of T1, 2021 COMP9334 speed p 33 References • Recommended reading • QueueswithPoissonarrivalarediscussedin • BertsekasandGallager,DataNetworks,Sections3.3to3.4.3 • Note:IderivedtheformulashereusingcontinuousMarkovchain but Bertsekas and Gallager used discrete Markov chain • MorHarchal-Balter.Chapters13and14 T1, 2021 COMP9334 34