TCP State Machine & Congestion Control Mechanics

The Transmission Control Protocol (RFC 793, RFC 5681, RFC 7323) represents one of the most intellectually sophisticated achievements in computer systems engineering. Operating over an inherently unreliable, packet-dropping, best-effort datagram substrate (the Internet Protocol), TCP provides an abstract, bidirectional, byte-stream communication channel characterized by four fundamental invariants:

1. Guaranteed In-Order Delivery: Application runtimes receive contiguous byte streams without reordering or duplication.
2. Reliability via Retransmission: Unacknowledged or corrupted segments are systematically resent.
3. Flow Control: Receivers protect their local socket buffers from being overrun by faster senders.
4. Congestion Control: Senders dynamically throttle transmission rates to prevent collapse of intermediate network switches and shared transit links.

While basic networking introductions treat TCP as a simplistic 3-way handshake followed by linear data transfer, modern distributed systems engineering requires an exacting, mathematically rigorous command of the complete 11-state transition matrix, connection teardown mechanics (TIME_WAIT and CLOSE_WAIT pathologies), and the algorithmic evolution of congestion control from Chiu-Jain phase-plane convergence to TCP Reno, TCP Cubic, and model-based Bottleneck Bandwidth and RTT (BBR).

1. The Complete 11-State TCP Finite State Machine (FSM)#

A TCP endpoint progresses through a deterministic series of 11 formal operational states defined in RFC 793:

+---------------------------------------------------------------------------------------+
|                               TCP State Transition Diagram                            |
|                                                                                       |
|                             +---------+                                               |
|                             | CLOSED  |                                               |
|                             +----+----+                                               |
|                     Passive OPEN |    | Active OPEN                                   |
|                      Create TCB  |    | Send SYN                                      |
|                                  v    v                                               |
|                             +---------+  Send SYN-ACK  +----------+                   |
|                             | LISTEN  | -------------> | SYN-SENT |                   |
|                             +----+----+                +----+-----+                   |
|                      Receive SYN |                          | Receive SYN-ACK         |
|                     Send SYN-ACK |                          | Send ACK                |
|                                  v                          v                         |
|                             +---------+                +----------+                   |
|                             |SYN-RCVD |                |ESTABLISHED                   |
|                             +----+----+                +----+-----+                   |
|                      Receive ACK |                          |                         |
|                                  v                          |                         |
|                             +---------+                     |                         |
|                             |ESTABLISHED|<------------------+                         |
|                             +----+----+                                               |
|                                  |                                                    |
|        Active CLOSE: Send FIN    |    Passive CLOSE: Receive FIN, Send ACK            |
|                                  +-----------------------+                            |
|                                  |                       |                            |
|                                  v                       v                            |
|                            +-----------+           +------------+                     |
|                            |FIN-WAIT-1 |           | CLOSE-WAIT |                     |
|                            +-----+-----+           +-----+------+                     |
|                     Receive ACK  |                       | Application Close:         |
|                     of our FIN   |                       | Send FIN                   |
|                                  v                       v                            |
|                            +-----------+           +------------+                     |
|                            |FIN-WAIT-2 |           |  LAST-ACK  |                     |
|                            +-----+-----+           +-----+------+                     |
|                      Receive FIN |                       | Receive ACK of FIN         |
|                      Send ACK    |                       v                            |
|                                  v                 +------------+                     |
|                            +-----------+           |   CLOSED   |                     |
|                            | TIME-WAIT |           +------------+                     |
|                            +-----+-----+                                              |
|                      2 MSL Timer |                                                    |
|                      Expires     v                                                    |
|                            +-----------+                                              |
|                            |  CLOSED   |                                              |
|                            +-----------+                                              |
+---------------------------------------------------------------------------------------+

Connection Establishment States#

1. CLOSED: Fictional starting point; no Transmission Control Block (TCB) exists in kernel memory.
2. LISTEN: The server creates a TCB, allocates a passive socket, binds to an IP/port, and listens for incoming connection requests.
3. SYN-SENT: The client executes an active connect(), chooses an Initial Sequence Number (ISN), transmits a SYN segment, and waits for server acknowledgment.
4. SYN-RCVD: The server receives the client's SYN, records the client's ISN, chooses its own ISN, transmits a SYN-ACK segment, and enters the half-open SYN-RCVD queue.
5. ESTABLISHED: The 3-way handshake is finalized. The connection is ready for full-duplex data streaming.

Connection Termination States & Pathological Diagnostics#

Graceful teardown in TCP is asymmetric; each direction of data transfer must be closed independently:

1. FIN-WAIT-1: An endpoint initiates an active close (close() or shutdown(SHUT_WR)), sending a FIN control segment.
2. CLOSE-WAIT: The passive peer receives the FIN, emits an immediate ACK, and informs the local application runtime that the remote peer has terminated writing.

