T7a

Congestion and Flow Control

Network Layers

• The discussion revisits the network layers, highlighting the progression from the physical layer (cables, space, and bits) through the link layer (Ethernet, WiFi), network layer, transport layer, to the application layer.
• Messages are segmented into packets, then frames, and finally bits for transmission.

Network Experience

• A user's network experience is the aggregate of all component paths and the interference from other traffic.
• There's a universal desire for rapid sending and receiving within a physically constrained environment.
• UDP is indifferent to network congestion, whereas TCP actively manages it.

TCP Sliding Windows

• TCP aims for reliability and high throughput by keeping the network pipe full.
• A single outstanding segment can be a bottleneck in high bandwidth-delay networks.
• Example: With a one-way delay of $50ms$, the round-trip time (RTT) is $100ms$. Sending one segment per RTT at $100ms$ equals $10 packets/s$.
• A typical packet size of $1000 bytes$ (approximately $10,000 bits$) results in $100kb/s$, which is only $0.1\%$ of a $100Mb/s$ link.
• Increasing bandwidth doesn't necessarily increase throughput without proper window management.

TCP Sliding Windows Mechanics

• TCP allows $W$ bytes to be 'outstanding' (unacknowledged) per RTT to keep the pipeline full.
• A 'window' of $W$ bytes is established, where $W \approx 2 \cdot \text{Bandwidth} \cdot \text{delay}$.
• For a $100Mb/s$ connection with a $50ms$ one-way delay, $W$ is approximately $10Mb$ (around $1MB$).
• With $10kb$ segments, this translates to $W = 1000$ segments in transit.

Sender-Side Sliding Window

• The sender buffers and sends $W$ segments, awaiting acknowledgment (ACK).
• Upon receiving an ACK, the window advances, creating space for new packets.

Receiver-Side Considerations

• The receiver typically buffers only one segment.
• If the received segment is the next in sequence, it's acknowledged.
• If not, the receiver drops it and acknowledges the last correctly received segment, prompting the sender to retransmit the necessary segments.
• The sender uses a single timer and retransmits all unacknowledged segments after a timeout.
• This approach is simple but can be inefficient.

Sender/Network Orientation

• The sender is responsible for managing transmission.
• UDP is a 'send-and-forget' protocol without control mechanisms.
• TCP aims to fill the network pipe and awaits ACKs, providing a guarantee of delivery.
• TCP is optimized to maximize network utilization.
• However, the receiver application might be overwhelmed, necessitating flow control.
• Example: Streaming HD video to a low-capacity device requires the receiver to regulate the flow.

Flow Control: Receiver-Side Sliding Windows

• The transport layer receives segments from the network and adds them to a buffer.
• The application reads from the transport buffer using recv(N-bytes).
• If the application is slow, the buffer can overflow.

Two Windows in TCP

• TCP employs two sliding windows:
  • The TCP Sender Sliding Window ($W$) is based on RTT and other network conditions.
  • The Receiver Sliding Window (WIN), also known as the Flow Control Window, indicates the number of acceptable segments/bytes.
• The sender uses the smaller of $W$ and WIN as the 'effective' window size.

Simplified Flow Control

• Sequence numbers track the sender's progress.
• Acknowledgments track the receiver's progress.
• The receiver reports its available buffer space.
• WIN reports may lag by $W$ segments due to network delays.
• The system aims for relative stability over time.

Congestion

• Congestion is analogous to a traffic jam, where something is filled up, causing delays.
• It's a dynamic condition occurring somewhere along the path.
• Senders continuing to send exacerbate congestion, leading to packet loss.
• Links themselves don't 'cause' loss but set the limits based on their capacity.

Routers/Switches and Congestion

• Congestion arises when there are too many inputs for a single output in routers or switches.

Router Buffers: Queues

• Router buffers are useful for absorbing short bursts of traffic.
• When the data-rate in exceeds the data-rate out, queues can overflow, leading to packet drops.
• FIFO (First-In, First-Out) queues are common on every interface.
• Congestion is largely driven by traffic patterns, where multiple conversations randomly send data along the same path simultaneously.
• The analysis typically assumes similar bandwidth links in and out.

