114 Delay Models in Data Networks Chap.3 3.2 QUEUEING MODELS-LITTLE'S THEOREM We consider queueing systems where customers arrive at random times to obtain service.The probability distribution of the time between two successive arrivals (the interarrival time),and the probability distribution of the customers'service time are given. In the context of a data network,customers represent packets assigned to a communication link for transmission.Service time corresponds to the packet transmission time and is equal to L/C,where L is the packet length in bits and C is the link transmission capacity in bits/sec.In this chapter it is convenient to ignore the layer 2 distinction between packets and frames;thus packet lengths are taken to include frame headers and trailers.In a somewhat different context (which we will not dwell on very much),customers represent active conversations (or virtual circuits)between points in a network and service time corresponds to the duration of a conversation. We shall be typically interested in estimating quantities such as: 1.The average number of customers in the system (i.e.,the "typical"number of customers either waiting in queue or undergoing service). 2.The average delay per customer (i.e.,the "typical"time a customer spends waiting in queue plus the service time). We first need to clarify the meaning of the terms above.Let us denote Pn(t)=Probability of n customers waiting in queue or under service at time t The typical situation is one whereby we are given the initial probabilities pn(0) at time 0 and enough statistical information is provided to determine,at least in principle,the probabilities pn(t)for all times t.Then denoting N(t)=Average number in the system at time t we have N=∑npn() n=0 Note that both N(t)and pn(t)depend on t as well as the initial probability dis- tribution (po(0),P1(0),...).However,the queueing systems that we will consider typically reach eguilibrium in the sense that for some pn and N (independent of the initial distribution),we have ioPm(=pm,n=0,l,… (3.1) and Nnp() n=0
Delay Models in Data Networks Chap. 3 3.2 QUEUEING MODELS--LITTLE'S THEOREM We consider queueing systems where customers arrive at random times to obtain service. The probability distribution of the time between two successive arrivals (the interarrival time), and the probability distribution of the customers' service time are given. In the context of a data network, customers represent packets assigned to a communication link for transmission. Service time corresponds to the packet transmission time and is equal to LI/C, where L is the packet length in bits and C is the link transmission capacity in bits/sec. In this chapter it is convenient to ignore the layer 2 distinction between packets and frames; thus packet lengths are taken to include frame headers and trailers. In a somewhat different context (which we will not dwell on very much), customers represent active conversations (or virtual circuits) between points in a network and service time corresponds to the duration of a conversation. We shall be typically interested in estimating quantities such as: 1. The average number of customers in the system (i.e., the "typical" number of customers either waiting in queue or undergoing service). 2. The average delay per customer (i.e., the "typical" time a customer spends waiting in queue plus the service time). We first need to clarify the meaning of the terms above. Let us denote p,(t) = Probability of n customers waiting in queue or under service at time t The typical situation is one whereby we are given the initial probabilities p,(0) at time 0 and enough statistical information is provided to determine, at least in principle, the probabilities pn(t) for all times t. Then denoting N(t) = Average number in the system at time t we have 0o E= n pnt) n=o Note that both N(t) and pn(t) depend on t as well as the initial probability distribution {po(0), p1(0),...}. However, the queueing systems that we will consider typically reach equilibrium in the sense that for some pn and N (independent of the initial distribution), we have lim pn(t) = pn, n = 0, 1,... (3.1) t--oo and 00 N = np, lim W(t) n=O
Sec.3.2 Queueing Models-Little's Theorem 115 We will be interested primarily in the equilibrium probabilities and the average number in the system.Note that it is possible that N=oo and this will occur whenever the arrival rate exceeds the service capacity of the system.Individual sample functions of the number of customers in the system will be denoted by N(t).The time average of such a sample function in the interval [0,t]is defined by M=N) Almost every system of interest to us is ergodic in the sense that ling N:=ling N(t)=N holds with probability one.The equality of long term time average and ensem- ble average of various stochastic processes will often be accepted in this chapter on intuitive grounds since a rigorous mathematical justification requires technical arguments that are beyond the scope of this text. Regarding average delay per customer,the situation is one whereby enough statistical information is available to determine in principle the probability distri- bution of delay of each individual customer (ie.,the first,second,etc.).From this, we can determine the average delay of each customer.The average delay of the kth customer,denoted T,typically converges as koo to a steady-state value T-ingT The limit above is what we will call average delay per customer.(Again,T=oo is possible.)For the systems of interest to us,the steady-state average delay T is also equal(with probability one)to the long-term time average of customer delay, i.e.s T=mTk=皿 k+00 =1 where Ti is the delay of the ith customer. The average number in the system N and the average delay T are related by a simple formula that makes it possible to determine one given the other.This result,known as Little's Theorem,has the form N=λT where A=Average customer arrival rate and is given by 入=lim Expected number of arrivals in the interval
Sec. 3.2 Queueing Models-Little's Theorem We will be interested primarily in the equilibrium probabilities and the average number in the system. Note that it is possible that N = oo and this will occur whenever the arrival rate exceeds the service capacity of the system. Individual sample functions of the number of customers in the system will be denoted by N(t). The time average of such a sample function in the interval [0, t] is defined by Nt = N(r) d Almost every system of interest to us is ergodic in the sense that lim Nt = lim N(t) = N t-OO t-+OO holds with probability one. The equality of long term time average and ensemble average of various stochastic processes will often be accepted in this chapter on intuitive grounds since a rigorous mathematical justification requires technical arguments that are beyond the scope of this text. Regarding average delay per customer, the situation is one whereby enough statistical information is available to determine in principle the probability distribution of delay of each individual customer (i.e., the first, second, etc.). From this, we can determine the average delay of each customer. The average delay of the kth customer, denoted Tk, typically converges as k -- oo to a steady-state value T = lim Tk k-oo The limit above is what we will call average delay per customer. (Again, T = oo is possible.) For the systems of interest to us, the steady-state average delay T is also equal (with probability one) to the long-term time average of customer delay, i.e., k T = lim Tk•= lim Ti i=1 where Ti is the delay of the i t h customer. The average number in the system N and the average delay T are related by a simple formula that makes it possible to determine one given the other. This result, known as Little's Theorem, has the form N= AT where A = Average customer arrival rate and is given by A = lim Expected number of arrivals in the interval [0, t] t--oo t
116 Delay Models in Data Networks Chap.3 (We will be assuming that the limit above exists.)Phenomena reflecting Little's Theorem are familiar from everyday experience.For example,on a rainy day,traffic on a rush hour moves slower than average (large T)while the streets are more crowded (large N).Similarly,a fast-food restaurant (small T)needs a smaller waiting room (small N)than a regular restaurant for the same customer arrival rate. Little's Theorem is really an accounting identity and its derivation is very simple.We will give a graphical proof,which assumes that customers are served in the order they arrive.A similar proof is possible for the case where the order of service is arbitrary (see Problems 3.31 and 3.32).For any sample system history let us denote: a(t)=Number of arrivals in the interval [0,t] B(t)=Number of departures in the interval [0,t] Assuming an empty system at time 0,the number in the system at time t is N(t)=a(t)-B(t) Let ti and Ti be the time of arrival and the time spent in the system,respectively, by the ith customer.Consider any time t and the shaded area in Fig.3.1 which lies between the graphs of a(r)and B(r)up to time t.This area can be expressed as N(r)dr Jo but also as ) a() Ti+ (t-t) i=1 =()+1 Dividing both expressions above by t and equating them,we obtain N:AT (3.2) where N= N(r)dr t -Time average of the number of customers in the system in the interval [0,t := () -Time average of the customer arrival rate in the interval 0,t B(t a() ∑+ (t-t) T= =1 =(t)+1 a(t) =Time average of the time a customer spends in the system in the interval 0,t
Delay Models in Data Networks (We will be assuming that the limit above exists.) Phenomena reflecting Little's Theorem are familiar from everyday experience. For example, on a rainy day, traffic on a rush hour moves slower than average (large T) while the streets are more crowded (large N). Similarly, a fast-food restaurant (small T) needs a smaller waiting room (small N) than a regular restaurant for the same customer arrival rate. Little's Theorem is really an accounting identity and its derivation is very simple. We will give a graphical proof, which assumes that customers are served in the order they arrive. A similar proof is possible for the case where the order of service is arbitrary (see Problems 3.31 and 3.32). For any sample system history let us denote: a(t) = Number of arrivals in the interval [0, t] ,6(t) = Number of departures in the interval [0, t] Assuming an empty system at time 0, the number in the system at time t is N(t) = a(t) - f(t) Let t4 and Ti be the time of arrival and the time spent in the system, respectively, by the ith customer. Consider any time t and the shaded area in Fig. 3.1 which lies between the graphs of a(r) and 6(r) up to time t. This area can be expressed as otN(r) dr but also as 3(t) a(t) Ti+ (t-t ) i=1 i=fi(t)+1 Dividing both expressions above by t and equating them, we obtain Nt = AtTt (3.2) where fot N(r) dr Nt =Time average of the number of customers in the t system in the interval [0, t] At = t) =Time average of the customer arrival rate in the t interval [0, t] 0(t) a(t) -Ti+ F (t-ti) i=1 i=8(t)+l Tt(t =Time average of the time a customer spends in =a(t) the system in the interval [0, t] _·_ Chap. 3
Sec.3.2 Queueing Models-Little's Theorem 117 7 6 可 a(T] 3 Delay 72 Delay 7 Customer 天0 B(7) t2 Figure 3.1 Proof of Little's Theorem.The shaded area can be expressed (t) (t) bohs6 (r)dr ad∑r+∑ (t-ti).Dividing both expressions =1=(t)+1 by t,equating them,and taking the limit as t-oo gives Little's Theorem. Assuming that N+N,λt→λ，T+T we obtain from Eq.(3.2)the desired formula. Note that the expression T includes the total time spent in the system for all the arrivals from 1 to (t),but omits the time spent beyond t for the customers still in the system at time t.Assuming that N-N<oo,this end effect due to customers in the system at time t will be small relative to the accumulated time in the system of customers 1 to (t),and Ti for large t can be interpreted as the time average of the system time. Strictly speaking,for the argument above to be correct,we must be assured that the time averages N:,At,T:converge with probability one to the corresponding ensemble averages N,A,and T.This is true in just about every case of interest to us,and in subsequent analysis,we will accept Little's Theorem without further scrutiny. The significance of Little's Theorem is due in large measure to its generality. It holds for almost every queueing system that reaches statistical equilibrium in the limit.The system need not consist of just a single queue.Indeed,the theorem
Sec. 3.2 Queueing Models-Little's Theorem I.t- (LO >0 a. 0 0 EE zz Figure 3.1 Proof of Little's Theorem. The shaded area can be expressed 0(t) a(t) both as f N(r) dr and as Ti + (t - ti). Dividing both expressions i=1 i=0(t)+l by t, equating them, and taking the limit as t -* oo gives Little's Theorem. Assuming that Nt - N, At - A, Tt -T we obtain from Eq. (3.2) the desired formula. Note that the expression Tt includes the total time spent in the system for all the arrivals from 1 to P(t), but omits the time spent beyond t for the customers still in the system at time t. Assuming that NAt - N < oo, this end effect due to customers in the system at time t will be small relative to the accumulated time in the system of customers 1 to f(t), and Tt for large t can be interpreted as the time average of the system time. Strictly speaking, for the argument above to be correct, we must be assured that the time averages Nt, At, Tt converge with probability one to the corresponding ensemble averages N, A, and T. This is true in just about every case of interest to us, and in subsequent analysis, we will accept Little's Theorem without further scrutiny. The significance of Little's Theorem is due in large measure to its generality. It holds for almost every queueing system that reaches statistical equilibrium in the limit. The system need not consist of just a single queue. Indeed, the theorem
118 Delay Models in Data Networks Chap.3 holds for many complex arrival-departure systems with appropriate interpretation of the terms N,A,and T.The following examples illustrate its broad applicability. Example 1 If A is the arrival rate in a transmission line,No is the average number of packets waiting in queue (but not under transmission),and W is the average time spent by a packet waiting in queue (not including the transmission time),Little's Theorem gives No=AW Furthermore if X is the average transmission time,then Little's Theorem gives the average number of packets under transmission as p=灭 Since at most one packet can be under transmission,p is also the line's utilization factor,i.e.,the proportion of time that the line is busy transmitting a packet. Example 2 Consider a network of transmission lines where packets arrive at n different nodes with corresponding rates 1,...,n.If N is the average total number of packets inside the network,then(regardless of the packet length distribution and method for routing packets)the average delay per packet is N T=- 1 Furthermore,Little's Theorem also yields Ni=AiTi,where Ni and Ti are the average number in the system and average delay of packets arriving at node i, respectively. Example 3 A packet arrives at a transmission line every K seconds with the first packet arriving at time 0.All packets have equal length and require aK seconds for transmission where a 1.The processing and propagation delay per packet is P seconds. The arrival rate here is A=1/K.Because packets arrive at a regular rate (equal interarrival times),there is no delay for queueing,so the time T a packet spends in the system(including the propagation delay)is T=aK+P According to Little's Theorem,we have N=XT=a+K
Delay Models in Data Networks holds for many complex arrival-departure systems with appropriate interpretation of the terms N, A, and T. The following examples illustrate its broad applicability. Example 1 If A is the arrival rate in a transmission line, NQ is the average number of packets waiting in queue (but not under transmission), and W is the average time spent by a packet waiting in queue (not including the transmission time), Little's Theorem gives NQ = AW Furthermore if X is the average transmission time, then Little's Theorem gives the average number of packets under transmission as p= AX Since at most one packet can be under transmission, p is also the line's utilization factor, i.e., the proportion of time that the line is busy transmitting a packet. Example 2 Consider a network of transmission lines where packets arrive at n different nodes with corresponding rates A1,..., A, . If N is the average total number of packets inside the network, then (regardless of the packet length distribution and method for routing packets) the average delay per packet is N Furthermore, Little's Theorem also yields Ni = AiTi, where N1 and Ti are the average number in the system and average delay of packets arriving at node i, respectively. Example 3 A packet arrives at a transmission line every K seconds with the first packet arriving at time 0. All packets have equal length and require aK seconds for transmission where a < 1. The processing and propagation delay per packet is P seconds. The arrival rate here is A = 1/K. Because packets arrive at a regular rate (equal interarrival times), there is no delay for queueing, so the time T a packet spends in the system (including the propagation delay) is T = aK + P According to Little's Theorem, we have P N=AT=a+-K Chap. 3