Problem 6: TCP Congestion Control & Window Mechanics

Background Theory & Core Principles

To understand the mathematical behavior of TCP Reno and SACK, we must first break down
the core governing mechanisms of window-based congestion control. TCP relies on an end-
to-end control loop where the sender throttles its transmission speed using a Congestion
Window (CW N D ). The actual volume of data allowed in flight is bounded by:

Max In-Flight Data = min(CW N D, Receiver Window (RW N D))

Assuming the network path is the bottleneck (RW N D ≫ CW N D ), CW N D completely

dictates performance. TCP transitions through distinct phases governed by specific
algorithms:

[ Start / Timeout ]
│
▼
┌───────────────┐
│ Slow Start │ ──( CWND >= ssthresh )──► ┌──────────────────────┐
│ (Exponential) │ │ Congestion Avoidance │
└───────────────┘ ◄──( Timeout / Reset )─── │ (Linear) │
│ └──────────────────────┘
│ │
(Triple Dup ACKs) (Triple Dup ACKs)
│ │
▼ ▼
┌──────────────────────────────────────────────────────────┐
│ Fast Retransmit / Fast Recovery (Reno) │
│ Halves ssthresh, updates CWND │
└──────────────────────────────────────────────────────────┘

1. Slow Start Phase

Trigger: Initiated at startup or after a retransmission timeout (RTO).

Growth Equation: For every individual valid acknowledgement (ACK) received, the
window expands by 1 Maximum Segment Size (MSS):

CW N Dt+1 = CW N Dt + 1 MSS
​ ​
 Systemic Effect: Because an entire window of size CW N D generates CW N D
individual ACKs over one Round-Trip Time (RTT), the window effectively doubles every
RTT. This results in exponential growth:

CW N D(t) = CW N D0 ⋅ 2t ​

Where t represents the number of elapsed RTTs.

2. Congestion Avoidance Phase

Trigger: Occurs when CW N D ≥ ssthresh (Slow Start Threshold).

Growth Equation: To prevent aggressive network saturation, growth shifts to a linear

model. For each incoming ACK, the window increases fractionally:

1
CW N Dt+1 = CW N Dt +
​ ​

CW N Dt ​
​

Systemic Effect: Across a full window of transmissions (CW N D packets), the

cumulative increase equals exactly 1 MSS per RTT. This is the Additive Increase
component of AIMD:

CW N D(t) = CW N Dstart + t ​

3. Loss Detection and Recovery Mechanics

Triple Duplicate ACKs (Mild Congestion): Indicates that packets are arriving out of
order, but still reaching the destination (often due to transient buffer overflows). TCP
Reno executes Fast Retransmit and Fast Recovery:

ssthreshnew = max ( CW2N D , 2)

​ ​

CW N Dnew = ssthreshnew
​ ​

Timeout (Severe Congestion): Indicates a complete drop in the network pipeline where
no packets are getting through.

ssthreshnew = max ( CW2N D , 2)

​ ​

CW N Dnew = 1 MSS
​
Step-by-Step Solutions

Part a) Throughput Before and After Packet Loss

Step 1: Meticulous Mapping of Window Growth

We must identify the precise state of the connection at the moment the 100th successful
segment transmission is completed.

Initial State: CW N D = 1 MSS, ssthresh = 50 MSS.

Let's calculate the cumulative count of successfully transmitted and acknowledged packets
round-by-round:

RTT 1 (Slow Start):

Window transmits 1 packet.

1 ACK is received.

Update: CW N D = 1 + 1 = 2 MSS.

Cumulative Packets: 1

RTT 2 (Slow Start):

Window transmits 2 packets.

2 ACKs are received.

Update: CW N D = 2 + 2 = 4 MSS.

Cumulative Packets: 1 + 2 = 3

RTT 3 (Slow Start):

Window transmits 4 packets.

4 ACKs are received.

Update: CW N D = 4 + 4 = 8 MSS.

Cumulative Packets: 3 + 4 = 7

RTT 4 (Slow Start):

 Window transmits 8 packets.

8 ACKs are received.

Update: CW N D = 8 + 8 = 16 MSS.

Cumulative Packets: 7 + 8 = 15

RTT 5 (Slow Start):

Window transmits 16 packets.

16 ACKs are received.

Update: CW N D = 16 + 16 = 32 MSS.

Cumulative Packets: 15 + 16 = 31

RTT 6 (Transition Phase):

At the start of this round, CW N D = 32 MSS. The remaining room before hitting the
slow-start threshold is:

