Section 11.2. Birth-and-Death Process

11.2. Birth-and-Death Process

If a packet arrives at or leaves from a queueing node of a computer network, the state of the node's buffer changes, and thus the state of the queue changes as well. In such cases, as discussed in Appendix C, if the system can be expressed by a Markov process , the activity of the processin terms of the number of packetscan be depicted by a state machine known as the Markov chain . A particular instance of a Markov chain is the birth-and-death process .

In a birth-and-death process , any given state i can connect only to state i - 1 with rate µ _i or to state i + 1 with rate » _i , as shown in Figure 11.3. In general, if A(t) and D(t) are the total number of arriving packets and the total number of departing packets, respectively, up to given time t , the total number of packets in the system at time t is described by K(t) = A(t) - D(t) . With this analysis, A(t) is the total number of births , and D(t) is the total number of deaths . Therefore, K(t) can be viewed as a birth-and-death process representing the cumulative number of packets in a first-come, first- served service discipline.

Figure 11.3. A general birth-and-death process and its transitions

Let p _i be the probability that the chain is in state i . The balance equation for the steady-state probability at state 0 denoted by p is related to the one for State 1 denoted by p ₁ as

Equation 11.6

Similarly, for state 1, the balance equation is

Equation 11.7

and by using Equation (11.6), we derive the balance equation of state 1 as » ₁ p ₁ - µ ₂ p ₂ = 0. This development can continue up to state i - 1, where the balance equation can be derived as

Equation 11.8

We define as state i utilization . Thus, we can express the balance Equation (11.8) by a generic form as

Equation 11.9

If we apply Equation (11.9) for every state, starting with p ₁ = ₁ p up to p _i = _i p _{i -1} , and combine all the equations, we obtain a generic equation

Equation 11.10

Since the sum of all the probabilities is always equal to 1, as , pi in Equation (11.10) can also be obtained from

Equation 11.11

The significance of this result is that a state probability p _i is expressed in terms of state utilizations , ₁ , ₂ ,..., _i only.