2. Data Link Layer (DLL): Flow & Error Control

This chapter covers Lectures 3 (flow control) and 4 (error control). Both look at one link between two nodes: a sender and a receiver. They answer two questions:

1. Flow control: how does the sender avoid sending faster than the receiver can store the frames?
2. Error control: what does the sender do when a frame is lost or damaged?

These topics carry most of the calculations in Part I: link utilisation, window size, and how fast a middle node must send so that its buffer does not overflow. Section 6 shows how to use the formulas for each of these.

1. Where This Fits

The data link layer (DLL) moves frames across one link. Its jobs are framing, link access, flow control and reliable delivery. IEEE splits the DLL into two sub-layers: LLC (Logical Link Control, which faces the network layer) and MAC (Medium Access Control, which faces the medium).

Not examinable (slide labels): the list of DLL roles, framing (byte-oriented and bit-oriented), asynchronous start/stop bits, and link configuration (topology and duplex). Everything about flow control and ARQ is examinable.

2. The Four Times You Need

Every calculation in this chapter uses these quantities. Get the units right first.

Think of $a$ like this: if $a = 3$, the first bit of a frame arrives at the receiver only after the sender has sent 3 frames’ worth of time.

3. Flow Control

3.1 The problem

The receiver keeps each arriving frame in a buffer (a small memory) until it can process the frame. If the sender sends too fast, the buffer fills and new frames are lost. Flow control makes the sender wait for permission from the receiver.

In this section we assume that no frame has errors. Section 4 adds errors.

3.2 Stop-and-wait

The simplest method:

1. The source sends one frame.
2. The destination receives the frame.
3. The destination sends back an acknowledgement (ACK) when it is ready for the next frame.
4. The source waits until the ACK arrives.
5. The source sends the next frame.

The receiver can stop the flow at any time. It simply does not send the ACK.

Sequence numbers. Stop-and-wait only needs a 1-bit number: frames alternate 0, 1, 0, 1, …. The ACK carries the number of the frame that the receiver expects next. So “ACK1” means “I have frame 0, now send frame 1”.

3.3 Link utilisation of stop-and-wait

Link utilisation $U$ is the fraction of time the link carries useful data:

$$U = \frac{\text{time spent sending data}}{\text{total time of one cycle}} = \frac{T_{\text{frame}}}{T_{\text{cycle}}}$$

One cycle has these parts:

$$T_{\text{cycle}} = T_{\text{frame}} + T_{\text{prop}} + T_{\text{proc}} + T_{\text{ACK}} + T_{\text{prop}} + T_{\text{proc}}$$

The ACK is very short and processing is fast, so we ignore $T_{\text{ACK}}$ and $T_{\text{proc}}$:

$$T_{\text{cycle}} \approx T_{\text{frame}} + 2T_{\text{prop}} \quad\Rightarrow\quad \boxed{U_{\text{S\&W}} = \frac{T_{\text{frame}}}{T_{\text{frame}} + 2T_{\text{prop}}} = \frac{1}{1 + 2a}}$$

Worked example (lecture). $R = 2.4$ Mbit/s, $d = 50$ km, $v = 2\times10^8$ m/s, $L = 300$ bytes.

• $T_{\text{prop}} = 50\,000 / (2\times10^8) = 250\ \mu$s
• $T_{\text{frame}} = 2400 / (2.4\times10^6) = 1000\ \mu$s
• $a = 250 / 1000 = 0.25$
• $U = 1 / (1 + 0.5) = 2/3 \approx \mathbf{66.7\%}$

3.4 What is wrong with stop-and-wait

• Lost frame or lost ACK. The source waits for ever. We need a timeout: if no ACK arrives in time, the source sends the frame again. (Section 4 covers this.)
• Long links. When $a$ is large, the sender is idle for most of the cycle. For example, $a = 10$ gives $U = 1/21 < 5\%$. The bottom of the fraction, $1 + 2a$, is set by physics. We cannot make it smaller. But we can make the top bigger by sending more than one frame per cycle. That is the sliding window.

3.5 Sliding window

The idea. The receiver has buffers for $N$ frames. So the sender may send up to $N$ frames before it gets an ACK.

Rules:

• Each frame carries a sequence number with $k$ bits. The numbers go $0, 1, \dots, 2^k - 1$, then start again at 0 (we count modulo $2^k$).
• An ACK carries the number of the next frame the receiver expects. “ACK 3” means “I have everything up to frame 2. Send frame 3 next.” One ACK can acknowledge many frames at once.
• Sender window: the list of frames that the sender may send now. It shrinks from the left (trailing edge) each time the sender sends a frame. It grows at the right (leading edge) each time an ACK arrives.
• Receiver window: the list of frames the receiver can accept. It shrinks as frames arrive and grows as the receiver sends ACKs.