- Production Pathology: Sockets persisting in CLOSE-WAIT signify an application runtime bug. The operating system kernel has acknowledged the closure, but the user-space application code (e.g., Python, Node.js, Java) has leaked the socket handle by failing to invoke socket.close(). These orphaned descriptors accumulate until the operating system encounters process file descriptor exhaustion (EMFILE).

1. FIN-WAIT-2: The active closer receives the ACK acknowledging its own FIN and waits for the remote peer to finish streaming data and transmit its corresponding FIN.

- Production Pathology: If the remote application hangs in CLOSE-WAIT and never sends its FIN, the active closer can become stranded in FIN-WAIT-2 indefinitely. Linux mitigates this via tcp_fin_timeout (default 60 seconds), after which the kernel forcefully purges the orphaned TCB.

1. CLOSING: Rare state where both peers initiate simultaneous active closes, transmitting FIN segments concurrently prior to receiving the other's ACK.
2. LAST-ACK: The passive closer finally finishes transmitting local buffered data, sends its FIN, and waits for the final ACK from the active closer.
3. TIME-WAIT (The 2MSL State):

- Entered by whichever endpoint executed the active close after receiving the remote peer's FIN and sending the final ACK.

- The endpoint starts a countdown timer set to 2 × MSL (Maximum Segment Lifetime). RFC 793 historically defined MSL as 120 seconds (yielding a 4-minute TIME-WAIT); modern Linux kernels hardcode MSL to 30 or 60 seconds (yielding a 60-to-120-second TIME-WAIT).

Why TIME-WAIT Is Architecturally Essential

Software engineers frequently attempt to eliminate TIME-WAIT (via aggressive TCP tuning or SO_LINGER), viewing it as wasted memory. However, TIME-WAIT satisfies two vital protocol invariants:

1. Guaranteeing Reliable Teardown (Final ACK Delivery):

- If the active closer's final ACK is dropped in transit across the Internet, the remote peer (stuck in LAST-ACK) will timeout and retransmit its FIN.

- If the active closer immediately transitioned to CLOSED and recycled the socket, the arriving retransmitted FIN would find no matching TCB and trigger an ungraceful RST (Connection Reset) error on the remote server, corrupting transactional state. By remaining in TIME-WAIT, the active closer can safely re-emit the final ACK.

1. Preventing Delayed Stale Packet Ingestion:

- Packets can become delayed in intermediate router buffers or multi-path routing loops.

- If a connection between {ClientIP:Port, ServerIP:Port} closes, and an identical 4-tuple socket is immediately re-opened, a delayed duplicate segment from the previous incarnation of the connection could arrive and be injected into the new stream, corrupting data integrity.

- The 2MSL interval guarantees that all ghost segments traversing the global Internet have expired (their IP TTL decremented to 0) before the identical 4-tuple can be legally reused.

2. Flow Control vs. Congestion Control: The Effective Window#

A universal point of confusion is the distinction between Flow Control and Congestion Control:

+---------------------------------------------------------------------------------------+
|                               Window Dynamics Architecture                            |
|                                                                                       |
|   +-------------------------------------------------------------------------------+   |
|   | SENDER RUNTIME                                                                |   |
|   |                                                                               |   |
|   |   +----------------------------------+   +--------------------------------+   |   |
|   |   | Congestion Window (cwnd)         |   | Advertised Recv Window (rwnd)  |   |   |
|   |   | (Dynamic internal state variable |   | (Dynamic feedback from remote  |   |   |
|   |   |  measuring network link capacity)|   |  receiver socket buffer space) |   |   |
|   |   +-----------------+----------------+   +---------------+----------------+   |   |
|   |                     \                                    /                    |   |
|   |                      \                                  /                     |   |
|   |                       v                                v                      |   |
|   |                   +----------------------------------------+                  |   |
|   |                   | Effective Transmission Window (W_eff)  |                  |   |
|   |                   |      W_eff = min(cwnd, rwnd)           |                  |   |
|   |                   +-------------------+--------------------+                  |   |
|   +---------------------------------------|---------------------------------------+   |
|                                           | Unacknowledged in-flight bytes            |
|                                           v                                           |
|                                 ======================                                |
|                                 Physical Network Pipe                                 |
+---------------------------------------------------------------------------------------+

1. Flow Control (rwnd):

- A receiver-driven feedback mechanism.

- The receiver communicates its available socket buffer space in every ACK header via the Window Size field (multiplied by the negotiated Window Scale factor).

- If the receiver application processes bytes slowly, rwnd shrinks. If rwnd = 0, transmission completely halts.

1. Congestion Control (cwnd):

- A sender-driven probing mechanism.

