A DEMERS. S. KESHAV AND S SHENKER way to emulate the bit-by-bit round-robin algorithm is to let the quantities Fa define the sending order of the packets. Our packet-by-packet transmission algorithm is simply defined by the rule that, whenever a packet finishes transmission, the next packet sent is the one with the smallest value of F. The continuity requirement mentioned earlier can be restated precisely as demanding that the relative transmission priorities depend continuously on the packet arrival times. The fact that the Fas depend continuously on the t@s means that our algorithm satisfies this continuity requirement In a preemptive version of this algorithm, newly arriving packets whose finishin lumber Fo is smaller than that of the packet currently in transmission preempt the transmitting packet. For practical reasons, we have implemented the nonpreemptive version, but the preemptive algorithm (with resumptive service) is more tractable analytically. Clearly the preemptive and nonpreemptive packetized algorithms do not give the same instantaneous bandwidth llocation as the bR version. However, for each conversation the total bits sent at a given time by these three algorithms are always within Pmax of each other, where Pmax is the maximum packet size (this lation discrepancy bound is proved in Greenberg and Madras(1990). Thus, over sufficiently long conversations, the packetized algorithms asymptotically approach the fair bandwidth allocation of the br scheme Recall that a user's request for promptness is not made explicit. The IP protocol(USC Information Sciences Institute, 1981a)does have a field for type-of-service, but not enough applications make intelligent use of this option to render it a useful hint. Consequently promptness allocation must be based solely on data already available at the gateway One such allocation strategy is to give more promptness(less delay) to us tho use less than their fair share of bandwidth. Separating the promptness allocation from the bandwidth allocation can be accomplished by introducing a nonnegative parameter 8, and defining a new quantity, the bid Bo, via B.=Pa+ MAX(F-1, R(9-8).The quantities R(O, Nac(o), Fo and So remain as before, but now the sending order is determined b the Bs, not the Fs. The asymptotic bandwidth allocation is independent of 6, since the Fs control the bandwidth allocation, but the algorithm gives slightly faster service to packets that arrive at an inactive conversation. The parameter 8 controls the extent of this additional promptness. Note that the bid B is continuous in ri, so that the forementioned continuity requirement is met The role of this term 8 can be seen more clearly by considering the two extreme cases 8=0 and 8=00. If an arriving packet has R(oasFo-I, then the conversation a is active (i.e. the corresponding conversation in the BR algorithm would have bits in the queue) In this case, the value of 8 is irrelevant and the bid number depends only on the finishing lumber of the previous packet. However, if R(r)>Fi-1, so that the a conversation is inactive, the two cases are quite different. With 8=0, the bid number is given by Bo Po+R() and is completely independent of the previous history of user a. With a=ox the bid number is B:= Pa+ Fa-I and depends only the previous packet's finishing number, no matter how many rounds ago. For intermediate values of 8, scheduling decisions for packets arriving at inactive conversations depend on the previous packet's finishing round as long as it was not too long ago, and 8 controls far back this dependence goes Recall that when the queue is full and a new packet arrives, the last packet from the conversation currently using the most buffer space is dropped. We have chosen to leave
FAIR QUEUEING ALGORITHM the quantities Fa and S unchanged when we drop a packet, This provides a small penalty for ill-behaved hosts, in that they will be charged for throughput that, because of their own poor flow control, they could not use. Subsequent work(Heybey and Davin, 1989) raises questions about the desirability of this aspect of our algorithm Performance The desired bandwidth and buffer allocations are completely specified by the definition of fairness, and we have demonstrated that our algorithm achieves those goals. However we have not been able to characterize the promptness allocation for an arbitrary arrival stream of packets. To obtain some quantitative results on the promptness, or delay performance of a single FQ gateway, we consider a very restricted class of arrival streams in which there are es of sources There are FtP-like file transfer sources which always have and transmit them whenever permitted by the source flow control (which, for simplicity, is taken to be sliding window flow control), and the are Telnet-like interactive sources, which produce packets intermittently according to some unspecified generation process. What are the quantities of interest? An FTP source is typically transferring a large file, so the quantity of interest is the transfer time of the file, which for asymptotically large files depends only on the bandwidth allocation. Given the configuration of sources this bandwidth allocation can be computed a priori by using the fairness property of FQ gateways. The interesting quantity for Telnet sources is the average delay of each packet, and it is for this quantity that we now provide a rather limited result Consider a single FQ gateway with N FTP sources sending packets of size Pe,and low a single packet of size Pr from a Telnet source to arrive at the gateway at time t. It will be assigned a bid number B=R(t)+ Pr-8; thus, the dependence of the queueing delay on the quantities Pr and 8 is only through the combination Pr-8. We will denote the queueing delay of this packet by (0), which is a periodic function with period NP We are interested in the de NPE p(r)di The finishing numbers Fa for the N FTPs can be expressed, after perhaps renumbering the packets, by Fo=(i+/m)P, where the ls obey Os/<1. The queueing delay of the Telnet packet depends on the configuration of ls whenever Pr<P. One can show that the delay is bounded by the extremal cases of /@=0 for all a and /o=a/N for a=0, N-1. The delay values for these extremal cases are straightforward to calculate; for the sake of brevity we omit the derivation and merely display the result below. The average queueing delay is given by 4=A(Pr-8), where the function A(P), the delay with 8=0, is defined below(with integer k and small constant 6, 0se<1, defined via Pr=PF(k+e)/
A DEMERS, S KESHAV AND S SHENKER Preemptive A(P)=NP- for P=Pp NP2 NP 1/P NPZ N NP2 P Lve A(P)=N(- for P=PF NI P A(P)=)11+xk2+k(2e-1)}forP PE PE 1)1/ for A(P)≤1+Nk2+k(2∈-1) +:≥P Now consider a general Telnet packet generation process (ignoring the effects of flow control)and characterize this generation process by the function D (PT)which denotes the queueing delay of the Telnet source when it is the sole source at the gateway. In the BR algorithm, the queueing delay of the Telnet source in the presence of N FTP sources is merely Do[(N+1)Prl For the packetized preemptive algorithm with 8=0, we can express the queueing delay in the presence of N FTP sources, call it D(PT),in terms of D, via the relation(averaging over all relative synchronizations between the FTPs and the Telnet) DN(PT)=Do[(N+1)Pr]+ A(Pr) where the term A(PT)reflects the extra delay incurred when emulating the BR algorithm by the preemptive packetized algorithm For nonzero values of 8, the generation process must be further characterized by the quantity lo(Pr, t)which, in a system where the Telnet is the sole source, is the probability that a packet arrives at a queue which has been idle for time f. The delay is given by DM(Pr)=Dol(N+1)Pr|+ A(Pr)- lol(N+1)Pr A(P1)-APr- MININ where the last term represents the reduction in delay due the nonzero 8. These expressions for DN, which were derived for the preemptive case, are also valid for the nonpreemptive algorithm when Pr≥P