Queueing Theory 2. Nikolaos Limnios

      For the system S, we define an auxiliary system S₀ with input flow X₀ such that when the number of customers in the system becomes less than m a new customer immediately arrives in the system. Therefore, there are always customers for service in S₀. Other characteristics such as the initial state, the sequence

stochastic process

and a functional Φ are the same as for the system S. If in the system S the initial number of customers Q (0) < m, then the process X₀ has the jump m – Q(0) at zero instant. We determine an auxiliary service process Y(t) as the number of customers served in S₀ during (0, t). Since the flow Y is defined by the processes

and V and these processes do not depend on the input flow X at the system S, we conclude that X and Y are independent flows.

      We also need additional assumptions.

      CONDITION 1.1.– For the continuous-time case, Y is a strongly regenerative flow with the sequence

as points of regeneration.

      We call the regenerative flow Y strongly regenerative if the regeneration period

has the form

      [1.2]

      where

are independent random variables and

CONDITION 1.2.– For the discrete-time case, processes X and Y are regenerative aperiodic flows. As usually, aperiodicity means that the greatest common divisor (GCD)

      Then we may determine common points of regeneration

for both processes X and Y letting in the discrete-time case

[1.3]

      and in the continuous-time case

[1.4]

      LEMMA 1.1.– Let for the continuous-time (discrete-time) condition 1.1 (condition 1.2) be fulfilled. Then the sequence

consists of common regeneration points for X and Y and

[1.5]

      for the continuous-time case,

[1.6]

      for the discrete-time case.

PROOF.– Since the proof of [1.5] is almost the same as the proof of [1.6], we consider the discrete-time case only. Let

so that

Then

is a sequence of iid random variables and in accordance with Wald’s identity

(Feller 1971). Therefore, we need to prove the finiteness of Eν1. Denote by h₂(t) (h(t)) the mean number of renewals at time t for the renewal process

so that

      and

      Taking into account condition 1.2, we derive from Blackwell’s theorem (Thorisson 2000)

      Because of X and Y independence

      Since

w.p.1, then

w.p.1. Therefore, from Lebesgue s dominated convergence theorem, we obtain

■

      Later we consider both cases (discrete-time and continuous-time) together. We only have to take condition 1.2 instead of condition 1.1.

      Let

      Then

We define the traffic rate as follows:

[1.7]

      We think of λX and λγ as the arrival and service rate, respectively. Intuitively, it is clear that the number of customers in the system S is a stochastically bounded process if ρ < 1 and it is not the case if ρ ≥ 1. The main stability result of this chapter consists of the formal proof of this fact.

      We define the stochastic flow

as the number of customers served at the system S during time interval [0, t).

      CONDITION 1.3.– The following stochastic inequalities take place:

      Let Q(t) be the number of customers in the system S including the customers on the servers at time t so that

      CONDITION 1.4.– There are