- The sender maintains an internal state variable, cwnd (Congestion Window), which estimates the maximum number of unacknowledged bytes the intervening network paths can support without dropping packets or inducing queue bufferbloat.

1. The Effective Transmission Window (W_{eff}):

At any instant in time, the volume of unacknowledged data the sender is permitted to transmit is strictly bounded by:

W_{eff} = min(cwnd, rwnd)

3. The Mathematics of Congestion Control: Chiu-Jain Convergence & AIMD#

Why do Internet transport protocols use Additive Increase, Multiplicative Decrease (AIMD)? In 1989, Dah-Ming Chiu and Raj Jain published their seminal mathematical proof demonstrating why AIMD is the only linear control algorithm that converges to both Efficiency (optimal link utilization) and Fairness (equitable bandwidth distribution among competing flows).

Flow 2 Bandwidth (x2)
  ^
  |               / Fairness Line (x1 = x2)
  |              /
  |             /           Efficiency Line (x1 + x2 = C)
  |            /       .---'
  |           /    .--'
  |          / .--'
  |         .-'   AIMD Vector:
  |       .' \    Add: (x1+1, x2+1) -> 45-degree trajectory parallel to fairness
  |     .'    \   Drop: (x1/2, x2/2) -> Trajectory towards origin
  |   .'       \
  |  /          v
  | /
  +--------------------------------------------------> Flow 1 Bandwidth (x1)

The Chiu-Jain Phase-Plane Vector Proof#

Consider two independent TCP flows, Flow 1 and Flow 2, sharing a bottleneck link of capacity C. Let x_1(t) and x_2(t) represent their allocated transmission rates at time t.

We define two fundamental objective lines in the two-dimensional state space:

1. Efficiency Line: x_1 + x_2 = C. Any point below this line represents under-utilization; any point above represents network congestion and buffer overflow.
2. Fairness Line: x_1 = x_2. Every point along this line represents perfectly equitable sharing.
3. The Optimal Operating Point: The intersection of the two lines:

x_1^ = x_2^ = C / 2

Now consider how different feedback control algorithms behave upon receiving binary congestion feedback (1 = overload/drop, 0 = underload/success):

Case 1: Multiplicative Increase, Multiplicative Decrease (MIMD)

• When no loss: x_i(t+1) = a_I · x_i(t) where a_I > 1.
• When loss occurs: x_i(t+1) = b_D · x_i(t) where 0 < b_D < 1.
• Vector Trajectory: Both increase and decrease vectors pass directly through the origin (0,0). The ratio x_1(t) / x_2(t) remains mathematically invariant over time. MIMD oscillates along a ray from the origin; it never moves towards the fairness line. A flow that starts with more bandwidth retains its unfair advantage indefinitely.

Case 2: Additive Increase, Additive Decrease (AIAD)

• When no loss: x_i(t+1) = x_i(t) + a_I.
• When loss occurs: x_i(t+1) = x_i(t) - b_D.
• Vector Trajectory: Both increase and decrease vectors are parallel to the 45-degree fairness line. The system oscillates in a fixed limit cycle parallel to the fairness line, never converging to optimal fairness.

Case 3: Additive Increase, Multiplicative Decrease (AIMD)

• Additive Increase (Probe):

x_i(t+1) = x_i(t) + α (α > 0)

The state vector moves along a 45-degree trajectory (slope = 1), parallel to the fairness line.

• Multiplicative Decrease (Backoff):

x_i(t+1) = β · x_i(t) (0 < β < 1, typically β = 0.5)

The state vector points directly toward the coordinate origin (0,0).

• The Convergence Dynamic:

When a drop occurs, the flow consuming more bandwidth suffers a larger absolute reduction than the flow consuming less bandwidth:

Δ x_1 = (1 - β) x_1, Δ x_2 = (1 - β) x_2

If x_1 > x_2, then Δ x_1 > Δ x_2. The absolute gap between the flows shrinks:

|x_1(t+1) - x_2(t+1)| = β |x_1(t) - x_2(t)|

4. Classical Loss-Based Algorithms: Reno to Cubic#

For decades, the Internet relied exclusively on loss-based congestion control, which operates on the premise that packet loss is the sole reliable indicator of network congestion.

TCP Reno (RFC 5681)#

TCP Reno structures its control loop around two core phases governed by the Slow Start Threshold (ssthresh):

cwnd (Segments)
  ^
  |                                 /\ (Loss Event: cwnd drops to ssthresh)
  |                                /  \
  |                ssthresh ----> +----+-----------------
  |                              /     | \
  |                             /      |  \ Linear Additive Increase
  |                            /       |   \ (Congestion Avoidance)
  |                           /        |
  |             Exponential  /         |
  |             Slow Start  /          |
  +------------------------+-----------+--------------------> Time

