4.4 SOME IMPORTANT RELATIONSHIPS IN QUEUEING THEORYWe mentioned in Section 4.1 that queueing theory has been highly successful in deriving expressions for the low moments of quantities such as the waiting times of the users of a queueing system or the number of users present in the system at a given time. We shall now begin our discussion with the derivation of a few important relationships involving the expected values of these quantities, , _{q}, , and _{q} for a very general queueing system. J. D. C. Little [LITT 611 is generally credited with being the first to prove these relationships formally. Subsequent authors have shown that Little's results are valid for queueing systems more general than he assumed in his original work [STID 74]. Here we shall use an informal and intuitive argument paralleling the one offered by Kleinrock [KLEI 75]. The search for the relationships is motivated by the intuitionsatisfying notion that the average length of the queue in front of a facility offers a good indication of the average waiting time for use of that facility (and vice versa). These relationships turn out to be especially simple. First, we shall position ourselves at the "entrance" of a queueing system and count the number of users that arrive there during an interval of arbitrary length, , beginning at the time t = 0 when the system is empty (see also Figure 4.3). We let
Next, we count the number of users leaving the system at its "exit" and let
If the system is empty at t = 0, the number of users in the system at the time t = is given by
We can now use (4.6) to express the total amount of time, l(), spent by all users in the queueing system during the interval [0,l. We have Clearly, 1() represents the area between the functions a() and c(), as illustrated in Figure 4.3. The average number of users () in the queueing system during the interval [0, ] can now be obtained by dividing the total amount of time spent by all users in the queueing system, l(), by the time : (4.8) We have written (4.8) in this form because both ratios on its righthand side have very real physical meaning. The ratio a()/ is simply the average number of arrivals per unit of time (the arrival rate) during the interval and can be indicated, given our earlier notation, as _{}. Similarly, l()/a() is the average time spent by a user in the queueing system during the interval [0, ] and can be indicated, given our earlier notation, as _{}. We can then write () = _{} _{} (4.9) If we now let the length of the interval, , tend to infinity, it is clear from our earlier definitions of , , and that these quantities represent the limits of () _{}, and _{} respectively. So if the limits of the last two quantities ( _{}, and _{}) actually exist, the limit of () also exists and from (4.9) we have the relationship = (4.10) This is one of the bestknown results of queueing theory and is referred to as Little's formula. Later in this chapter we shall explore the conditions under which the limits of _{} and of () exist for many types of queueing systems. A few important remarks are in order:
