Several objectives have been identified in developing the random early drop (RED): decreasing queueing delay, increasing throughput, and increasing fairness between short and long lived connections. It has been believed that indeed the drop probability of a packet in RED does not depend on the size of the file to which it belongs. In this paper we study the fairness properties of RED where fairness is taken with respect to the size of the transferred file. We focus on short lived TCP sessions. Our findings are that (i) in terms of loss probabilities, RED is unfair: it favors short sessions, (ii) RED is fairer in terms of the average throughput of a session (as a function of its size) than in terms of loss probabilities. We study various loading regimes, with various versions of RED.
One of the objectives of random early drop (RED) has been to get rid of the bias of drop-tail buffers against bursty traffic [3]. It has been confirmed in [4, Section IX] that indeed RED gets rid of this bias and is fair in terms of fraction of lost packets. This has been demonstrated in a framework where both bursty as well as “smooth” traffic were taken as permanent FTP connections. The higher burstiness was obtained by using smaller windows and longer round-trip times. In a recent paper [7], the authors show that conclusions drawn from simulating permanent TCP connections can be qualitatively quite different than those obtained from simulations of transfers that have large time scale variability. The latter is obtained by replacing the infinite source model by ones in which transfered files have heavy-tailed distributions. This motivated us to question the qualitative conclusions drawn in [4] and restudy the fairness issue using Pareto distributed file sizes. We are interested in the following questions: (i) how does the drop probability of a packet depend on the file size? (ii) how does the average throughput experienced by a file depend on its size?
If we identify arrival of packets from a file as a “batch” (which is justified by our simulations), then the fairness in terms of the file size also answer the question of fairness in terms of batch sizes.
Our main findings are that in terms of loss probabilities, RED is biased against long files. Furthermore, we show that this bias increases as the workload decreases. We study this phenomenon and provide an explanation for it. We further show that RED is fairer in terms of throughput than it is in terms of loss probabilities. When comparing to drop-tail buffers, we see that for all loads, RED has smaller loss probabilities for almost all transfer sizes; the drop-tail buffer is more fair in terms of drop probabilities (as a function of the transfer size) since it has many more drops for short file transfers. In terms of throughput, RED is slightly fairer than the drop-tail buffer. Our conclusions similar for four different variants of RED that we tested.
We briefly mention some related work. Fair RED (FRED) is proposed in [10] which needs however to keep some per-active-flow states.1 Its performance is analyzed by simulating permanent TCP connections. In [14], stabilized RED (SRED) is proposed, requiring per-flow state information too. Unlike RED, the drop probabilities depend only on the instantaneous buffer occupation and on the estimated number of active flows. Fairness according to the transfer size is not considered there. [2] analyzes biasness with respect to bursty traffic. Both smooth as well as bursty traffic are modeled as Poisson processes, but in the smooth case each arrival corresponds to a single packet, where as in the bursty traffic case each arrival brings a batch of B packets. The conclusions of the paper are that indeed RED decreases the bias against bursty traffic. The traffic models used are not closed loop (they do not adapt to congestion), and as we learn from [1] and [7, Section 4], qualitative behavior of closed loop traffic can be quite different from open loop. Although there are also some TCP simulations of RED in [2], these use permanent connections. Other papers studied RED using long lived TCP connections [6], [9], [11], [12], [13], [15], [16] and [17] as well as short lived connections [8] and [17]. But the fairness issue is not examined in these references.
We study the standard as well as the adaptive RED version, both with and without the gentle option of RED.2 We introduce the model and simulation setup in Section 2, present some preliminary simulation results in Section 3, then present the fairness results in terms of the loss probabilities in Section 4 and in terms of the throughput in Section 5. The analysis of these results and explanation of the causes for the observed behavior are given in Section 6, and we end with a concluding section.
We examined how loss rate of a transfer and the transfer throughput are related to its size. We have seen that RED is biased against long connections in terms of loss probabilities but that this bias decreases as the load increases. In terms of throughput, RED is fairer than in terms of the loss rate. Best performance has been obtained with gentle RED, and in general all variants of RED performed better than drop-tail.
In our simulation scenarios, file transfers could be identified with bursts. For example, “spikes” in Fig. 25 and Fig. 26 correspond to file transfers. In that case, fairness in terms of the size of a file can be identified with fairness in terms of burst size. Our conclusions on fairness in terms of burst size are then different than those that had been obtained in previous work through simulations of permanent connections.
