Capacity Planning for Computer Systems
and Networks
Week 6: Discrete event simulation (1)
S1,2018
COMP9334
2
Week 3: Queues with Poisson arrivals
• Multi-server M/M/m
1
2
m
mservers
Arrivals
Departures
Exponential inter-arrivals (l)
Exponential service time (µ)
• Single-server M/M/1
Arrivals
Departures
Exponential inter-arrivals (l)
Exponential service time (µ)
S1,2018
COMP9334
3
Week 4: Closed-queueing networks
• Analyse closed-queueing network with Markov chain
• The transition between states is caused by an arrival or a
departure according to exponential distribution
CPU
Disk
• General procedure
• Identify the states
• Find the state transition rates
• Set up the balance equations
• Solve for the steady state
probabilities
• Find the response time etc.
S1,2018
COMP9334
4
Week 5: Queues with general arrival service time
• Queues with general inter-arrival and service time distributions
Arrivals
Departures
General Inter-arrivals time distribution
General service time distribution
• M/G/1 queue
• Can calculate delay with the P-K
formula
• G/G/1 queue
• No explicit formula, get a bound or
approximation
S1,2018
COMP9334
5
Analytical methods for queues
• You had learnt how to solve a number of queues
analytically (= mathematically) given their
• Inter-arrival time probability distribution
• Service time probability distribution
• Queues that you can solve now include M/M/1, M/M/m,
M/G/1, M/G/1 with priorities etc.
• If you know the analytical solution, this is often the most
straightforwad way to solve a queueing problem
• Unfortunately, many queueing problems are still
analytically intractable!
• What can you do if we have an analytically intractable
queueing problem?
S1,2018
COMP9334
6
This lecture and next lecture
• The lectures for these two weeks will focus on using
discrete event simulation for queueing problems
• Simulation is an imitation of the operation of real-life system over
time.
• The topics for this week are
• What are discrete event simulation?
• How to structure a discrete event simulation?
• How to generate pseudo-random numbers for simulation?
• Next week
• How to choose simulation parameters?
• How to analyse data?
• What are the pitfalls that you need to avoid?
S1,2018
COMP9334
7
Motivating example
• Consider a single-server queue
with only one buffer space (=
waiting room)
• If a customer arrives when the
buffer is occupied, the customer is
rejected.
• Given the arrival times and service
times in the table on the right, find
• The mean response time
• % of rejected customers
Assuming an idle server at time = 0.
Arrivals Departures
Customer
number
Arrival
time
Service
time
1 3 4
2 8 3
3 9 4
4 17 6
5 18 3
6 19 2
7 20 2
8 25 3
9 27 2
S1,2018
COMP9334