Question 6 of 6: The data link layer and peer-to-peer protocols

Question 6: The data link layer and peer-to-peer protocols (20 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.

Given. A CRC system with generator polynomial $g(x) = x^{2}+1$ and information polynomial $i(x) = x^{5}$, all arithmetic being modulo 2 over the field GF(2). For the efficiency comparison of part (d) the worked link is 1 Mbit/s carrying 1000-bit frames over a geostationary satellite hop of one-way propagation delay 270 ms.

Find. How a CRC detects errors, the codeword produced by the given encoder, the operation of stop-and-wait and go-back-N ARQ, and which of the two is more efficient when propagation delay dominates.

Part (a) — how a CRC detects errors. A CRC treats a block of $k$ information bits as the coefficients of a polynomial $i(x)$ of degree $k-1$ over GF(2), where addition and subtraction are both the exclusive-OR. Sender and receiver agree in advance on a generator polynomial $g(x)$ of degree $r$. The sender shifts the message left by $r$ places, forming $x^{r}i(x)$, divides that by $g(x)$ using modulo-2 long division, and appends the $r$-bit remainder $R(x)$ as the check bits. The transmitted codeword is $$T(x) = x^{r}i(x) + R(x)$$ and because subtracting the remainder in GF(2) is the same as adding it, $T(x)$ is by construction exactly divisible by $g(x)$. The receiver divides the whole received block by the same $g(x)$: a zero remainder means the block is a valid codeword and is accepted, and any non-zero remainder proves an error. Writing the received block as $T(x) + E(x)$, where $E(x)$ has a one in every corrupted position, the remainder depends only on $E(x)$, so an error escapes detection if and only if $g(x)$ divides $E(x)$ exactly. This is what makes the choice of generator an engineering decision rather than an arbitrary one. A generator with at least two non-zero terms detects every single-bit error, since $E(x) = x^{j}$ cannot be divisible by it; a generator containing the factor $(x+1)$ detects every error affecting an odd number of bits; and a generator of degree $r$ detects every burst of length $r$ or less, because such a burst is $x^{j}$ times a polynomial of degree below $r$, which cannot be a multiple of $g(x)$. Standard generators such as the 32-bit CRC of Ethernet are chosen to have all of these properties at once, and the whole computation reduces in hardware to a shift register of $r$ stages with exclusive-OR taps at the non-zero coefficients of $g(x)$, which is why a CRC can be computed at line rate.

1. Part (b) — set up the division. Here $g(x) = x^{2}+1$, so $r = \deg g = 2$ and two check bits will be appended. Shifting the message left by two places gives $$x^{r}i(x) = x^{2}\cdot x^{5} = x^{7}$$ which in bits is 10000000, the six information bits 100000 followed by two zeros.
2. Divide modulo 2. Long division of $x^{7}$ by $x^{2}+1$ over GF(2) proceeds in three steps: $x^{7} \oplus x^{5}(x^{2}+1) = x^{5}$, then $x^{5} \oplus x^{3}(x^{2}+1) = x^{3}$, then $x^{3} \oplus x(x^{2}+1) = x$. The degree of $x$ is now less than $\deg g = 2$, so the division stops with $$q(x) = x^{5}+x^{3}+x, \qquad R(x) = x$$ The same result follows in one line from modular arithmetic: since $x^{2} \equiv 1 \pmod{x^{2}+1}$, we have $x^{7} = x\,(x^{2})^{3} \equiv x \cdot 1 = x$.
3. Form the codeword. Appending the two check bits, which are the coefficients of $R(x) = x$, that is 10, to the shifted message gives $$T(x) = x^{7} + x$$ $$\boxed{T(x) = x^{7}+x \;\longrightarrow\; 1\,0\,0\,0\,0\,0\,1\,0}$$ that is the eight-bit output 10000010, made of the information bits 100000 and the CRC bits 10.
4. Check the answer. A valid codeword must divide exactly, and $$x^{7}+x = x\,(x^{6}+1) = x\,(x^{2}+1)(x^{4}+x^{2}+1)$$ so the remainder on division by $g(x)$ is zero, as required. It is also worth noting that $g(x) = x^{2}+1 = (x+1)^{2}$ over GF(2) is a poor generator in practice: it has a repeated root, so although it catches all single-bit errors and all bursts of length two or less, it fails on the double error $E(x) = x^{j}(x^{2}+1)$. A real system uses a primitive or standardised polynomial such as CRC-16 or CRC-32.

Part (c) — the operation of ARQ. Automatic repeat request is the family of protocols that turns an unreliable link into a reliable one using three ingredients: an error-detecting code such as the CRC above, an acknowledgement returned by the receiver, and a timer at the sender. The receiver checks each frame and acknowledges only those that pass; the sender retains a copy of every unacknowledged frame and retransmits it when the timer expires. Sequence numbers are what make this safe, because an acknowledgement can itself be lost and the resulting retransmission would otherwise be accepted as new data. In stop-and-wait ARQ the sender transmits one frame and then waits: it sends nothing further until the acknowledgement arrives or the timer expires. A single-bit sequence number alternating 0 and 1 suffices, since only one frame is ever outstanding, and the acknowledgement carries the number of the frame expected next so that a duplicate can be discarded. The protocol is trivial to implement and needs one frame buffer at each end, but it leaves the link idle for a whole round trip after every frame. In go-back-N ARQ the sender may have up to $N$ frames outstanding, a sliding window that advances as acknowledgements arrive; acknowledgements are cumulative, so an acknowledgement of frame $j$ implicitly acknowledges everything before it. The receiver keeps a window of one and simply discards any frame arriving out of order, which is why an error is expensive: when frame $j$ is lost or damaged, the receiver rejects $j+1, j+2, \ldots$ as well, and on timeout the sender goes back and retransmits frame $j$ and every frame after it. That keeps the receiver simple at the cost of retransmitting up to $N$ frames per error, and it requires the sequence number modulus to exceed the window, so $m$-bit sequence numbers permit $N \le 2^{m}-1$. Selective-repeat ARQ is the third member of the family: it buffers out-of-order frames at the receiver and retransmits only the frame actually lost, which is more efficient on a high error rate link but needs a receiver window, a reassembly buffer, and a modulus of at least $2N$.

1. Part (d) — compare the two efficiencies. With frame transmission time $T_{f} = L/R$ and one-way propagation delay $\tau$, define the normalised delay $a = \tau / T_{f}$. Stop-and-wait occupies the link for $T_{f}$ out of every $T_{f} + 2\tau$, so $$\eta_{SW} = \frac{T_{f}}{T_{f}+2\tau} = \frac{1}{1+2a}$$ whereas go-back-N sends $N$ frames per round trip and so achieves $\eta_{GBN} = \min\bigl(1,\ N/(1+2a)\bigr)$, which is $N$ times better until the window is large enough to fill the pipe.
2. Put the worked numbers in. For the 1 Mbit/s satellite link, $T_{f} = 1000/10^{6} = 1\text{ ms}$ and $\tau = 270\text{ ms}$, so $a = 270$ and $1+2a = 541$. Then $$\eta_{SW} = \frac{1}{541} = 0.185\ \%$$ — the link delivers about 1.85 kbit/s of the 1 Mbit/s available — while a window of $N = 7$ gives $$\eta_{GBN} = \frac{7}{541} = 1.29\ \%,$$ about 12.9 kbit/s, exactly seven times as much. Filling the pipe completely would need $N \ge 541$ frames outstanding, which is why satellite links use large windows and the TCP window scale option.
3. State the conclusion. When the propagation delay is large compared with the frame transmission time, $\boxed{\text{go-back-N is the more efficient}}$, because it keeps the link busy during the round trip instead of leaving it idle. The advantage grows in direct proportion to the window size, and it disappears only when the error rate is high enough that the $N$ frames discarded after each loss outweigh the gain — the regime in which selective repeat becomes worthwhile.