CS268 Reading Review

Random Early Detection Gateways for Congestion Avoidance

Sally Flyod and Van Jacobson
Review by Feng Zhou
2/12/2003

The problem: Drop Tail queueing policy at gateways has a couple a problems. It is inefficient in case of congestion because it has to drop a lot of packets before the end-hosts are notified of the congestion. This also causes the synchronization problem. It also biases against bursty traffic. This paper proposes a new congestion avoidance scheme at the gateway that tries to solve these problems without introducing per-flow state into gateways, as is the case with Fair Queueing.

Key points:

  1. The basic scheme is as following. The gateway has a minimal threshold and a maximal threshold for queue length. It "marks" packets with a probability related to queue length after it exceeds the min threshold. It marks all packets after the queue length exceeds the max threshold. The "mark" operation can be either setting a bit in TCP header or dropping the packet, depending on the end-host transport protocol implementation.
  2. The "statelessness" is an important property of RED. No per-flow state is maintained. Unlike Fair Queueing, which solves similar problems "better" in some sense, RED can be implemented much more easily and more efficiently. It also scales better than Fair Queueing.
  3. The problem of selfish users is not explicitly addressed by RED gateways. The only penalty for the more aggressive ones is that the number of packets they loose during congestion is proportional to the bandwidth they use. This doesn't really form a penalty. The selfish users can still occupy as much bandwidth as they want. So it maybe interesting to see whether we can possible penalize these behavior without using per-flow state. Or alternatively, we can proove this is impossible to achieve.