Queue input stream of calls

A random process given in some form or other and describing the appearance of calls in the queue. The input stream is usually defined by random sequences $ \{ \tau _ {j} ^ {e} , \nu _ {j} ^ {e} \} $, where $ \tau _ {j} ^ {e} $, $ j = 1 , 2 \dots $ are the time intervals between the arrivals in the system of the batches of requests of sizes $ \nu _ {1} ^ {e} \geq 1 , \nu _ {2} ^ {e} \geq 1 \dots $ respectively. If $ \nu _ {j} ^ {e} \equiv 1 $, the stream is called single. Equivalently, the input stream can be given by a point process $ \{ {e ( t) } : {t \geq 0 } \} $, giving the number of calls arriving in the system up to time $ t $. It can be assumed, for the sake of being specific, that $ e ( t) = e ( t - 0 ) $.

The most common requirement usually placed on the input stream is stationarity. This condition can be of two kinds: either stationarity in the narrow sense is required of the sequence $ \{ \tau _ {j} ^ {e} , \nu _ {j} ^ {e} \} $( denoted by $ \{ \tau _ {j} ^ {e} , \nu _ {j} ^ {e} \} \in G _ {S} $), or it is required that $ e ( t) $ be a process with increments that are stationary in the narrow sense (denoted by $ \{ e ( t) \} \in G _ {IS} $). These requirements, in general, do not coincide (cf. Stationary stochastic process).

The intensity of a stationary stream is the number

$$ \mu = \lim\limits _ {t \rightarrow \infty } \ \frac{ {\mathsf E} ( e ( t) - e ( 0) ) }{t} . $$

If $ \{ e ( t) \} \in G _ {IS} $, then

$$ \mu = {\mathsf E} ( e ( t + 1 ) - e ( t) ) = \ {\mathsf E} ( e ( 1) - e ( 0) ) , $$

so that $ \mu $ is equal to the mean number of calls which arrive in the system in unit time. If the sequence $ \{ \tau _ {j} ^ {e} \} $ is stationary and ergodic and if $ \{ \nu _ {j} ^ {e} \} \in G _ {I} $, then

$$ \mu = \ \frac{ {\mathsf E} \nu _ {j} ^ {e} }{ {\mathsf E} \tau _ {j} ^ {e} } . $$

In other cases the relation between $ \mu $ and the distribution of the sequence $ \{ \tau _ {j} ^ {e} , \nu _ {j} ^ {e} \} \in G _ {S} $ can be more complicated.

Let there be given a process $ \{ e ( t) \} \in G _ {IS} $ with intensity $ \mu $ and initial value $ e ( 0) = 0 $. Closely associated with the number $ \mu $ is another parameter of the input stream, defined by

$$ \alpha = \lim\limits _ {t \rightarrow 0 } \ \frac{ {\mathsf P} ( e ( t) \geq 1 ) }{t} . $$

This limit always exists and $ \alpha \leq \mu $. If $ \mu < \infty $, then $ \alpha = \mu $ if and only if the input stream is single.

In studying the properties of the input stream one often uses the so-called Palm functions

$$ \tag{1 } \phi _ {k} ( t) = \ \lim\limits _ {\tau \rightarrow 0 } \ \frac{ {\mathsf P} \{ e ( t + \tau ) - e ( \tau ) = k , e ( \tau ) \geq 1 \} }{ {\mathsf P} \{ e ( \tau ) \geq 1 \} } , $$

$$ k = 0 , 1 ,\dots $$

(here $ e ( 0) = 0 $), which have the meaning of the conditional probabilities that $ k $ calls arrive in the interval $ ( 0 , t ) $ under the condition that a call has arrived at time $ 0 $. The function $ \phi _ {k} ( t) $ is related to the distribution of $ e ( t) $ by:

$$ {\mathsf P} \{ e ( t) = 0 \} = 1 - \lambda \int\limits _ { 0 } ^ { t } \phi _ {0} ( u) d u , $$

$$ {\mathsf P} \{ e ( t) = k \} = \lambda \int\limits _ { 0 } ^ { t } [ \phi _ {k-} 1 ( u) - \phi _ {k} ( u) ] d u . $$

If $ \{ \tau _ {j} ^ {e} \} \in G _ {I} $, then

$$ \phi _ {0} ( t) = {\mathsf P} \{ \tau _ {j} ^ {e} \geq t \} , $$

