Untitled

Congestion Control in Network Systems

Overview of Network Systems Congestion Control

  • Instructor: Pieter-Tjerk de Boer
  • Course: UT/EWI - Network Systems 2026
  • Exam Information: 3rd exam approaching in 2 weeks covering less material for 1.5 hours.
  • Weekly Topics:
    • Week 1: Resource Allocation
    • Week 2: Network Security (starting this Friday)
  • Challenge: Next week Wednesday, half day exam scheduled.
  • Caution: Students may find the 3rd exam harder than the first two.

Key Themes in Resource Allocation

  • Questions in Resource Allocation:
    • How to share resources fairly?
    • How to prevent network overload? → Introduces congestion control.
    • Ensuring effective audio/video performance | Focus on Quality of Service (QoS) in upcoming lecture.

Congestion Control Agenda for Today

  1. Define congestion.
  2. Discuss Additive Increase, Multiplicative Decrease (AIMD) congestion control.
  3. Calculate resultant speed using the TCP Friendly formula.
  4. Introduce slow start for rapid initial data transmission.
  5. Maintain data flow during packet loss using triple duplicate acknowledgment (ACK) and fast recovery techniques.
  6. Address issues in long fat pipes.
  7. Explore alternative approaches to congestion control:
    • TCP Vegas: monitors delay to detect congestion.
    • TCP Cubic: utilizes a third-power polynomial to manage the congestion window.

Understanding Congestion

Problem Identification
  • Congestion in a Single Queue:
    • Regular Packet Arrival: Packets arrive at a constant rate with a transmission time of 1 ms per packet.
    • Relationship between packet delay and arrival rate analyzed through queue dynamics.
    • Random Packet Arrival: Transmission patterns are unpredictable leading to variations in queue delays.
Finite Queue Dynamics
  • Behavior of Finite Queues:
    • If the queue is full, packets are dropped, preventing infinite delays but requiring retransmissions, leading to extra load on both endpoints and routers.
Networking Congestion Summary
  • Cause of Congestion: Sending packets too quickly into the network.
  • Effects of Congestion:
    • Leads to long queues in routers → increased delays.
    • Causes overflow in routers → packet loss occurs.
    • Lost packets necessitate retransmissions, wasting previously allocated bandwidth.
    • Long delays can trigger unnecessary timeouts and redundant retransmissions.
    • Infinite buffers are not a solution; without feedback, networks risk congestion collapse.

Classification of Congestion Control Approaches

  • Router-centric vs. Host-centric.
  • Reservation-based vs. Feedback-based.
  • Window-based vs. Rate-based.

Congestion Control Mechanism in TCP

Algorithm Requirements
  • Need an algorithm that:
    • Learns the optimal data rate.
    • Adapts to changing conditions.
    • Fairly shares bandwidth among users.
Congestion Control Principles in TCP
  • TCP Control:
    • Host-centric, feedback-based, and window-based mechanism.
    • Detects packet drops as indicators of congestion.
    • Adjusts the congestion window (cwnd) according to network feedback:
    • Controls the amount of unacknowledged data in the network, thereby managing buffer space usage within routers.
Congestion Window Control Algorithm Example
  • Given situations of:
    • Packet loss: Decrease the congestion window.
    • No packet loss during a round-trip time (RTT): Increase the congestion window.

Additive Increase, Multiplicative Decrease (AIMD)

AIMD Detailed Mechanism
  • TCP maintains cwnd in bytes.
  • MSS (Maximum Segment Size) impacts adjustments:
    • Increase cwnd by 1 MSS each RTT when no loss occurs.
    • Halve cwnd on packet loss.
AIMD Fairness Evaluation Question
  • Evaluate bandwidth distribution with parameters:
    • Increase cwnd by multiplying by 1.5 every RTT, decrease by 10 packets on loss.
  • Options listed indicating potential outcomes of bandwidth allocation.

TCP Throughput Estimation Based on AIMD

  • Formula:
    • Given loss ratio ρ\rho, the maximum window is defined as:
      W=83ρW = \frac{8}{3\rho}
    • The average sending rate:
      rate≈32⋅MSS⋅1RTT⋅ρ\text{rate} \approx \frac{3}{2} \cdot \text{MSS} \cdot \frac{1}{\text{RTT}} \cdot \sqrt{\rho}
    • Importance of TCP friendliness for differentiating between TCP and UDP bandwidth usage in the same conditions.

Slow Start Mechanism in TCP

Objectives of Slow Start
  • Rapidly identify available network capacity.
  • Parameters and states based on CongWnd thresholds and packet loss dynamics.
Slow Start Dynamics
  • Maintain a congestion window increment strategy based on RTT and acknowledgment conditions.

Fast Retransmit and Fast Recovery Mechanisms

Objectives and Techniques
  • Fast Retransmit: By utilizing three duplicate ACKs, retransmit packets immediately instead of waiting for timeouts.
  • Fast Recovery: Skip the slow start phase following a fast retransmit, thus efficiently utilizing network capacity.

Summary of TCP Congestion Control ("New Reno")

  1. Slow Start: Quickly ramp up until cwnd reaches ssthr.
  2. Congestion Avoidance: Upon reaching ssthr, change strategy to additive increase.
  3. Fast Recovery: Post the triple duplicate ACK condition, adjust thresholds and cwnd effectively.
  4. Timeout Handling: Resets configured thresholds and maintains a minimum data rate.

Issues with TCP and Long Fat Pipes

Identifying Challenges
  • High round-trip times (RTT) lead to long durations for cwnd growth, prohibiting efficient bandwidth utilization:
    • Example metrics based on RTT (100 ms), bandwidth (1 Gbps), and packet size (1500 bytes) demonstrate the inefficiency.
    • Estimated requirements for packed queues to fulfill bandwidth expectations lead to impractical scenarios in sustaining low packet loss rates.

Improvement Initiatives for TCP Congestion Control

TCP Variants Proposed to Address Long Fat Pipe Problems
  • Numerous TCP variants have been conceptualized to enhance throughput and fairness:
    • Examples include Agile-SD TCP, Binary Increase, C2TCP, Compound TCP, High Speed TCP, TCP BBR, TCP CUBIC, TCP Vegas, and many more.

TCP Vegas Principles

Principles Governing Throughput and Queue Interactions
  • As queue lengths increase, measured round-trip time escalates signaling congestion; window size adjustments adhere to this observation for effective control.

TCP Cubic Overview (Current Linux Default)

Mechanism of TCP CUBIC
  • Upon triple duplicate ACK:
    • Set the maximum previous window (Wmax).
    • Reduce congestion window by 30%.
    • Calculate the new window based on the cubic function:
      W(t)=0.4imes(t−K)3+WmaxW(t) = 0.4 imes (t - K)^3 + Wmax
      where t indicates time since the last acknowledgment.

Conclusion of Today's Material

  • Key Topics Covered:
    • Understanding and defining congestion.
    • Exploring AIMD control approach.
    • Using TCP friendly formulas for speed calculation.
    • Implementing slow start mechanisms.
    • Maintaining data flow during single packet loss incidents via refined TCP methods.
    • Discussing properties and issues related to long fat pipes, including alternative approaches like TCP Vegas and TCP Cubic.