4.5 Fundamental Queueing Model

We turn now to the examination of a queueing model which we shall call the fundamental birth-and-death model. This model includes features that are quite general, and as a result, a rather extensive class of well-known and oftenapplied queueing systems can be viewed as simply special cases of the fundamental birth-and-death model.

The model assumes a queueing system with m (m = 1, 2, 3, . . .) parallel identical servers and infinite system capacity, operating in the following fashion:

1. Whenever there are n users in the system (in queue plus in service) new users arrive at the system in a Poisson manner with a mean arrival rate of _n. expected arrivals per unit time.
2. Whenever there are n users in the system, service completions occur in a Poisson manner with a mean service rate of _n. per unit time.
3. The queueing system operates under a FCFS queue discipline.

It should be noted that _n here is defined as the combined rate of service of those servers which are busy when there are n users in the queueing system for any value of n. Note also that the rate of arrivals and the rate of service are permitted to depend on the number of users already in the system, a situation that is hardly unusual in actual life. We have already investigated two cases in Chapter 3 (see Sections 3.9.1 and 3.9.2) in which the arrival rate depended on the number of those already "in the system."

We can now go back to the review of the Poisson process (Section 2.12) and recognize that, if the number of users in the queueing system at a time t is given by N(t), we can write the following conditional probabilities for our fundamental model:

where o(t), in the terminology of Chapter 2, is a "collection of terms that go to zero faster than k t as t goes to zero (for any constant k)." For a small t, we can therefore ignore the o(t) terms and state that "if the queueing system contains n users at time t, then at time t + t, it will contain either n + 1 users with probability _nt or n - 1 users with probability _nt, or n users with probability 1 - (_n + _n) t." This statement is illustrated schematically in Figure 4.4.

We can now proceed, as follows. Given (4.14)-(4.17), assuming a small t and using the notation P_n(t) P[N(t) = n], we can write

        (4.18)

Rearranging terms and dividing by t, we have

     (4.19)

Letting t -> 0, in (4.19) we obtain the differential equation

    (4.20)

This equation makes sense intuitively: it states that the rate of change of the probability of having exactly n users in the queueing system is equal to the probability of exactly n + 1 or n - 1 users in the system at time t multiplied, respectively, by the rate at which users leave or enter the system (with n + 1 and n - 1 users present, respectively) minus the probability that there are n users present at time t multiplied by the rate at which the number of users present can either increase (_n) or decrease (_n). Note the similarities between the interpretation of (4.20) and the interpretation of (2.55) in our discussion of the Poisson process in Chapter 2.

While (4.20) holds for n = 1, 2, 3, . . . , we also require an equation for n = 0. By following a similar derivation or a similar logical argument as above, we can write

                       (4.21)

Equations (4.20) and (4.21) together define a set of differential equations, one for each possible value of n, for the queueing system analyzed here. Since, by assumption, the system capacity is infinite, so is the number of first-order differential equations.

A pictorial summary of the system of (4.20) and (4.21) is provided by Figure 4.5. The status of the queueing system is described by the state variable n (i.e., the total number of users in it). Thus, we shall say that the queueing system "is in state W' whenever there are n users in the system. Each state is represented by a circle in Figure 4.5 and the circles, in turn, are connected by directed links with the associated transition rate indicated on each link. Figure 4.5 is thus a typical state transition diagram for a queueing system. It is also clear from the diagram why our fundamental model is referred to as a birth-and-death model: in population applications of the model, the state n represents the "current population" and transitions out of state n can occur only to states n + 1 (a birth) and n - 1 (a death) at the rates _n and _n, respectively. Note also that, in this light the variants of the Poisson process described in Sections 3.9.1 and 3.9.2 (see Figures 3.35 and 3.36) can be considered "pure birth" processes.

Continuing with our analysis we can now examine the queueing system when it is in equilibrium (steady state). Under proper conditions, such an equilibrium will be reached after the system has been operating for some time. Equilibrium, in turn, implies that the state probabilities P_n(t) eventually become independent of t and approach a set of constant values P_n, n = 0, 1, 2,. . . , where 4

P_n P_n(t) = steady-state probability that there are n users in the queueing system

Since dP_n(t)/dt = 0 under these circumstances, in the steady state, (4.20) and (4.21) are then transformed to

The linear equations (4.24) and (4.25) are known as the equilibrium equations or the balance equations for our queueing system. Balance equations [as

well as transition-rate difrerential equations such as (4.20) and (4.21)l can be written by inspection directly from the state-transition diagram of queueing systems. For the balance equation (4.23), for instance, the argument goes like this. For any time t when the system is in equilibrium, the probability of observing a transition out of state n in the next t must be equal to the probability of observing a transition into state n. The former quantity is given by P_n (= the probability that at time t the system is in state n) times (_n + _n) t. Similarly, the probability of observing a transition into state n in the next t is given by .

Exercise 4.1
For birth-and-death queueing systems, another set of balance equations, even easier to solve than (4.22) and (4.23), can be obtained by (figuratively speaking) stationing ourselves at points such as those indicated by the dashed lines in Figure 4.5 and writing

₀ P₀ = ₁ P₁

₁ P₁ = ₂ P₂

and in general

_n P_n = _n+1 P_n+1    for n = 0,1,2,3,...      (4.24)

a. Argue the validity of (4.24).
b. Derive (4.24) using (4.22) and (4.23).

 

4 In Section 4.3 we used the more explicit notation PN(n) for the steady-state probability P[N = n]. From now on, for reasons of conciseness, we shall denote PN(n) by P_n. (Remember that N is the random variable indicating the total number of users in a queueing system under steadystate conditions.)