A Markov chain is a stochastic process in a countable state space (i.e., in discrete space, S= {0,1,2, . . .}) with the special property that the probability of being at statej at a time instant depends only on the statei it was at in the previous time instant, not on any time instant before that; this is commonly known as the memoryless property. Time can be de- scribed either in discrete time or continuous time; these then correspond to the discrete time Markov chain, and the continuous time Markov chain, respectively. We will consider here the continuous time Markov chain, for which the memoryless property can be stated in terms of transition probability as follows:
pij(t)=Pr{x(t+u)=j|x(u)=i}, t>0
This is interpreted as follows: if we are at stateiat timeu, then for any small positive time movementt sinceu, the transition probability for timet,pij(t), to be at statejdepends only on being at stateiat timeu, nothing before that. Now, if we consider all the possible states to which transition is possible given that the system is at statei, we can write
j∈S
pij(t)=1, for eachi. (B.12.1)
The initial system at start time,t=0, is described bypii(0)=1; otherwise,pij=0, forj=i.
If we now consider the steady-state system, i.e., to describe the system that is irrespective of time, then it is more meaningful to consider the steady-state transition rateqijfor going from stateitoj. It can be shown (by using limits) that Eq. (B.12.1) translates to the following in a steady-state:
j∈S
qij=0, for eachi. (B.12.2)
Now, the steady state probability of being at particular statej, to be denoted bypj(note: the difference frompij(t)), is related to the transition rateqij by the following set of equations [481]:
p0q00+p1q10+p2q20+ ã ã ã =0 p0q01+p1q11+p2q21+ ã ã ã =0 p0q02+p1q12+p2q22+ ã ã ã =0 . . .
(B.12.3)
This set is known as the set of balance equations. It may also be noted that the sum of the steady-state probabilities,pj, must add to 1, i.e.,
p0+p1+p2+ ã ã ã =1. (B.12.4) For many well-known systems,qij is known or can be derived; thus, by solving Eq. (B.12.3) along with Eq. (B.12.4), we can determine the steady-state probabilitypj.
B.12.1 Birth-and-Death Process
The birth-and-death process is a specialized continuous-time Markov chain. This name has stuck on since this model was first used for population birth and death modeling; in a net- working system, a better name would be to call it the arrival-and-service process. In this special Markov chain,qij is measurable only to its immediate one-step neighbors, i.e., going fromitoi+1or toi−1; the transition rate is zero, otherwise. Typically, we write going from itoi+1asλi(“birth” or arrival rate) and fromitoi−1asμi(“death” or service rate). Thus, the transition rate can be summarized as follows:
qi,i+1=λi, i=0,1,2, . . .
qi,i−1=μi, i=1,2, . . . (B.12.5)
qi,j=0, forj=i+1,i−1,i.
Due to relation (B.12.2) and (B.12.5), we can see that for the birth-and-death process, we can write:
qii= −(λi+μi), forinot in a boundary state.
Rewriting Eq. (B.12.3) with this knowledge, we have
−p0λ0+p1μ1 =0 p0λ0−p1(λ1+μ1)+p2μ2=0 p1λ1−p1(λ2+μ2)+p3μ3=0 . . .
(B.12.6)
The above balance equations for the birth-and-death process can be easily depicted pictorially by considering each stateiand observing the balance maintained by rates going into a state and out of that state as shown below:
For example, consider state1to which from state 0 where steady-state probability isp0, rate λ0is going in; similarly, from state 2 where steady-state probability isp2, rateμ2is going into state 1; now, from state 1 where steady-state probability isp1, two ratesλ1andμ1are going out. Thus,p0λ0+p2μ2=p1(λ1+μ1); this is the second equation in (B.12.6). Similarly, others can be determined. The set of equations given by Eq. (B.12.6) can be analytically solved by substitution and elimination to obtain:
p1=λ0
μ1p0, p2= λ1
μ2p1= λ0λ1 μ1μ2p0, . . . Generalizing, we have
pj=λ0λ1ã ã ãλj−1
μ1μ2ã ã ãμj p0, j≥1. (B.12.7) Now, plugging inpj to Eq. (B.12.4), we can obtainp0, and thus allpjs; this assumes that the summation converges, i.e., the following condition is satisfied:
j
λ0λ1ã ã ãλj−1 μ1μ2ã ã ãμj <∞.
B.12.2 M/M/1 System
AnM/M/1 system is a special case of the birth-and-death process. In this system, transition rate for birth (arrival) is the same regardless of the state; similarly, the transition rate for death (service) is the same regardless of the state.
qi,i+1=λi=λ, i=0,1,2, . . . qi,i−1=μi=μ, i=1,2, . . .
qi,j =0, forj=i+1,i−1,i.
(B.12.8)
This system is stable if the arrival rate,λ, is smaller than the service rate,μ. Here, the steady- state probabilitypj, given in Eq. (B.12.7), reduces to:
pj= λ
μ j
p0, j=1,2, . . .
Accounting for Eq. (B.12.4), we can write pj=
1− λ
μ λ
μ j
, j=1,2, . . .
An advantage of knowing the steady-state probability is that the average number in a system can be determined as follows:
N=∞
j=0
jpj= λ
μ−λ. (B.12.9)
(We have shown above the result of the summation, without showing the detailed deriva- tion.) A well known result, known as Little’s law, says that the average number in a system and the average delay is related as follows:N=λ×T. Thus, we can write the average delay as:
T = 1
μ−λ. (B.12.10)
Consider now a network link with bandwidthCand average packet sizeκ, the service rate becomesμ=C/κ. If we denote utilization byρ=λ/μ=λ×κ/C, then we can rewrite the average delay in a network link as
T = 1
C/κ−λ= κ
C(1−ρ). (B.12.11)
B.12.3 Trunk Reservation Model
The trunk reservation model presented in Section 11.8.3 is also a specialized case of the birth- and-death process. In this case, the total number of state is finite, which is the total number of circuits on a link, denoted byccircuits; thus,S= {0,1, . . . ,c}. Ifris the trunk reservation parameter, then the arrival rate up to statec−ris to allow both direct and alternate routed arrival, i.e,λdirect+λalternate, and after the statec−ris reached, only direct routed calls are allowed, i.e. the arrival rate isλdirect. Furthermore, in a circuit-switched environment, the ser- vice rate,qi,i−1, is defined by the number circuits being currently occupied by calls assuming the average call duration to be1/μ, i.e., the per-circuit service rate to beμ. Thus, we can write
qi,i+1=λdirect+λalternate, i=0,1,2, . . . ,c−r−1 qi,i+1=λdirect, i=c−r, . . . ,c−1 qi,i−1=iμ, i=1,2, . . . ,c
(B.12.12)
Now consider the discussion in Section 11.8.3. In term of offered load,A and a described there, this means that
A=(λdirect+λalternate)/μ, i=0,1, . . . ,c−r−1
a=λdirect/μ, i=c−r, . . . ,c−1. (B.12.13)
Thus, the result shown in Eq. (11.8.22a) can be derived from Eq. (B.12.7) using Eq. (B.12.12) and Eq. (B.12.13).