Readings for Lecture Sep 16, 2008

Random Early Detection (RED) Gateways for Congestion Avoidance

Different from DECbit congestion avoidance scheme, the RED gateways detect potential congestion by computing the average queue size. Then the gateways can implicitly notify the sources of congestion connections either by dropping packets at the gateways or by setting a bit in packet headers then when the destinations of connections return ACK to the source, it includes this bit.

The next improvement of RED is the mechanism to drop a packet. When the average queue length exceeds a certain drop level, then the gateway drops each packet arriving at the gateway randomly with a fixed drop probability. If the average queue length exceeds a certain max drop level then every packet arriving is marked.

For each queue, the average queue length, avg, is estimated by: avg = (1 – weight) * avg + weight * currentQueueLen. If minth ≤ avg ≤ maxth, then the probability pb = maxp(avg – minth)/(maxth – minth) and pa = pb/(1 – count * pb). If avg ≥ maxth all the arriving packet are marked.

The value minth reflects the utilization of the link. If the typical traffic is rather busty, then minth has to be set to corresponding large to allow the link to be maintained at acceptable high bandwidth. While maxth depends in part on the maximum average delay that can be allowed by the gateway. The RED gateway function most effectively when maxth - maxth is larger then the typical increase in the calculated average queue size in one roundtrip time.

The mechanism presented in this paper is particularly useful in networks where it is undesirable to drop packet since the RED gateways predict and control the average queue size before congestions can happen. However, The paper does not specify whether the queue size should be measured in bytes or in packet.

Congestion Control for High Bandwidth-Delay Product
Explicit Control Protocol (XCP) generalizes the explicit congestion notification. In XCP protocol, the efficiency control and fairness control is separated. The senders in XCP maintain their congestion window cwnd and round trip time rtt and communicate these to the routers via a congestion header in every packet. Based on the difference between the link bandwidth and its input traffic rate, the router tells the flows sharing that link to increase or decrease their congestion windows.

Each XCP packet carries a congestion header, which is used to communicate a flow’s state to routers and feedback from the routers on to the receivers. The H_cwnd is the sender current congestion windows, H_rtt is the sender’s current RTT estimate. The H_feedback is initialized by the sender and modified by the routers along the path to directly control the congestion windows of the sources.

Whenever a new acknowledgment arrives, positive feedback increases the senders cwnd and negative feedback reduces it: cwnd = max(cwnd : H_feedback, s) where s is the packet size. The receivers whenever acknowledging a packet, it copies the congestion header from the data packet to its acknowledgement.

The efficiency control’s (EC) purpose is to maximize link utilization while minimizing the drop rate and persistent queues. Since the EC is separated from fairness control, so the aggregate feedback φ is computed for each control interval: φ = α.avgRTT.SpareBandwidth - β.PersistentQueueSize. The aggregate feedback φ computed from EC is divided equally between all flows (positive or negative). The principle for converging to the fairness is Additive Increase, Multiplicative Decrease.

The delay issue is not really evaluated in this paper. The question is that can we extend the protocol to guarantee timing delay of a packet is bounded?