Congestion Effects

• As load increases, buffers fill, causing delays to rise.
• Overflowing buffers result in packet drops and increased loss.
• Receivers request retransmission of lost packets, and senders retransmit, exacerbating congestion.
• Goodput decreases as the network becomes saturated with retransmitted packets.

Managing Capacity

• The goal is to operate just below the point of congestion damage to utilize the network to near capacity.
• This requires efficient allocation without causing congestion and fairness in bandwidth distribution.

Roles in Congestion Management

• Both the Transport and Network layers play a role.
• The Network layer (IP) detects congestion in router buffers and could provide feedback.
• The Transport layer (TCP) causes congestion but doesn't see where it occurs, so it must back off on transmissions without knowing how or when.

Statistical Multiplexing

• Allowing senders to compete can lead to uneven distribution; everyone loses in congestion.
• This is challenging due to different application behaviors, constantly changing loads, distributed congestion, and a lack of central coordination.
• Solutions must involve senders adapting concurrently and continuously to achieve efficiency and fairness.

Fairness and Efficiency

• Fairness and efficiency are sometimes conflicting goals.
• Example Scenario:
  • Fair allocation: AB = 0.5, BC = 0.5, AC = 0.5, Total = 1.5
  • Efficient allocation: AB = 1, BC = 1, AC = 0, Total = 2.0

Equal Per Flow Fairness

• If AC uses more of the network, is that fair compared to AB or BC?
• Exact fairness is difficult to achieve; avoiding starvation is more critical.

Network Bottlenecks - Unequal Paths

• When AB and AC are limited by the A-B link and BC by the B-C link, fairness becomes complex.

Max-Min Fairness

• Max-Min Fairness:
  • Bandwidth allocation such that increasing the rate of one flow will decrease the rate of a smaller flow.
  • Maximizing the minimum allocation and sharing remaining bandwidth.

Max-Min Fairness Example

• Start from zero and increase send rates until a bottleneck occurs.
• The bandwidth is allocated equally to all flows sharing the bottleneck link.

Adapting: Control Laws

• Control laws for adapting send rates:
  1. Open/Closed Loop:
     • Open: Reserve resources ahead of time.
     • Closed: Adjust based on feedback.
  2. Host or Network Driven:
     • Host manages allocation.
     • Network enforces policies.
  3. Bandwidth Allocation:
     • Rate-based: Tell application to send at a specific rate.
     • Window-based: Manage window sizes.
• TCP is Closed-Loop, Host-Driven, and Window-Based.

Two Layers Working Together

• The Network layer (IP) provides congestion feedback.
• The Transport layer (TCP) modifies sending behavior, adjusting TCP window sizes dynamically.
• Additive Increase, Multiplicative Decrease (AIMD) is used.
  • Senders gently increase rate in the absence of congestion and quickly decrease rate when congestion is detected.

AIMD Sawtooth Behavior

• AIMD results in a sawtooth pattern:
  • Slowly increase to probe the network.
  • Quickly decrease to avoid congestion collapse.

AIMD Features

• Converges towards fair and efficient allocation when all hosts use it.
• Works effectively compared to other adaptation rules.
• Requires a single signal from the network: congested or not.

Bandwidth Allocation Over Time

• Bandwidth allocation changes as flows start and stop.

Sender Signal

• How the sender gets a congestion signal:
  • Packet Loss: Obvious but reacts late.
  • Packet Delays: Detects congestion earlier but is more inferred.
  • Router Signal (Explicit Congestion Notification - ECN): Detects congestion early but requires router and host support.

Implementing AIMD

• Optimal increase/decrease values depend on the path and time.
• Several TCP components contribute to AIMD.
• ACK clocking is a key process.

ACK Clocking Process

• ACK clocking adapts the sending rate based on feedback from ACKs.
• If a sender transmits a burst of packets to a slower link, the packets buffer.

