Congestion Control Mechasims

Network congestion refers to the reduced quality of service, reduced speed and delays in establishing connections between computers in the network. If a network node is not able to keep up forwarding the traffic at the same rate as it is receiving traffic, these nodes become choke points of the network. When a network is in this condition, it settles into a stable state where quality of service, packet delay and packet loss are extremely poor and throughput is very low compared to demand.

Congestion control mechanisms aid in managing traffic entry to a network to avoid congestion collapse.

Slow Start

Slow Start was the first congestion control implementation for TCP developed by Jacobson and Karels. In Slow Start, the rate at which the sender can transmit data is based on the rate at which the receiver sends acknowledgements. This enables equilibrium such that incoming and outgoing packets to and from the network are maintained at the same rate.

In Slow start the number of segments sent at the start is small (which implies slow bandwidth for the connection) and is increased gradually as it gets confidence about network throughput.

The Slow Start transmission window (number of segments sent) is managed by the CWND (Congestion Window) flag. Slow start starts with a small window size (CWND is set to maximum TCP segment size of client OR recipients allowed window; which of is has the lower value)

SSTHRESH defines the threshold till which CWND will keep on incrementing by one for each acknowledgement received back to the client. When the value of CWND passes SSTHRESH value, the congestion window has closely reached network capacity. From here onwards Congestion-Avoidance algorithm is used, where for each acknowledgement received the value of CWND is increased only b by 1/CWND.

If a client fails to receive an acknowledgement it assumes there is congestion in the path and reduced SSTHRESH is reduced by setting it to half of current window size. Window Size set to 1 by setting CWND to 1.

The above steps are for the client-end of the connection. Even if the client has passed Slow Start phase the server might still be in Slow Start mode if it has not send any data back to the client except acknowledgements for TCP segments sent by the client.

Experiments with Slow Start in TCP found 200% increase in non-retransmit bandwidth using Slow-Start compared to prior TCP implementation without Slow-Start which only used 35% of the bandwidth due to retransmission. Slow Start makes the bottleneck path to be at maximum capacity due to window size being increased till ACK is not received and on timeouts window size is made half the maximum window size allowed by bottleneck. This leads to oscillation as the process is iterated over.

Slow-Start is a TCP Standard for Congestion-Control and Avoidance and most TCP implementations either utilize or modify the slow-start method.

Random Early Detection

The main goal of RED is to help in congestion avoidance by monitoring gateway queue and controlling queue size by either dropping incoming packets or marking packet headers with a certain congestion probability. To avoid bias on traffic bursts the packet drops are done at even spaced slots.

RED calculates average queue size, and for longer-lived congestion (indicated by increase in average queue size) randomly notifies some connections to reduce size of windows.

To calculate the average queue size RED uses the following algorithm:

When a new packet is received to an empty queue it finds number of packets m that could have been transmitted during the idle time till the current time and then calculates the average queue size assuming m packets were transmitted during idle period. queue Weight variable is derived by RED algorithm by taking in the size and period of queue size bursts. RED can either drop the packet to indicate congestion or in supported transport protocols, set a bit in every arriving packet header, when a maximum threshold for average queue size is increased. This allows RED gateways to support current TCP/IP networks and paves the path for gradual implementation on the internet. If the average queue size is less than minimum threshold(minth) no packets are marked. If the average queue size is between minimum and maximum threshold incoming packets are marked with a probability Pb which is a function of average queue size (Floyd, 1993).

Connections with larger input bandwidth will have a higher probability of being marked since they can contribute to an increase in queue size as well as have larger number of input packets (received since last packet drop) (Lin, 1997).

Performance

The authors performed tests comparing Drop-Tail, RED and random-drop gateways and found that RED was not biased against burst traffic unlike the other two as well as showing larger throughput for smaller buffer-sizes (Floyd, 1993).

Fairness

In a setup with several flows where many are in slow-start mode at the same time, either max_thresh can be hit or some connections may not receive congestion indications. This will lead to unfairness.

Compatibility with Current Technology

RED is one of the most commonly used congestion-avoidance algorithms used. Cisco uses an enhanced version of RED Weighted RED(WRED) and Distributed WRED(DWRED) in its platforms (cisco.com, 2013)

Explicit Congestion Notification

If source and gateway support ECN, it provides a way to notify congestion without the need to drop packets. The client does not have to wait for timeout or three consecutive acknowledgements since gateway informs the client of congestion as it occurs, through the ECN bit set in packet header for packets that would have been otherwise dropped. When the client receives a packet with ECN set, it should take actions to avoid congestion by halving CWND. This is done only once per RTT to avoid multiple reactions to congestion indications. When a packet is dropped, TCP responds by initiating slow-start phase and retransmitting the segment.

To follow this guidelines, the following implementation was done.

• Gateways can set the ECN bit in packet header. This is to notification of congestion probability while the queue has not yet maxed.
• In response to a received ECN bit, the client sets ECN bit in the next ACK issued by the client.
• If three ACKs are received to a packet which has been acknowledged before and if the client hasn’t responded to congestion in last RTT, Fast Retransmit and recovery procedures are initiated.
• If after sending a response to an ECN, and client receives three ACKS for the same lost segment, the client will not decrease ssthresh and cwnd, and the packet for the ACK is retransmitted and Fast recovery is done by using the ACKS to set the time of outgoing packets.

Performance

In simulations done by the authors, five connections with high data/transmission rate were used. the gateway is congested. RED gateway with ECN bit setting capability was compared with drop-tail gateway and a RED gateway that drops packets to notify congestion. The results show ECN-capable gateway as having high throughput and low packet delay over various conditions regardless of the size of buffer, window size, TCP clock granularity or RED gateway variation. Tests were also done with RED g/w that drop packets. It was found under certain conditions, without ECN bit also an acceptable level of throughput and delay was achievable. Using ECN that doesn’t drop packets at highly congested networks leads to low performance. AQM implementations of ECN fixes this issue.

Fairness

Connections with larger round-trip times will have lower performance since it takes longer to identify and react to congestion due to single ECN bit notification.

Compatibility with Current Technology

Microsoft Windows (from Vista onwards), MAC OSX, Linux (2.3 onwards), FreeBSD, NetBSD, Cisco (from 12.2(8)) onwards, Sun, IBM and various tools support ECN.