So recently I was looking at the Linear programming formulations of Traffic engineering problems and one of the problem was to find the path with the goal to minimize the Average network delay. Which got me thinking that for topology design related problems, how can I calculate the Average network delay? As you can guess, This blog post is all about this.
Before starting few things to keep in mind:
- A background in Probability theory, particularly familiarity with Poisson and Exponential distribution will help. There is no way I can do the justice in explaining all the basics without distracting from the main goal of the blog post.
- This post will involve Queuing theory and the Math involved in Queuing theory gets complicated very fast, especially for an average guy like me. What we are going to look at is the most basic form.
- Please be aware that whatever we cover here only allows us to measure the first order approximation of what happens in real life and it is good for use cases like topology design but not for measuring the exact state of a network for operational purposes.
- My as usual disclaimer, that I am going to take some luxuries while explaining to keep things simple, so it’s possible that some statements may not be mathematically accurate.
Factors contributing to Packet Delay:
There are typically four factors which contribute to a packet delay in a network. Out of the Four factors, queuing delay is the one which is most interesting and most complicated.
Total Delay = Processing Delay + Transmission Delay + Propagation Delay + Queuing Delay
Queuing delay is the time spent by the packet sitting in a queue waiting to be transmitted onto the link. The amount of time it needs to wait depends on the size of the Queue. If the Queue is empty, then it transmitted immediately, but if it’s sitting behind other packets, then it needs to wait for the packets in front to be transmitted first (common sense).
In order to understand more about Queueing delay, we have to take a step back and look at the basics of Queuing theory first. Then we will look at the simple Queueing model, derivation and then see how we can use that to calculate the Average Network delay.
So What is Queuing Theory?
Queuing theory is basically the mathematical study of waiting lines. We see Queues every day in our life, whether it’s a line in Starbucks, queues of vehicles on the road, packets in Data networks, Grocery line etc.
Typically, a Queue is formed when people arrive at a place to get some kind of service like getting coffee, grocery, medical help etc. In Queueing theory, we create a model of the Queuing system so that we can predict the performance of the system for parameters like:
- Average number of customers waiting in a line (Average Queue length)
- Average time a customer spends waiting in a line.
- How utilized servers serving the queues are.
Queuing theory has been used extensively in Operations Research. As a matter of fact, some of the best lectures I have found on Queuing theory were taught as part of Operations research curriculum.
Components of a Queuing System:
Below is a representation of various components in a Queueing systems
At a basic level a Queuing system consists of one or more Servers serving the customers, One or more Queues in which Customers will come and line-up. The length of these Queues can be assumed infinite or finite length to hold customers waiting for service.
- Arrival Process: Represents the Customer arrival pattern. We will look more into the details.
- Service Pattern: how many servers we have and the speed of the Service which is called Service Rate.
- Queue Length: How many people a Queuing system can hold. 10, 20, 200, infinite?
- Queue Discipline: This represents if the queue will be served in First come First serve (FCFS), Last come First Serve (LCFS), Random etc. manner. Typically, it’s FCFS and that is what we will assume for the rest of the article.
Customer Arrival Pattern (Arrival Process)
Customer arrival pattern basically specifies how customers are arriving in the Queuing system. For instance, they can come either in a scheduled manner or they can be totally random. Few parameters we consider here are:
- Arrival Rate: This represents the average rate at which the customers are coming. For instance, let’s say we have a grocery store and we know that on an average, there are 5 customers every hour walks into the store. So the Average rate is 5 customers per hour and is typically represented by λ(lambda).
- Inter-arrival time: This is the time between the customer arrivals.
If we knew that the Customers come in a scheduled manner or follow some sort of pattern, then things would be easy. For instance, going back to our grocery store example, let’s say we are trying to figure out how many cash registers we have to put to handle the customers. We know that on an average 5 customers come every hour and let’s assume that it takes on an average 10 mins to service a single customer which means our Service Rate is 6 customers per hour.
Now If 5 customers walk into the store at a gap of 12 mins each, then there won’t be any queue formed because by the time next customer comes, you would have serviced the previous customer and life would be just good with a single register. But unfortunately life is not that simple, they all can just show up at the same time and that will form a Queue. So If your service time is too long then you have the risk of them walking out.
So at this point I am hoping we have built some sort of intuition on why we need to study Queues. Now in our scope, we will assume that Customers arrival pattern is Random in nature.
(Similarly, later we will assume that the packet arrival in Networks is also a Random though in reality it may not be entirely true).
We will model the customer arrival pattern as a Poisson process. If you don’t know what a Poisson process, I am just going to mention it briefly and some of the key properties, but this might be a good time to go and brush up on that first.
Poisson Arrival Model:
A Poisson process is typically used to model scenarios where we are counting the occurrences of certain events that appear to happen at a certain rate, but completely at random. For example, going back to our grocery store example, we know that average customer arrival rate is 5 but we don’t know when they will show up at the store. Poisson process is a perfect to model this kind of behavior.
I am not going to derive the above formula, but essentially it can help you in answering questions like, give me the probability of 8 customers arriving in our grocery shop in an hour given that we know on an average 5 customer per hour(λ=5) walks into the store.
The inter-arrival times of a Poisson process is independent and it follows an exponential distribution.
Exponential distribution has one key property which is Memoryless. Meaning the past doesn’t affect the Future. It’s also called forgetfulness property and simple examples would be like flipping a Coin. I think I also exhibit symptoms of Memoryless :).
Queuing Models Taxonomy:
So in Queuing theory, we use certain kind of notation (Kendal’s notation) to refer to various types of Queuing system. The format of the notation is below
A / B / s / K / n / D
- A – Arrival Process, Inter arrival times distribution. It can be either of these
- M = Represents Markovian or Memory less property like Poisson process.
- D = deterministic (Constant)
- G = General distribution
- B – Service distribution. It can be either of these
- M = Represents Markovian or Memory less property like Exponential service time.
- D = deterministic (Constant)
- G = General distribution
- s – number of servers
- K – system’s capacity (e.g. maximum number of customers in the system including the one being served). Typically, we omit this when it’s infinity.
- n – population size. Usually we consider Infinity for this.
- D – Queue Discipline like FIFO, LIFO, Random etc.
For the majority, we only use the first three i.e. “A / B / s” to represent a Queuing system. Below are few Queuing type examples
- Arrival Process: The First “M” represents memory less property i.e. Poisson arrival process. The customer arrival rate is represented by λ.
- Service Distribution: The Second “M” represents memory less property i.e. exponential service time. The service rate is represented by “µ” and the mean of Exponential distribution is given by 1/ µ.
- 1: represents the number of server.
- Infinity: Represents that the Queue length can be infinite. Off course we know that in real world this cannot be true.
- Arrival Process: “M” represents memory less i.e. Poisson Process
- Service Distribution: “M” represents memory less i.e. exponential service time
- c: Represents the number of Servers like 2 in our case.
- 10: Represents the maximum length of the Queue.
Other examples of Queuing systems could be like M/G/1, M/D/1 etc.
Out of all the different types of Queuing system, M/M/1 is the simplest Queuing model. We can model the output link of a router as an M/M/1 Queue which is actually what we will do later in the example.
At this point we know that in a Queuing system we have Customer Arrival rate (λ) which tells us how fast the customers are coming in and Service rate (µ) which is the average time taken to service each customer. A good Queuing system has a property that service Rate (µ) is always greater than the customer arrival Rate (λ) and the ratio (λ/µ) is represented by “ρ”.
Obviously the next question comes to mind is why we will have a Queue to begin with if Service Rate is higher than the Customer arrival rate? We should know this because we addressed this earlier in our earlier Grocery example i.e. Customer inter-arrival pattern is random.
In the below figure, we have a service rate of 6 per hour and arrival rate of 5 per hour and we will form Queue for bottom two illustrations where customer arrival pattern is random.
We also make another important assumption that during a very small interval (let’s call it “h”), only one event takes place. Let’s say the current time is “t” then in time “t+h”, either a customer will arrive in the Queue or a Customer is Served. We cannot have both Customer arrival and Customer getting Served in the same time interval “h”. Essentially “h” is so small that only one thing happens (Arrival or Service).
Alright, so what kind of questions we can answer with the help of Queuing Theory?
Assuming that the system is in a steady state, we can answer things like what is the probability that a system has 0, 1, 2……… to infinity customers, in the Queue? The number of people in the Queue can go either to “Infinity” or to “N” where N is the maximum size a Queue can hold depending on the type of Queuing model we are using like M/M/1: Infinity vs M/M/1: n.
Typically, we are interested in getting the value for below parameters for a given Queueing system
Little’s Law gives us below two relationships between the parameters for any steady state queuing system:
Distance = Speed x Time
The distance covered is a product of the Speed an object is moving and Time spent. Now assume that the arrival rate (λ) is the Speed and the waiting time is the time spend. This will give us the length. We are not going to prove Little’s law, but if you have an interest, the proof is widely available in lots of text books.
Relationship between Total Turnaround, Queuing and Service Times
In a queuing system, a customer’s time is either spent waiting for service or getting service. Thus, we get this relationship:
Analysis of an M/M/1 Queuing System
It’s time for us to derive some equations. An M/M/1 queuing system is a single-queue single-server queuing system in which arrivals are Poisson and service time is exponential. The notation M/M/1 describes the “queue” in the system as having a Markovian arrival process (i.e. Poisson) and a Markovian (i.e. Exponential) service discipline with 1 server.
Probability of Arrival and Departure
So as we said earlier, assume a very small time interval of length “h” and in this time interval (h), only one event happens either an arrival or departure (customer is serviced).
Since the rate of arrival is λ per unit time, then we can say that rate of arrival per interval “h” is “λh”. To think about this intuitively, let’s say we have an arrival rate of λ = 2 per second and h=5 second then arrival rate per 5 second is 10 (5 x 2).
We know that the probability density of the Poisson distribution is:
Since we are assuming that “h” is a very small period, we can ignore the higher order terms because they become negligible (intuition: If h = 0.001 then h^2 = 0.000001 which is really small ) which will leave us with λh.
P (arrival) = λh
Similarly, we can show that the probability that a customer will leave the system (i.e. a customer for whom the service was finished) given that somebody is in the system in the first place is µh.
P (departure) = µh
State (rate) transition diagram for M/M/1
Consider a M/M/1 system at steady state (i.e. Equilibrium). Such a system will have a variable number of customers. In particular, at any point of time, a customer may be added to the system through an arrival event, or a customer may be removed from the system due to a departure event.
Average number of customer in an M/M/1 System
Now we are ready to compute the average number of customers in an M/M/1 system. The total number of customers in the system (q) can be given by the sum of the number of customers and their respective probability.
Average number of customers waiting for service in a M/M/1 system
We know that q = w + ρ. Thus
Average time in a M/M/1 system
So now we have a way to calculate the average time a customer waits in an M/M/1 queuing system with infinite buffer. We could use this to figure out average delay a packet may experience on a link by Modeling a Router (store and forward) as M/M/1 Queue.
But the next question comes to mind is that in the real world we know that routers don’t have infinite buffers. In that case, if we want we could model Router’s with finite buffer as M/M/1/c Queuing system where is the “c” is the length of the buffers (or Queue size) and derive the equations for getting an average time for an M/M/1/c system.
But before you think “Oh gosh another proof and formula”, it turns out that an Infinite buffer model is a good approximation of finite buffer systems so we will skip that.
Networks of M/M/1 Queues:
Assuming that we are modelling Routers as an M/M/1 Queueing system, we know that every router is connected to each other (like Tandem Queues) where traffic enters multiple queues, exits multiple queues, traffic streams merge or splits repeatedly. This fact presents the challenge that once packets have passed the first M/M/1 Queue, are there inter-arrivals still random on the next Queue or they become strongly correlated? Because if they are not random any more than this will invalidate the Queueing models based on Poisson arrival.
It turns out that a very smart person (Leonard Kleinrock) observed and resolved the problem by introducing the Klein rock independence assumption. It turns out that by due to the effect of multiple streams merging and splitting at hops, it restores the Randomness of Inter arrival property hence making assuming Poisson arrival for packets as a valid assumption.
(Added a video link of him in References which I thought was fascinating. He did his PHD under Claude Shannon)
Average Network Delay:
We can approximate average network delay of a network that consists of more than one link in which traffic feeds from one link into another, by assuming each link behaving as an independent M/M/1 system.
Now let’s try to apply what all we have learned so far with an example. Assume that we have this network topology.
All links are of 1 Gbps capacity for simplicity. In reality we can have a capacity matrix giving us the capacity of each link. We assume that the average packet size in this network is 600 Bytes (4800 bits).
In our case this will be the Service Rate for every link as we are assuming same link capacity and average packet size. We also have the below Routing matrix for this topology which tells how traffic is routed between the Nodes.
We can look at the Routing Matrix and the Traffic Demand Matrix of the network to derive the aggregate demand for each link in the network. For Instance, from Routing matrix we know that the link “AB” will carry traffic for the demands for “AB”, “ABC”, “ABF” and “ABFD”.
Let’s say that we had a Traffic Demand matrix and after combining that with the Routing matrix, we came up with the below Aggregate Traffic Demand matrix for the links, this gives us the Arrival rate for each link.
Aggregate Traffic in PPS(Mbps) derived from Routing table.
In this blog, we started with the basics of Queuing theory, then we derived some equations for the key parameters for the M/M/1 Queueing system. Then we looked at how the M/M/1 Queuing system can be applied to Network and ended with an example.
We could have just looked at the final formula without going through the derivation, but my goal was to show how it’s derived because that is something I have found many times is not very clear in the books/articles out there. It also helps in building an understanding of the assumptions behind derived equations. Once you have developed an understanding/intuition, I do not think you have to remember the details. I hope some of you will find this useful.
I was originally thinking of covering below questions but, but decided to leave it to the user:
- Whether Poisson traffic is the right model for traffic arrival or not?
- Is M/M/1 Queuing system is the right way to model the Routers? Or we should have looked at some Queuing systems like M/G/1 where service rate distribution is modelled as a generalized distribution.
- If yes, then how can we find an average network delay in those cases.
Useful links and References:
- MIT OCW Probabilistic Systems Analysis and Applied Probability
- Intuition behind Poisson Distribution:
- Khan Academy Poisson Process Introduction
- Advanced Operations Research by Prof. G.Srinivasan
- Exponential Process Introduction https://www.youtube.com/watch?v=bKkLYSi5XNE
- Queuing and Loss Simulation: http://www.ccs-labs.org/teaching/rn/animations/queue/
- Leonard Kleinrock: https://www.youtube.com/watch?v=qsgrtrwydjw
- Network Routing, Second Edition: Algorithms, Protocols, and Architectures (The Morgan Kaufmann Series in Networking)
- High Performance Data Network Design: Design Techniques and Tools
- Queueing Modelling Fundamentals: With Applications in Communication Networks