Difference between revisions of "Queue with refusals"
(Importing text file) |
m (link) |
||
Line 75: | Line 75: | ||
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076830/q076830104.png" /></td> </tr></table> | <table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076830/q076830104.png" /></td> </tr></table> | ||
− | exists, it is necessary and sufficient that the highest common factor of the possible values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076830/q076830105.png" /> be 1. Here, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076830/q076830106.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076830/q076830107.png" /> is non-lattice, then | + | exists, it is necessary and sufficient that the [[highest common factor]] of the possible values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076830/q076830105.png" /> be 1. Here, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076830/q076830106.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076830/q076830107.png" /> is non-lattice, then |
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076830/q076830108.png" /></td> </tr></table> | <table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076830/q076830108.png" /></td> </tr></table> |
Revision as of 21:53, 21 November 2014
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.
Queue with refusals. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Queue_with_refusals&oldid=18217