ΔCW N D = ssthresh − CW N Dcurrent = 50 − 32 = 18 MSS

​

The first 18 packets transmitted in this round return their ACKs. Each ACK adds 1 MSS to
the window because TCP is still technically below ssthresh.

Once those 18 ACKs arrive, CW N D reaches exactly 50 MSS.

Packets acknowledged up to this threshold point: 31 + 18 = 49 packets.

The remaining packets from the RTT 6 flight (32 − 18 = 14 packets) are now processed
under Congestion Avoidance rules. Each ACK increases the window by 1/CW N D .

Window increase from the remaining flight: 14 × (1/50) = 0.28 MSS.

End of RTT 6: CW N D = 50 + 0.28 = 50.28 MSS.

Cumulative Packets: 31 + 32 = 63 packets.

RTT 7 (Congestion Avoidance):

We start this round with CW N D = 50.28 MSS and a total of 63 packets successfully
processed.
 We need to find the window size precisely when the cumulative count reaches 100.

Required additional packets: ΔPackets = 100 − 63 = 37 packets.

Each of these 37 packets returns an ACK. Under Congestion Avoidance, each ACK adds
approximately 1/CW N Dbase to the window: ​

37
ΔCW N D = 50.28 ​ ≈ 0.74 MSS

At the exact instance of the 100th successful transmission:

CW N Dbefore = 50.28 + 0.74 = 51.02 MSS ≈ 51 MSS

​

Step 2: Formulating and Calculating Throughput Before Loss

Throughput (T ) is defined mathematically via an adaptation of Little's Law for window-based

protocols:

Data Transmitted per Cycle CW N D×MSS

T = Duration of Cycle
​
= RTT
​

Given RTT = 10 ms = 0.01 s and CW N D = 51 MSS:

51×MSS
Tbefore =
​

0.01 s
​ = 5100 × MSS [bytes/sec]

Concrete Example: If using a standard Ethernet Max Segment Size (MSS =

1500 bytes = 12000 bits):

51×12000 bits
Tbefore =​

0.01 s ​ = 61.2 Mbps

Step 3: Calculation of Throughput After Loss

Because the problem specifies a packet loss occurs via a normal drop scenario handled by
standard Reno fast-recovery (implied by the comparative nature of the problem tracking
consecutive packets), TCP Reno invokes its Multiplicative Decrease property:

CW N Dbefore 51 MSS
ssthreshnew = ​

2
​

​ = 2
​ = 25.5 MSS

Once Fast Recovery completes its retransmission and exits, the window settles at the new
threshold:

CW N Dafter = 25.5 MSS

​

Calculating the instantaneous network throughput immediately following recovery:

 25.5×MSS
Tafter =
​

0.01 s
​ = 2550 × MSS [bytes/sec]

Using the 1500-byte MSS example:

25.5×12000 bits
Tafter =​

0.01 s
​
= 30.6 Mbps

Part b) TCP-SACK Effective Throughput During Recovery Phase

Step 1: Mathematical Theory of SACK Recovery Pipelines

Standard TCP Reno suffers heavily when multiple packets drop out of a single window
because cumulative ACKs can only communicate a single "hole" at a time. This forces Reno to
either wait an entire RTT to discover the next missing packet or stall and trigger a timeout.

TCP Selective Acknowledgment (SACK, RFC 2018) solves this by appending explicitly bounded
blocks of received out-of-order data inside the TCP options header. To manage transmission
safely during recovery, SACK implementations use a state variable called pipe to track data
density in flight:

pipe = HighData − LowData − SACKed_Bytes + Retransmitted_Bytes

The sender is permitted to transmit a segment if and only if:

pipe < ssthresh

Step 2: Tracking the Flight Metrics

Pre-loss Window (CW N D ): 1000 packets

Number of Lost Packets: 2

Number of Successfully Received Packets: 1000 − 2 = 998 packets

Round Trip Time (RTT): 50 ms = 0.05 s

When the loss is recognized via triple duplicate ACKs:

1. ssthresh is adjusted downward:

1000
ssthresh = CW N D
2
​ = 2
​ = 500 packets

2. The 998 successfully received packets trigger 998 individual duplicate ACKs containing
SACK option blocks.
 3. As these ACKs arrive back at the sender, each ACK informs the engine that a packet has
exited the network pipeline and landed safely in the receiver's buffer. This continuously
decrements the pipe variable by 1.

