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 $ q _ {n} $( or $ q ( t) $) of busy lines at the time of arrival of the $ n $- th call (at time $ t $). However, in contrast to a system with an infinite number of channels here $ q _ {n} \leq m $, where $ m $ is the number of channels in the system. If $ q _ {n} = m $ when the $ n $- th call arrives, then this calls is lost and removed from the system. If $ q _ {n} < m $, then the call is directed into service in one of the free channels.

1) If the control sequence $ \{ \tau _ {j} ^ {e} , \tau _ {j} ^ {s} \} \in G _ {S} $ is assumed to be metrically transitive and $ {\mathsf E} \tau _ {j} ^ {s} < \infty $, 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 $ \{ Q ^ {k} \} $ of queue lengths. The variable $ Q ^ {0} $ 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 $ \gamma $, then $ Q _ {l} ^ {0} $ is defined as the number of lines busy with calls which arrived before the call $ \gamma $ at the time of arrival of the call with index $ \gamma + l $, so that $ Q _ {0} ^ {0} = Q ^ {0} $, $ Q _ {2} ^ {0} \leq Q ^ {0} $. Then, if the probability of the event

$$ A = \{ {Q _ {k} ^ {0} \leq m - 1 - k } : {k = 0 \dots m - 1 } \} $$

is positive, the distribution of the sequence $ \{ {q _ {n+} k } : {k \geq 0 } \} $ of queue lengths for a loss system will converge to the distribution of the stationary sequence $ \{ {q ^ {k} } : {k \geq 0 } \} $ as $ n \rightarrow \infty $. The meaning of the event $ A $ is very simple: it consists of "renewal" of the system: after it, only calls with index $ \gamma $ 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 $ \{ \tau _ {j} ^ {e} \} \in G _ {I} $, $ \{ \tau _ {j} ^ {s} \} \in G _ {I} $, then for the stated conditions to be satisfied it suffices that

$$ {\mathsf P} \{ \tau _ {j} ^ {e} \leq m \tau _ {j} ^ {e} \} \ > 0 ,\ {\mathsf E} \tau _ {j} ^ {s} < \infty . $$

A result similar to the one given above will hold for the convergence as $ t \rightarrow \infty $ of the processes $ \{ {q ( t + u ) } : {u \leq 0 } \} $ to the stationary process $ \{ {q ^ {s} ( u) } : {u \geq 0 } \} $ of queue lengths. Here, besides the listed conditions it is also required that the input process $ \{ e ( t) \} $( the number of calls which have arrived up to time $ t $) be a process with stationary increments.

2) If $ \{ \tau _ {j} ^ {e} \} \in E $, $ \{ \tau _ {j} ^ {s} \} \in G _ {I} $, then Erlang's formula holds:

$$ {\mathsf P} \{ q ^ {k} = j \} \ = {\mathsf P} \{ q ^ {s} ( u) = j \} = c \frac{( \alpha a ) ^ {j} }{j!} , $$

where $ a = {\mathsf E} \tau _ {j} ^ {s} $, $ \alpha $ is the exponent of the distribution of $ \tau _ {j} ^ {e} $ and

$$ c = \left [ \sum _ { j= } 0 ^ { m } \frac{( \alpha a ) ^ {j} }{j} \right ] ^ {-} 1 . $$

If $ \{ \tau _ {j} ^ {e} \} \in G _ {I} $, $ \{ \tau _ {j} ^ {s} \} \in E $, then the sequence $ q _ {n} $ is related to a simple homogeneous Markov chain with a finite number $ ( m + 1 ) $ of states. In this case the probabilities

$$ p _ {j} = {\mathsf P} \{ q ^ {0} = j \} = \ \lim\limits _ {t \rightarrow \infty } \ {\mathsf P} \{ q _ {n} = j \} $$

also can be found explicitly. In addition, if the distribution of $ \tau _ {j} ^ {e} $ is non-lattice and if $ {\mathsf E} \tau _ {j} ^ {e} < \infty $, then

$$ {\mathsf P} \{ q ^ {s} ( 0) = j \} \ = \lim\limits _ {t \rightarrow \infty } \ {\mathsf P} \{ q ( t) = j \} = \ \frac{p _ {k-} 1 }{k \alpha {\mathsf E} \tau _ {j} ^ {e} } , $$

where $ \alpha $ is the exponent of the distribution of $ \tau _ {j} ^ {e} $.

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

$$ {\mathsf P} \{ q ^ {0} = m \} \ = \lim\limits _ {t \rightarrow \infty } \ {\mathsf P} \{ q _ {n} = m \} . $$

3) Stability theorems for loss systems are completely analogous to stability theorems for systems with an infinite number of channels. Suppose sequences $ \{ \tau _ {j} ^ {(} n) e \} $, $ \{ \tau _ {j} ^ {(} n) s \} $, $ n = 1 , 2 \dots $ have been given, controlling sequences, satisfying the following conditions:

A) there is a sequence $ \{ \tau _ {j} ^ {e} , \tau _ {j} ^ {s} \} $ for which the distributions are the limits as $ n \rightarrow \infty $ of the finite-dimensional distributions of $ \{ \tau _ {j} ^ {(} n) e , \tau _ {j} ^ {(} n) s \} $. 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 $ \{ {q ^ {(} n) k } : {k \geq 0 } \} $ and $ \{ {q ^ {k} } : {k \geq 0 } \} $, two more conditions must be introduced:

