Queue with refusals

loss system

A queue for which the algorithm provides for the loss of calls which arrive at a moment when all channels are busy. The fundamental definitions and notations are in Queue.

A natural characteristic of a queue with refusals is the number (or ) of busy lines at the time of arrival of the -th call (at time ). However, in contrast to a system with an infinite number of channels here , where is the number of channels in the system. If when the -th call arrives, then this calls is lost and removed from the system. If , then the call is directed into service in one of the free channels.

1) If the control sequence is assumed to be metrically transitive and , then an ergodic theorem for a loss system can be stated if one utilizes the system with an infinite number of channels controlled by the same sequence. For this system there is a proper stationary sequence of queue lengths. The variable is the number of busy lines of the stationary system at the time of arrival of a call. If one denotes the index of this call by , then is defined as the number of lines busy with calls which arrived before the call at the time of arrival of the call with index , so that , . Then, if the probability of the event

is positive, the distribution of the sequence of queue lengths for a loss system will converge to the distribution of the stationary sequence as . The meaning of the event is very simple: it consists of "renewal" of the system: after it, only calls with index and higher will be found in the system.

The quoted theorem is a particular case of a more general result, obtaining using the so-called renewal method. If , , then for the stated conditions to be satisfied it suffices that

A result similar to the one given above will hold for the convergence as of the processes to the stationary process of queue lengths. Here, besides the listed conditions it is also required that the input process (the number of calls which have arrived up to time ) be a process with stationary increments.

2) If , , then Erlang's formula holds:

where , is the exponent of the distribution of and

If , , then the sequence is related to a simple homogeneous Markov chain with a finite number of states. In this case the probabilities

also can be found explicitly. In addition, if the distribution of is non-lattice and if , then

where is the exponent of the distribution of .

These results give conditions for the existence, and the explicit form, of the stationary loss probability, which is equal to

3) Stability theorems for loss systems are completely analogous to stability theorems for systems with an infinite number of channels. Suppose sequences , , have been given, controlling sequences, satisfying the following conditions:

A) there is a sequence for which the distributions are the limits as of the finite-dimensional distributions of . In addition, all the sequences named satisfy conditions (see, for example, part 1) guaranteeing the existence of stationary sequences of queue lengths. In order to have convergence of the distributions of these stationary sequences of queue lengths, denoted by and , two more conditions must be introduced:

B) as ;

C) the distributions of

are continuous at the point for all .

Under conditions A), B) and C) the finite-dimensional distributions of the sequences converge weakly to the distributions of .

4) Asymptotic methods of investigation of loss systems may also be effective for the study of systems with heavy traffic or with a large number of service channels.

The investigation of systems with heavy traffic is connected with results obtained under assumptions close to those considered in the asymptotic analysis of systems with an infinite number of channels. The study of systems with a large number of channels is conducted both by means of asymptotic analysis of explicit formulas, which become effective for large , and by studying the closeness of the distribution of to the distribution of the number of busy lines in the similar system with an infinite number of service channels.

For example, for systems with sequences , the stationary loss probability is equal to

where

and is the exponent of the distribution of . For large these relations are of little use in the search for the numerical values of . At the same time it turns out that as there are fairly simple formulas which establish the asymptotic behaviour of and which, consequently, can be used for the approximate calculation of the loss probability. Here a definite role is played by the parameter , which characterizes the ratio of the mean number of calls arriving in the system to the mean number of calls which can be served by the system in unit time. If , then the system is satisfactorily loaded; if , the system is overloaded. If as , for some , then . If as , then the given relation for is preserved as , provided . If, however, , then behaves asymptotically like , where the constant has been found explicitly. The asymptotic behaviour of in the case has also been found.

5) Single-server loss systems (when ) can be studied rather more completely. For example, let . The random variable is defined by

where . Then, in order that under any initial condition the limit

exists, it is necessary and sufficient that the highest common factor of the possible values of be 1. Here, . If is non-lattice, then

always exists.

Under the broader interpretation of the loss probability as the limit of the ratio , where is the number of unserved calls among the first arrivals, the conditions for the existence of will be broader. For example, for the case , the limit of always exists and is equal to .

For references see Queueing theory.