Random Early Detection Gateways for Congestion Avoidance

Sally Floyd and Van Jacobson, "Random Early Detection Gateways for Congestion Avoidance"

The proposed algorithm is implemented in the gateway (see 16. of the previous post) and uses FIFO scheduling together with a random drop policy. The gateway can signal congestion through dropping or marking packets, and will do so before the queue will overrun (see previous post for motivation). It will do so in a manner where the packet drop probability will depend continuously on the queue size (see 19. of previous post) and where the drop probability is proportional to the bandwidth of the corresponding flow to archive fairness.

The design goals were:

• cooperat with current transport protocol implementations and gateways
• congestion avoidance: avoid long queues/delays and low throughput
• avoid global syncronity (see 6. of previous post)
• no negative bias against bursty traffic (see 5.)
• fair bandwidth allocation (though not complete isolation from misbehaving senders)
• no per-flow state
  

The algorithm has several parts:

• Computing the average queue size (through expontial weight low pass filter: this distinguishes between persistent queue and bursty traffic)
• Use average queue size to determine the drop/congestion notification probability. This will be a piecewise linear function.
• Drop packet with that probability, do a little math trick: if a packet wasn't droped for a long time (with respect to the drop packet probability), bias the probability, that way packets will be dropped more uniformly. Since the packet is chosen randomly, a flow with a higher bandwidth has a higher probability of being impacted.

Since packets might have very different sizes, the probability might be multiplied with the packet size to ensure fairness.

The paper discusses good ranges for the various parameters and shows simulations.