FAIR QUEUEING ALGORITHM 1 What do these forbidding formulae mean? Consider, for concreteness, a Poisson arrival A, packet sizes Pr=PF=P, a linespeed u=1 and an FTP chronization described by l =a/N for a=0, 1,.,. N-1. Define p to be the average Iwidth of the stream, measured relative to the fair share of the Telnet: p=AP(N+1) for the nonpreemptive algorithm P2(1-)2+N(1-0(1-(N~少exp(N+1) DN(P) p MIN This equation represents the throughput/delay curve the FQ gateway offers the Poisson Telnet source (the formulae for different FTP synchronizations are substantially more complicated, but have the same qualitative behavior). This throughput/delay curve can be contrasted with that offered by an FCFS gateway; however, the FCFS results depend in detail on the flow control used by the FTP sources and on the surrounding network environment. We consider a network where all other communications speeds are infinitely fast in relation to the outgoing linespeed of the gateway, and where the FTPs all use sliding window flow control with window size w, so there are always Nw FTP packets in the queue or in transmission. Figure 1 shows the throughput/delay curves of such a system with parameters N=3 and w=5 for both an FCFS gateway and an FQ gateway with 8=0 and 8=P. For p-0, FCFS gives a large queueing delay of(Nw-2)P, whereas Q gives a queueing delay of NP/2 for 8=0 and P/2 for 8-P. This ability to provide a the FTPs, is one of the most important features or la dependent of the window sizes of lower delay to lower throughput sources, completely ine eueing. Note also that the FQ queueing delay diverges as p1, reflecting FQ's insistence that no conversation gets more than its fair share. In contrast, the fCfs curve remains finite for all p<(N+1), showing that an ill-behaved source can consume an arbitrarily large fraction of the bandwidth What happens in a network of FQ gateways? There are few results here, but Hahne (1986)has shown that for strict round-robin service gateways and only FTP sources there is fair allocation of bandwidth(in the multiple resource sense) when the window sizes are sufficiently large. She also provides examples where insufficient window sizes, but much larger than the communication path, result in unfair allocations. We believe, but have been unable to prove, that both of these properties hold for our fair queueing FLOW CONTROL ALGORITHMS Flow control algorithms are both the benchmarks against wh congestion control properties of fair queueing are measured, and also the envi which FQ gateways will operate. We already know that, when combined with teways ese control algorithms all suffer from the fundamental problem of vulnerability to ill-behaving sources. Also, there is no mechanism for separating the promptness allocation from the bandwidth and buffer allocation. The remaining question is then how fairly do these flow control algorithms allocate bandwidth. Before proceeding, note that there are really two distinct problems in controlling congestion Congestion recovery allow from a badly congested state, whereas congestion avoidance attempts to prevent the congestion from occurring (Jain and Ramakrishnan, 1988). In this paper, we are focusing on congestion avoidance and will not discuss congestion recovery mechanisms at length