ECE358- Project 1: M/M/1 and M/M/1/K Queue Simulation Solved

1         OBJECTIVE
On the Internet, messages are queued up in routers and host computers, and queues impact the end-to-end delay of the messages. Therefore, it is important to understand the impact of various network parameters on network delay. The objective of this lab work is to design a simulator to study the behaviour of two basic types of queues (M/M/1 and M/M/1/K). After this experiment, students are expected to learn:

the basic elements of a network simulator; and
the behaviour of a single buffer queue with different parameters.
 

2         EQUIPMENT
A computer/ laptop with a C compiler. (You may choose Python, Java or any other language.)

 

3         OVERVIEW
The performance of a communication network is a key aspect of network engineering. Delay and packet loss are two important performance metrics of computer networks. Daly and packet loss are directly related to queues in a computer network. Delay is a measure of the time it takes the packet to reach from source to destination and major part of this delay is the queuing delay which is the average time a packet has to wait before being transmitted by a router. Packet loss is the percentage of data packets that are lost in the system. Packet losses happen when a packet is received in a finite queue which is already full. In this case the queue does not have enough buffer to store the packet and the packet has to be dropped. The performance of computer networks can be evaluated by using network models. The three common types of network models are analytical (i.e., mathematical) models, simulation models, and prototype implementation models. It is difficult to build exact analytical models of complex systems. Therefore, we try to get an approximate analytical model which is validated with a simulation model.  

Simulation is not only useful for validating approximate solutions but also in many other scenarios. During the design of a system, it allows us to compare potential solutions at a relatively low cost. It is also very useful to dimension a system, i.e., to decide how much resources to allocate to the system based on a-priori knowledge of the inputs. In addition, it is used to check how potential modifications of an existing system could affect the overall performance. To perform a simulation, we need a model of the system, as well as models for input(s). In this project, you are going to simulate and understand the behaviour of two basic types of queues.

4         BACKGROUND MATERIAL
 

4.1        Kendall Notation
Queues are typically described using Kendall notation of the form: A/S/C/K/D, where

A corresponds to the arrival process of the packets (more precisely the distribution of the inter-arrival time between packets). A can be M (Markovian), D (Deterministic) or G (General).
S corresponds to the server process for the packets. S can again be M, D or G.
C corresponds to the number of servers (or network interfaces).
K corresponds to the buffer size, i.e. the number of packets that can be accommodated in the “waiting room”. If omitted, the buffer is assumed to be infinitely large.
D corresponds to the queueing discipline, which is almost always FIFO (First-In-First-Out) see Figure 1. and is therefore often omitted from the notation.
 

For example, M/M/c queue means that both the arrival and service processes are Markovian and that there are c servers. A Markovian arrival process means that the arrival process follows a Poisson distribution. In a Poisson distribution, the distribution of the time between successive arrivals (also called inter-arrival time) follows exponential distribution. A service process M means that the distribution of the service time is identical for each customer/packet, is independent from one customer to another, and is exponentially distributed

The queues you need to simulate in this experiment are M/M/1 and M/M/1/K. 

4.2        M/M/1 and M/M/1/K queues
Consider M/M/1 queue with arrival rate of 10 packets/sec and service rate of 500 packets/sec. In this queue, packets will arrive to the queue following a Poisson process where the queue is expected to receive 10 packets/sec on average. When a packets arrives to the queue, it can be serviced (i.e., transmitted by the server) right away if the queue is empty. If the queue is not empty, an arriving packet has to wait in the queue for its turn to be serviced. Note that the queue size in M/M/1 queue is infinite, and hence, any arriving packet will find a room in the queue and no packet will be dropped. The packet waiting time in the queue (queuing delay) is an important metric to measure the performance of a computer network. In this project, you will measure the queueing delay in different queue models. Once a packet arrives at the server, it will be transmitted with a service rate following exponential distribution. A service rate of 500 packets/sec means that the queue server will transmit on average 500 packets every second. But why the number of the serviced packets per sec could change? The answer is simply because each packet will have a different length, and hence, different service rate. In other words, the packet length will have the same exponential distribution as the service rate.  

Now let us consider M/M/1/K queue model. The only difference between M/M/1 queue and M/M/1/K is that the buffer size (K) in M/M/1 is infinite while it is limited in M/M/1/K to a size of K packets. As a result, if a packet arrives to M/M/1/K queue and this queue has already K packets in the queue, the packet has to be dropped, i.e., the packet will be lost. Packet loss ratio is another performance metric of a computer network. In this project, you will calculate the packet loss ratio for M/M/1/K queue.

From the aforementioned discussion, it is clear that in order to simulate queues we need to simulate the packets arrival process as a random variable with Poisson distribution and the packet length as a random variable with exponential distribution but how can we simulate random variables with different distribution? The answer to this question will be explained in the upcoming sections of this manual.

