Question 3 of 5: Data Link Layer and Peer-to-Peer Protocols

Question 3: Data Link Layer and Peer-to-Peer Protocols (25 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Part (a) — How a CRC detects errors. A cyclic redundancy check treats a block of bits as the coefficients of a polynomial over the binary field $\mathrm{GF}(2)$, in which addition and subtraction are both the exclusive-OR operation and there are no carries. A $k$-bit information block becomes an information polynomial $i(x)$ of degree at most $k-1$. Sender and receiver agree in advance on a generator polynomial $g(x)$ of degree $n-k$; this is the only shared secret the scheme needs, and it is fixed by the standard, for example CRC-32 in Ethernet.

The encoder shifts the information up by the degree of the generator, forming $x^{n-k} i(x)$, divides that by $g(x)$ in $\mathrm{GF}(2)$ to obtain a remainder $r(x)$ of degree less than $n-k$, and transmits $b(x) = x^{n-k} i(x) + r(x)$. Because subtracting the remainder is the same as adding it in this arithmetic, the transmitted codeword is divisible by $g(x)$ with no remainder by construction. The information bits appear unaltered in the high-order positions, so the code is systematic and no decoding is needed to recover the data.

The receiver simply divides the whole received block by the same $g(x)$. A zero remainder means the block is a legitimate codeword and is accepted; any non-zero remainder proves an error occurred and the frame is discarded, to be recovered by the ARQ machinery of part (c). Writing the received block as $b(x) + e(x)$ for an error pattern $e(x)$, the syndrome is the remainder of $e(x)$ alone, so a CRC fails to detect an error exactly when $g(x)$ divides $e(x)$. Generators are chosen to make that improbable: a generator with more than one term catches every single-bit error; including the factor $(x+1)$ catches every odd-weight error; a generator of degree $n-k$ catches every burst of length $n-k$ or less; and a random longer burst slips through with probability about $2^{-(n-k)}$, roughly one in four billion for CRC-32. The whole computation is a shift register with a few XOR taps, which is why it runs at line rate in hardware.

Part (b) — Output of the CRC encoder.

Given. Generator polynomial $g(x) = x^{2} + 1$, of degree $n-k = 2$; information polynomial $i(x) = x^{5}$, that is the six-bit block 100000. All arithmetic is over $\mathrm{GF}(2)$.

Find. The transmitted codeword $b(x)$, expressed both as a polynomial and as a bit string.

Approach. Shift the information polynomial up by the degree of the generator, divide by $g(x)$ modulo 2, and append the remainder.

1. Shift the information by the number of check bits. The generator has degree 2, so two check bits are appended and $$x^{n-k} i(x) = x^{2} \cdot x^{5} = x^{7},$$ which as an eight-bit string is 10000000.
2. Reduce $x^{7}$ modulo $g(x)$. In $\mathrm{GF}(2)$ the relation $x^{2} + 1 = 0$ gives $x^{2} = 1$, because a coefficient and its negative are the same thing. Repeatedly substituting, $$x^{7} = x \cdot (x^{2})^{3} = x \cdot 1^{3} = x,$$ so the remainder is $r(x) = x$, that is the two check bits 10. The same result follows from long division: $x^{7} = x^{5}(x^{2}+1) + x^{5}$, then $x^{5} = x^{3}(x^{2}+1) + x^{3}$, then $x^{3} = x(x^{2}+1) + x$.
3. Assemble the codeword. Adding the remainder to the shifted information gives $$b(x) = x^{n-k} i(x) + r(x) = x^{7} + x$$ and hence the encoder output $$\boxed{b(x) = x^{7} + x \quad \Longleftrightarrow \quad 1000\,0010}$$ in which the leading six bits 100000 are the original information and the trailing 10 are the CRC.
4. Verify by re-dividing. A valid codeword must leave no remainder. Since $x^{2} = 1$ under $g(x)$, we have $x^{7} + x = x + x = 0$, confirming $g(x)$ divides $b(x)$ exactly. Note in passing that $g(x) = x^{2}+1 = (x+1)^{2}$ over $\mathrm{GF}(2)$ is a weak generator — a poor choice in practice, but a convenient one for hand calculation.

Part (c) — Automatic repeat request. ARQ is the error-control mechanism that turns the unreliable, error-detecting service of part (a) into a reliable one. Its three ingredients are error detection on every frame, acknowledgements returned by the receiver, and a timer at the sender that fires when an acknowledgement fails to arrive. A frame that is received in error is simply discarded, and the resulting silence is indistinguishable to the sender from a lost frame; the timeout therefore covers both cases. Sequence numbers are essential, because without them a retransmission caused by a lost acknowledgement would be accepted as new data and duplicated.

Stop-and-wait ARQ is the simplest form. The sender transmits one frame and then stops, holding a copy, until an acknowledgement for it returns or the timer expires, in which case the frame is re-sent. A single-bit sequence number alternating between 0 and 1 suffices, since only one frame is ever outstanding: the receiver accepts a frame only if its sequence number matches the one expected, and re-acknowledges without delivering if a duplicate arrives. The virtues are a one-frame buffer at each end and almost no bookkeeping; the vice is that the channel sits idle for a full round-trip time after every frame.

Go-back-n ARQ removes that idle time by pipelining. The sender may have up to $n$ unacknowledged frames in flight, governed by a sliding window that advances as acknowledgements arrive; sequence numbers must now span at least $n+1$ values, and in practice a field of $m$ bits with $n \le 2^{m}-1$. The receiver remains deliberately simple: it accepts frames strictly in order, discards anything out of order, and returns cumulative acknowledgements meaning “all frames up to and including this one are safe”. When a frame is lost, every frame behind it is discarded by the receiver even if received perfectly, and on timeout the sender goes back to the erroneous frame and retransmits it together with all its successors — hence the name. The cost is wasted retransmissions on a noisy link; the benefit is a receiver needing only one frame of buffer. Selective-repeat ARQ is the refinement that buffers out-of-order frames and retransmits only the missing one, at the price of a larger receiver buffer and out-of-order delivery.

Part (d) [printed in the paper as a second “a.”] — Which is more efficient when propagation delay is large?

Given. A link on which the propagation delay $t_{\text{prop}}$ is large compared with the time $t_{f}$ needed to transmit one packet; error-free operation is assumed so that the comparison isolates the pipelining effect.

Find. Which of stop-and-wait and go-back-n ARQ makes better use of the channel, with the reasoning.

Approach. Form the normalised delay-bandwidth product $a = t_{\text{prop}}/t_{f}$ and compare the throughput efficiency of the two protocols as $a$ grows large.

1. Write the efficiency of stop-and-wait. Each frame occupies the channel for $t_{f}$ but consumes a cycle of $t_{f} + 2t_{\text{prop}}$ (ignoring the small acknowledgement and processing times), so $$\eta_{\text{SW}} = \frac{t_{f}}{t_{f} + 2t_{\text{prop}}} = \frac{1}{1 + 2a}, \qquad a = \frac{t_{\text{prop}}}{t_{f}}.$$
2. Write the efficiency of go-back-n. With a window of $n$ frames the sender keeps transmitting until the window empties, giving $$\eta_{\text{GBN}} = \begin{cases} 1, & n \ge 1 + 2a \\[2pt] \dfrac{n}{1 + 2a}, & n \lt 1 + 2a. \end{cases}$$
3. Take the large-delay limit. As $a \rightarrow \infty$ the stop-and-wait efficiency collapses like $1/(2a)$, while go-back-n retains a factor $n$ and reaches unity outright whenever the window is large enough to cover the pipe. Therefore $$\boxed{\eta_{\text{GBN}} = n \, \eta_{\text{SW}} \ge \eta_{\text{SW}}: \ \text{go-back-n is more efficient.}}$$
4. Put numbers on it. On a geostationary satellite hop the one-way propagation delay is about 270 ms; a 1000-bit frame on a 1 Mbit/s link takes 1 ms, so $a = 270$ and $1 + 2a = 541$. Stop-and-wait then achieves $\eta = 1/541 \approx 0.18\%$ — about 1.8 kbit/s out of a megabit — whereas go-back-n with a window of 541 frames fills the link completely. This is precisely why the window must be sized to the delay-bandwidth product, and why TCP needed the window-scale option once long fat networks appeared.