124 Delay Models in Data Networks Chap.3 However,N,T,No,and W cannot be specified further unless we know some- thing more about the statistics of the system.Given these statistics,we will be able to derive the steady-state probabilities Pn=Probability of n customers in the system,n=0,1,... From these probabilities,we can get n=0 and,using Little's Theorem, T- N Similar formulas exist for No and W.Appendix B provides a summary of the results for the M/M/1 system and the other major systems analyzed later. The analysis of the M/M/1 system as well as several other related systems, such as the M/M/m or M/M/oo systems,is based on the theory of Markov chains summarized in Appendix A.An alternative approach is to use simple graphical arguments based on the concept of mean residual time introduced in section 3.5. This approach does not require that the service times are exponentially distributed, i.e.,it applies to the M/G/1 system.The price paid for this generality is that the characterization of the steady-state probabilities is less convenient and simple than for the M/M/1 system.The reader wishing to circumvent the Markov chain analysis may start directly with the M/G/1 system in section 3.5 after a reading of the preliminary facts on the Poisson process given in subsections 3.3.1 and 3.3.2. 3.3.1 Main Results A stochastic process {A(t)t >0}taking nonnegative integer values is said to be a Poisson process with rate A if 1.A(t)is a counting process that represents the total number of arrivals that have occurred from 0 to time t,i.e.,A(0)=0,and for s<t,A(t)-A(s) equals the number of arrivals in the interval(s,t. 2.The numbers of arrivals that occur in disjoint time intervals are independent
Delay Models in Data Networks However, N, T, NQ, and W cannot be specified further unless we know something more about the statistics of the system. Given these statistics, we will be able to derive the steady-state probabilities p, = Probability of n customers in the system, n = 0, 1,... From these probabilities, we can get 00 N= npn n=0 and, using Little's Theorem, N T=- Similar formulas exist for NQ and W. Appendix B provides a summary of the results for the M/M/1 system and the other major systems analyzed later. The analysis of the M/M/1 system as well as several other related systems, such as the M/M/m or M/M/oo systems, is based on the theory of Markov chains summarized in Appendix A. An alternative approach is to use simple graphical arguments based on the concept of mean residual time introduced in section 3.5. This approach does not require that the service times are exponentially distributed, i.e., it applies to the M/G/1 system. The price paid for this generality is that the characterization of the steady-state probabilities is less convenient and simple than for the M/M/1 system. The reader wishing to circumvent the Markov chain analysis may start directly with the M/G/1 system in section 3.5 after a reading of the preliminary facts on the Poisson process given in subsections 3.3.1 and 3.3.2. 3.3.1 Main Results A stochastic process { A(t) I t > 0} taking nonnegative integer values is said to be a Poisson process with rate A if 1. A(t) is a counting process that represents the total number of arrivals that have occurred from 0 to time t, i.e., A(O) = 0, and for s < t, A(t) - A(s) equals the number of arrivals in the interval (s, t]. 2. The numbers of arrivals that occur in disjoint time intervals are independent. Chap. 3
Sec.3.3 The M/M/1 Queueing System 125 3.The number of arrivals in any interval of length r is Poisson distributed with parameter Ar.That is,for all t,r>0, P4+-4=m=6r”,n=0.1, (3.10) We list some of the properties of the Poisson process that will be of interest: (a)Interarrival times are independent and exponentially distributed with parameter A,i.e.,if tn denotes the time of the nth arrival,the intervals Tn=tn+1-tn have the probability distribution P{n≤s}=1-e-A,8≥0 (3.11) and are mutually independent.(The corresponding probability density function is p(n)=Ae-Ar.The mean and variance of in are 1/A and 1/λ2，respectively.) (b)For every t≥0and6≥0 P{A(t+6)-A(t)=0}=1-λ6+o(6) (3.12) P{A(t+6)-A(t)=1}=λ6+o(6) (3.13) P{A(t+6)-A(t)≥2}=o(6) (3.14) where we generically denote by o(6)a function of 6 such that o(6) 6 =0 These equations can be verified using Eq.(3.10)(see Prob.3.10). Note that if the arrivals in n disjoint intervals are independent and Poisson distributed with parameters Ar,...,Arn,then the number of arrivals in the union of the intervals is Poisson distributed with parameter A(++n).This follows from properties of the Poisson distribution and guarantees that the requirement of Eq.(3.10)is consistent with the independence requirement in the definition of the Poisson process (see Prob.3.10).Another fact that we will frequently use is that if two or more independent Poisson processes A1,...,Ak are merged into a single process A =A1+A2+...+Ak,then the latter process is Poisson with a rate equal to the sum of the rates of its components(see Prob.3.10). Our assumption regarding the service process is that the customer service times have an exponential distribution with parameter u,i.e.,if sn is the service time of the nth customer, P{sn≤8}=1-e-us,8≥0
Sec. 3.3 The M/M/1 Queueing System 3. The number of arrivals in any interval of length r is Poisson distributed with parameter Ar. That is, for all t, r > 0, P {A(t + r) - A(t) = n} = e- , n = 0, 1,... (3.10) We list some of the properties of the Poisson process that will be of interest: (a) Interarrival times are independent and exponentially distributed with parameter A, i.e., if tn denotes the time of the nth arrival, the intervals rn = tn+l - tn have the probability distribution P {r, 5s}l =1 - eA , s > 0 (3.11) and are mutually independent. (The corresponding probability density function is p(Tn) = Ae- r . The mean and variance of rn are 1/A and 1/A2 , respectively.) (b) For every t > 0 and 6 > 0 P {A(t + 6) - A(t) = 0} = 1 - A6 + o(6) (3.12) P {A(t + 6) - A(t) = 1} = A6 + o(6) (3.13) P {A(t + 6) - A(t) > 2} = o(6) (3.14) where we generically denote by o(6) a function of 6 such that lim o(6) = 0 6-o 6 These equations can be verified using Eq. (3.10) (see Prob. 3.10). Note that if the arrivals in n disjoint intervals are independent and Poisson distributed with parameters Arl,..., Ar, then the number of arrivals in the union of the intervals is Poisson distributed with parameter A(rl + ---+ Tr). This follows from properties of the Poisson distribution and guarantees that the requirement of Eq. (3.10) is consistent with the independence requirement in the definition of the Poisson process (see Prob. 3.10). Another fact that we will frequently use is that if two or more independent Poisson processes A 1 ,..., Ak are merged into a single process A = A1 + A 2 + - --+ Ak, then the latter process is Poisson with a rate equal to the sum of the rates of its components (see Prob. 3.10). Our assumption regarding the service process is that the customer service times have an exponential distribution with parameter p, i.e., if sn is the service time of the nth customer, P {sn s} = 1 - e- e" 8 , s > 0
126 Delay Models in Data Networks Chap.3 (The probability density function of s is p(n)=ue-n,and its mean and vari- ance are 1/u and 1/u2,respectively.)Furthermore,the service times sn are mutu- ally independent and also independent of all interarrival times.The parameter u is called the service rate,and represents the rate (in customers served per unit time) at which the server operates when busy. An important fact regarding the exponential distribution is its memoryless, character,which can be expressed as P[tn>r+tTn>t)=Pitn>r),for r,t0 P[on >r+tlsn>t)=P[8n >r},for r,t 20 for the interarrival and service times rn and sn,respectively.This means that the additional time needed to complete a customer's service in progress is independent of when the service started.Similarly,the time up to the next arrival is independent of when the previous arrival occurred.Verification of the memoryless property follows from the calculation P≥+>-吉--6=P> The memoryless property together with our earlier independence assumptions on interarrival and service times imply that once we know the number N(t)of customers in the system at time t,the times at which customers will arrive or complete service in the future are independent of the arrival times of the customers presently in the system and of how much service the customer currently in service (if any)has already received.This means that {N(t)t>0}is a continuous-time Markov chain. We could analyze the process N(t)in terms of continuous-time Markov chain methodology;most of the queueing literature follows this line of analysis.It is sufficient,however,for our purposes in this section to use the simpler theory of discrete-time Markov chains(briefly summarized in Appendix A). Let us focus attention at the times 0,6,26,…,k6,.… where 6 is a small positive number.We denote N=Number of customers in the system at time k6 Since N&N(k6)and,as discussed,N(t)is a continuous-time Markov chain, we see that {Nlk=0,1,...}is a discrete-time Markoy chain.Let Pi;denote the corresponding transition probabilities Pij P(Nk+1=jlNk=i)
Delay Models in Data Networks (The probability density function of s, is p(s,) = pe- Ps , and its mean and variance are 1/pu and 1/p•2, respectively.) Furthermore, the service times s, are mutually independent and also independent of all interarrival times. The parameter p is called the service rate, and represents the rate (in customers served per unit time) at which the server operates when busy. An important fact regarding the exponential distribution is its memoryless, character, which can be expressed as P{rn > r+tn > t} = P{r > r}, for r,t >O P {s > r+tlsn > t} = P {s, > r}, for r,t >O for the interarrival and service times rn and s8, respectively. This means that the additional time needed to complete a customer's service in progress is independent of when the service started. Similarly, the time up to the next arrival is independent of when the previous arrival occurred. Verification of the memoryless property follows from the calculation P {rn > r + t} > t} = r e-_ = P {r. > r} P {rn > t} e-xt The memoryless property together with our earlier independence assumptions on interarrival and service times imply that once we know the number N(t) of customers in the system at time t, the times at which customers will arrive or complete service in the future are independent of the arrival times of the customers presently in the system and of how much service the customer currently in service (if any) has already received. This means that {N(t)|t > 0} is a continuous-time Markov chain. We could analyze the process N(t) in terms of continuous-time Markov chain methodology; most of the queueing literature follows this line of analysis. It is sufficient, however, for our purposes in this section to use the simpler theory of discrete-time Markov chains (briefly summarized in Appendix A). Let us focus attention at the times 0, 6, 26,...,kb,... where 6 is a small positive number. We denote Nk = Number of customers in the system at time k6 Since Nk = N(k6) and, as discussed, N(t) is a continuous-time Markov chain, we see that {Nklk = 0,1,...} is a discrete-time Markov chain. Let P,, denote the corresponding transition probabilities Pij = P {Nk+l = jlNk = i Chap. 3
Sec.3.3 The M/M/1 Queueing System 127 1-入6 1-λ6-u6 1-6-6 1-6-5 1-8-u8 8…8 Flgure 3.5 Discrete-time Markov chain for the M/M/1 system.The state n corresponds to n customers in the system.Transition probabilities shown are correct up to an o(6)term. Note that Pij depends on 6,but to keep notation simple,we do not show this dependence.By using Egs.(3.12)through (3.14),we have Po=1-λ6+o(6) (3.15)） P=1-λ6-46+o(6), 21 (3.16) P,+1=A6+o(6), i20 (3.17） P,-1=46+o(6), 21 (3.18) P=o(6), i and j卡i,t+1,t-1 To see how these equations are verified,note that,when at a state i>1, the probabilities of 0 arrivals and 0 departures in an intervalI=(k6,(k+1)6]is (e-A6)(e45);this is because the number of arrivals and the number of departures are Poisson distributed and independent of each other.Expanding this in a power series in 6, P[0 customers arrive and 0 depart in Ik}=1-A6-46+o(6) (3.19) Similarly,we have that P(0 customers arrive and 1 departs in Ik}=u+o(5) P{1 customer arrives and 0 depart in I}=A6+o(6) These probalities add up to one plus o(6).Thus,the probability of more than one arrival or departure is negligible for 6 small.This means that,for i>1,pii,which is the probability of an equal number of arrivals and departures in Ik,is within o(6)of the value in Eq.(3.19);this verifies Eq.(3.16).Equations (3.15),(3.17), and (3.18)are verified in the same way. The state transition diagram for the Markov chain {N}is shown in Fig.3.5 where we have omitted the terms o(). Consider now the steady-state probabilities Pn lim P(Nk =n} k+00 =lim P(N(t)=n}
Sec. 3.3 The M/M/1 Queueing System Figure 3.5 Discrete-time Markov chain for the M/M/1 system. The state n corresponds to n customers in the system. Transition probabilities shown are correct up to an o(6) term. Note that Pij depends on 6, but to keep notation simple, we do not show this dependence. By using Eqs. (3.12) through (3.14), we have Poo= 1 - A6 + o(6) (3.15) Pii= 1 - A6 - p6 + o(6), i > 1 (3.16) Pii+1= A6 + o(6), i > 0 (3.17) Pi,i-1-= p6 + o(6), i > 1 (3.18) Pii= o(6), i and j Z i, i + 1, i - 1 To see how these equations are verified, note that, when at a state i > 1, the probabilities of 0 arrivals and 0 departures in an interval Ik = (kb, (k + 1)6] is (e-AS)(e-'6); this is because the number of arrivals and the number of departures are Poisson distributed and independent of each other. Expanding this in a power series in 6, P{0 customers arrive and 0 depart in Ik} = 1 - Ab - p6 + o(6) (3.19) Similarly, we have that P{0 customers arrive and 1 departs in Ik) = p6 + o(6) P{1 customer arrives and 0 depart in Ik} = A6 + 0(6) These probalities add up to one plus o(6). Thus, the probability of more than one arrival or departure is negligible for 6 small. This means that, for i > 1, pii, which is the probability of an equal number of arrivals and departures in Ik, is within o(6) of the value in Eq. (3.19); this verifies Eq. (3.16). Equations (3.15), (3.17), and (3.18) are verified in the same way. The state transition diagram for the Markov chain {Nk} is shown in Fig. 3.5 where we have omitted the terms o(6). Consider now the steady-state probabilities Pn= lim P {Nk = n} k- oo = lim P {N(t) = n} t-0oo 1- ? I-I-I-. 1- M-rs 1 -?,8 -/Z6 1-u6- rs
128 Delay Models in Data Networks Chap.3 Note that for any k>1,n>0,during the time from 6 to k6,the total number of transitions from state n to n+1 must differ from the total number of transitions from n+1 to n by at most 1.Thus,in steady state,the probability that the system is in state n and makes a transition to n+1 at the next transition instant is the same as the probability that the system is in state n+1 and makes a transition to n,i.e., pPn6+o(6)=pm+1u6+o6) (3.20) (These equations are called global balance equations corresponding to the set of states (0,1,...,n}and {n+1,n+2,...}.See Appendix A for a more general statement of these equations,and for an interpretation that parallels the argument given above to derive Eq.(3.20).)Since pn is independent of 6,by taking the limit inEq.(3.20)as6→0，we obtain pn+1=Ppn,n=0,1,. where 入 p= It follows that Pn+1=pm+1po,n=0,1,… (3.21) If p<1(service rate exceeds arrival rate),the probabilities pn are all positive and add up to unity,so 1=2=rw="。 0 (3.22) n=0 n=0 This equation,together with Eq.(3.21),gives finally Pm=p(1-p),n=0,1,… (3.23) We can now calculate the average number of customers in the system in steady state: N=巴Ewe=2=2nH-月 +00 =-是gt=t-鼎（运） 台0 n=0 n=0 =pI-p品()=I-a2 and,finally,using p=A/u (3.24
Delay Models in Data Networks Note that for any k 2 1, n > 0, during the time from 6 to k6, the total number of transitions from state n to n + 1 must differ from the total number of transitions from n+l to n by at most 1. Thus, in steady state, the probability that the system is in state n and makes a transition to n + 1 at the next transition instant is the same as the probability that the system is in state n + 1 and makes a transition to n, i.e., pnA6 + o(6) = pn+l1A6 + 0(6) (3.20) (These equations are called global balance equations corresponding to the set of states {0,1,...,n} and {n+ 1,n+2,...}. See Appendix A for a more general statement of these equations, and for an interpretation that parallels the argument given above to derive Eq. (3.20).) Since pn is independent of 6, by taking the limit in Eq. (3.20) as 6 -* 0, we obtain Pn+I=PPn, n=0,1,... where A It follows that Pn+l = P+l P0, n = 0, 1,... (3.21) If p < 1 (service rate exceeds arrival rate), the probabilities pn are all positive and add up to unity, so 00 00 1= Pn = p"p = P o (3.22) n=O n=O This equation, together with Eq. (3.21), gives finally P = pn(1 - p), n=0,1,... (3.23) We can now calculate the average number of customers in the system in steady state: N= lim E{N(t)}= -npn= E'np(1-p) n=O n=O = p(1 - p) n pOn- 1 = p(l - p) p n=O -- pn=o = (1 - p)-- p(1 - p) p p(1 - p) and, finally, using p = A/p N= p (3.24) 1-p -A __ _· Chap. 3