COMP9334
Capacity Planning for Computer Systems and Networks
Week 4B: Discrete event simulation (1)
COMP9334
1
Week 4A: Queues with general arrival & service time
• Queueswithgeneralinter-arrivalandservicetimedistributions
General Inter-arrivals time distribution Arrivals General service time distribution
• M/G/1 queue
• CancalculatedelaywiththeP-K
formula
• G/G/1 queue
• Noexplicitformula,getaboundor
approximation
Departures
T1,2021 COMP9334 2
Analytical methods for queues
• You had learnt how to solve a number of queues analytically (= mathematically) given their
• Inter-arrivaltimeprobabilitydistribution • Servicetimeprobabilitydistribution
• Queues that you can solve now include M/M/1, M/M/m, M/G/1, M/G/1 with priorities etc.
• Ifyouknowtheanalyticalsolution,thisisoftenthemost 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?
T1,2021 COMP9334 3
Lectures 4B, 5A, 5B: Discrete event simulation
• For a number of lectures, we look at the topic of using discrete event simulation for queueing problems
• Simulationisanimitationoftheoperationofreal-lifesystemover time.
• The topics to be covered are
• (4B)Whatarediscreteeventsimulation?
• (4B)Howtostructureadiscreteeventsimulation?
• For5Aand5B
• • • • •
How to choose simulation parameters?
How to analyse data?
What are the pitfalls that you need to avoid?
How to generate pseudo-random numbers for simulation? Reproducibility
T1,2021
COMP9334 4
Motivating example
Arrivals
Departures
Customer Arrival Service
time time
3
8
9
17
18
19
20
25
• Considerasingle-serverqueue with only one buffer space (= waiting room)
• Ifacustomerarriveswhenthe buffer is occupied, the customer is rejected.
• Giventhearrivaltimesandservice times in the table on the right, find
• The mean response time
• % of rejected customers Assuming an idle server at time = 0.
number 14 23 34 46 53 62 72 83 9 27 2
T1,2021 COMP9334
5
Let us try a graphical solution
• In the graphical solution, we will keep track of • Thestatusoftheserver:busyoridle
• Thestatusofthebuffer:occupiedorvacant
Arrival pattern
Server status busy
idle
3 89 17181920 2527
time
(1)
(2) (3)
(4)(5)(6)(7) (8) (9)
Customer # is enclosed within ( )
time
T1,2021
COMP9334
6
A graphical solution (To be completed)
Arrival pattern
Server status
busy idle
Buffer status occupied
vacant
Departure from Server /
Reject
(1)
(2) (3)
8 9
(4)(5)(6)(7)
17181920
(8) (9)
25 27
3
7
11 15
23
26
29
31
1,2021 COMP9334 (1) (2) (3) (6)(7) (8) (9) (5) (4) 7
T
A graphical solution
Arrival pattern
Server status
busy idle
Buffer status occupied
vacant
Departure from Server /
Reject
(2) (3)
8 9
(8) (9)
25 27
(1)
(4)(5)(6)(7)
17181920
3
(1)
(2)
(3)
(4)
(5)
(8)
(9)
(9)
(3)
(5)
(1)
7
(2)
11
(3)
15
(6)(7)
(8)
(4) (5) (8) (9)
23
26
29
31
T1,2021 COMP9334
8
Using the graphical solution (1)
Arrival pattern
(1)
(2) (3)
8 9
(4)(5)(6)(7)
17181920
(8) (9)
2527
3
We can find the response time of each customer & average response time
(1)
7
(2)
11
(3)
15
(6)(7)
(4) (5) (8) (9)
Departure from Server /
Reject
23
26
29
31
T1,2021 COMP9334
9
Using the graphical solution (2)
We can find the server utilisation
(1)
(2)
(3)
(4)
(5)
(8)
(9)
We can find % of rejected customers
Server status
busy idle
(1)
7
(2) (3)
11 15
(6)(7)
(4) (5) (8) (9)
Departure from Server /
Reject
23
26
29
31
T1,2021
COMP9334
10
From graphical solution to computer solution (1)
• How can we turn this graphical solution into a computer solution, i.e. a computer program that can solve the problem for us
• We need to keep track of the status of the server and the status of the buffer,
• Thisallowsustomakedecisions
• E.g.IfserverisBUSYandbufferisOCCUIPIED,anarriving
customer is rejected.
• E.g.IfserverisBUSYandbufferisVACANT,anarrivingcustomer goes to the buffer.
• E.g.IfserverisIDLE,anarrivingcustomergoestothesever
• What this means: We need to keep track of the status of
some variables in our computer solution.
T1,2021 COMP9334 11
From graphical solution to computer solution (2)
(2) (3)
89
(1)
occupied vacant
(1)
7
• Observation #1:
• Anarrivingordepartingcustomer causes the server or buffer status to change
(1)
3
• Examples:
• At time = 3, the arrival of customer #1 causes the server to switch from IDLE to BUSY
• At time = 7, the departure of customer #1 causes the server to switch from BUSY to IDLE
busy
idle
(2)
(3)
• At time = 9, the arrival of customer #3 causes the buffer to switch from VACANT to OCCUPIED
(2)
11
(3)
15
• Etc. T1,2021
COMP9334
12
(3)
From graphical solution to computer solution (3)
(2) (3)
89
(1)
occupied vacant
(1)
7
• Let us call the arrival of a customer or the departure of a customer an event
• Observation #2:
• Thestatusoftheserverandthe
status of the buffer remain the same between two consecutive events
• What this means:
• Weneedtokeeptrackofthe timing of the events
(1)
3
busy
idle
(2)
(3)
(3)
• •
Events can cause status transitions
In between events, status remain the same
(2)
11
(3)
15
T1,2021
COMP9334
13
From graphical solution to computer solution (4)
• In our computer solution, we will use a master clock to keep track of the current time
• We will advance the master clock from event to event
• In order to see how the computer solution works, let us try
it out on paper first
T1,2021 COMP9334 14
On paper simulation
• Inoursimulation,wekeeptrackofanumberofvariables
• MC = Master clock
• Status of
• Server: 1 = BUSY, 0 = IDLE
• Buffer: 1 = OCCUPIED, 0 = VACANT
• Event time:
• Next arrival event and service time of this arrival
• Next departure event and arrival time of this departure
• The (arrival time, service time) of the customer in buffer
• In order to compute the response time, we keep track of
• The cumulative response time (T)
• Cumulative number of customers rejected (R)
MC
Next arrival
Next departure
Server status
Buffer status
+ customer in buffer
TR
Arrival time
3
8
8
Service time
4
3
3
Departure time
–
7
–
Arrival time of this departure
00 30 70
–
3
–
0
1
0
0
0
0
0
0
4
T1,2021 COMP9334 15
On paper simulation (To be completed)
MC Next arrival Next departure Server status
00 30 70
Buffer status +
Customer in buffer
TR
Arrival time
3
8
8
Service time
4
3
3
Departure time
–
7
–
Arrival time of this departure
–
3
–
0
1
0
0
0
0
0
0
4
Can you continue?
(Arrival time, service time) of the customer in the buffer.
T1,2021 COMP9334
16
On paper simulation
MC Next arrival Next departure Server status
00 30 70 80 90
11 0 15176- -00130
Buffer status +
Customer in buffer
TR
Arrival time
17
17
3
8
8
9
Service time
4
3
3
4
6
6
Departure time
11
11
15
–
7
–
Arrival time of this departure
–
3
–
8
8
9
0
1
0
1
1
1
0
0
0
0
1 (9,4)
0
0
0
4
4
4
7
Can you continue?
(Arrival time, service time) of the customer in the buffer.
T1,2021 COMP9334
17
Logic of the program (1)
• At each step, we advance to the next event that will take place
Find next event
Advance master clock to the next event
Take appropriate action depending on type of event
T1,2021 COMP9334 18
Three cases according to the server and/or buffer status
Arrival event
• Changebufferstatus to OCCUPIED
• Storethearrivaltime and service time of this arrival with buffer information
• Addadepartureevent with departure time = current time + service time of the arrival
• Changeserverstatusto BUSY
• Rejectthis customer
• Incrementthe cumulative number
of rejected customers by one
• Lookupthelistofarrivaltofillintheinformationforthenextarrival event
Handling an arrival event
Server IDLE (Buffer VACANT)
Server BUSY Buffer VACANT
Server BUSY Buffer OCCUPIED
T1,2021
COMP9334
19
Two cases according to the buffer status
Departure event
• Updatethecumulativeresponsetime
• T!T + current time – arrival time of the departing customer
• Changeserverstatusto IDLE
• Nextdepartureevent becomes empty
• Updatethedepartureeventwith information of the customer in the buffer
• Nextdeparturetime=
current time + service time of the
customer in the buffer
• ChangebufferstatustoVACANT
Handling an departure event
Buffer VACANT
Buffer OCCUPIED
T1,2021 COMP9334 20
Discrete event simulation
• The above computer program is an example of a discrete event simulation
• It allows you to solve a queueing problem with one server and one buffer space
• You can generalise the above procedure to • Multi-server
• Finiteorinfinitebufferspace • Differentqueueingdisciplines
• Let us generalise it to the case of single-server with infinite buffer
T1,2021 COMP9334 21
Single server with infinite buffer simulation
• In this case, we will use buffer status to denote the number of customers in buffer
• Bufferstatus=0,1,2,3,…
• We also need to store all the (arrival time, service time) of
all the customers in the buffer
• Compare with the single-server single-buffer case, we only need to change the handling of
• Anarrivalevent
• Adepartingevent
T1,2021 COMP9334 22
Two cases according to the server status
Arrival event
• Incrementnumberofcustomers in the buffer by 1
• Storethearrivaltimeand service time of this arrival with buffer information
• Addadepartureeventwith departure time = current time + service time of the arrival
• ChangeserverstatustoBUSY
• Lookupthelistofarrivaltofillintheinformationforthenextarrival
Handling an arrival event
Server IDLE
Server BUSY
T1,2021 COMP9334 23
Two cases according to the buffer status
Departure event
• Updatethecumulativeresponsetime
• T!T + current time – arrival time of the departing customer
• Updatethedepartureeventwithfirst customer in the buffer
• Nextdeparturetime=
current time + service time of the first
customer in the buffer
• Deletefirstcustomerfrombuffer
• Decrementnumberofcustomersinthe buffer by 1
• Changeserverstatusto IDLE
• Departureevent becomes empty
Handling an departure event
Buffer = 0 Buffer 1 0
T1,2021 COMP9334
24
One missing piece
• We know how to write a discrete event simulation program to simulate a single-server queue with infinite buffer assuming that we have the arrival times and service times
• Where do arrival times and service times come from?
• If we want to simulate an M/M/1 queue
• Theinter-arrivaltimeisexponentiallydistributed • Theservicetimeisexponentiallydistributed
• We can get the arrival times and service times if we can generate exponentially distributed random numbers
T1,2021 COMP9334 25
The Python random library
• The library can be used to generate random numbers from many probability distributions
• random.expovariate() can be used to generate exponentially distributed random numbers
T1,2021 COMP9334 26
Exponential distributed random numbers
• Generate10,000 exponentially distributed number and plot the histogram
• File: hist_random_expo.py
• Note:lambdaisa Python keyword. Cannot use lambda as a variable name
T1,2021 COMP9334 27
Arrival and service times
Service time s1
i1 (0.886)
Service time s2
i1+i2
Service time s3
i1+ i2 +i3
time
0
i1 i2i3
T1,2021
COMP9334
28
Simulating M/M/1 queue
• In order to test how well our discrete event simulation program works, we will use it to simulate an M/M/1 queue and compare it with the expected result
• An M/M/1 simulation program is given in sim_mm1.py (available on the course web site)
• We will:
• Take a look at the program
• Runitandmakesomeobservations
T1,2021 COMP9334 29
Observations from running the simulation
• The mean response time from simulation can be close to (but not equal to) the theoretical mean simulation time
• Each simulation run gives a different mean response time
T1,2021 COMP9334 30
Trace driven simulation
Arrivals
Departures
• •
• •
We considered this example in the beginning of this lecture
We simulated using
• A sequence (or trace) of arrival times
• A sequence of service times
We call this trace driven simulation Trace driven simulation is useful
• You have a server and you have a log of the arrival time and service time of the job
• You are considering changing to a new server
• You can use the traces that you have and simulation to calculate the response time of the new server
4
5
6
7
8
9 27 2
Customer Arrival Service
number 1
2
3
time time
3
4
8
3
9
4
17
6
18
3
19
2
20
2
25
3
T1,2021 COMP9334
31
Trace driven simulation
• An example of trace driven simulation is in the file sim_1server_trace.py
• Notethatsim_1server_trace.pyassumesinfinitebufferratherthan finite buffer
• Earlier we used random number generators to produce inter-arrival and service time
• Fortracedrivensimulation,thearrivaltimeandservicetimeare read from the supplied trace
T1,2021 COMP9334 32
References
• Discrete event simulation of single-server queue
• Winston,“OperationsResearch”,Sections23.1-23.2
• LawandKelton,“Simulationmodellingandanalysis”,Section1.4
• Generation of random numbers
• RajJain,“TheArtofComputerSystemsPerformanceAnalysis”
• Sections 26.1 and 26.2 on LCG
• Section 28.1 on the inverse transform methods
• Note: We have only touched on the basic of discrete event simulations. For a more complete treatment, see
• LawandKelton,“Simulationmodellingandanalysis”
• HarryPerros,“ComputerSimulationTechniques:Thedefinitive
introduction”, an e-book that can be downloaded from
• http://www4.ncsu.edu/~hp/files/simulation.pdf
T1,2021 COMP9334 33