1. Slow Start:

- Initial state (or following an RTO timeout). Starts with cwnd = 10 segments (RFC 6928).

- For every incoming cumulative ACK:

cwnd = cwnd + 1 MSS

- For every Round-Trip Time (RTT), the congestion window doubles:

cwnd(t+1) = 2 × cwnd(t)

- Exponential growth continues until cwnd >= ssthresh.

1. Congestion Avoidance (Additive Increase):

- Once cwnd >= ssthresh, exponential probing ceases to prevent buffer overfill.

- For each incoming ACK:

cwnd = cwnd + (1 / cwnd) MSS

- Across a full RTT window of ACKs, cwnd expands linearly by exactly 1 MSS per RTT:

cwnd(t+1) = cwnd(t) + 1 MSS

1. Loss Recovery:

- Fast Retransmit / Fast Recovery (3 Duplicate ACKs):

The sender infers a single packet drop while intermediate buffers remain healthy:

ssthresh = max(cwnd / 2, 2 MSS)

cwnd = ssthresh + 3 MSS

Inflates cwnd by 1 MSS for each additional duplicate ACK. Upon receipt of a new ACK, deflates cwnd = ssthresh and resumes linear congestion avoidance.

- Retransmission Timeout (RTO):

Indicates total network failure or queue collapse:

ssthresh = cwnd / 2

cwnd = 1 MSS

Re-enters Slow Start from the floor.

TCP Cubic (RFC 8312)#

While Reno functions well on low-speed networks, on modern high-speed, long-distance networks (Long Fat Networks, or LFNs), Reno's additive increase of 1 MSS per RTT is unacceptably slow. For example, recovering a 10 Gbps flow across a 100 ms link after a drop requires over 1 hour of linear probing.

Linux adopted TCP Cubic as its default congestion control algorithm. Cubic decouples window growth from round-trip time by modeling cwnd as a cubic polynomial function of elapsed real time t since the last congestion event:

W_{cubic}(t) = C · (t - K)^3 + W_{max}

where:

• W_{max}: The congestion window size in MSS immediately prior to the most recent congestion drop.
• C: A scaling parameter (standardized at 0.4).
• t: Elapsed wall-clock time in seconds since the congestion event.
• K: The calculated time required for the cubic function to ramp the window back up to W_{max} without any further loss:

K = ∛((W_max · β) / C)

where β is Cubic's multiplicative decrease factor (β = 0.7; Cubic backs off by 30% rather than Reno's 50%).

cwnd
  ^
  |                        W_max
  |                          :   Concave Growth       Convex Growth
  |                     .....+.....                   .-------------
  |                   .'     :     `.               .'
  |                 .'       :       `.           .'
  |               .'         :         `.       .'
  |  Loss Event .'           :           `.   .'
  |     v     .'             :             `.'
  |    +----+'               :              + (Inflection point: t = K)
  +----+---------------------+----------------------------------------> Time (t)

Cubic Growth Dynamics:

1. Concave Region (t < K): As t approaches K, window growth flattens asymptotically. This stability period allows intermediate network buffers to drain and stabilizes queue lengths near the link's maximum capacity.
2. Inflection Point (t = K): The derivative of the cubic function hits zero; cwnd matches W_{max}.
3. Convex Region (t > K): If no loss occurs at W_{max}, the cubic function curves upwards aggressively, rapidly probing for newly available bandwidth on upgraded or less-utilized links.

5. Modern Model-Based Congestion Control: BBR (Bottleneck Bandwidth and RTT)#

Despite Cubic's mathematical sophistication, it shares an inherent vulnerability with all loss-based algorithms: Bufferbloat.

In 2016, Neal Cardwell, Yuching Cheng, C. Stephen Gunn, Soheil Hassas Yeganeh, and Van Jacobson (Google) published BBR (Bottleneck Bandwidth and RTT).

Delivery Rate
      ^
      |                Kleinrock's Optimal Point
      |                    (BtlBw, RTprop)
BtlBw +--------------------------*======================== (Throughput Saturated)
      |                         /|
      |                        / |
      |                       /  |
      |                      /   |
      +---------------------+----+-----------------------> Inflight Data
                            :    :
                            :    +--- Bufferbloat / Loss starts here
                            +-------- BDP = BtlBw * RTprop

The Inherent Flaw of Loss-Based Control#

Loss-based algorithms (Reno, Cubic) increase cwnd until intermediate router buffers are 100% full and packets are forcefully dropped.

• The Bufferbloat Catastrophe: Over-buffered commercial switches and cable modems do not drop packets when the physical link is saturated; they buffer tens of thousands of packets in giant FIFO queues. RTT surges from 20 ms to 2,000 ms, introducing massive latency while throughput remains completely flat.
• Furthermore, on modern wireless networks (5G, Wi-Fi), non-congestion packet loss (e.g., radio interference, antenna handoffs) causes loss-based algorithms to falsely halve their window, crippling wireless throughput by up to 90%.

