Queuing Theory – Notation

Knowledge Base & Community Wiki

Queuing Theory – Notation

in

It is common to use to use Kendall’s notation consisting of the following symbols to describe a queuing system:

  • Lamda(λ) to be the mean (or average) number of arrivals per time period, i.e. the mean arrival rate
  • µ to be the mean (or average) number of customers served per time period, i.e. the mean service rate

The standard notation system to classify queuing systems using Kendall’s notation is A/B/m/K/n/D, where:

  • A represents the probability distribution for the arrival process
  • B represents the probability distribution for the service process
  • m represents the number of channels (servers)
  • K represents the maximum number of customers allowed in the queuing system (either being served or waiting for service)
  • n represents the maximum number of customers in total
  • D : Service discipline.

Common options for A and B are:

  • M for a Poisson arrival distribution (exponential inter arrival distribution) or a exponential service time distribution
  • D for a deterministic or constant value
  • G for a general distribution (but with a known mean and variance)

If D and E are not specified then it is assumed that they are infinite.

For example the M/M/1 queuing system, the simplest queuing system, has a Poisson arrival distribution, an exponential service time distribution and a single channel (one server). Note here that in using this notation it is always assumed that there is just a single queue (waiting line) and customers move from this single queue to the servers.

M/M/1 Example: Suppose we have a single server in a shop and customers arrive in the shop with a Poisson arrival distribution at a mean rate of lamda=0.5 customers per minute, i.e. on average one customer appears every 1/lamda = 1/0.5 = 2 minutes. This implies that the inter arrival times have an exponential distribution with an average inter arrival time of 2 minutes.

The server has an exponential service time distribution with a mean service rate of 4 customers per minute, i.e. the service rate µ=4 customers per minute. As we have a Poisson arrival rate/exponential service time/single server we have a M/M/1 queue in terms of the standard notation.

queuing_theory_wiki_v0.003Lamda(λ) = Mean Arrival Rate, Mu(μ) = Mean Service Time

Let’s take for example the system described above. The system has three elements i.e. a Client, a Server and the Network, all of them interconnected and, at some extent, making use of buffering. The ‘λ’ defines the inter arrival rate and the ‘μ’ defines the service time. Such a complex system can be analysed by involving the Queueing Theory modelling, as discussed earlier in the post. It would be interesting to simulate the performances of such a system before to deploy it, or in case the system is already in production, bottlenecks and performance analysis might be easily carried out.

It’s time to introduce a bit of formalism in this discussion. A Queueing System has to be modelled as a Stochastic Process, in which each variable/parameter is a Random Variable. According to the Kendall’s Notation, a system composed by one or more nodes can be represented using the following notation:

A / B / m / K / n / D

Where:

  • A : distribution function of the inter arrival times,
  • B : distribution function of the service times,
  • m : number of servers
  • K : system’s capacity (e.g. maximum number of customers in the system, comprehensive of the one being served)
  • n : population size (e.g. numbers of sources of customers),
  • D : Service discipline.

An example: M / M / m / infty / infty / FIFO, that’s a queuing system modeled by a Markov process for Arrival and Service times, composed by m Servers, having infinite (i.e. infty) Queue and Population capacities but FIFO service policing.

The most common types of random distributions are:

  • M : Markovian (memoryless exponential distribution),
  • D : Deterministic,
  • G : Generic.

An example: M / M / 1 has Markovian inter arrival and service time, but only 1 Server; on the other hand, M / G / r, has a Markovian inter arrival, a Generic service time and r Servers.

Queuing Systems can be classified in:

  • Finite-Source System.The inter arrival rate depends on the system’s state (e.g. number of cusomers/requests already in the system),
  • Infinite-Source System. The inter arrival rate is independent on the system’s state (e.g. requests arrival rate is completely independent from the number of requests already in the system).

From the above perspective, a Queuing Model aids in identifying a set of statistics characterizing a system, like:

Main Statistics

  • Mean Number of Customers in a System and Variance.
  • Mean Number of Waiting Customers, mean Queue Length and Variance.
  • Server Utilization.
  • Distribution of the Response Time of a Customer.
  • Distribution of the Waiting Time.

Modelling Solution: VisualizeIT offers access to a bunch of Analytical Models, Statistical Models and Simcropped-visualize_it_logo__transparent_090415.pngulation Models. Access to all the Analytical (Mathematical) models is free. We recommend you try out the Analytical models at VisualizeIT which are free to use and drop us a note with your suggestions, input and comments. You can access the VisualizeIT website here and the VisualizeIT modelling solution here –VisualizeIT.

This entry was posted in   .
Bookmark the   permalink.

Admin has written 0 articles

VisualizeIT Administrator & Community Moderator