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:
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 Pn(t) P[N(t) = n], we can write
Rearranging terms and dividing by t, we have
Letting t -> 0, in (4.19) we obtain the differential equation
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
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 Pn(t) eventually become independent of t and approach a set of constant values Pn, n = 0, 1, 2,. . . , where 4
Since dPn(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