Project 1: M/M/1 and M/M/1/K Queue Simulation

ECE 358: Computer Networks
Project 1: M/M/1 and M/M/1/K Queue
Simulation
2
Table    of    Contents
1 OBJECTIVE................................................................................................................................................ 3
2 EQUIPMENT ............................................................................................................................................. 3
3 OVERVIEW ............................................................................................................................................... 3
4 BACKGROUND MATERIAL......................................................................................................................... 3
4.1 Kendall Notation.............................................................................................................................. 3
4.2 M/M/1 and M/M/1/K queues.......................................................................................................... 4
4.3 Basics of Simulation Modeling.......................................................................................................... 4
4.4 Generation of input variables with different distributions................................................................ 5
4.4.1 Generating exponential random variables............................................................................... 5
4.5 Designing a Discrete Event Simulator (DES)...................................................................................... 5
4.5.1 Simulating A Queue................................................................................................................. 6
4.6 Notations......................................................................................................................................... 7
5 QUESTIONS............................................................................................................................................... 7
6 FINAL REPORT........................................................................................................................................... 8
7 REFERENCES ............................................................................................................................................. 8
3
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.
4
• 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.
5
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.,
� = �()(�)
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 − �(/ 0 (1)
Set �(�) equal to � which is a uniform random variable
�(�) = � (2)
Then, substitute from (1) in (2) and solve for �
1 − �(/ 0 = �
�(/ 0 = 1 − �
−�� = ln(1 − �)
� = − 4
�
�
7 ��(� − �)
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.
6
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.
1. 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:
a. 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.
b. 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
c. 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
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
7
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).
2. 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
3. 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 l=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 l=75? (if not, check your code, since this would really impact the remainder of your
experiment).
8
I. 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.
1. E[N], the average number of packets in the queue as a function of r (for 0.25 < r < 0.95, step size 0.1). Explain
how you do that.
2. PIDLE, the proportion of time the system is idle as a function of r, (for 0.25 < r < 0.95, step size 0.1). Explain
how you do that.
Question 4: For the same parameters, simulate for r=1.2. What do you observe? Explain.
II. 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:
1. A complete report with
a. Table of contents
b. Answer all the questions and provide explanations as asked for.
2. 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
A. Law, W. D. Kelton, Simulation Modeling and Analysis, 2nd edition, McGraw-Hill, 1991.