Two extra controls:

• RNR (Receive Not Ready): “I have your frames up to $n-1$, but stop sending.” To restart the flow, the receiver later sends a normal ACK (RR).
• Piggybacking: when both sides send data, a node puts its ACK number inside its own data frame. This saves sending a separate ACK frame.

Window size limit for pure flow control. With $k$ bits there are $2^k$ different numbers, so the window can hold at most $2^k$ frames:

$$N \le 2^k$$

The ARQ methods in Section 4 need a smaller limit. Use the ARQ limit when the question includes errors.

3.6 Link utilisation of sliding window

Time starts when the sender sends the first bit of frame 0. The ACK for frame 0 comes back at time $T_{\text{frame}} + 2T_{\text{prop}} = T_{\text{frame}}(1 + 2a)$. In that time the sender can send $(1 + 2a)$ frames. There are two cases:

• Case 1: $N \ge 1 + 2a$. The ACK for frame 0 arrives before the window is used up. The sender never stops. $U = 1$.
• Case 2: $N < 1 + 2a$. The sender sends $N$ frames in $N \cdot T_{\text{frame}}$, then waits for the ACK. Each cycle lasts $T_{\text{frame}}(1+2a)$.

$$\boxed{U_{\text{SW}} = \begin{cases} 1 & N \ge 1 + 2a \\[4pt] \dfrac{N}{1 + 2a} & N < 1 + 2a \end{cases}}$$

Stop-and-wait is the special case $N = 1$.

Smallest window for a target throughput. A 100 kbit/s link carries 1000-bit frames. $T_{\text{prop}} = 25$ ms. No errors. What is the smallest window that gives at least 50 kbit/s?

• $T_{\text{frame}} = 1000 / 100\,000 = 10$ ms, so $a = 25/10 = 2.5$ and $1 + 2a = 6$.
• We need $U \ge 50/100 = 0.5$.
• $N/(1+2a) \ge 0.5 \Rightarrow N \ge 3$. So $N = \mathbf{3}$. If the division gives a fraction, round up, because a window is a whole number of frames.
• Check the sequence number: with $k = 2$ bits, $N \le 2^2 = 4$, so 2 bits are enough.

4. Error Control (ARQ)

4.1 Two kinds of frame error

• Lost frame: the frame does not arrive, or its header is so damaged that the receiver cannot recognise it.
• Damaged frame: the frame arrives, but some bits are wrong. The receiver’s error check finds this.

4.2 Two ways to deal with errors

• Forward Error Correction (FEC): the sender adds extra bits so that the receiver can repair errors itself (for example, Hamming codes and Reed–Solomon codes).
• Automatic Repeat reQuest (ARQ): the receiver finds the error, and the sender sends the frame again. This happens in two ways:
  • retransmission after a timeout (no ACK arrives in time), and
  • retransmission on request (the receiver sends a NAK, a negative acknowledgement).

ARQ turns an unreliable link into a reliable one. Each flow-control method has an ARQ version:

Not examinable (slide labels): parity check, the “seven prisoners” puzzle, and CRC.

4.3 Stop-and-wait ARQ

The source keeps a copy of the frame and starts a timer when it sends.

Utilisation. Let $P$ be the probability that a frame is in error. On average a frame needs $1/(1-P)$ attempts. So:

$$\boxed{U_{\text{S\&W ARQ}} = \frac{1 - P}{1 + 2a}}$$

Lecture example: with $a = 0.25$ and $P = 0.1$, $U = 0.9 / 1.5 = 0.6$.

4.4 Go-back-N ARQ (the “cautious” method)

The receiver accepts frames only in order.

• Frame types: RR = ACK (receive ready), RNR = receive not ready (flow control), REJ = NAK (reject).
• At the destination: when frame $i$ has an error, the destination sends REJ $i$. It then discards frame $i$ and every frame after it until a good copy of frame $i$ arrives.
• At the source: after a REJ $i$ or a timeout, the source goes back and sends frame $i$ and every frame after it again.

Maximum window for Go-back-N:

$$\boxed{N_{\text{GBN}} \le 2^k - 1}$$

Why not $2^k$? Take $k = 3$, so the numbers are 0 to 7.

• With $N = 8$: the source sends frames 0 to 7. All arrive, and the receiver now expects a new frame 0. Its ACK is lost. The source times out and sends the old frame 0 again. The receiver cannot tell old from new. It accepts the old frame 0 as new data. Error.
• With $N = 7$: the source sends frames 0 to 6. The receiver now expects frame 7. The old frame 0 arrives. It is not frame 7, so the receiver discards it. Correct.

