Elementary and sliding window protocols: stop-and-wait, Go-Back-N, Selective Repeat

On the previous page you saw how the link layer notices errors. Noticing is not enough: a corrupted frame is discarded, and the data still has to reach the other side. The way to do this is ARQ (automatic repeat request): the receiver sends an acknowledgment (ACK), and the sender retransmits if no ACK arrives. The same ideas come back in week 7 with TCP, so learn them well here.

Exam questions come in three patterns: utilization calculation, “which frames are retransmitted?” traces, and the number of sequence-number bits. Golden rules:

1. $U = N \cdot (L/R) / (RTT + L/R)$, and it cannot exceed 1. In stop-and-wait $N = 1$.
2. The GBN receiver discards out-of-order frames, the SR receiver buffers them.
3. In GBN the window is $\le 2^k - 1$, in SR it is $\le 2^{k-1}$.
4. RTT is two-way. If the one-way propagation is given, multiply by two.

Elementary protocols, step by step

Textbooks build reliable delivery as a series of protocols going from simple to complex. Each one removes a convenience that the previous one assumed.

Why a sequence number? Scenario: the sender sends frame 0, the receiver gets it and sends an ACK, and the ACK is lost. At the timeout the sender sends 0 again. Without a sequence number the receiver would think it is new data and deliver it to the upper layer twice. One bit is enough: the receiver says “I was expecting 1 now, this 0 is a duplicate”, discards it, but still sends an ACK.

PITFALL · ACK the duplicate frame too. The receiver discards the duplicate frame but must still send the ACK. If it doesn’t, the sender resends the same frame forever, because the first ACK was already lost.

Why is stop-and-wait slow?

The sender sends one frame and waits until the ACK arrives. The first bit of the frame leaves at $t = 0$, the last bit at $L/R$, and the ACK returns at $RTT + L/R$. The fraction of time the sender is really putting bits on the link is:

$U_{sender} = \frac{L/R}{RTT + L/R}$

Worked example

$R = 100$ Mbps, $L = 10{,}000$ bits, $RTT = 20$ ms.

L/R = 10,000 / 10^8        = 0.1 ms
U   = 0.1 / (20 + 0.1)     = 0.004975   (about 0.5%)
throughput = U x R         = 497.5 kbps

Not even half a megabit gets through a 100 Mbps link. The problem is not the link, it is the protocol.

The parameter $a$

Some books define $a = d_{prop}/d_{trans}$. If the ACK size and the processing time are neglected, $RTT = 2 d_{prop}$:

$U_{SW} = \frac{1}{1 + 2a}$

In the example $d_{prop} = 10$ ms, $d_{trans} = 0.1$ ms, $a = 100$, $U = 1/201$. The same number.

Pipelining and the sliding window

The solution: send several frames without waiting for ACKs. The sender can keep at most $N$ unacknowledged frames “in flight”. This $N$ is the window size. When an ACK arrives, the window slides forward.

$U = \min\left(1,\ \frac{N \cdot L/R}{RTT + L/R}\right)$

In the same example with $N = 50$: $U = 50 \times 0.1 / 20.1 = 0.2488$. For full utilization:

$N \ge \frac{RTT + L/R}{L/R} = \frac{20.1}{0.1} = 201$

This is the bandwidth-delay product idea from week 1, expressed in frames: the pipe must be full.

The sender’s sequence-number space looks like this:

 [ acknowledged ][ sent, waiting for ACK ][ can be sent ][ not yet usable ]
                 ^ base                    ^ nextseqnum
                 |<-------------- window N -------------->|

Pipelining recovers from errors in two different ways: Go-Back-N and Selective Repeat.

Go-Back-N (GBN)

• Receiver window is 1. The receiver accepts only the frame it expects next in order. It discards everything that arrives out of order.
• Cumulative ACK. “ACK n” means everything up to and including n was received. When an out-of-order frame arrives, the receiver resends the ACK of the last in-order frame it received.
• A single timer, for the oldest unacknowledged frame. At the timeout the sender resends all frames in the window, starting from that frame. Hence the name: go back N.

Trace: window 6, frame 2 lost

Sender  : 0  1  2  3  4  5
Channel : ok ok X  ok ok ok
Receiver: acc acc - drop drop drop        (expected is always 2)
ACK     : 0  1     1  1  1          (repeated ACK1)
Timeout(2): resend 2 3 4 5   -> 4 frames

Advantage: the receiver is simple, with no buffer. Disadvantage: a single loss also throws away the correctly received frames behind it. With a high error rate and a large window on the link, it wastes a lot.

Selective Repeat (SR)

• The receiver also keeps a window and buffers frames that are out of order but inside the window.
• Each frame is ACKed individually (not cumulative).
• Each frame has its own timer. Only the frame whose timer expires is resent.
• When the missing frame arrives, the receiver hands the in-order block in the buffer to the upper layer together.

The same trace, with SR

Sender  : 0  1  2  3  4  5
Channel : ok ok X  ok ok ok
Receiver: acc acc - buffer buffer buffer
ACK     : 0  1     3  4  5
Timeout(2): only 2  -> 1 frame
When 2 arrives: 2,3,4,5 delivered in order

How many bits should the sequence number have?

If the sequence number is $k$ bits, the values cycle through $0, 1, \ldots, 2^k - 1$.

Why not $2^k$ in GBN? If the window were $2^k$, the sender would send 0..7 and either all the ACKs are lost or all arrive; in both cases the next frame the receiver expects is 0. The sender cannot tell whether an “ACK 7” it receives refers to the new window or the old one.

Why half in SR? The receiver’s window also slides forward. The sender’s and receiver’s windows must not overlap in the sequence space.

k = 2 (0..3), W = 3:
receiver got 0,1,2, the ACKs were lost
receiver window is now {3, 0, 1}
sender resends the old 0 -> receiver thinks it is a NEW 0, wrong delivery

k = 2, W = 2:
receiver window {2, 3}, the old 0 is outside -> correctly discarded (and ACKed)

Worked example: a satellite link

$R = 1$ Mbps, $L = 1000$ bits, one-way propagation 270 ms.

L/R = 1 ms,  RTT = 540 ms
SW                : U = 1 / 541         = 0.00185
GBN, k=3 (N=7)    : U = 7 / 541         = 0.0129
For full use      : N = 541
GBN bit count     : 2^10 - 1 = 1023 >= 541  -> k = 10
SR  bit count     : 2^10 = 1024 >= 541      -> k = 11

Stop-and-wait with error probability

If each frame is corrupted independently with probability $p$, the expected number of transmissions per frame is:

$E[\text{transmissions}] = \frac{1}{1-p}$

For $p = 0.2$ it is 1.25. The efficiency drops by the same factor. On a noisy link, GBN repeats many frames after a single error, so SR’s advantage grows.

TIP · piggybacking. When data flows in both directions, instead of sending a separate ACK frame, the receiver puts the ACK in the header of its own data frame going the other way. This saves bandwidth. TCP works this way too.

Security note

None of these protocols verifies who the other party is. If the sequence number becomes predictable, someone in the middle can inject a forged frame with the right sequence number. This is one reason TCP chooses its initial sequence number at random (week 7).

Common mistakes