Sec.3.2 Queueing Models-Little's Theorem 119 Nt)◆ 3 1st Packet 2nd Packet arrival arrival 2 2K 3K 1st Packet 2nd Packet departure departure Figure 3.2 The number in the system in Example 3,N(t), is deterministic and does not converge as too.However,Little's Theorem holds if N,A,and T are interpreted as time averages. One should be careful about interpreting correctly the formula in this example Here the number in the system N(t)is a deterministic function of time.Its form is shown in Fig.3.2 for the case where K<aK +P 2K,and it can be seen that N(t)does not converge to any value (the system never reaches statistical equilibrium.)However,Little's Theorem is correct provided N is viewed as a long- term time average of N(t),i.e., N=lim N(r)dr t-00 t Example 4 Consider a window fow control system (as described in subsection 2.8.1)with a window of size N for each session.Suppose that a session always has packets to send and that acknowledgements take negligible time;then,when packet i arrives at the destination,packet i+N is immediately introduced into the network.Since the number of packets in the system per session is always N,Little's Theorem asserts that the arrival rate A of packets into the system for each session,and the average packet delay are related by N=AT.Thus,if congestion builds up in the network and T increases,A must decrease.Note also that if the network is congested and
Sec. 3.2 Queueing Models Little's Theorem departure departure Figure 3.2 The number in the system in Example 3, N(t), is deterministic and does not converge as t -- oo. However, Little's Theorem holds if N, A, and T are interpreted as time averages. One should be careful about interpreting correctly the formula in this example. Here the number in the system N(t) is a deterministic function of time. Its form is shown in Fig. 3.2 for the case where K < aK + P < 2K, and it can be seen that N(t) does not converge to any value (the system never reaches statistical equilibrium.) However, Little's Theorem is correct provided N is viewed as a longterm time average of N(t), i.e., N= lim S N(r)dr t-oo t Example 4 Consider a window flow control system (as described in subsection 2.8.1) with a window of size N for each session. Suppose that a session always has packets to send and that acknowledgements take negligible time; then, when packet i arrives at the destination, packet i + N is immediately introduced into the network. Since the number of packets in the system per session is always N, Little's Theorem asserts that the arrival rate A of packets into the system for each session, and the average packet delay are related by N = AT. Thus, if congestion builds up in the network and T increases, A must decrease. Note also that if the network is congested and
120 Delay Models in Data Networks Chap.3 capable of delivering only A packets per unit time for each session,then increasing the window size N for all sessions merely serves to increase the delay T. Example 5 Consider a queueing system with K servers,and with room for at most N >K customers (either in queue or in service).The system is always full;we assume that it starts with N customers and that a departing customer is immediately replaced by a new customer.(Queueing systems of this type are called closed.)Suppose that the average customer service time is X.We want to find the average customer time in the system T.We apply Little's Theorem twice,first for the entire system,obtaining N=AT,and then for the service portion of the system,obtaining K=AX(since all servers are constantly busy).By eliminating A in these two relations we have NX T= K Example 6:Estimating throughput in a time-sharing system Little's Theorem can sometimes be used to provide bounds on the attainable system throughput A.In particular,known bounds on N and T can be translated into throughput bounds via A N/T.As an example,consider a time-sharing computer system with N terminals.A user logs into the system through a terminal,and, after an initial reflection period of average length R,submits a job that requires an average processing time P at the computer.Jobs queue up inside the computer and are served by a single CPU according to some unspecified priority or time-sharing rule. We would like to get estimates of the throughput sustainable by the system (in jobs per unit time),and corresponding estimates of the average delay of a user. Since we are interested in maximum attainable throughput,we assume that there is always a user ready to take the place of a departing user,so the number of users in the system is always N.For this reason,it is appropriate to adopt a model whereby a departing user immediately reenters the system as shown in Fig.3.3. Applying Little's Theorem to the portion of the system between the entry to the terminals and the exit of the system (points A and C in Fig.3.3),we have N λ二 (3.3) where T is the average time a user spends in the system.We have T=R+D (3.4) where D is the average delay between the time a job is submitted to the computer and the time its execution is completed.Since D can vary between P(case where the user's job does not have to wait for other jobs to be completed)and NP(case
Delay Models in Data Networks capable of delivering only A packets per unit time for each session, then increasing the window size N for all sessions merely serves to increase the delay T. Example 5 Consider a queueing system with K servers, and with room for at most N > K customers (either in queue or in service). The system is always full; we assume that it starts with N customers and that a departing customer is immediately replaced by a new customer. (Queueing systems of this type are called closed.) Suppose that the average customer service time is X. We want to find the average customer time in the system T. We apply Little's Theorem twice, first for the entire system, obtaining N = AT, and then for the service portion of the system, obtaining K = AX (since all servers are constantly busy). By eliminating A in these two relations we have NX K Example 6: Estimating throughput in a time-sharing system Little's Theorem can sometimes be used to provide bounds on the attainable system throughput A. In particular, known bounds on N and T can be translated into throughput bounds via A = NIT. As an example, consider a time-sharing computer system with N terminals. A user logs into the system through a terminal, and, after an initial reflection period of average length R, submits a job that requires an average processing time P at the computer. Jobs queue up inside the computer and are served by a single CPU according to some unspecified priority or time-sharing rule. We would like to get estimates of the throughput sustainable by the system (in jobs per unit time), and corresponding estimates of the average delay of a user. Since we are interested in maximum attainable throughput, we assume that there is always a user ready to take the place of a departing user, so the number of users in the system is always N. For this reason, it is appropriate to adopt a model whereby a departing user immediately reenters the system as shown in Fig. 3.3. Applying Little's Theorem to the portion of the system between the entry to the terminals and the exit of the system (points A and C in Fig. 3.3), we have N A = -(3.3) where T is the average time a user spends in the system. We have T=R+D (3.4) where D is the average delay between the time a job is submitted to the computer and the time its execution is completed. Since D can vary between P (case where the user's job does not have to wait for other jobs to be completed) and NP (case Chap. 3
Sec.3.2 Queueing Models-Little's Theorem 121 Terminal 1 Terminal 2 Computer Terminal N Average reflection Average job processing time R time P Figure 3.3 N terminals connected with a time-sharing computer system.To estimate maximum attainable throughput,we assume that a departing user immediately reenters the system or,equivalently,is immediately replaced by a new user. where the user's job has to wait for the jobs of all the other users;compare with Ex.5),we have R+P≤T≤R+NP (3.5) Combining this relation with Eq.(3.3),we obtain N N R+NP≤A≤R+P (3.6) The throughput A is also bounded above by the processing capacity of the computer. In particular,since the execution time of a job is P units on the average,it follows that the computer cannot process in the long run more than 1/P jobs per unit time, i.e. As后 (3.7) (This conclusion can also be reached by applying Little's Theorem between the entry and exit points of the computer's CPU.) By combining relations (3.6)and(3.7),we obtain the bounds N R+Wp≤AS min 了1N PR+P (3.8)
Sec. 3.2 Queueing Models Little's Theorem Figure 3.3 N terminals connected with a time-sharing computer system. To estimate maximum attainable throughput, we assume that a departing user immediately reenters the system or, equivalently, is immediately replaced by a new user. where the user's job has to wait for the jobs of all the other users; compare with Ex. 5), we have R + P T < R+NP (3.5) Combining this relation with Eq. (3.3), we obtain N N < A < - (3.6) R+NP R+P The throughput A is also bounded above by the processing capacity of the computer. In particular, since the execution time of a job is P units on the average, it follows that the computer cannot process in the long run more than 1/P jobs per unit time, i.e., 1 A < (3.7) -P (This conclusion can also be reached by applying Little's Theorem between the entry and exit points of the computer's CPU.) By combining relations (3.6) and (3.7), we obtain the bounds N N N < A < min N (3.8) R +NP - ' R+P
122 Delay Models in Data Networks Chap.3 for the maximum attainable throughput.By using T=N/A,we also obtain bounds for the average user delay when the system is fully loaded max{NP,R+P}≤T≤R+NP (3.9) These relations are illustrated in Fig.3.4. It can be seen that as the number of terminals N increases,the throughput approaches the maximum 1/P,while the average user delay rises essentially in direct proportion with N.The number of terminals becomes a throughput bottleneck when N<1+R/P,in which case the computer resource stays idle for a substantial portion of the time while all users are engaged in reflection.In contrast,the limited processing power of the computer becomes the bottleneck when N>1+R/P.It is interesting to note that while the exact maximum attainable throughput depends on system parameters,such as the statistics of the refection and processing times, and the manner in which jobs are served by the CPU,the bounds obtained are independent of these parameters.We owe this convenient situation to the generality of Little's Theorem. 3.3 THE M/M/1 QUEUEING SYSTEM The M/M/1 queueing system consists of a single queueing station with a single server (in a communication context,a single transmission line).Customers arrive according to a Poisson process with rate A,and the probability distribution of the service time is exponential with mean 1/u sec.We will explain the meaning of these terms shortly.The name M/M/1 reflects standard queueing theory nomenclature whereby: 1. The first letter indicates the nature of the arrival process (e.g.,M stands for memoryless,which here means a Poisson process (i.e.,exponentially dis- tributed interarrival times),G stands for a general distribution of interarrival times,D stands for deterministic interarrival times). 2.The second letter indicates the nature of the probability distribution of the service times (e.g.,M,G,and D stand for exponential,general,and deter- ministic distributions,respectively).In all cases,successive interarrival times and service times are assumed to be statistically independent of each other. 3.The last number indicates the number of servers. We have already established,via Little's Theorem,the relations N=XT, NQ=入W
Delay Models in Data Networks Chap. 3 for the maximum attainable throughput. By using T = N/A, we also obtain bounds for the average user delay when the system is fully loaded max {NP, R + P} < T < R + NP (3.9) These relations are illustrated in Fig. 3.4. It can be seen that as the number of terminals N increases, the throughput approaches the maximum 1/P, while the average user delay rises essentially in direct proportion with N. The number of terminals becomes a throughput bottleneck when N < 1 + RIP, in which case the computer resource stays idle for a substantial portion of the time while all users are engaged in reflection. In contrast, the limited processing power of the computer becomes the bottleneck when N > 1 + R/P. It is interesting to note that while the exact maximum attainable throughput depends on system parameters, such as the statistics of the reflection and processing times, and the manner in which jobs are served by the CPU, the bounds obtained are independent of these parameters. We owe this convenient situation to the generality of Little's Theorem. 3.3 THE M/M/1 QUEUEING SYSTEM The M/M/1 queueing system consists of a single queueing station with a single server (in a communication context, a single transmission line). Customers arrive according to a Poisson process with rate A, and the probability distribution of the service time is exponential with mean 1/p sec. We will explain the meaning of these terms shortly. The name M/M/1 reflects standard queueing theory nomenclature whereby: 1. The first letter indicates the nature of the arrival process (e.g., M stands for memoryless, which here means a Poisson process (i.e., exponentially distributed interarrival times), G stands for a general distribution of interarrival times, D stands for deterministic interarrival times). 2. The second letter indicates the nature of the probability distribution of the service times (e.g., M, G, and D stand for exponential, general, and deterministic distributions, respectively). In all cases, successive interarrival times and service times are assumed to be statistically independent of each other. 3. The last number indicates the number of servers. We have already established, via Little's Theorem, the relations N = AT, NQ = AW
Sec.3.3 The M/M/1 Queueing System 123 Bound induced by Bound induced by X indyBnojyL limited number CPU processing of terminals capacity 1/P Guaranteed throughput curve 0 1+R/P Number of Terminals N (a) 0 Number of Terminals N (b) Figure 3.4 Bounds on throughput and average user delay in a time- sharing system.(a)Bounds on attainable throughput Eq.(3.8)]. (b)Bounds on average user time in a fully loaded system [Eq.(3.9)].The time increases easentially in proportion with the number of terminals N. between the basic quantities, N:Average number of customers in the system T:Average customer time in the system N:Average number of customers waiting in queue W:Average customer waiting time in queue
Sec. 3.3 The M/M/1 Queueing System 123 Bound induced by Bound induced by limited number CPU processing of terminals capacity IGuaranteed I throughput curve 0 1 + R/P Number of Terminals N (a) /I 1 - / ' 1 - I 0 1 Number of Terminals N (b) Figure 3.4 Bounds on throughput and average user delay in a timesharing system. (a) Bounds on attainable throughput [Eq. (3.8)]. (b) Bounds on average user time in a fully loaded system [Eq. (3.9)]. The time increases essentially in proportion with the number of terminals N. between the basic quantities, N : Average number of customers in the system T: Average customer time in the system NQ : Average number of customers waiting in queue W : Average customer waiting time in queue -C I-M 1/P 03 -0 30 "• E R +P •3C S R 03 IM