Queueing theory

The branch of probability theory in which one studies mathematical models of various kinds of real queues (cf. Queue). These models are presented as random processes of a special form, sometimes called service processes. The definitions of these processes are most often descriptive, since their formal construction is very complicated and not always effective.

Queueing theory mainly uses the apparatus of probability theory. The fundamental problems of queueing theory usually are these: Based on "local" properties of the random processes under discussion, study their stationary characteristics (if they exist) or the behaviour of these characteristics over a long period of time. One of the main aims of research in this area is the choice of a preferable organization for a queueing system.

For example, for a typical object of queueing theory such as an automatic telephone exchange (see Queue with refusals) one of the basic characteristics is the proportion of calls lost, that is, the limit $ p $, as $ t \rightarrow \infty $( if it exists), of the ratios $ r ( t) / e ( t) $ of the number $ r ( t) $ of calls lost up to time $ t $ to the number $ e ( t) $ of calls which arrived up to the same time. Here the distribution of the time intervals $ \tau _ {1} ^ {e} , \tau _ {2} ^ {e} \dots $ between the arrivals of calls and the distribution of the service times $ \tau _ {1} ^ {s} , \tau _ {2} ^ {s} \dots $ of these calls are assumed to be known. The assignment of the distribution of a random (control) sequence $ \{ {\tau _ {j} ^ {e} , \tau _ {j} ^ {s} } : {j = 1, 2 ,\dots } \} $ together with the description of an algorithm of how the queue evolves form the initial data, characterizing the "local" properties of the service process.

Similarly, for multi-server queues (cf. Queue, multi-channel with waiting) one studies the limit as $ n \rightarrow \infty $ of the distributions of the probabilities $ {\mathsf P} \{ w _ {n} < x \} $ and $ {\mathsf P} \{ q _ {n} < x \} $ for the time $ w _ {n} $ which the $ n $- th call arriving in the system has to wait before the beginning of its service and the queue length $ q _ {n} $ at the time of its arrival. The limit distribution $ \lim\limits _ {t \rightarrow \infty } {\mathsf P} \{ q ( t) < x \} $ for the queue length at time $ t $, etc., are also discussed. Here, again, the initial data are the assignment of the control sequences (the distribution of the intervals of service times) and the algorithm defining the operation of the queue.

For relatively simple queues, and under certain assumptions on the control sequence, the required characteristics can be found by analytic methods. However, the number of such systems is not large. The nature of the conditions imposed on the control sequence can be demonstrated by the example of a queue with refusals (an automatic telephone exchange). Let 1) the random variables $ \tau _ {j} ^ {e} $ be exponentially distributed:

$$ {\mathsf P} \{ \tau _ {j} ^ {e} > x \} = e ^ {- \alpha x } ,\ \alpha > 0, $$

that is, the input stream is Poisson; 2) the variables $ \tau _ {j} ^ {s} $ be independent and identically distributed and not dependent on $ \{ \tau _ {j} ^ {e} \} $. Then the probability of refusal $ p $, defined above, exists and is equal to

$$ p = \ \frac{\rho ^ {n} }{n!} \left ( \sum _ { k= } 0 ^ { n } \frac{\rho ^ {k} }{k!} \right ) ^ {-} 1 , $$

where $ \rho $ is the ratio of the mathematical expectations:

$$ \rho = \ \frac{ {\mathsf E} \tau _ {j} ^ {s} }{ {\mathsf E} \tau _ {j} ^ {e} } = \alpha {\mathsf E} \tau _ {j} ^ {s} . $$

For this system, if one of the conditions 1) or 2) fails, then the search of explicit formulas for $ p $ becomes very complicated or even impossible.

Underlying the analytic approach to the search for explicit expressions for the desired characteristics is a method connected with the construction of Markov processes describing the state of the system. These processes are very well studied and the solution of the problem in this case reduces to the formulation and solution of the corresponding equations for stationary distributions (invariant measures).

Such a process is often used in a modified form by forming semi-Markov processes or imbedded Markov processes (the Markov property is satisfied only at certain random times).

For certain complicated queues exact analytic methods, as a rule, are not effective and one uses asymptotic methods or simulates the random processes by a Monte-Carlo method. Asymptotic methods are relevant in those cases when the system under consideration is close (in its local properties) to another system which is either well studied and allows the calculation of the necessary characteristics, or is in some sense critical. The direction of asymptotic investigation in the first case is described by stability (or continuity) theorems. In the second case stationary characteristics often do not exist, but one can establish "collective" limit theorems for them, that is, theorems in which the limit behaviour is determined not by individual properties of the control sequences but only by certain numerical parameters. Examples of the second type are theorems on the so-called single-server queues with heavy traffic. They have been established as follows. Let the inter-arrival intervals $ \tau _ {j} ^ {e} $, $ j = 1 , 2 \dots $ and the inter-service times $ \tau _ {j} ^ {s} $, $ j = 1 , 2 \dots $ form mutually-independent sequences of independent identically-distributed variables and let the expectation