Kleinrock's Optimal Operating Point#

In 1979, Leonard Kleinrock proved that the optimal operating point for any packet network is defined by the simultaneous satisfaction of two physical constraints:

1. Bottleneck Bandwidth (BtlBw): The maximum physical data rate of the slowest link along the end-to-end path.
2. Round-Trip Propagation Time (RTprop): The minimum possible round-trip delay imposed by physical speed-of-light propagation through fiber and silicon switching delays (when all queue buffers are empty).

The volume of data required to fully saturate the path without creating an artificial queue is the Bandwidth-Delay Product (BDP):

BDP = BtlBw × RTprop

• If Inflight < BDP: The bottleneck link is underutilized; transmission capacity is wasted.
• If Inflight > BDP: The bottleneck link cannot transmit any faster; the excess bytes accumulate in router queues, generating delay without increasing throughput.

How BBR Operates#

BBR does not treat packet loss as congestion. Instead, it continuously constructs an explicit real-time physical model of the network path:

• BtlBw Estimation: BBR measures the maximum delivery rate over a moving window of recent transaction rounds:

BtlBw = max_{t ∈ [T-10, T]} ( ΔDelivered / Δt )

• RTprop Estimation: BBR tracks the absolute minimum observed RTT over a longer window (typically 10 seconds):

RTprop = min_{t ∈ [T-10s, T]} (RTT_t)

• Rate-Based Pacing:

BBR abandons bursty TCP ACK-clocking. Instead, it computes an explicit Pacing Rate:

Pacing Rate = pacing_gain × BtlBw

• Inflight Bounding:

BBR caps the maximum in-flight unacknowledged bytes using a Target Congestion Window:

Target cwnd = cw_gain × BDP

By continuously pacing packets at precisely the rate the bottleneck link can drain them, BBR achieves maximum theoretical throughput while driving queue occupancy and queuing delay close to zero.

6. Programmatic TCP State Machine & Congestion Engine in Python#

The following script models an operational TCP connection, simulating both Reno AIMD dynamics and BBR pacing models across variable network conditions:

# Programmatic TCP Reno vs BBR Congestion Control Simulation
import math
from typing import List, Tuple

class TCPReno:
    def __init__(self, initial_cwnd: float = 10.0, ssthresh: float = 64.0, mss: int = 1460):
        self.cwnd = initial_cwnd          # in MSS units
        self.ssthresh = ssthresh          # in MSS units
        self.mss = mss
        self.state = "SLOW_START"

    def on_ack_received(self):
        # Evaluates window expansion on acknowledgment arrival
        if self.cwnd < self.ssthresh:
            # Slow start: exponential doubling per RTT
            self.cwnd += 1.0
            self.state = "SLOW_START"
        else:
            # Congestion avoidance: additive increase (+1 MSS per RTT)
            self.cwnd += (1.0 / self.cwnd)
            self.state = "CONGESTION_AVOIDANCE"

    def on_loss_event(self, triple_duplicate_ack: bool = True):
        # Evaluates window backoff upon packet loss
        if triple_duplicate_ack:
            # Fast Retransmit / Fast Recovery
            self.ssthresh = max(self.cwnd / 2.0, 2.0)
            self.cwnd = self.ssthresh
            self.state = "FAST_RECOVERY"
        else:
            # Retransmission Timeout (RTO)
            self.ssthresh = max(self.cwnd / 2.0, 2.0)
            self.cwnd = 1.0
            self.state = "SLOW_START"

class TCPBBRModel:
    def __init__(self, btl_bw_bps: float, rtprop_sec: float, mss: int = 1460):
        self.btl_bw = btl_bw_bps          # Bottleneck Bandwidth in bits/sec
        self.rtprop = rtprop_sec          # Min propagation delay in seconds
        self.mss = mss
        self.pacing_gain = 1.0
        self.cwnd_gain = 2.0

    @property
    def bdp_bytes(self) -> float:
        # Bandwidth-Delay Product in bytes
        return (self.btl_bw * self.rtprop) / 8.0

    @property
    def pacing_rate_bps(self) -> float:
        # Transmission pacing rate
        return self.pacing_gain * self.btl_bw

    @property
    def target_cwnd_bytes(self) -> float:
        # Maximum allowed in-flight bytes
        return self.cwnd_gain * self.bdp_bytes

    def simulate_rtt_cycle(self, measured_delivery_rate: float, measured_rtt: float):
        # Update path model dynamically
        if measured_delivery_rate > self.btl_bw:
            self.btl_bw = measured_delivery_rate
        if measured_rtt < self.rtprop:
            self.rtprop = measured_rtt