$$ \sum _ { j= } 0 ^ { k } \phi _ {j} ( t) = {\mathsf P} \{ \tau _ {1} ^ {e} + \dots + \tau _ {k+} 1 ^ {e} \geq t \} . $$

A significant role in queueing theory is played by the so-called simplest, or Poisson, input stream — a stationary input stream for which $ \nu _ {j} ^ {e} = 1 $, $ \{ \tau _ {j} ^ {e} \} \in E $. In order to define the simplest stream in terms of $ e ( t) $ it is required that $ \{ e ( t) \} $ be Poisson (cf. Poisson process). The increments of this process in disjoint time intervals are independent and have Poisson distributions with parameters proportional to the length of the intervals.

Non-homogeneous Poisson streams also find broad application (particularly in telephony); these are characterized as processes $ e ( t) $ with independent increments distributed by the Poisson law:

$$ {\mathsf P} \{ e ( t + u ) - e ( t) = k \} = $$

$$ = \ \frac{e ^ {- A ( t + u ) - A ( t) } }{k!} ( A ( t + u ) - A ( t) ) ^ {k} , $$

where $ A ( t) $ is the drift function of the process (in the homogeneous case $ A ( t) = \alpha t $).

The special role of Poisson processes in queueing theory is explained in many respects by the fundamental limit theorem for input streams, which asserts that under broad assumptions the sum of a large number of arbitrary independent stationary input streams of low intensity converges to a Poisson process. The frequent use of the assumption that the input flow is Poisson rests on the fact that in many applications real input streams are formed in precisely that way (for example, the stream of calls arriving at a telephone exchange is the sum of the weak streams originating from the individual subscribers).

Below, the fundamental limit theorem is given in two forms. The first relates to the sum of arbitrary (non-stationary) input streams.

Suppose one is given increasing sets of independent process $ e _ {1n} ( t) \dots e _ {nn} ( t) $, $ n = 1 , 2 \dots $ depending on $ n $( that is, a triangular array), and the following notation:

$$ A _ {n} ( t , u ) = \ \sum _ { r= } 1 ^ { n } {\mathsf P} \{ e _ {rn} ( t) - e _ {rn} ( u) \geq 1 \} , $$

$$ B _ {n} ( t , u ) = \sum _ { r= } 1 ^ { n } {\mathsf P} \{ e _ {rn} ( t) - e _ {rn} ( u) \geq 2 \} . $$

In addition, for any fixed $ t > 0 $, let

$$ {\mathsf P} \{ e _ {rn} ( t) - e _ {rn} ( 0) \geq 1 \} \rightarrow 0 , $$

as $ n \rightarrow \infty $, uniformly in $ r $( this is the condition of low intensity of the streams $ e _ {rn} ( t) $). Then in order that the finite-dimensional distributions of the process

$$ e _ {n} ( t) = \sum _ { r= } 1 ^ { n } e _ {rn} ( t) $$

converge to the distributions of a Poisson process with drift function $ A ( t) $, it is necessary and sufficient that as $ n \rightarrow \infty $,

$$ A _ {n} ( t , u ) \rightarrow A ( t) - A ( u) ,\ B _ {n} ( t , u ) \rightarrow 0 . $$

If in the triangular array under discussion the processes $ e _ {rn} ( t) \in G _ {IS} $ and are single, then the following result also holds. Let $ u _ {rn} $ be the intensity of $ e _ {rn} ( t) $ and, as $ n \rightarrow \infty $, let

$$ \sum _ { r= } 1 ^ { n } \mu _ {rn} \rightarrow \alpha . $$

Then for the convergence of the finite-dimensional distributions of the processes $ e _ {n} ( t) $ to a distribution of a Poisson process $ e ( t) $ with parameter $ \alpha $ it is necessary and sufficient that for each $ t $,

$$ \tag{2 } \sum _ { r= } 1 ^ { n } \mu _ {rn} \int\limits _ { 0 } ^ { t } \phi _ {0} ^ {(} r) ( u) d u \rightarrow \alpha t , $$

where $ \phi _ {0} ^ {r} ( u) $ is the Palm function for the process $ e _ {rn} ( t) $, defined by (1). If, as $ n \rightarrow \infty $,

$$ ( 1 - \phi _ {0} ^ {(} r) ( t) ) \rightarrow 0 , $$

uniformly in $ r $, then (2) is obviously satisfied.

For references see Queueing theory.