ACK Clocking Process Continued

• The ACKs return at the rate of the slowest link, signaling the sender to adjust its sending rate accordingly.

ACK Clocking Process Details

• Sender matches ACK rate, preventing continued buffer build-up.
• The 'Congestion Window' (CWND) is introduced, being smaller than W (Bandwidth * Delay).

Getting Started with TCP

• On initial TCP connection, the initial value of CWND must be determined.
• TCP Additive Increase (on start):
  • Start with CWND of $N$ bytes (one packet).
  • Increase CWND by one packet every RTT without loss.

TCP Slow-Start

• TCP Slow-Start doubles CWND every RTT (1,2,4,8,…).
• Starts slow, but quickly reaches higher CWND.

Slow-Start Overshoot

• Slow-start gets to the right CWND quickly, but will often overshoot.
• This can cause congestion and packet loss, leading to multiplicative decrease (MD) in CWND.
• To mitigate this: Define a threshold: $ssthresh = \frac{1}{2} \cdot CWND_{\text{@loss}}$

Combined Behavior

• TCP combines Slow-Start with Additive Increase:
  • Start with slow-start.
  • After the first overshoot, move to AIMD phase.
  • This maintains performance within the good $ssthresh$-$CWND$ band.

TCP Tahoe, Reno

• These are common TCP codebases from the 1990s.
• The congestion window is adjusted based on packet loss, triggering multiplicative decrease and slow start.
• Fast recovery mechanisms improve performance.

TCP Improvements

• Instead of reacting to loss, look at delays (RTT).
• TCP Vegas: Watch RTT increases to anticipate loss and back off.
• Improvements address jitter and compatibility with TCP Reno.

TCP Improvements Methods

• Employing loss alongside modified Additive Increase (AI) methods.
• AI -> BICC -> CUBIC: More assertive increase, assuming steady-ish path.
• BIC=binary, CUBIC=third-order, capped, Used in (some) Linux.

Hybrid Approaches

• Monitor RTT changes (Vegas).
• Monitor CWND (Reno).
• Google BBR: Bottleneck bandwidth and round-trip propagation time.
  • Used on YouTube, but its interoperability with other protocols is not fully clear.

Diverse TCP variants

• Various TCP variants exist, each with different feedback mechanisms, required changes, benefits, and fairness properties.

Fast Retransmit (and Recovery) Explained

• Loss -> timeouts = restart
• If timeout is too long, lose ACK clock.
• Restart: Retransmit all CWND’s of packets! And Slow start (CWND=1) then AIMD.
• If many packets arrive, receiver sends a duplicate ACK
• Third duplicate ACK triggers a resend of Seq#+1 (lost?) segment
• Fast Retransmit repairs the single segment loss.

TCP fast Recovery

• With losses/congestion, must multiplicative-decrease the CWND
• Wait for receiver to tell what caught up (Seq#)
• Take a chance: advance the sliding window as if everything (else) is ok…
• Don’t resend everything from the loss point
• MD the CWND and then continue sending from window (Fast Recovery)

TCP Advancements Overview

• TCP Reno can repair one loss per RTT
• TCP NewReno is Able to repair multiple losses per RTT
• TCP SACK (Set/Selective ACK): Improves reliability; the Receiver sends ACK set, so sender can retransmit without guessing

“Selective Repeat” ARQ

• Receiver buffers many segments, which Reduces retransmissions
• ACK what has been received in order
• ACK recv’d segments that are out of order - Any gaps indicates missing segment(s)!
• Selective ACK (SACK)
• Sender has a timer per unACKed-segment - As each timer expires, resend that segment

Router assistance: ECN

• Explicit Congestion Notification (ECN); TCP drives network to congestion and backs off - Prefer to detect congestion before it happens
• Really simple, in-band signalling
  1. Router notices queues getting full
  2. Marks packets in forward queue (ECN “congestion looming” – IP header)
  3. Receiver marks TCP segments sent back to Sender (ACK or normal)
  4. Sender notices, and backs down (MD of CWND)