4.3        Basics of Simulation Modeling
A simulation model consists of three kinds of elements: Input variables, Simulator, and Output variables. The simulator is a mathematical/logical relationship between the input and the output. A simulation experiment is simply a generation of several instances of input variables, according to their distributions, and of the corresponding output variables from the simulator. We then use the output variables (usually some statistics) to analyze the performance measures of the system. The generation of the input variables and the design of the simulator will be discussed next.

4.4        Generation of input variables with different distributions
In this project, you will need to simulate random variables with certain probability distributions. One method to generate a random variable with a specific probability distributions is called the inverse method. If you need to generate a random variable X with a distribution function 𝐹(𝑥) using the inverse method, you start by setting 

𝑈 = 𝐹(𝑥), where U is a uniform random variable in the range (0, 1)

Then, find the inverse of the distribution function, i.e.,  

𝑥 = 𝐹−1(𝑈)

Now, if you generate uniform random variable U in the range (0, 1) and substituted in the previous  equation, you will get a random variable 𝑥 that has a distribution 𝐹(𝑥). You will need to use the inverse method to generate the required random variables for M/M/1 and M/M/1/K.

In this project you will be required to simulate Poisson process. A Poisson distribution is concerned with the number of events that happen in a period of time. However, what we are interested in is when an event is going to happen. The interarrival time between events in Poisson process follows exponential distribution. In other words, we need to generate a random variable X with exponential distribution  in order to determine the timing between events represented by the random variable X.  

4.4.1        Generating exponential random variables
Assume that we want to generate an exponential random variable  𝑥 with average 1/𝜆 , where 𝜆 is the rate parameter.  We will use the inverse method. We start by the exponential cumulative distribution function given as:

𝐹(𝑥) = 1 − 𝑒−𝜆 𝑥                                   (1)

Set 𝐹(𝑥) equal to 𝑈  which is a uniform random variable

𝐹(𝑥) = 𝑈                               (2)  

Then, substitute from (1) in (2) and solve for 𝑥 

1 − 𝑒−𝜆 𝑥 = 𝑈 

𝑒−𝜆 𝑥 = 1 − 𝑈 

−𝜆𝑥 = ln(1 − 𝑈)  𝒙 = − (𝟏) 𝒍𝒏(𝟏 − 𝑼)  

𝝀

where U is a uniformly generated number and 𝑥 is the exponential random variable.

4.5        Designing a Discrete Event Simulator (DES)
Discrete Event Simulation (DES) is commonly used to study the performance of evolving systems whose states change at discrete points in time in response to external and internal events. A DES simulator consists of  a set of time-ordered events Ei, i = 1,…, N, along with their occurrences time, such that  t(Ei) < t(Ei+1) for all i as shown in Table 1. The time of the last event , which is t(Ei+3) in this case, is the called the simulation time. Note that there is a difference between the simulation time and the execution time of your code. The execution time is how long your code will run for in order to simulate a system for an amount of time equal to the simulation time.

 

 

 

Table 1. Discrete Event Simulation (DES)

Event 
Time 
Ei
t(Ei)
Ei+1
t(Ei+1)
Ei+2
t(Ei+2)
Ei+3
t(Ei+3)
To perform DES, you need to create events and their corresponding occurrence time. But when should the DES terminate? By performing DES, we are performing a statistical experiment. In order to get good results in a statistical experiment, your simulation time should be large enough to truly represent the system under consideration, which is a queue in this case. An easy way to get stable simulation results is to run the experiment for T seconds, take the result, run the experiment again for 2T seconds  and see if the expected values of the output variables are similar to the output from the previous run.  For example, the difference should be within 5% of the previous run.  If the results agree, you can claim the result is stable.  If not, you try again for 3T, 4T, … If you cannot seem to find a proper T, it may mean that your system is unstable. For the purpose of this project, the value of T should be starting from than 1000 seconds but you should still use the procedure described above to check the stability (and hence the validity) of your results.

4.5.1        Simulating A Queue
Systems involving queues are generally simulated with a DES simulator. A queue comprises two components: a buffer and one or many servers. 

In order to simulate a queue using DES, you need to select the simulation time T and create queue events and their corresponding time. In a queue, you have three types of events:Packet arrival: Based on the type of the arrival process specified in the Kendall notation, generate a random variable that represents the arrival times of packets to a queue. For example, in M/M/1 queue, the packet arrival will follow an exponential distribution. Use the inverse method previously explained to generate packet arrivals for a period of time equal to the simulation time T.
 

Packet departure: Calculate the departure time of a packet based on the state of the queue, i.e., whether the queue has packets or it is idle. If the queue has packets, then the departure time of a packet pkti will be the departure time of the previous packet pkti-1 plus the transmission time of pkti . If the queue is idle, then the departure time of packet pkti will be its arrival time plus its transmission time. See Table 2.
Table 2. Example of generating arrivals and departures

Event
Arrival

Time
Length