4. Transmission is blocked until pipe drops below ssthresh = 500. This occurs after the
first (998 − 500) = 498 ACKs are processed.

5. For every remaining ACK that arrives within that same recovery RTT, the sender can
execute exactly 1 packet transmission to maintain equilibrium (pipe = 500).

Allowed Transmissions = Total ACKs Received − ssthresh = 998 − 500 =

498 packets

Step 3: Determining Content and Throughput

Out of the 498 transmission opportunities:

The engine uses 2 slots to retransmit the two missing packets reported by the SACK gaps.

The remaining slots are filled with completely new data from the transmission queue:

New Packets Sent = 498 − 2 = 496 packets

Total packets successfully pushed into the link during this single recovery RTT cycle:
498 packets.
Packets Transmitted 498 packets
Effective ThroughputSACK = ​

RTT ​ = 0.05 s ​ = 9960 packets/second

Part c) RTTs to Increase CW N D via AIMD

Step 1: Formula Derivation

Under the Additive Increase rule of the AIMD algorithm during the Congestion Avoidance
phase, the window size increases by exactly 1 MSS for every full round of successful
transmissions (1 RTT).

Let CW N D(t) be the window size at RTT step t. The discrete evolution is modeled as:

CW N D(t) = CW N Dinitial + α ⋅ t ​

Where α = 1 MSS/RTT. Rearranging the linear model to solve for elapsed time (t):

CW N Dtarget −CW N Dinitial

t= ​

α
​

​
Step 2: Computation

Given CW N Dinitial = 6 MSS and CW N Dtarget = 12 MSS:

​ ​

12 MSS−6 MSS
t= 1 MSS/RTT
​ = 6 RTTs

Part d) RTTs to Recover to 24 MSS After a Timeout

Step 1: State Adjustments Post-Timeout

When a Retransmission Timeout (RTO) fires at CW N D = 24 MSS, the state architecture

undergoes an immediate reset:

CW N Dcrashing 24
ssthreshnew = = = 12 MSS
​

2 ​

2 ​

CW N Dreset = 1 MSS
​

The protocol enters Slow Start.

Step 2: Step-by-Step RTT Timeline Calculation

We map out the window size at the beginning of each RTT iteration:

Elapsed Window Size (

Phase Type Mechanics / Mathematical Action
Time (t) CW N D)

Sends 1 packet. Receives 1 ACK →

0 RTT Slow Start 1 MSS
CW N D doubles.

Sends 2 packets. Receives 2 ACKs →

1 RTT Slow Start 2 MSS
CW N D doubles.

Sends 4 packets. Receives 4 ACKs →

2 RTT Slow Start 4 MSS
CW N D doubles.

Sends 8 packets. Receives 8 ACKs →

3 RTT Slow Start 8 MSS
Window hits threshold (ssthresh = 12).

Congestion Shifting to additive linear increase:

4 RTT 12 MSS
Avoidance +1 MSS per RTT.

From t = 4 RTT, the growth follows the linear progression:

CW N D(t) = 12 + (t − 4)
We want to find t when CW N D(t) = 24 MSS:

24 = 12 + (t − 4) ⟹ t − 4 = 12 ⟹ t = 16 RTTs

Total recovery time required is exactly 16 RTTs.

Problem 7: TCP Selective Acknowledgments (SACK)

Detailed Analysis

Background Protocol Mechanics

The TCP SACK option header (RFC 2018) alters the foundational acknowledgment framework
of standard TCP:

+-------------------------------------------------------------------+
| Standard TCP Header (Cumulative ACK = Next Expected Byte) |
+-------------------------------------------------------------------+
| SACK Option Kind = 5 | Length = N bytes |
+-------------------------------------------------------------------+
| Left Edge of 1st Block (First out-of-order byte received) |
+-------------------------------------------------------------------+
| Right Edge of 1st Block (First byte beyond out-of-order chunk) |
+-------------------------------------------------------------------+
| ... |
+-------------------------------------------------------------------+

The Edge Definition Rules

Left Edge: Stores the sequence number of the first byte of the non-contiguous, out-of-
order block currently sitting in the receiver's queue.

Right Edge: Stores the sequence number immediately following the final byte of that
out-of-order block (making the boundary representation mathematically exclusive on
the right side: [Left Edge, Right Edge)).

Meticulous Breakdown of the Segment Stream

The sender transmits 12 contiguous segments, each carrying a payload of 1000 bytes. We
map the structural layout of these sequence numbers below:
 Segment 1: [1, 1001) → Bytes: 1 − 1000

