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:

N = λT

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.