Queueing Theory Basics
We have seen that as a system gets congested, the service delay in the system
increases. A good understanding of the relationship between congestion and delay
is essential for designing effective congestion control algorithms. Queuing
Theory provides all the tools needed for this analysis. This article will focus
on understanding the basics of this topic.
Communication Delays
Before we proceed further, lets understand the different components of delay
in a messaging system. The total delay experienced by messages can be classified
into the following categories:
| Processing
Delay |
- This is the delay between the time of receipt of a packet for
transmission to the point of putting it into the transmission
queue.
- On the receive end, it is the delay between the time of reception of
a packet in the receive queue to the point of actual processing
of the message.
- This delay depends on the CPU speed and CPU load in the
system.
|
| Queuing
Delay |
- This is the delay between the point of entry of a packet in the
transmit queue to the actual point of transmission of the message.
- This delay depends on the load on the communication link.
|
| Transmission
Delay |
- This is the delay between the transmission of first bit of the
packet to the transmission of the last bit.
- This delay depends on the speed of the communication link.
|
| Propagation
Delay |
- This is the delay between the point of transmission of the last bit
of the packet to the point of reception of last bit of the packet at
the other end.
- This delay depends on the physical characteristics of the
communication link.
|
| Retransmission
Delay |
- This is the delay that results when a packet is lost and has to be
retransmitted.
- This delay depends on the error rate on the link and the protocol
used for retransmissions.
|
In this article we will be dealing primarily with queueing delay.
Little's Theorem
We begin our analysis of queueing systems by understanding Little's Theorem.
Little's theorem states that:
The average number of customers (N) can be determined from the following
equation:
Here lambda is the average customer arrival rate and T is the average service
time for a customer.
Proof of this theorem can be obtained from any standard textbook on queueing
theory. Here we will focus on an intuitive understanding of the result. Consider
the example of a restaurant where the customer arrival rate (lambda) doubles but
the customers still spend the same amount of time in the restaurant (T). This
will double the number of customers in the restaurant (N). By the same logic if
the customer arrival rate remains the same but the customers service time
doubles, this will also double the total number of customers in the restaurant.
Queueing System Classification
With Little's Theorem, we have developed some basic understanding of a
queueing system. To further our understanding we will have to dig deeper into
characteristics of a queueing system that impact its performance. For example,
queueing requirements of a restaurant will depend upon factors like:
- How do customers arrive in the restaurant? Are customer arrivals more
during lunch and dinner time (a regular restaurant)? Or is the customer
traffic more uniformly distributed (a cafe)?
- How much time do customers spend in the restaurant? Do customers typically
leave the restaurant in a fixed amount of time? Does the customer service
time vary with the type of customer?
- How many tables does the restaurant have for servicing customers?
The above three points correspond to the most important characteristics of a
queueing system. They are explained below:
| Arrival
Process |
- The probability density distribution that determines the customer
arrivals in the system.
- In a messaging system, this refers to the message arrival
probability distribution.
|
| Service
Process |
- The probability density distribution that determines the customer
service times in the system.
- In a messaging system, this refers to the message transmission time
distribution. Since message transmission is directly proportional to
the length of the message, this parameter indirectly refers to the
message length distribution.
|
| Number of
Servers |
- Number of servers available to service the customers.
- In a messaging system, this refers to the number of links between
the source and destination nodes.
|
Based on the above characteristics, queueing systems can be classified by the
following convention:
A/S/n
Where A is the arrival process, S is the service process and n is the number
of servers. A and S are can be any of the following:
| M (Markov) |
Exponential probability density |
| D
(Deterministic) |
All customers have the same value |
| G (General) |
Any arbitrary probability distribution |
Examples of queueing systems that can be defined with this convention are:
- M/M/1: This is the simplest queueing
system to analyze. Here the arrival and service time are negative
exponentially distributed (poisson process). The system consists of only one
server. This queueing system can be applied to a wide variety of problems as
any system with a very large number of independent customers can be
approximated as a Poisson process. Using a Poisson process for service time
however is not applicable in many applications and is only a crude
approximation. Refer to M/M/1 Queueing System
for details.
- M/D/n: Here the arrival process is
poisson and the service time distribution is deterministic. The system has n
servers. (e.g. a ticket booking counter with n cashiers.) Here the service
time can be assumed to be same for all customers)
- G/G/n: This is the most general
queueing system where the arrival and service time processes are both
arbitrary. The system has n servers. No analytical solution is known for
this queueing system.
| 