Utilisation. The exact Go-back-N formula is not required. The lecture says: use the selective-reject formula for Go-back-N too.

4.5 Selective-reject ARQ (the “efficient” method)

Also called selective repeat. The receiver accepts frames out of order if they fall inside its window.

• At the destination: when frame $i$ has an error, the destination sends SREJ $i$ (selective reject). It keeps and buffers the frames that arrive after $i$.
• At the source: the source sends again only frame $i$ (and any frame whose timer ran out).
• When the good copy of frame $i$ arrives, the destination puts the frames back in order and passes them up.

Maximum window for selective-reject:

$$\boxed{N_{\text{SR}} \le 2^{k-1}}$$

Why half? Take $k = 3$.

• With $N = 5$: the source sends frames 0 to 4. All arrive. The receiver window moves to {5, 6, 7, 0, 1}. The ACKs are lost. The source times out and sends the old frame 0. Frame 0 is inside the new window, so the receiver accepts it as new. Error.
• With $N = 4$: the window moves to {4, 5, 6, 7}. The old frame 0 is outside the window, so the receiver discards it and sends ACK 4 again. Correct.

The rule: the old window and the new window must not share any number. Two windows of size $N$ must fit inside $2^k$ numbers, so $2N \le 2^k$.

Utilisation:

$$\boxed{U_{\text{SR}} = \begin{cases} 1 - P & N \ge 1 + 2a \\[4pt] \dfrac{N(1 - P)}{1 + 2a} & N < 1 + 2a \end{cases}}$$

4.6 Go-back-N versus selective-reject

5. Formula Summary

Throughput (in bit/s) $= U \times R$.

If the question gives a bit error probability $p_b$ instead of a frame error probability, the frame is good only if every bit is good:

$$P = 1 - (1 - p_b)^{L}$$

6. Using the Formulas

Every calculation in this chapter starts the same way. Write these four lines first, in one unit of time:

1. $T_{\text{frame}} = L / R$
2. $T_{\text{prop}} = d / v$ (or distance × delay per km)
3. $a = T_{\text{prop}} / T_{\text{frame}}$
4. $1 + 2a$

Then compare the window $N$ with $1 + 2a$ to choose the case. The rest of this section shows the kinds of question this leads to.

6.1 Utilisation, the best window, and the sequence bits

Setup. $R = 1$ Mbit/s, $L = 500$ bytes, $d = 1000$ km at 5 µs/km, frame error probability $P = 0.1$, selective-reject.

• $L = 4000$ bits, so $T_{\text{frame}} = 4000 / 10^6 = 4$ ms.
• $T_{\text{prop}} = 1000 \times 5\ \mu\text{s} = 5$ ms.
• $a = 5/4 = 1.25$, so $1 + 2a = 3.5$.

Utilisation for a given window, $N = 2$. $2 < 3.5$, so the window runs out before the first ACK returns:

$$U = \frac{N(1-P)}{1+2a} = \frac{2 \times 0.9}{3.5} = 0.514$$

The throughput is $0.514 \times 1 \text{ Mbit/s} = 514$ kbit/s.

The smallest window that gives the maximum utilisation. The sender never stops when $N \ge 1 + 2a = 3.5$. The window must be a whole number, so $N = \lceil 3.5 \rceil = \mathbf{4}$. Then $U = 1 - P = 0.9$. A larger window cannot do better, because errors still cost 10%.

The fewest sequence bits for that window. Each method has its own limit, so the answer depends on the method:

Header overhead. The sequence number sits in the frame header, so it carries no user data. If the question says that the frame length $L$ includes the $k$ sequence bits, only $(L - k)/L$ of each frame is useful. Multiply the utilisation by this fraction to get the useful utilisation.

6.2 Frame errors from bit errors

Sometimes the question gives a bit error probability $p_b$, not a frame error probability $P$. A frame is good only if every one of its $L$ bits is good:

$$P = 1 - (1 - p_b)^{L}$$

For $L = 2000$ bits and $p_b = 10^{-4}$: $P = 1 - 0.9999^{2000} \approx 0.181$. Longer frames have a higher $P$.

6.3 A middle node must not overflow its buffer

The problem. Frames go A → B → C. B stores each frame from A in its buffer, then sends it on to C. If frames arrive at B faster than B can send them on, the buffer fills and frames are lost. So B’s outgoing throughput must be at least its incoming throughput. The question usually asks for the slowest data rate on link B–C that achieves this.

Method:

