16 · Utilization: stop-and-wait vs pipelining ★

Slides 3-30 → 3-33 · HW3 P4

What utilization means

Sender utilization $U_{sender}$ = the fraction of time the sender is actually busy sending bits. 1 = the link is always in use. 0.0003 = the link is idle almost all the time.

Where the formula comes from

$t = 0$: the sender starts sending packet 1.
$t = L/R$: the last bit leaves. (That's the transmission delay from topic 3.)
The bits travel to the receiver, and the ACK comes back. That takes one RTT.
$t = \text{RTT} + L/R$: the ACK arrives and the sender can send again.

So one cycle lasts $\text{RTT} + L/R$. In that cycle, the sender is busy for $N$ packets × $L/R$ each.

$$U_{sender} = \frac{N \cdot \frac{L}{R}}{\text{RTT} + \frac{L}{R}}$$

$N$ = window size (packets sent per RTT). Stop-and-wait: $N = 1$.

Assumptions (the standard ones): ACKs are tiny (ignore their transmission time), the receiver ACKs as soon as the last bit arrives, and no losses. $\text{RTT} = 2 \times$ one-way propagation delay.

Throughput follows from it:

$$\text{throughput} = U \times R \qquad \text{(or: } \frac{N \cdot L}{\text{RTT} + L/R}\text{)}$$

Traps
• RTT = 2 × one-way propagation. "15 ms one-way" → RTT = 30 ms.
• Bytes → bits: 1500 bytes = 12,000 bits.
• Use the same time unit on top and bottom (all ms, or all s).
• $U$ can't exceed 1. If the formula gives more than 1, the window is big enough to keep the link busy the whole time, so $U = 1$.

Slide example: stop-and-wait stinks

1 Gbps link, 15 ms one-way propagation (RTT = 30 ms), 8000-bit packet.

$$\frac{L}{R} = \frac{8000}{10^9} = 8 \ \mu\text{s} = 0.008 \text{ ms}$$ $$U_{sender} = \frac{0.008}{30 + 0.008} = \frac{0.008}{30.008} \approx \mathbf{0.00027}$$

The sender is busy 0.027% of the time. One 1 KB packet every 30 ms ≈ 33 kB/s of throughput on a 1 Gbps link. The protocol, not the link, limits performance.

3-packet pipelining (slide 3-33)

$$U_{sender} = \frac{3 \times 0.008}{30.008} = \frac{0.024}{30.008} \approx \mathbf{0.00081}$$

3 packets per RTT → 3× the utilization. (The slide prints the numerator as ".0024", a typo; the result 0.00081 is right.)

Worked example: HW3 P4

Q: How big must the window be for utilization above 98%? $R = 1$ Gbps, one-way propagation = 15 ms, packet = 1500 bytes (header included).

Step 1: transmission time

$$\frac{L}{R} = \frac{1500 \times 8}{10^9} = \frac{12{,}000}{10^9} = 12 \ \mu\text{s} = 0.012 \text{ ms}$$

Step 2: RTT

$$\text{RTT} = 2 \times 15 = 30 \text{ ms}$$

Step 3: set up the inequality

$$\frac{N \times 0.012}{30 + 0.012} > 0.98$$

Step 4: solve for N

$$N > \frac{0.98 \times 30.012}{0.012} = 0.98 \times 2501 = 2450.98$$

N must be a whole number of packets, so round up:

N = 2451 packets

Check: $2451 \times 0.012 / 30.012 = 0.98001$ ✓ (and 2450 gives 0.97961, just short).

By hand: $30.012 / 0.012$: multiply top and bottom by 1000 → $30{,}012 / 12 = 2501$. Then $0.98 \times 2501 = 2501 - 0.02 \times 2501 = 2501 - 50.02 = 2450.98$.

General "solve for the window" formula

$$N \ge \frac{U_{target} \times (\text{RTT} + L/R)}{L/R}$$

For 100% utilization: $N \ge (\text{RTT} + L/R)/(L/R)$. In the slide example that's $30.008 / 0.008 = 3751$ packets.

Ties to topic 15

Pipelining (GBN, SR) is why $N$ can be bigger than 1.
But the window is limited by the seq # bits: a GBN window of 2451 needs $2^k - 1 \ge 2451$ → $k \ge 12$ bits ($2^{12} = 4096$). SR needs $2^{k-1} \ge 2451$ → $k \ge 13$.

Quick check

1. R = 10 Mbps, L = 1000 bits, RTT = 10 ms. Stop-and-wait utilization? Throughput?

$$\frac{L}{R} = \frac{1000}{10^7} = 0.1 \text{ ms} \qquad U = \frac{0.1}{10 + 0.1} = \frac{0.1}{10.1} \approx \mathbf{0.0099}$$ Throughput = $0.0099 \times 10 \text{ Mbps} \approx \mathbf{99 \text{ kbps}}$.

2. Same link, window N = 50?

$$U = \frac{50 \times 0.1}{10.1} = \frac{5}{10.1} \approx \mathbf{0.495}$$

3. Same link. Smallest window for U ≥ 90%?

$$N \ge \frac{0.9 \times 10.1}{0.1} = 90.9 \ \Rightarrow\ \mathbf{N = 91}$$

4. Same link, window N = 200. Utilization?

$200 \times 0.1 / 10.1 = 1.98 > 1$, so U = 1. Any window ≥ 101 keeps the link 100% busy.

5. One-way propagation delay is 20 ms. What RTT goes in the formula?

40 ms (2 × one-way).

6. Stop-and-wait on a faster link (R doubles). Does utilization go up or down?

Down. $L/R$ halves, but the RTT stays the same, so the sender is idle an even bigger fraction of the time.

7. Why does pipelining with N packets multiply utilization by about N?

In each RTT + L/R cycle, the sender sends N packets instead of 1, so it's busy N times as long. (As long as $N \cdot L/R$ stays below the cycle length.)

← 15 · GBN & SR · all topics · 17 · rdt details →