Computer and Communication Networks (paperback)
11.1. Little's Theorem
The fundamental concept of packet queueing is based on Little's theorem , or Little's formula . This formula states that for networks reaching steady state, the average number of packets in a system is equal to the product of the average arrival rate, » , and the average time spent in the queueing system. For example, consider the communication system shown in Figure 11.1. Assume that the system starts with empty state at time t = 0. Let A i and D i be the i th arriving packet and i th departing packet, respectively, and let A(t) and D(t) be the total number of arriving packets and the total number of departing packets, respectively, up to a given time t . Figure 11.1. Overview of a buffered communication system with arriving and departing packets
Thus, the total time a packet i spends in the system is expressed by T i = D i - A i , and the total number of packets in the system at time t is described by K(t) = A(t) - D(t) . The cumulative timing chart of packets in a first-come, first- served service discipline is shown in Figure 11.2. The total time that all packets spend in the system can be expressed by Equation 11.1
Figure 11.2. Accumulation of 5 packets in a queueing system
Similarly, the average time a packet spends in the system, T a , can be represented by Equation 11.2
Also, the average number of arriving packets per second is given by » as Equation 11.3
By combining Equations (11.1), (11.2), and (11.3), we obtain Equation 11.4
This important result leads to a final form: Little's formula. This formula makes the assumption that t is large enough and that K a and T a therefore converge to their expected values of corresponding random processes E [ K(t) ] and E [ T ], respectively. Thus: Equation 11.5
Little's formula holds for most service disciplines with an arbitrary number of servers. Therefore, the assumption of first-come, first-served service discipline is not necessary.
|