Congestion control

Congestion happens when too many packets are sent through a network, so it starts to reach its limit.

Packet retransmission:

• fixes a symptom of network congestion:
  • a segment loss resulting from the overflowing of router buffers
• but it does not fix the cause:
  • too many sources sending data too fast at the same time

To treat the cause, mechanisms are needed to slow down or control how fast senders transmit data.

The costs of congestion

What happens as hosts increase their transmission rate and the network becomes congested?

Rising queueing delay

Two senders (hosts A and B) each send data over a single shared link to their destinations:

With:

• \( \lambda \) (lambda): data rate (bytes/sec)
  • \( \lambda_{in} \): rate entering the router
  • \( \lambda_{out} \): rate reaching the destination
• \( R \): link capacity (bytes/sec)

Assumptions:

• both hosts:
  • send data into a socket at a constant rate \( \lambda_{in} \) indefinitely
  • use a simple transport protocol (no flow control, error control, or congestion control)
• the router has unlimited buffer space

Throughput vs. delay:

Standpoint	Explanation	Diagram
Throughput (débit) number of bits/second of data that get through	If each sender transmits at \( \le R/2 \): throughput equals the sending rate all data is delivered (with some delay) If each sender transmits at \( > R/2 \): the throughput stays at \( R/2 \) per sender the link is fully used and cannot deliver more So no matter how fast they send, each host is limited to \( R/2 \) throughput.
Delay (latency) time required to deliver a packet	As sending rate approaches \( R/2 \): queues in the router start to build up because processing packets take time delay increases because the queue fills up and packets wait in line If sending rate exceeds \( R/2 \): the queue keeps growing without bound delay becomes extremely large (theoretically infinite)

Achieving a per-connection throughput of \( R/2 \):

• might be ideal from a throughput standpoint (because the link is fully utilized)
• but it is far from ideal from a delay standpoint

Cost of congestion: when traffic nears link capacity, queuing delays grow rapidly.

Losses and unnecessary retransmissions

Now we assume:

1. router buffers are finite, so packets are dropped when the buffer is full
2. connections are reliable: if a packet is dropped, the sender will retransmit it

Because of retransmissions, we distinguish two rates:

• \( \lambda_{in} \): rate of original data sent by the application (bytes/sec)
• \( \lambda'_{in} \): rate of all packets sent into the network by the transport layer, including retransmissions (bytes/sec), sometimes called the offered load

The performance now depends strongly on how retransmission is performed:

1. if Host A is able to magically determine whether or not a buffer is free in the router:
   • it sends a packet only when a buffer is free
   • no loss occurs
   • \( \lambda_{in} = \lambda'_{in} \)

2. if Host A retransmits only after correctly detecting loss:

   • i.e. it sets its timeout large enough to be virtually assured that a packet that has not been acknowledged has been lost

   Cost of congestion: the sender must perform retransmissions in order to compensate for dropped (lost) packets due to buffer overflow.

3. if Host A times out prematurely and retransmits a packet that has been delayed in the queue but not yet lost:

   • the receiver discards the retransmission (it needs only one copy of this packet)

   Cost of congestion: unneeded retransmissions by the sender in the face of large delays may cause a router to use its link bandwidth to forward unneeded copies of a packet.

Wasted transmission due to downstream packet loss

Now, four hosts send packets, each over two overlapping routers.

All hosts have the same input rate \( \lambda_{in} \).

Example:

• the A–C flow traverses R1 → R2
• along the way, it competes for resources with other flows (D–B shares R1, and B–D shares R2).

Under low load (\( \lambda_{in} \) small):

• buffer overflows are rare
• throughput ≈ offered load

Under high load (\( \lambda_{in} \) large):

• at R2, both A–C and B–D flows compete for buffer space
• as load increases:
  • more B–D packets occupy the buffer
  • fewer A–C packets get through
• in extreme cases:
  • any free buffer slot is immediately taken by a B–D packet
  • the throughput of the A–C connection at R2 goes to zero

In the high load scenario outlined above:

• whenever a packet is dropped at a downstream router
• the upstream router(s) have already spent capacity forwarding it
• that transmission effort is wasted if the packet is eventually discarded
• packets that have already traversed more hops may deserve higher priority than new ones

Packet loss due to congestion wastes capacity:

Cost of congestion: when a packet is dropped along a path, all upstream resources used to carry it are wasted.

Approaches to congestion control

Two approaches to congestion control are taken in practice:

• end-to-end congestion control:
  • the network layer provides no explicit support to the transport layer
  • presence of network congestion must be inferred on observed network behavior (e.g. packet loss and delay)
• network-assisted congestion control:
  • routers provide explicit feedback to the sender and/or receiver regarding the congestion state of the network
  • this feedback may be as simple as a single bit indicating congestion at a link