7. Checkpoint Practice Problems & Applied Walkthroughs#

Apply theoretical principles to four comprehensive multi-step mathematical problems.

Problem 1: Chiu-Jain Convergence of AIMD vs. MIMD#

Two competing network flows, Flow 1 and Flow 2, share an unbuffered 100 Mbps bottleneck link (C = 100 Mbps). Initial transmission rates are:

• x_1(0) = 20 Mbps
• x_2(0) = 60 Mbps

The system experiences synchronous feedback every RTT cycle. When the aggregate bandwidth exceeds capacity (x_1 + x_2 > C), a congestion signal is emitted to both senders.

We compare two control algorithms:

1. Algorithm A (MIMD):

- When no congestion: Multiply rate by a_I = 1.2.

- When congestion: Multiply rate by b_D = 0.5.

1. Algorithm B (AIMD):

- When no congestion: Add α = 10 Mbps.

- When congestion: Multiply rate by β = 0.5.

Calculations Required:

1. Compute the state vector (x_1, x_2) for both algorithms across the first 4 cycles.
2. Evaluate the Chiu-Jain Fairness Index J after each cycle:

J(x_1, x_2) = ((x_1 + x_2)^2) / (2 · (x_1^2 + x_2^2))

1. Prove whether MIMD or AIMD converges toward optimal fairness (J = 1.0).

Step-by-Step Solution:

Initial State Evaluation:

• Aggregate initial throughput: x_1(0) + x_2(0) = 20 + 60 = 80 Mbps ≤ 100 Mbps (No congestion).
• Initial Fairness Index:

J(0) = ((20 + 60)^2) / (2 · (20^2 + 60^2)) = (80^2) / (2 · (400 + 3600)) = (6400) / (2 · 4000) = (6400) / (8000) = 0.800

Simulation of Algorithm A (MIMD)

Cycle 1:

• Aggregate was 80 Mbps < 100 Mbps -> No congestion. Increase by factor 1.2:

x_1(1) = 20 × 1.2 = 24.0 Mbps

x_2(1) = 60 × 1.2 = 72.0 Mbps

x_1(1) + x_2(1) = 96.0 Mbps ≤ 100 Mbps

• Fairness:

J_A(1) = ((24 + 72)^2) / (2 · (24^2 + 72^2)) = (96^2) / (2 · (576 + 5184)) = (9216) / (2 · 5760) = (9216) / (11520) = 0.800

Cycle 2:

• Aggregate was 96.0 Mbps < 100 Mbps -> No congestion. Increase by factor 1.2:

x_1(2) = 24.0 × 1.2 = 28.8 Mbps

x_2(2) = 72.0 × 1.2 = 86.4 Mbps

x_1(2) + x_2(2) = 115.2 Mbps > 100 Mbps -> CONGESTION EVENT!

• Fairness:

J_A(2) = ((28.8 + 86.4)^2) / (2 · (28.8^2 + 86.4^2)) = 0.800

Cycle 3:

• Congestion occurred -> Apply multiplicative decrease b_D = 0.5:

x_1(3) = 28.8 × 0.5 = 14.4 Mbps

x_2(3) = 86.4 × 0.5 = 43.2 Mbps

x_1(3) + x_2(3) = 57.6 Mbps ≤ 100 Mbps

• Fairness:

J_A(3) = ((14.4 + 43.2)^2) / (2 · (14.4^2 + 43.2^2)) = 0.800

Mathematical Verdict for MIMD: The ratio x_1(t) / x_2(t) = 20 / 60 = 1 / 3 is permanently conserved across every multiplication operation. The fairness index remains strictly locked at 0.800. MIMD completely fails to converge to fairness.

Simulation of Algorithm B (AIMD)

Cycle 1:

• Aggregate was 80 Mbps < 100 Mbps -> No congestion. Add α = 10 Mbps:

x_1(1) = 20 + 10 = 30.0 Mbps

x_2(1) = 60 + 10 = 70.0 Mbps

x_1(1) + x_2(1) = 100.0 Mbps ≤ 100 Mbps

• Fairness:

J_B(1) = ((30 + 70)^2) / (2 · (30^2 + 70^2)) = (100^2) / (2 · (900 + 4900)) = (10000) / (2 · 5800) = (10000) / (11600) ≈ 0.8621

Cycle 2:

• Aggregate is 100.0 Mbps ≤ 100 Mbps -> No congestion yet. Add α = 10 Mbps:

x_1(2) = 30 + 10 = 40.0 Mbps

x_2(2) = 70 + 10 = 80.0 Mbps

x_1(2) + x_2(2) = 120.0 Mbps > 100 Mbps -> CONGESTION EVENT!

• Fairness:

