S. Floyd and V. Jacobson, “Random early detection gateways for congestion avoidance,” IEEE/ACM Trans. Networking, vol. 1, pp. 397–413, Aug. 1993.
By 1993, the main gateway queueing methods were Drop Tail (FIFO w. limited buffer) and Random Drop algorithms. As shown by several researchers by that time, Drop Tail gateways are biased against bursty flows and will drop their packets disproportionately to their share of band-width. Furthermore they will cause global synchronization among source congestion control algorithms in which will cause degraded utilization. Even though Random Drop algorithms with sufficiently large buffers should alleviate the bias against bursty traffic to some degree (even though synchronization problem still remains) large buffer size and therefore average queue size, translates to large average delays in the queues which is unpleasant in high speed networks. In order to avoid large buffer sizes and global synchronization, there had been several studies of Early Random Drop gateways in which above a certain threshold the algorithm would drop the packets with fixed probabilities.
The main contribution of this paper is an improvement over Early Random Drop gateways called Random Early Drop (RED) gateway algorithm in which the drop probability is dynamically changed in between two threshold in order to better remove the bias against bursty traffics and furthermore remove global synchronization. This algorithm does not aim fair allocation of resources and does not include any per flow state/processing.
Even though I found the RED algorithm an interesting improvement, I did not found the comparisons between different schemes well designed. For example, in previous work section, the authors mention a version of Early Random Drop gateway algorithms given by Zhang[36] in which a misbehaving user was able to achieve 73% higher throughput than regular TCP users. I did not find any evidence that RED algorithm will have any better performance against misbehaving users when there is no extra identification mechanisms in which could be applied to the Zhang algorithm as well.
Furthermore, there had been too much emphasis in comparing RED gateways with Drop Tail gateways! I would assume that Random Drop gateways had already made a first order improvement over Drop Tail gateways and the true competitor of RED is either Random Drop gateways, Early Random Drop schemes or DECbit. For example, the authors could have shown that for similar traffic burstiness and throughput share, Random Drop gateway will require a larger average queue size and therefore larger delay. In general I didn't found the simulation results precise enough; for example figure 13, 14 and 15 are given side-by-side while x-axis is different in figure 15 and can be quite misleading. Furthermore, it is not obvious for larger average queue sizes how the figure 15 would look like!
By 1993, the main gateway queueing methods were Drop Tail (FIFO w. limited buffer) and Random Drop algorithms. As shown by several researchers by that time, Drop Tail gateways are biased against bursty flows and will drop their packets disproportionately to their share of band-width. Furthermore they will cause global synchronization among source congestion control algorithms in which will cause degraded utilization. Even though Random Drop algorithms with sufficiently large buffers should alleviate the bias against bursty traffic to some degree (even though synchronization problem still remains) large buffer size and therefore average queue size, translates to large average delays in the queues which is unpleasant in high speed networks. In order to avoid large buffer sizes and global synchronization, there had been several studies of Early Random Drop gateways in which above a certain threshold the algorithm would drop the packets with fixed probabilities.
The main contribution of this paper is an improvement over Early Random Drop gateways called Random Early Drop (RED) gateway algorithm in which the drop probability is dynamically changed in between two threshold in order to better remove the bias against bursty traffics and furthermore remove global synchronization. This algorithm does not aim fair allocation of resources and does not include any per flow state/processing.
Even though I found the RED algorithm an interesting improvement, I did not found the comparisons between different schemes well designed. For example, in previous work section, the authors mention a version of Early Random Drop gateway algorithms given by Zhang[36] in which a misbehaving user was able to achieve 73% higher throughput than regular TCP users. I did not find any evidence that RED algorithm will have any better performance against misbehaving users when there is no extra identification mechanisms in which could be applied to the Zhang algorithm as well.
Furthermore, there had been too much emphasis in comparing RED gateways with Drop Tail gateways! I would assume that Random Drop gateways had already made a first order improvement over Drop Tail gateways and the true competitor of RED is either Random Drop gateways, Early Random Drop schemes or DECbit. For example, the authors could have shown that for similar traffic burstiness and throughput share, Random Drop gateway will require a larger average queue size and therefore larger delay. In general I didn't found the simulation results precise enough; for example figure 13, 14 and 15 are given side-by-side while x-axis is different in figure 15 and can be quite misleading. Furthermore, it is not obvious for larger average queue sizes how the figure 15 would look like!
No comments:
Post a Comment