B) $ {\mathsf E} \tau ^ {(} n) s \rightarrow {\mathsf E} \tau ^ {s} $ as $ n \rightarrow \infty $;

C) the distributions of

$$ \tau _ {-} j ^ {s} - \sum _ { k=- } j ^ { 0 } \tau _ {k} ^ {e} $$

are continuous at the point $ 0 $ for all $ j \geq 0 $.

Under conditions A), B) and C) the finite-dimensional distributions of the sequences $ \{ {q ^ {(} n) k } : {k \geq 0 } \} $ converge weakly to the distributions of $ \{ {q ^ {k} } : {k \geq 0 } \} $.

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 $ n $, and by studying the closeness of the distribution of $ q ^ {k} $ 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 $ \{ \tau _ {j} ^ {e} \} \in G _ {I} $, $ \{ \tau _ {j} ^ {s} \} \in E $ the stationary loss probability is equal to

$$ p _ {m} = \ \left ( \sum _ { j= } 0 ^ { m } A _ {j} \right ) ^ {-} 1 , $$

where

$$ A _ {0} = 1 ,\ \ A _ {j} = \ \left ( \begin{array}{c} m \\ j \end{array} \right ) \prod _ { k= } 1 ^ { j } \frac{1 - \phi ( k / m ) }{\phi ( k / m ) } ,\ \ \phi ( t) = {\mathsf E} e ^ {- t m \alpha \tau _ {j} ^ {e} } $$

and $ \alpha $ is the exponent of the distribution of $ \tau _ {j} ^ {s} $. For large $ m $ these relations are of little use in the search for the numerical values of $ p _ {m} $. At the same time it turns out that as $ m \rightarrow \infty $ there are fairly simple formulas which establish the asymptotic behaviour of $ p _ {m} $ and which, consequently, can be used for the approximate calculation of the loss probability. Here a definite role is played by the parameter $ \rho = {\mathsf E} m \alpha \tau _ {j} ^ {e} $, which characterizes the ratio of the mean number $ 1 / {\mathsf E} \tau _ {j} ^ {e} $ of calls arriving in the system to the mean number $ m / {\mathsf E} \tau _ {j} ^ {s} = m \alpha $ of calls which can be served by the system in unit time. If $ \rho < 1 $, then the system is satisfactorily loaded; if $ \rho > 1 $, the system is overloaded. If $ \rho < 1 - \epsilon $ as $ m \rightarrow \infty $, for some $ \epsilon > 0 $, then $ p _ {m} / ( 1 - \rho ) \rightarrow 1 $. If $ {\mathsf E} ( m \alpha \tau _ {j} ^ {e} ) ^ {2} < c < \infty $ as $ m \rightarrow \infty $, then the given relation for $ p _ {m} $ is preserved as $ \rho \rightarrow 1 $, provided $ ( 1 - \rho ) \sqrt m \rightarrow \infty $. If, however, $ ( 1 - \rho ) \sqrt m \rightarrow \textrm{ const } $, then $ p _ {m} $ behaves asymptotically like $ b / \sqrt m $, where the constant $ b $ has been found explicitly. The asymptotic behaviour of $ p _ {m} $ in the case $ ( 1 - \rho ) \sqrt m \rightarrow - \infty $ has also been found.

5) Single-server loss systems (when $ m = 1 $) can be studied rather more completely. For example, let $ \{ \tau _ {j} ^ {e} , \tau _ {j} ^ {s} \} \in G _ {I} $. The random variable $ \eta $ is defined by

$$ \eta = \max \{ {k } : {X _ {k} \geq \tau _ {1} ^ {s} } \} , $$

where $ X _ {k} = \tau _ {1} ^ {e} + \dots + \tau _ {k} ^ {e} $. Then, in order that under any initial condition the limit

$$ \lim\limits _ {t \rightarrow \infty } \ {\mathsf P} \{ q _ {m} = 1 \} = p _ {1} $$

exists, it is necessary and sufficient that the highest common factor of the possible values of $ \eta $ be 1. Here, $ p _ {1} = 1 - 1 / {\mathsf E} \eta $. If $ \tau ^ {e} $ is non-lattice, then

$$ \lim\limits _ {t \rightarrow \infty } \ {\mathsf P} \{ q ( t) = 1 \} \ = \frac{ {\mathsf E} \tau ^ {s} }{ {\mathsf E} \tau ^ {e} {\mathsf E} \eta } $$

always exists.

Under the broader interpretation of the loss probability as the limit of the ratio $ \pi _ {n} = r _ {n} / n $, where $ r _ {n} $ is the number of unserved calls among the first $ n $ arrivals, the conditions for the existence of $ \lim\limits _ {n} \pi _ {n} $ will be broader. For example, for the case $ \{ \tau _ {j} ^ {e} , \tau _ {j} ^ {s} \} \in G _ {I} $, the limit of $ \pi _ {n} $ always exists and is equal to $ 1 - 1 / {\mathsf E} \eta $.

For references see Queueing theory.