Segment 2: [1001, 2001) → Bytes: 1001 − 2000

Segment 3: [2001, 3001) → Bytes: 2001 − 3000

Segment 4: [3001, 4001) → Bytes: 3001 − 4000 (LOST IN TRANSIT)

Segment 5: [4001, 5001) → Bytes: 4001 − 5000

Segment 6: [5001, 6001) → Bytes: 5001 − 6000

Segment 7: [6001, 7001) → Bytes: 6001 − 7000

Segment 8: [7001, 8001) → Bytes: 7001 − 8000

Segment 9: [8001, 9001) → Bytes: 8001 − 9000 (LOST IN TRANSIT)

Segment 10: [9001, 10001) → Bytes: 9001 − 10000

Segment 11: [10001, 11001) → Bytes: 10001 − 11000

Segment 12: [11001, 12001) → Bytes: 11001 − 12000

Step-by-Step Question Solutions

1. What ACK number and SACK blocks are sent after the first reception of all
segments?

When the receiver processes the incoming sequence stream up to Segment 12, it encounters
two structural gaps (holes) caused by the lost segments:

[1 - 3000] [3001 - 4000] [4001 - 8000] [8001 - 9000] [9001 - 12000]

Received LOST Received LOST Received
▲ ▲
Cumulative ACK Isolated Block 1 Isolated Block 2

1. Cumulative ACK Field: The cumulative ACK points to the next expected in-order byte.
Segments 1, 2, and 3 arrived cleanly, establishing a contiguous buffer from byte 1 to
3000. Because Segment 4 (3001 − 4000) is missing, the tracking pointer stalls.

ACK = 3001

2. SACK Block 1 (First Continuous Island): Composed of Segments 5, 6, 7, and 8. The data
range spans from byte 4001 to 8000. Following the exclusive right-edge rule:

Left Edge = 4001, Right Edge = 8001

 3. SACK Block 2 (Second Continuous Island): Composed of Segments 10, 11, and 12. The
data range spans from byte 9001 to 12000. Following the exclusive right-edge rule:

Left Edge = 9001, Right Edge = 12001

Per RFC 2018 guidelines, SACK blocks must be ordered by recency (the block containing the
most recently received segment goes first). Assuming chronological arrival, the final ACK
packet sent after this burst contains:

Cumulative ACK Field: 3001

SACK Block Fields: [9001, 12001], [4001, 8001]

2. Which segments will the sender choose to retransmit?

The sender parses the returning SACK header options and contrasts them against its
unacknowledged data tracking boundaries:

Missing Ranges = [Cumulative ACK, End of Flight] ∖ ⋃ [SACK Blocks]

Evaluating this set difference highlights exactly two missing blocks:

The hole bounded between the current cumulative pointer ( 3001 ) and the left edge of
the first block ( 4001 ) → Segment 4 (Base Seq: 3001)

The hole bounded between the right edge of the first block ( 8001 ) and the left edge of
the second block ( 9001 ) → Segment 9 (Base Seq: 8001)

The sender will selectively retransmit Segment 3001 and Segment 8001.

3. After retransmission of segment 3001, what ACK and SACK options will the
receiver send?

When the retransmitted Segment 4 (carrying bytes 3001 to 4000) lands safely at the receiver:

1. The first structural hole is filled.

2. The receiver's buffer engine chains together the previously isolated data island spanning
from 4001 to 8001 with the newly arrived block.

3. The new contiguous data block now runs seamlessly from byte 1 all the way to byte 8000
.

4. The tracking engine hits its next obstacle at byte 8001 because Segment 9 has not been
repaired yet.
 [1 - 8000] [8001 - 9000] [9001 - 12000]
Now Contiguous Received LOST Remaining SACK Block
▲
New Cumulative ACK

New Cumulative ACK Field: 8001

Remaining SACK Block Field: [9001, 12001]

4. What is the final ACK configuration after both retransmissions are processed?

When the retransmitted Segment 9 (carrying bytes 8001 to 9000) is received:

1. The final delivery gap is filled.

2. The data block running from 1 to 8000 merges with the newly arrived segment (8001 −
9000) and the final buffered island (9001 − 12000).
3. The receiver now holds a completely unbroken, contiguous data stream from byte 1 to
byte 12000.

Final Cumulative ACK Field: 12001 (Informing the sender it is ready for the first byte of
Segment 13).

SACK Blocks Field: None (The stream contains no remaining out-of-order blocks).