COMP5416 Week 6. Simulation of M/M/1 Queue.
In this lab, you need to implement a simulator of M/M/1 queue to verify its properties. The skeleton code of the M/M/1 simulation is provided. To design the simulator, the core is to characterize:
(A) Whenever a unit arrives/leaves the queue, how does the system change? (B) At what time instant, a unit arrives at the queue?
(C) At what time instant, a unit leaves the queue?
(D) How do you find the average number of users in the system?
A. System Evolution by FSM
The system can be characterized as an FSM as follow, where N is the number of units in the system. The four ¡°arrows¡± showing four ¡°state transitions¡± are in ¡°four blocks¡± in the skeleton code.
B. Unit arrival
The arrival times can be generated as a priori, as it is NOT relevant to how the system evolves. In the code, it is generated as
C. Unit departure
The departure time depends on the system state. A departure time of a unit can only be known when the system starts to serve this unit. There are two possibilities, if the system is empty, the departure time is known when a unit arrives; if the system is not empty, the next departure time is known when the previous unit leaves the system.
Next, how do you know whether the next event is an arrival or departure event? You need to record the departure times in departure and arrival times in arrival. In this skeleton code, there is
at most one entry in departure, but we still use a list in order to facilitate a later extension to an M/M/n queue.
Experiments and Questions
1. Work on the skeleton code and find out the mean and stationary distribution of the number of units in the system.
In the simulation, if the system lasts 10 s, and there is 0 unit in the system for 4.7 s, 1 unit in the system for 4.2 second, and 2 units in the system for 1.1 s, then, the simulated stationary distribution will be ¦Ð(0)=0.47, ¦Ð(1)=0.42, ¦Ð(2)=0.11. The mean number is 0.47*0+0.42*1+0.11*2=0.64. Verify the distribution/mean of M/M/1 queue by simulation and theoretical analysis.
2. Poisson Arrivals See Time Average (PASTA). The above stationary distribution is a non- conditional distribution. That means, given an external observer of the queue, the observer will think that the probability of ith state is ¦Ð(i). However, we are also interested in considering the conditional distribution of the queue observed by arriving units. That is, what is the conditional distribution of the queue when a unit arrives?
In most situations, the two distributions are different. Given an example as follows: A unit arrives every 10 seconds, and each unit is served by the system for exactly 5 seconds. As an external observer, we see that the system is busy with a probability of 0.5 and idle with 0.5. However, when a unit arrives, it will always see that the system is idle, so that the system idle probability is 1 seen by arrivals (it can always be served immediately)!
Fortunately, if the arrival follows Poisson Process, the two distributions are the same. Work on the skeleton code again to verify this PASTA property! (You need to find the distribution of the system state when a unit arrives!)