$$ a = {\mathsf E} ( \tau _ {j} ^ {s} - \tau _ {j} ^ {e} ) $$

of the difference between $ \tau _ {j} ^ {s} $ and $ \tau _ {j} ^ {e} $ be positive. Then there is a non-degenerate limit distribution

$$ w ( x) = \lim\limits _ {n \rightarrow \infty } \ {\mathsf P} \{ w _ {n} \geq x \} $$

for the waiting time $ w _ {n} $ of the $ n $- th call. In addition, let the random variables $ \tau _ {j} ^ {e} $, $ \tau _ {j} ^ {s} $ vary so that $ a \downarrow 0 $( $ a $ tends to zero from the positive side), so that the variance $ {\mathsf D} ( \tau _ {j} ^ {s} , \tau _ {j} ^ {e} ) $ converges to a positive limit $ \sigma ^ {2} < \infty $ and so that the expectation $ {\mathsf E} [ \tau _ {j} ^ {s} - \tau _ {j} ^ {e} ] ^ {2 + \gamma } $ is uniformly bounded for some $ \gamma > 0 $. Then for each fixed $ z $,

$$ \tag{* } w \left ( \frac{z}{a} \right ) \rightarrow \ e ^ {- 2 z / \sigma ^ {2} } . $$

This relation allows the approximate calculation of $ w ( x) $ for small values of $ a $. The limit system, corresponding to $ a = 0 $, is critical in the sense that for it there is no non-degenerate limit distribution $ w ( x) $, and $ w ( x) = 1 $ for each $ x > 0 $( the waiting time of the $ n $- th client increases unboundedly as $ n $ increases). Relation (*) can be extended to a broad class of queues with waiting under very general assumptions on the control sequences.

The emergence of queueing theory has produced an interest in the novel mathematical problems which arise in the organization of telephone networks. The first publication in this connection is due to A. Erlang in 1907. The later development of queueing theory occurred in the 1940's and 1950's in papers by C. Palm, F. Pollaczek, A.Ya. Khinchin, and others. The last coined the term "queue" . In the USSR, work on queueing theory was continued by B.V. Gnedenko, with a group of his students, and others.

The development of queueing theory has been stimulated both by a variety of applications and by the mathematical content of the problems that arise. Although formally a part of the theory of random processes, queueing theory has evolved into an independent area of research with its own problems and methods of solution.

References

[1]	A.Ya. Khinchin, "Mathematical methods in the theory of queueing" , Griffin (1960) (Translated from Russian)
[2]	B.V. Gnedenko, I.N. Kovalenko, "Introduction to queueing theory" , Israel Program Sci. Transl. (1968) (Translated from Russian)
[3]	A.A. Borovkov, "Stochastic processes in queueing theory" , Springer (1976) (Translated from Russian)
[4]	A.A. Borovkov, "Asymptotic methods in queueing theory" , Wiley (1984) (Translated from Russian)

Comments

A facility for collective use has usually a limited capacity and congestion (loss) arises when the momentary demands of the users surpass the capacity. Facilities for collective use are encountered in a large variety in present day society, e.g. ticket windows, road junctions, beds in a hospital, communication trunks in a telephone network, the central processor unit in a computer.

The need to evaluate the performance of a facility led to the development of queueing theory. The basic model concerns a single-server system and the description of the arrival process, of the service times required by the customers and the service discipline, which specifies the schedule of handling the customers.

The irregularities in the arrival stream and also those in the demands of the service times require for their modelling a probabilistic approach; in fact, they are modelled as stochastic processes. Consequently, performance characteristics such as the waiting time of the $ m $- th arriving customer, the queue length of the $ n $- th arrival and the workload of the server as a function of time have to be analyzed as stochastic processes. Queueing theory studies the relations between these performance characteristics and the input processes (arrival and service times), and as such queueing theory is an important branch of applied probability theory.

The early developments of queueing theory took place in the first decade of the 20th century; congestion phenomena in telephone communication have been the direct impetus. Until 1940 queueing theory has been developed mainly for purposes in telecommunication engineering. The growing interest after 1940 in operations research had a considerable influence on the developments of queueing theory. At present a huge variety of queueing models are studied: many-server models, batch arrivals instead of individual arrivals, group service, and sophisticated service disciplines like random service, priority service, processor sharing, and feedback of customers. Next to a single-service facility, networks of queues require analysis. In a network a customer or a message has to be transported via the nodes connected by links to a certain destination; at the switching nodes congestion may occur. The routing of the customers through the network is usually modelled as a stochastic protocol.

The mathematical analysis concerned with the relations between the performance and model characteristics is the analytical part of queueing theory; simulation techniques are used to study such relations experimentally.

References

[a1]	W. Feller, "An introduction to probability theory and its applications", 1–2, Wiley (1966)
[a2]	L. Kleinrock, "Queueing systems", 1–2, Wiley (1976)
[a3]	J.W. Cohen, "The single server queue", North-Holland (1982) pp. Chapt. II.1
[a4]	R. Syski, "Congestion theory", North-Holland (1986)