AN
SW
ER
S
ECMM424
(with Answers)
UNIVERSITY OF EXETER
COLLEGE OF ENGINEERING, MATHEMATICS
AND PHYSICAL SCIENCES
COMPUTER SCIENCE
Examination, May 2019
Computer Modelling and Simulation
Module Leader: Dr. Jia Hu
Duration: TWO HOURS
Answer Question 1 (40%) and any TWO of the other three questions (30%
for each).
Candidates may use calculators provided they are non-programmable.
This is a CLOSED BOOK examination.
AN
SW
ER
S
ECMM424 – 01/Mar/2019 – with answers Page 1
Question 1
(a) Both computer simulation and analytical modelling can be used to evaluate
the performance of systems.
(i) Describe the methods of computer simulation and analytical modelling,
respectively.
(4 marks)
(ii) Explain the situations where it is better to use analytical modelling for
performance evaluation than computer simulation.
(3 marks)
(iii) Explain the situations where computer simulation is more suitable than
analytical modelling for performance evaluation.
(3 marks)
Solutions:
Computer simulation is a computer program that mimics the behaviour
or operations of a real-world system or process over time, including its
inputs and outputs. Simulation experiments imitate the operations of a
real-world process or system over time using a computer program.
(2 marks)
Analytical modelling uses mathematical concepts, tools, and equations
to describe the behaviour or operations of a system and generates closed-
form solutions to the equations.
(2 marks)
Analytical modelling is used if the model is simple enough and
mathematical approach is feasible.
If the model structure is simple, then we could use mathematical
methods to implement the model and get the exact information for
questions of interest, this is called analytical modelling. Different
mathematical techniques (e.g., calculus, algebra, probability theory) can
be applied in this method to implement the model.
(3 marks)
ECMM424 (2019) 1
AN
SW
ER
S
ECMM424 – 01/Mar/2019 – with answers Page 2
However, many real world systems are so complex that models of these
systems are virtually impossible to solve mathematically. In these cases
computer simulation can be used to imitate the behavior of the system
over time for performance evaluation.
(3 marks)
(b) The figure below shows the logical relationship of components in discrete-
event simulation. Describe the flow control of discrete-event simulation
and the functions of the Main program, Initialization routine, Time routine,
Event routine, and Report generator, respectively.
(10 marks)
Solutions:
The simulation begins at time zero with the main program invoking the
initialization routine, where the simulation clock is set to zero. Also in
the initialization routine the systems state and statistical counters and the
event list are initialized.
(2 marks)
After these settings the control goes back to the main program. In the
ECMM424 (2019) 2 Please Turn Over
AN
SW
ER
S
ECMM424 – 01/Mar/2019 – with answers Page 3
next step the main program invokes the timing routine to determine
which type of event is the most imminent.
Based on the type of the next occurring event the simulation clock is
advanced to the time that event type will occur. The time of occurrence
of events is dependent on their type and their distribution in time.
(2 marks)
Then the control goes back to the main program again.
Based on the type of event, the main program invokes the appropriate
routine. If the next event is arrival then the arrival routine is invoked else
the departure routine is invoked.
(2 marks)
In general inside the event routines three main activities occur:
The system state is updated to account for the fact that an event of a
specific type has occurred.
Information about the system performance is gathered by updating
the statistical counters. The times of occurrence of future events are
generated, and this information is added to the event list.
In order to generate future events some random variates are used which
we will talk about more in detail in future sessions.
(2 marks)
After all processing has occurred in the event routine and the main
program, a check is typically made to determine (relative to some
stopping condition) if the simulation should now be terminated.
If it is time to terminated the simulation, the report generator will be
invoked from the main program to compute estimates of the desired
performance measures using the statistical counters.
If it is not to terminate the simulation then the control is passed back
to the main program. Then the main program routine invokes the
timing routine, then again the control of the program goes back to
the main program routine, then to the event routine, and so on. . . .
The termination check cycle is repeated until the stopping condition is
eventually satisfied. Time can be compressed or expanded allowing for
speedup or slowdown of the phenomena under consideration.
(2 marks)
ECMM424 (2019) 3
AN
SW
ER
S
ECMM424 – 01/Mar/2019 – with answers Page 4
(c) Consider 3 boxes. Box A contains 2 white and 4 red balls; Box B contains 3
white and 6 red balls; and Box C contains 1 white and 2 red balls. If 1 ball
is selected from each box, what is the probability that the ball chosen from
box A was white, given that exactly 2 white balls were selected?
(10 marks)
Solutions:
By Bayes’s formula,
Pr(ball from A was white | 2 white balls selected)
=
Pr(ball from A was white ∩ 2 white balls selected)
Pr(2 white balls selected)
(3 marks)
Pr(ball from A was white ∩ 2 white balls selected)
=
2
6
∗ (3
9
∗ 2
3
+
6
9
∗ 1
3
) =
4
27
(3 marks)
Pr(2 white balls selected)
=
2
6
∗ 3
9
∗ 2
3
+
2
6
∗ 6
9
∗ 1
3
+
4
6
∗ 3
9
∗ 1
3
=
6
27
(3 marks)
So, the result is 2/3.
(1 mark)
(d) Buses arrive at a certain stop according to a renewal process, with interarrival
intervals taking three possible values: 80% of them are equal to 5 minutes,
15% are equal to 10 minutes, and 5% are equal to 20 minutes. How long, on
average, would a passenger coming at random to that stop have to wait for
the next bus?
(10 marks)
ECMM424 (2019) 4 Please Turn Over
AN
SW
ER
S
ECMM424 – 01/Mar/2019 – with answers Page 5
Solutions:
The average interval between consecutive bus arrivals is given by
m = 0.8 ∗ 5 + 0.15 ∗ 10 + 0.05 ∗ 20 = 6.5
(3 marks)
The second moment of the interval is given by
M2 = 0.8 ∗ 25 + 0.15 ∗ 100 + 0.05 ∗ 400 = 45
(3 marks)
The waiting time would be
E(R) =
45
2 ∗ 6.5 =
45
13
≈ 3.46minute
(4 marks)
(Total 40 marks)
ECMM424 (2019) 5
AN
SW
ER
S
ECMM424 – 01/Mar/2019 – with answers Page 6
Question 2
(a) Queueing networks are widely applied to model and analyse the performance
of computing and communication systems. Queueing networks can be clas-
sified into two categories: Open Queueing Networks and Closed Queueing
Networks.
(i) Describe what a queueing network is.
(2 marks)
(ii) Explain the differences between Open Queueing Networks and Closed
Queueing Networks.
(3 marks)
Solutions:
(i) Queueing Networks:
A queueing network is a collection of inter-connected nodes that
consist of queues and servers and are all connected to each other.
A queueing network is a model in which jobs departing from one
queue arrive at another queue.
(2 marks)
(ii) Open Queueing Networks:
Open Queueing Networks have external arrivals and departures and
thus the number of jobs in the system varies with time.
Closed Queueing Networks:
A closed network is just a special case of an open network where
there is no exterior, arrival or departure to or from the network.
In Open Queuing Networks, jobs may enter and leave the system.
But in Closed Queueing Networks, a fixed set of jobs circulate
between servers.
(3 marks)
(b) The following figure illustrates an open queueing network with multiple (say
N ) single-server queues in tandem.
(i) Draw the flowchart for the DEPARTURE routine of the n-th queuing
system, where 1 ≤ n ≤ N .
ECMM424 (2019) 6 Please Turn Over
AN
SW
ER
S
ECMM424 – 01/Mar/2019 – with answers Page 7
(10 marks)
(ii) Describe how the routine works.
(5 marks)
Solutions:
(i) The flowchart for the DEPARTURE routine of the n-th queuing
system, where 1 ≤ n ≤ N :
(5 marks for Arrival, 5 marks for Departure)
(ii) Describe how the routine works:
For the departure, as you can see on this flowchart, the first thing
to do is to check if we have reached the server of the final node
or not. The reason for doing this is that all the first (N-1) nodes
ECMM424 (2019) 7
AN
SW
ER
S
ECMM424 – 01/Mar/2019 – with answers Page 8
have a different departure to the last node. At the time of departure,
the first (N-1) nodes first schedule the arrival to the next connecting
node. The first thing they do is that they check to see if the server of
the next node is busy or not:
1- if the server is busy, the queue of the node is checked. If the
queue is not full the customer is sent into the queue otherwise it is
dropped.
2- if the server is idle then the customer goes directly into the server
for service. After dealing with the next neighboring node, the (N-
1) nodes then start to deal with their own queue. If their queue is
empty and no other customer is waiting then the server goes into an
idle state, otherwise another customer is removed from the queue
and all the relevant statistics are updated.
For the node at the end of the chain, node N, the only part of the
algorithm that is executed is the part where it has to check its own
queue status. So only the second half of the flowchart/ algorithm is
executed.
(5 marks)
(c) Confidence intervals are central to making meaningful inferences from the
results of stochastic simulation experiments.
(i) Explain what is meant by the confidence interval in simulation results.
(2 marks)
(ii) Compute the 95% confidence interval of a network where the 800
packets sent to destinations have the mean packet delay of 15 msec,
while the standard error is 2 msec. (The t distribution value for (30-1)
degrees of freedom and 95% confidence level is 2.0452).
(8 marks)
Solutions:
(i) Explain what is mean by confidence interval
During a simulation experiment, we attempt to generate only limited
ECMM424 (2019) 8 Please Turn Over
AN
SW
ER
S
ECMM424 – 01/Mar/2019 – with answers Page 9
samples of a large number of representative scenarios for a system.
Therefore a Confidence Interval is a region that contains the "true"
value (the parameter of interest) with a specified probability.
(2 marks)
(ii) Calculate the 95% confidence interval
X(n)± tn−1,1−α2
√
S2(n)
n
= 15± 2.0452
√
22
30
= 15± 0.75
⇒ confidence interval = [15.75, 14.25]
(8 marks, 2 marks for each correct step)
(Total 30 marks)
ECMM424 (2019) 9
AN
SW
ER
S
ECMM424 – 01/Mar/2019 – with answers Page 10
Question 3
(a) Random numbers are necessary ingredients in the simulation of almost all
discrete systems. Explain what are random numbers used in discrete-event
simulation. Describe two important statistical properties (i.e., uniformity
and independence) of random numbers.
(5 marks)
Solutions:
Random numbers in discrete-event simulation is a series of independent
and identically distributed numbers in the range from 0 to 1.
Uniformity: If the interval [0,1] is divided in to n subintervals of equal
length, the expected number of observations in each interval is N/n. The
values are uniformly distributed over a defined interval or set;
Independence: The probability of observing a value in a particular
interval is independent of the previous values drawn. It is impossible
to predict future values based on past or present ones.
(5 marks)
(b) The Linear Congruential Generator (LCG) is a widely applied random
number generator following the equation:
Xi = (aXi−1 + b)mod(m), i = 1, 2, ...
where a, b, and m are appropriate constants. Explain why LCG often has a
looping behaviour.
(5 marks)
Solutions:
When Xi takes on the values that it has had previously, exactly the same
sequence of values is regenerated, and this cycle repeats itself endlessly.
The length of the cycle is called the period of a generator.
(5 marks)
(c) Suppose X is a continuous random variable with a cumulative distribution
function (CDF), F (x) = P (X ≤ x). Describe how to generate random
variates (i.e., samples from statistical distributions) of X by using Inverse
ECMM424 (2019) 10 Please Turn Over
AN
SW
ER
S
ECMM424 – 01/Mar/2019 – with answers Page 11
Transform Technique.
(5 marks)
Solutions:
Step 1: Calculate F−1 that denotes the inverse of the function F
Step 2: Generate U (0, 1) (random-number generator)
Step 3: Find X such that (X) = F−1(U), and return this value X
(5 marks)
(d) What are the union, superposition, decomposition, and PASTA properties of
Poisson processes?
(15 marks)
Solutions:
Union: If I1 and I2 are two disjoint intervals of lengths x1 and x2
respectively, and I is their union, then the number of arrivals in I from a
Poisson process with rate λ has the Poisson distribution with parameter
λ(x1 + x2).
(3 marks)
Superposition: The superposition property. If B1 and B2 are two
independent Poisson processes with rates λ1 and λ2 respectively, then
the total number of arrivals from B1 and B2 during an interval of length
x has the Poisson distribution with parameter (λ1 + λ2)x.
(3 marks)
Decomposition: If a Poisson process, A, with rate λ, is decomposed
into processes B1, B2, ..., Bn, by assigning each arrival in A to Bi with
probability qi(q1 + q2 + ... + qn = 1), then B1, B2, ..., Bn are Poisson
processes with rates q1λ, q2λ, ..., qnλ respectively, and are independent
of each other.
(4 marks)
PASTA: In the long-term, the system state seen by an arrival from a
Poisson process has the same distribution as the state seen by a ‘random
observer’, i.e. at a point in time chosen at random.
ECMM424 (2019) 11
AN
SW
ER
S
ECMM424 – 01/Mar/2019 – with answers Page 12
(5 marks)
(Total 30 marks)
ECMM424 (2019) 12 Please Turn Over
AN
SW
ER
S
ECMM424 – 01/Mar/2019 – with answers Page 13
Question 4
Consider the Markovian queueing system shown below. Branch labels are arrival
and service rates. Node labels give the number of customers in the system.
(a) Solve for steady state probabilities pk(k = 0, 1, 2, 3).
(10 marks)
(b) Find the average number of customers in the system and the average
response time of a customer.
(6 marks)
(c) Write down the transition rate matrix (i.e., generator) Q for this problem and
give the matrix equation relating Q to the steady state probabilities.
(4 marks)
(d) Work out the average first passage times from the state 1 to the set of states
{2, 3}.
(10 marks)
Solutions:
(a) Balance equations:
λp0 = µp1
(λ+ µ)p1 = λp0 + µp2
λp2 = µp3
(6 marks)
Normalization equation:
p0 + p1 + p2 + p3 = 1
ECMM424 (2019) 13
AN
SW
ER
S
ECMM424 – 01/Mar/2019 – with answers Page 14
(1 mark)
Solving the above questions, we have
p0 =
1
1 + ρ+ ρ2 + ρ3
pi = ρ
ip0, i = 1, 2, 3
where ρ = λ
µ
.
(3 marks)
(b) The average number of customers in the system, L, is given by
1 ∗ p1 + 2 ∗ p2 + 3 ∗ p3 = ρ+ 2ρ
2 + 3ρ3
1 + ρ+ ρ2 + ρ3
(3 marks)
Using Little’s Law, the average response time, W , is given by
W =
L
λ
=
ρ+ 2ρ2 + 3ρ3
λ(1 + ρ+ ρ2 + ρ3)
(3 marks)
(c)
Q =

−λ λ
µ −λ− µ λ
µ −λ− µ λ
µ −µ

(2 marks)
pQ = 0, where p = (p0, p1, p2, p3).
(2 marks)
(d) Let the set of state S = {2, 3}
The average first passage time from 1 to S, m1,S , is given by
m1,S =
1
λ+ µ
+m0,S
µ
λ+ µ
(4 marks)
And the average first passage time from 0 to S, m0,S , is given by
m0,S =
1
λ
+m1,S
ECMM424 (2019) 14 Please Turn Over
AN
SW
ER
S
ECMM424 – 01/Mar/2019 – with answers Page 15
(4 marks)
Solving the above equation, we have
m1,S =
1
λ
+
µ
λ2
(2 marks)
(Total 30 marks)
ECMM424 (2019) 15 End of Paper





















































































































































































































































































































































































































































































































学霸联盟