1. Find the incoming throughput at B: $\text{throughput}_{AB} = U_{AB} \times R_{AB}$, with the correct $U$ formula for link A–B.
2. Write the outgoing throughput of link B–C in terms of the unknown rate $R$. For stop-and-wait, B sends one frame per cycle: $\dfrac{L}{T_{\text{frame}} + 2T_{\text{prop}}}$, with $T_{\text{frame}} = L/R$.
3. Set outgoing $\ge$ incoming. Solve for $T_{\text{frame}}$, then $R = L / T_{\text{frame}}$.

Example. All frames are 2000 bits, with no errors.

• A–B: $R = 200$ kbit/s, $T_{\text{prop}} = 15$ ms, sliding window $N = 2$.
• B–C: $T_{\text{prop}} = 5$ ms, stop-and-wait.

Step 1. On A–B, $T_{\text{frame}} = 10$ ms and $a = 1.5$, so $1 + 2a = 4$. Since $2 < 4$, $U = 2/4 = 0.5$. The incoming throughput is $0.5 \times 200 = 100$ kbit/s. In time: A sends 2 frames every 40 ms.

Step 2. On B–C, one cycle takes $T_{\text{frame}} + 2 \times 5 = T_{\text{frame}} + 10$ ms.

Step 3. Solve:

$$\frac{2000 \text{ bits}}{T_{\text{frame}} + 10\text{ ms}} \ge 100 \text{ bit/ms} \;\Rightarrow\; T_{\text{frame}} \le 10 \text{ ms} \;\Rightarrow\; R \ge \frac{2000 \text{ bits}}{10 \text{ ms}} = \mathbf{200\ kbit/s}$$

The same chain with ARQ on A–B. Now let link A–B have $P = 0.1$ and a 2-bit sequence number, and let A use the largest window that its method allows. Link B–C stays the same.

Go-back-N allows a larger window for the same $k$, so A sends faster, and B–C must be faster too.

Sanity check. Stop-and-wait can never carry more than $L / (2T_{\text{prop}})$, even with an infinite data rate, because every cycle includes the round trip. Here that is $2000 / 10 \text{ ms} = 200$ kbit/s. If the incoming throughput is larger than this, no rate on B–C works. Say so in your answer.

7. HDLC Time-Sequence Diagrams

HDLC (High-level Data Link Control) is a standard data link protocol that uses sliding windows. A time-sequence diagram shows the frames that two stations, A and B, send to each other over time. You must be able to label every frame in such a diagram.

7.1 The three frame types

All numbers are modulo $2^k$. With 3 bits, the number after 7 is 0.

7.2 Method

1. Treat the two directions separately. Each side has its own sequence counter.
2. For each sender, number its I-frames one after another: $i, i+1, i+2, \dots$ (mod 8).
3. For the second number $j$ in an I-frame, look at the frames that this side has received so far from the other side. $j$ = (last in-order frame received) + 1.
4. A lost frame does not move the receiver’s counter. When a later frame arrives, the receiver sees the gap and sends SREJ for the missing number.
5. After the missing frame arrives, the next RR or $j$ value jumps to one past the highest frame received.

7.3 Example trace

$k = 3$. A’s next frame number is 6. B’s next frame number is 0. Neither side has received anything yet.

In step 3, the two zeros mean different things. The first 0 is B’s own frame number. The second 0 is the next frame B expects from A.

8. Common Traps

• Convert bytes to bits. Convert all times to the same unit before you divide.
• Write $T_{\text{frame}}$, $T_{\text{prop}}$, $a$ and $1 + 2a$ first. Most of the work is in these four lines.
• Compare $N$ with $1 + 2a$ before you choose the formula. $U$ never goes above 1 (or $1 - P$ with errors).
• Window limits differ by method: flow control $2^k$; Go-back-N $2^k - 1$; selective-reject $2^{k-1}$. Use the ARQ limit whenever the link has errors.
• The smallest window for the maximum $U$ is $N = \lceil 1 + 2a \rceil$. Round up. Then find $k$ from the correct limit.
• Go-back-N has no separate formula in this course. Use the selective-reject formula for it.
• ACK $n$ (or RR $n$) means “the next frame I expect is $n$”, not “I received frame $n$”.
• In I($i$, $j$), $i$ counts the sender’s own frames, and $j$ counts the other side’s frames.
• A frame error probability $P$ is not a bit error probability. Convert with $P = 1 - (1-p_b)^L$.
• For a buffer question, find the incoming throughput first, then solve for the outgoing rate. Stop-and-wait has a ceiling of $L / (2T_{\text{prop}})$ that no data rate can beat.
• FEC repairs errors at the receiver. ARQ resends. Parity, CRC and the “seven prisoners” puzzle are not examined.