J_B(2) = ((40 + 80)^2) / (2 · (40^2 + 80^2)) = (14400) / (2 · (1600 + 6400)) = (14400) / (16000) = 0.900

Cycle 3:

• Congestion occurred -> Apply multiplicative decrease β = 0.5:

x_1(3) = 40.0 × 0.5 = 20.0 Mbps

x_2(3) = 80.0 × 0.5 = 40.0 Mbps

x_1(3) + x_2(3) = 60.0 Mbps ≤ 100 Mbps

• Fairness:

J_B(3) = ((20 + 40)^2) / (2 · (20^2 + 40^2)) = (3600) / (2 · (400 + 1600)) = (3600) / (4000) = 0.900

Cycle 4:

• Aggregate was 60.0 Mbps < 100 Mbps -> Add α = 10 Mbps:

x_1(4) = 20 + 10 = 30.0 Mbps

x_2(4) = 40 + 10 = 50.0 Mbps

x_1(4) + x_2(4) = 80.0 Mbps

• Fairness:

J_B(4) = ((30 + 50)^2) / (2 · (30^2 + 50^2)) = (6400) / (2 · (900 + 2500)) = (6400) / (6800) ≈ 0.9412

Mathematical Conclusion:

With AIMD, the fairness index progresses monotonically:

0.800 → 0.862 → 0.900 → 0.941 → ... → 1.000

The absolute difference |x_1 - x_2| shrank from 40 Mbps to 20 Mbps. AIMD mathematically guarantees convergence to perfect fairness.

Problem 2: TCP Cubic Window Growth Dynamics#

A TCP Cubic flow operates across a high-speed inter-datacenter link.

• Path Attributes: RTT = 50 ms (0.050 seconds).
• Congestion Event: The connection experiences a packet drop when its congestion window reaches W_{max} = 8,000 segments.
• Cubic Parameters: C = 0.4, β = 0.7.
• Calculations Required:

1. Determine the window size cwnd immediately following multiplicative backoff.

2. Compute the scaling constant K (in seconds) representing the time required to recover back to W_{max}.

3. Calculate the congestion window size W_{cubic}(t) at elapsed times t = 1.0 sec, t = K sec, and t = K + 2.0 sec.

Step-by-Step Solution:

Step 1: Compute window size immediately following backoff.

Under Cubic backoff:

W(0) = β · W_{max} = 0.7 × 8000 = 5600 segments

Step 2: Calculate time constant K.

The formula for K is:

K = ∛((W_max · (1 - β)) / C)

Notice: The volume of window that must be reclaimed is:

W_{max} - W(0) = W_{max} · (1 - β) = 8000 × (1 - 0.7) = 2400 segments

Substituting into the cube root equation:

K = ∛(2400 / 0.4) = ∛(6000)

Evaluating the cube root:

6000^{1/3} ≈ 18.1712 seconds

Thus, K ≈ 18.17 seconds.

Step 3: Calculate W_{cubic}(t) at specific time intervals.

The general Cubic formula is:

W_{cubic}(t) = C · (t - K)^3 + W_{max}

• At t = 1.0 second:

(t - K) = 1.0 - 18.1712 = -17.1712

(-17.1712)^3 ≈ -5062.96

W_{cubic}(1.0) = 0.4 × (-5062.96) + 8000 = -2025.18 + 8000 ≈ 5974.82 segments

• At t = K = 18.1712 seconds:

(t - K) = 0

W_{cubic}(K) = 0.4 × (0)^3 + 8000 = 8000.0 segments

The window recovers to exactly W_{max}.

• At t = K + 2.0 = 20.1712 seconds (Convex Probing Region):

(t - K) = 2.0

(2.0)^3 = 8.0

W_{cubic}(K + 2.0) = 0.4 × (8.0) + 8000 = 3.2 + 8000 = 8003.2 segments

Observation: Near t = K, the slope is virtually zero (growth of only 3.2 segments in 2 seconds), providing maximum stability at link capacity.

Problem 3: Kleinrock's Optimal Operating Point & BBR Inflight Analysis#

A high-performance cloud storage cluster streams backups across a wide-area network link.

• Physical Specifications: Bottleneck Bandwidth BtlBw = 4 Gbps (4 × 10^9 bits/sec); physical two-way propagation delay RTprop = 30 ms (0.030 seconds).
• Network Hardware: The intermediate bottleneck router features an unmanaged FIFO buffer of size B_{buf} = 5 MB (5 × 10^6 bytes).
• Calculations Required:

1. Compute the true Bandwidth-Delay Product (BDP) in megabytes.

2. Under traditional TCP Reno (which fills the queue to overflow before dropping), calculate the total data in flight at the instant of packet drop, and determine the resulting bloated RTT experienced by the flow.

