Queue, multi-channel with waiting

multi-server queue

A queue for which the algorithm provides for the calls to form a queue if the system is busy at the time of their arrival; here the service of calls takes place in several channels simultaneously. The basic definitions and notations are as in Queue.

The operation of a multi-server queue, controlled by a sequence , is as follows. Calls arrive at times . A time is spent on the service of the -th call, no matter which of the channels serves the call. Calls arrive and are immediately directed (in order of arrival) to a free channel if not all channels are busy, or wait until some channel is free and then proceed into service. For simplicity, let the system be free at time .

1) For clarity of exposition the following notation is used: is the vector of waiting times of the -th call, where is the time this call must wait until channels are free of calls which arrived before it, so is the "actual" waiting time. In addition, let ,

and let be the vector obtained from by placing the coordinates in increasing order (so the first coordinate of is ). Then the following recurrence relation holds for , generalizing the one-dimensional case:

(1)

If and , then there is a proper sequence which satisfies (1) and is such that the distribution function of converges monotone to the distribution function of as . This result has a generalization to the case and can also be extended to the queue length at the time of arrival of the -th call ( is the queue length excluding calls in service). There are formulas connecting the limit distributions of and .

If , , then (1) allows one to write an integral equation for the stationary distribution of . In this case it is possible to also give simple relations between the stationary distribution of the queue length and the waiting time. Specifically, if denotes the -th coordinate of the vector , then for ,

If , then

Here, all random variables under the probability sign are independent.

If, in addition, has a non-lattice distribution, similar formulas are true for the limit distribution of . If , then

2) If , , then it is possible to give explicit formulas for the limit distribution of , and . Let be the index of the distribution of and let . Then the numbers

can be described explicitly by rational functions of the values and , , where is the unique root in of the equation

If , then

where does not depend on . For the limit distribution of the waiting time,

If is a non-lattice random variable, then

exists, where

In case , ,

where

3) Stability theorems (about the continuous dependence of the stationary distributions of on the distributions of and ) are obtained in a less general form than for single-server systems, and are connected with a condition on the existence of so-called renewal events. However, in case , , the condition , must be satisfied. If for such systems, in triangular arrays, the distributions of and converge weakly to the distributions of and , respectively, and, in addition, , then the distribution of will converge weakly to the distribution of .

4) Asymptotic methods used in the analysis of multi-server systems with heavy traffic give results similar to the corresponding results for single-server systems.

In a series of control sequences , , let

( is the difference between the mean number of calls joining the system and the mean number of calls which the system can serve in unit time: if , , then can be taken to be the number , which has the same meaning). Now if

and , are uniformly bounded for some , then the following holds as , for the queue length at time :

for , ,

where is a standard Wiener process;

for ,

for , ,

Similar relations are true for the queue length and the waiting time .

Another possible direction for asymptotic investigation of multi-server systems is the study of systems with intensive input stream and an unboundedly increasing (with ) number of service channels.

5) The behaviour of multi-server systems with an infinite number of service channels and with a control sequence is described in the same way as the behaviour of multi-server systems with waiting; the only difference being that here there is always a free channel and, consequently, the waiting time for any call is equal to zero. As a characteristic of the state of the system one takes the number of busy lines at the time of arrival of the -th call or the number of busy lines at time (as everywhere above, and are the queue lengths and ).

Let and, in addition, let be metrically transitive. Then, if , the distribution of the sequence converges monotone, as , to the distribution of the strictly stationary sequence

(2)

where is the indicator of the event . The condition is nearly a necessary condition for the finiteness of (2).

6) For systems in which , , , the distribution of the stationary queue length can be described with the help of equations. For this, one introduces the variable

The number indicates how many calls are in the system operating in a stationary regime, if one goes back to a time after the arrival of a certain call but not counting that call and the calls arriving after it.

Denoting

one obtains

the system of functions satisfies the equations

Here must be equal to . Each of the first equations of this system, relative to , has a unique solution in the class of functions of bounded variation with the properties

Similar results hold for the distribution of . If , , then

where and is the exponent of the distribution of .

If , , then

where

and is the exponent of the distribution of . If, in addition, is a non-lattice random variable, then

7) Stability theorems in the case , as in the preceding sections, give conditions under which a small change in the control sequences leads to a small change in the stationary distribution of the number of busy lines.

For triangular arrays, when the system is controlled by a stationary sequence depending on a parameter let the following conditions hold.

A) There is a sequence such that is metrically transitive, and the finite-dimensional distributions of converge to the distributions of as .

B) as .

C) The distributions of for all are continuous at the point .

The stability theorem then asserts that under conditions A)–C) the distributions of the sequence of queue lengths (defined by (2) with respect to the control sequence ) converge to the distributions of as .

All three conditions A), B) and C) in this result are essential; the failure of any one of these immediately allows the construction of examples where the distributions of do not converge.

8) Asymptotic analysis of systems with an infinite number of service channels is natural and effective in the study of so-called traffic systems, when the input stream has high intensity. The advantage of the asymptotic approach lies in the great generality and universality of the laws established.

Let the input stream , denoting the number of calls arriving in the system up to time , depend on a parameter (a triangular array), so that as for each fixed and, in addition, let there exist a non-decreasing function , a function as and a continuous random process , defined on , such that the distribution of , where

converges weakly to the distribution of as , for any functional which is measurable and continuous in the uniform metric.

For example, if and if the control of the system is via a sequence , then the condition stated will be satisfied for any , where

and is a standard Wiener process.

Regarding the service mechanism it is assumed that . Then:

a) If , then the finite-dimensional distributions of the normalized queue

converge weakly as to the distributions of the process

b) If , then the finite-dimensional distributions of the process

converge weakly to the finite-dimensional distributions of the process

where is a centred Gaussian process not depending on with covariance function

If the functions or are required to have some degree of smoothness, then the convergence of to , , holds even in a stronger sense (for example, convergence of the distribution of to that of as for all functionals continuous relative to the uniform metric).

For references see Queueing theory.