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

CECS 474: Computer Network
Interoperability
Project 1: M/M/1 and M/M/1/K
Queue Simulation


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-toend 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 behavior
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 behavior 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 apriori 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 behavior 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 interarrival 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
5

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 𝑥 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 inter- arrival time between events in Poisson process follows exponential
distribution. In other words, we need to generate a random variable 𝑥 with exponential distribution in order
to determine the timing between events represented by the random variable 𝑥.
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 U 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 x 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
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
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
7

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).
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.
8

5 QUESTIONS
Read all the questions before you start designing your simulator.
Question 1: Write a short piece of 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).
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  (for 0.25 <   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 , (for 0.25 <   0.95, step
size 0.1). Explain how you do that.
Question 4: For the same parameters, simulate for  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 BeachBoard:
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 .txt file (name it “README.txt”) that shows how to re-run your source codes.