3. Under Google BBR (operating with cwnd_gain = 2.0 and pacing at BtlBw), compute the in-flight data, actual queue occupancy in the router, and observed RTT.

Step-by-Step Solution:

Step 1: Compute physical Bandwidth-Delay Product (BDP).

BDP_{bits} = BtlBw × RTprop

BDP_{bits} = (4 × 10^9 bits/sec) × 0.030 sec = 120,000,000 bits

Converting to bytes:

BDP_{bytes} = 120,000,000 / 8 = 15,000,000 bytes = 15.0 MB

Step 2: Analyze TCP Reno at buffer drop.

TCP Reno expands cwnd until the physical pipe AND the router buffer are 100% full:

Inflight_{Reno} = BDP + B_{buf} = 15.0 MB + 5.0 MB = 20.0 MB

Queuing delay introduced by the 5 MB buffer:

t_{queue} = B_{buf} / BtlBw = (5 × 10^6 × 8 bits) / (4 × 10^9 bits/sec) = 40 × 10^6 / 4 × 10^9 = 0.010 seconds = 10 ms

Total observed RTT under Reno:

RTT_{bloated} = RTprop + t_{queue} = 30 ms + 10 ms = 40 ms

Impact: The queue introduces a 33.3% latency penalty without a single bit per second increase in throughput.

Step 3: Analyze Google BBR operating point.

BBR paces transmission at precisely BtlBw:

Pacing Rate = 4 Gbps

Because packets arrive at the bottleneck switch at exactly the rate the switch interface drains them:

Router Queue Occupancy ≈ 0 bytes

Observed RTT = RTprop + 0 = 30 ms

Target cwnd cap with cwnd_gain = 2.0:

Target cwnd = 2.0 × 15.0 MB = 30.0 MB

Since the pacing rate prevents queue formation, actual in-flight bytes hover near 1 × BDP (15 MB), delivering maximum line-rate 4 Gbps throughput at minimum physical speed-of-light latency (30 ms).

Problem 4: TIME_WAIT Socket Exhaustion & Ephemeral Port Sizing#

A high-concurrency microservice acts as an API gateway, terminating inbound client requests and initiating outbound HTTP/1.1 connections to a backend caching cluster located at IP 10.0.1.50 on port 8080.

• System Constraints:

- The API gateway operates with a single egress IP address (10.0.1.10).

- The Linux kernel ephemeral port range is configured via net.ipv4.ip_local_port_range = 32768 60999.

- The gateway initiates an active close on every outbound backend HTTP connection without connection pooling.

- The operating system kernel enforces a standard 2MSL TIME_WAIT duration of 60 seconds.

• Calculations Required:

1. Calculate the total number of usable ephemeral ports available to the gateway.

2. Compute the maximum sustainable connection establishment rate (connections per second) to that specific backend IP:port before client-side port exhaustion occurs (EADDRNOTAVAIL).

3. Determine how deploying HTTP keep-alive connection pooling (reusing 100 persistent connections) alters the ephemeral port requirement.

Step-by-Step Solution:

Step 1: Calculate total available ephemeral ports.

The ephemeral port range spans ports 32768 to 60999 inclusive:

N_{ports} = 60,999 - 32,768 + 1 = 28,232 ports

Step 2: Calculate maximum sustainable connection rate.

A TCP connection is uniquely identified by the 4-tuple:

{ Source IP, Source Port, Destination IP, Destination Port }

Here:

• Source IP is fixed: 10.0.1.10
• Destination IP is fixed: 10.0.1.50
• Destination Port is fixed: 8080

The only variable in the 4-tuple is the Source Port (ephemeral port).

Because the gateway initiates the active close, every closed connection transitions to TIME_WAIT for T_{wait} = 60 seconds.

During this 60-second window, that specific source port cannot be reused for a new connection to the identical {Dest IP, Dest Port}.

The maximum sustainable connection rate R_{max} is governed by Little's Law:

N_{ports} = R_{max} × T_{wait}

R_{max} = N_{ports} / T_{wait} = 28,232 / 60 ≈ 470.53 connections per second

Engineering Takeaway: If the API gateway receives 500 requests per second, within 56 seconds it will completely exhaust its ephemeral port pool, generating fatal connect() failed: Cannot assign requested address errors.

Step 3: Architectural Mitigation via Connection Pooling.

By enabling HTTP/1.1 Keep-Alive connection pooling with a pool size of 100 persistent connections:

• The gateway opens 100 persistent TCP connections and holds them open across millions of HTTP requests.
• Ephemeral ports consumed: Exactly 100 ports.
• The remaining 28,132 ports remain available for other system services.
• Connection creation rate drops to near 0 cps, completely eliminating the TIME_WAIT bottleneck and slashing TCP handshake latency across microservice communication.