(bits)
Service

Time
Departure
Arrival
0.01172
3694.4
0.0037
0.0154136
Arrival
0.01942
13438
0.0134
0.032857
Arrival
0.04083
7341.3
0.0073
0.0481729
Arrival
0.06028
24220
0.0242
0.0845039
Arrival
0.0734
9477.1
0.0095
0.0939809
Arrival
0.08096
6789.5
0.0068
0.1007704
Arrival
0.09245
6895.9
0.0069
0.1076663
Arrival
0.11049
4626.9
0.0046
0.1151162
 

Observer: In order to monitor the queue, you need to generate observer events at which you are going to record the state of the queue. Generate a set of random observation times according to the packet arrival distribution with rate at least 5 times the rate of the packet arrival. At an observer event, you will record the state of the queue which can be done by recording the following: the time-average of the number of packets in the queue, E[N], the proportion of time the server is idle (i.e., the system is empty) PIDLE and in the case of a finite queue, the probability PLOSS that a packet will be dropped (due to the buffer being full when it arrives). The measurement and recording of the state should be performed such that we have statistically representative information on the performance that we are interested in. In order to record the state of the queue, you need to have three counters: Na = number of packet arrivals, Nd = number of  packets departures, and No = number of observations. The onset is on you to find out how to use the previous three counters to calculate the state of the queue, i.e., E[N], PIDLE, and PLOSS (in case of finite queue).
 

After generating all the three events, put all the events in a list and sort them according to time as shown in the Fig. 2.
Figure 2. DES example

Start processing the events in order from DES. Based on the event type, you should update the three counters Na, Nd and, No. If the event is observer, calculate the performance metrics of interest, e.g., PIDLE, PLOSS. After an event has been processed, it should be deleted from DES.
 

4.6        Notations
λ = Average number of packets generated /arrived (packets per second)
L = Average length of a packet in bits.
α = Average number of observer events per second
C = The transmission rate of the output link in bits per second.
ρ = Utilization of the queue (= input rate/service rate = L λ/C)
E[N] = Average number of packets in the buffer/queue
PIDLE = The proportion of time the server is idle, i.e., no packets in the queue nor a packet is being transmitted.
PLOSS = The packet loss probability (for M/M/1/K queue). It is the ratio of the total number of packets lost due to buffer full condition to the total number of generated packets.
 

5         QUESTIONS
Read all the questions before you start designing your simulator.

Question 1:  Write a short piece of C code to generate 1000 exponential random variable with =75.  What is the mean and variance of the 1000 random variables you generated?  Do they agree with the expected value and the variance of an exponential random variable with =75? (if not, check your code, since this would really impact the remainder of your experiment).

FOR ALL THE UPCOMING QUESTIONS YOU HAVE TO SHOW THAT THE OBTAINED RESULTS ARE CONSISTENT WHEN THE SIMULATION TIME CHANGES. OTHERWISE, YOU WILL LOSE MARKS 

M/M/1 Queue: Recall that it is a queue with an infinite buffer.
Question 2: Build your simulator for this queue and explain in words what you have done. Show your code in the report. In particular, define your variables.  Should there be a need, draw diagrams to show your program structure. Explain how you compute the performance metrics.

Question 3: The packet length will follow an exponential distribution with an average of L = 2000 bits. Assume that C = 1Mbps. Use your simulator to obtain the following graphs. Provide comments on all your figures.

E[N], the average number of packets in the queue as a function of  (for 0.25 <   95, step size 0.1). Explain how you do that.
PIDLE, the proportion of time the system is idle as a function of , (for 0.25 <   95, step size 0.1). Explain how you do that.
Question 4: For the same parameters, simulate for = What do you observe? Explain.

M/M/1/K Queue: Let K denote the size of the buffer in number of packets. Since the buffer is finite, packets arriving at a full buffer will be dropped.
Question 5: Build a simulator for an M/M/1/K queue, and briefly explain your design.  

Question 6: Let L=2000 bits and C=1 Mbps. Use your simulator to obtain the following graphs:

 E[N] as a function of ρ (for 0.5 < ρ < 1.5, step size 0.1), for K =  10, 25, 50 packets. Show one curve for each value of K on the same graph.

 PLOSS as a function of ρ (for 0.5 < ρ < 1.5) for K = 10, 25, 50 packets. Show one curve for each value of K on the same graph. Explain how you have obtained PLOSS.  

Briefly discuss your graphs.

 

6         FINAL REPORT
Submit the following to the dropbox on LEARN:

A complete report withTable of contents
Answer all the questions and provide explanations as asked for.
Source code with proper documentation/comments. Insufficient documentation will result in losing marks.
Include a makefile that builds and runs your code.

You may be asked to give a demo of your simulator.  

7         REFERENCES
Law, W. D. Kelton, Simulation Modeling and Analysis, 2nd edition, McGraw-Hill, 1991.