A CS 255 Paper Review for Random Early Detection Gateways for Congestion Avoidance by Sally Floyd and Van Jacobson
The paper comprehensively discusses Random Early Detection (RED) gateways for congestion avoidance.This algorithm notifies connections of congestion either by dropping packets or tagging each arriving packet (by setting a bit in the packet headers) randomly with a certain probability if the average queue length is between a given range. A probability such that it is proportional to the connection’s share in network throughput. RED gateways are designed for transport layer protocols that respond to congestion through marked packets (either dropped or with the congestion bit set). It was also mentioned that even if the transport protocol is not cooperating (it still floods the network even with congestion), the RED algorithm can still control the average queue length since it can drop the non-cooperating connection’s packets.
The paper also extensively compared early models of early detection congestion avoidance mechanisms and how each performed in various scenarios. The two most discussed mechanisms were Early Random Drop and Drop Tail gateways. The Early Randrom Drop gateway is almost the same as RED but it uses a fixed probability (i.e. does not adjust to network throughput) in determining which connection to notify. While for Drop Tail, on the other hand, since packets are dropped from several connections, global synchronization is introduced. Global synchronization is where multiple nodes receive the congestion notice so they all decrease their throughput at the same time, thus falling below optimal utilization of the network – a scenario that must be avoided and has long been studied.
Another congestion avoidance scheme that was thoroughly discussed and compared with RED is the DECbit congestion avoidance scheme. In contrasts to RED, DECbit marks all incoming packet when there is a congestion (RED select randomly with probability). Because of this, the receiving transport layer protocol still have to compute if the fraction of the received bits are enough to imply congestion. The arking overhead issue was also brought up with DECbit as it tags all incoming packets.
Next, the Design for the RED algorithm was presented. One of the highlights was flexibility through the parameters min, max, and average wherein the first 2 can be controlled and set by the system administrator. This flexibility also was complemented by the paper’s provided guidelines in choosing the right values( i.e. the minimum should not be too low that it would already lead to low network utilization, while the maximum must be high enough to approximate bursts but not too high that it won’t be able to prevent congestion).
The paper also did not lack in discussing the implementation details such as employing parallel computation so as to not consume much computation time especially in networks where a lot already happens in a split second. And how RED will tag all arriving packets if the average queue length is already way past the given maximum threshold.
Elaborations on actual network issues such as bursts (and what are the most like reasons behind them) and misbehaving users (users who still consume a large chunk of the network even if network congestion notice has already been sent) and how RED respond to these scenarios capped off the entire paper with a feel of real life applications and solutions.
Overall, the paper was a great and comprehensive read on the Random Early Detection gateways for congestion avoidance. Motivations behind, related mechanisms, design, and implementation details were thoroughly discussed and tackled. There was also an abundance of graphs, formulas, and chunks of pseudocode which made understanding the paper easier.
Photo from: community.michelinchallengebibendum.com