Congestion Control

Congestion - offered traffic exceeds available router, link, or processing capacity.

• Packet arrivals initially queue.
• Persistent overload causes packet drops.
• Drops and delay trigger retransmissions.
• Retransmissions increase offered load.

Congestion Control and Flow Control

Flow control - prevents a sender from overloading one receiver.

Congestion control - prevents overload across routers and links.

Control Models

Open-loop control - policies fixed without current network state.

• Example
  Limit VoIP calls per link.
• Prevention-oriented.

Closed-loop control - detect congestion, report it, then adapt operation.

Detection and Feedback

Router indicators:

• Packet-drop rate.
• Queue length.
• Link utilisation.

Endpoint indicators:

• Retransmission timeout.
• Increased packet delay.

Feedback methods:

• Send a control packet to the source or previous router.
• Mark a packet travelling to the receiver.
• Let the receiver report the mark to the sender.

Congestion Avoidance in Transport Layer

TCP Congestion Window

Congestion window - sender-side limit on unacknowledged bytes.

Advertised window - receiver-side limit on unacknowledged bytes.

TCP treats loss as congestion because transmission errors are rare.

Additive Increase, Multiplicative Decrease

During congestion avoidance:

$CongestionWindow \leftarrow CongestionWindow + \frac{MSS^2}{CongestionWindow}$

per acknowledged segment. This increases $CongestionWindow$ by approximately one Maximum-Segment-Size ($MSS$) per Round-Trip-Transmission (RTT).

After a timeout:

$CongestionWindow \leftarrow 1\ MSS$

The congestion threshold becomes half the prior usable window.

Slow Start

Exponential window growth.

• Start at $CongestionWindow = 1\ MSS$.
• Increase $CongestionWindow$ by one $MSS$ for every ACK.
• Window approximately doubles each RTT.
• Use at connection start and after a timeout.

A timeout returns the window to $1\ MSS$. Slow start then repeats.

TCP Linear Increase Threshold

Slow-start threshold ($ssthresh$) - the congestion window where exponential slow-start growth changes to linear congestion-avoidance growth.

• Initial $ssthresh$: $64\text{KB}$.
• Initial $CongestionWindow$: $1\text{ MSS}$.
• While $CongestionWindow < ssthresh$: increase $CongestionWindow$ by $1\text{ MSS}$ for every ACK.
• After each RTT below $ssthresh$: $CongestionWindow$ approximately doubles.
• When $CongestionWindow \ge ssthresh$: increase $CongestionWindow$ by approximately $1\text{ MSS}$ per RTT.
• After a timeout
  Reset $CongestionWindow$ to $1\text{ MSS}$. Set $ssthresh$ to half the previous usable window.

The usable window is the smaller of the congestion window and the advertised receiver window.

Fast Retransmit and Fast Recovery

Duplicate ACKs indicate that a segment arrived out of order.

• Three duplicate ACKs trigger fast retransmit.
• Retransmit the missing segment before timeout expiry.
• Set $ssthresh$ to half the previous $cwnd$.
• Fast recovery resumes near $ssthresh$.
• Slow start is skipped.

TCP Vegas

Host-centric congestion avoidance.

• Detects increasing RTT or a flattening sending rate.
• Infers queue growth before packet loss.
• Reduces the sending rate before overflow.

Router-Assisted Congestion Avoidance

Random Early Detection (RED)

Active queue management using average queue length.

• Low average queue
  Accept packets.
• Rising average queue
  Randomly drop packets with increasing probability.
• Full queue
  Drop all arriving packets.

Early drops signal TCP before queue overflow.

Explicit Congestion Notification (ECN)

Congestion signal encoded in packet headers.

• Router marks packets instead of dropping them.
• Receiver returns the congestion indication.
• Sender reduces its rate.

Congestion Avoidance in Network Layer

Resource Preallocation

Reserve buffers and bandwidth before data transmission.

• Common in virtual-circuit networks.
• Setup selects a path and allocates resources.
• The network rejects calls lacking sufficient resources.

Traffic Shaping

Control the transmission rate and pattern.

• Sender and carrier negotiate a traffic profile during setup.
• Leaky-bucket shaping enforces a steady output rate.

Choke Packets

Router notification instructing a sender to reduce its rate.

Isarithmic Control

Cap the total packets within a subnet.

• A router needs a permit before injecting a packet.
• The permit count limits in-network packets.

Virtual Circuits and Datagrams

Virtual-circuit subnets use:

• Admission control.
• Alternative routes for new circuits.
• Reservation during circuit setup.

Datagram subnets discard packets when resources are unavailable. The sending host retransmits dropped datagrams. In virtual circuits, the previous-hop router retransmits after missing acknowledgement.

Congestion Avoidance in Data Link Layer

• Retransmission policy
• Out-of-order caching policy
• Packet discard policy
• Load Shedding
• Jitter Control

Load Shedding

Intentional packet discard during congestion.

Discard policies:

• Oldest packet.
• Newest packet.
• Low-priority packet.
• Random early discard.

Jitter Control

Jitter - variation in packet-delay / packet inter-arrival-time.

• Prioritise time-critical packets in router queues.
• Use receiver buffering to mask remaining variation.