Queue (theory)

A queue can be described as follows: costumers (humans, process, messages, etc.) arrive for a service, wait in a queue if they can not be served immediately, and leave after having the serviceFig1.

The model, originally created by Erlang for the telephone system of 1909, makes it possible to model the traffic management, the planning and the dimensioning of infrastructures and machining.

Kendall’s notation

A queue has 6 criteria noted by: T/X/C/K/P/Z

  • T : the probability distribution of inter-arrival time. Customers can leave if they arrive while the queue is full. T can take the following values
    • M for Markov process / exponential law (Poisson)
    • G for the general law
    • D for the deterministic law
    • E(k) for the Erlang law
    • etc.
  • X : the probability distribution of the service time. A costumer is taken directly by a free server, once the service is completed the costumer leaves. The distribution is represented by the same symbols as in T.
  • C : the number of servers. In simple queues, the servers all have the same probability distribution of service time.

proba53

  • K : the capacity of the queue. If the queue is a finite number, the client is lost when the queue is full. The servers count in the capacity of the queue (1 per server).
  • P : the size of the population. The size of the population is finite or infinite. In the case of a finite population, the customer arrival rate is a function of the number of customers in the system.
  • Z : the service discipline
    • FCFS/FIFO (first come first served / first in first out)
    • LCFC/FILO (last come first served / first in last out)
    • RANDOM
    • HL (hold in line): if an « important » customer arrives, he takes first place in the queue (depending on the « importance » of the first customers)
    • PR (preemption): if an « important » customer arrives, it is served directly and the « less important » customer leaves the service to go to the queue
    • PS (processor sharing): all costumers are served at the same time with a speed inversely proportional to the number of clients
    • etc.

A queue can be browsed by different classes of customers characterized by:

  • Various birth rate
  • Various death rate
  • Various rewards/punishments (costumers may have a cost)
  • Scheduling in the queue according to their class

One will use the notation T/X/C when the queue is of infinite capacity, the size of the population is infinite and that the service is of discipline FIFO. This amounts to writing T/X/C/∞/∞/FIFO.

Performance measures

The purpose of a queue study is to calculate or estimate the performance of a system. This calculation is done in stationary mode in order to calculate: the rate X, the number of customers Q, the rate of use of the server U, the response time R. In general, one calculates the expectations of these parameters.

In the context of simple queues, the system is ergodic. We then try to calculate the stability of the system. Let’s take the following elements:

  • A(T): number of arrivals in the system between 0 and T
  • D(T): number of departures of the system between 0 and T
  • Xe(T) = A(T)/T: average input rate between 0 and T
  • Xs(T) = D(T)/T: average output rate between 0 and T
  • Q(T): average number of customers in the queue between 0 and T
  • Rk: residence time of the kth customer arrived
  • proba55: average residence time between 0 and T

a queue is stable if and only if the limit when T tends to infinity of the average input rate is equal to the limit when T tends to infinity of the average output rate. In other words, when the limit when T tends to the infinite of D(T)/A(T)=1. In a stable queue, the number of costumers in the queue remains finite.

Publicités