Section 11.1. Little s Theorem

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 . Thus, the average number of packets in the system, K _a , can be obtained 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.

Example.	Consider a data-communication system with three transmission lines; packets arrive at three different nodes with arrival rates » 1 = 200 packets/sec, » 2 = 300 packets/sec, and » 3 = 10 packets/sec, respectively. Assume that an average of 50,000 same- size packets float in this system. Find the average delay per packet in the system.
Solution.	This delay is derived by This is a simple application of Little's formula in a communication system.