Reliability in the Data Link Layer
When data is transmitted over a physical medium, the journey is rarely perfect. Signals can become distorted by electrical noise, frames can be entirely lost, and a fast sender can easily overwhelm a slow receiver.
To combat these issues, the Data Link Layer employs two critical mechanisms: Error Control, to detect and correct corrupted data, and Flow Control, to regulate transmission speeds and prevent receiver buffer overflow.
Part A: Error Control
Error control is a strict set of techniques used to guarantee that every single frame sent by the transmitter successfully reaches the receiver without corruption. It relies on a protocol mechanism known as Automatic Repeat Request (ARQ).
Automatic Repeat Request (ARQ)
In ARQ, the receiver explicitly sends feedback messages to the sender. An Acknowledgement (ACK) confirms a frame arrived correctly. A Negative Acknowledgement (NAK) indicates a frame arrived corrupted. If the sender's timer expires without receiving an ACK, it assumes the frame was lost and retransmits it.
1. Stop and Wait ARQ
The simplest error control mechanism. The sender transmits exactly one frame and completely stops until an ACK is received. If the timer expires, it retransmits that single frame.
- Example: Device A sends Frame 0. Device B receives it and replies with ACK 1 (meaning 'I received 0, send 1'). Device A sends Frame 1. If Frame 1 is lost, Device A's timer expires, and it retransmits Frame 1.
- Advantages: Extremely simple to implement and logically guarantees delivery.
- Disadvantages: Highly inefficient. The communication channel sits completely idle while waiting for the ACK, wasting massive amounts of bandwidth.
2. Go Back N ARQ (Sliding Window)
To improve efficiency, the sender can transmit multiple frames up to a predefined window size N before requiring an acknowledgement. However, if a single frame is lost, the receiver discards it and all subsequent frames, forcing the sender to retransmit the entire sequence.
- Example: With a window of 4, the sender transmits frames 0, 1, 2, 3. Frame 1 is lost. The receiver gets Frame 2 but strictly discards it because Frame 1 is missing. It discards Frame 3 as well. The sender goes back to Frame 1 and retransmits 1, 2, and 3.
- Advantages: Keeps the channel busy and does not require complex buffering at the receiver.
- Disadvantages: Highly wasteful when error rates are high because perfectly valid frames are discarded and retransmitted unnecessarily.
3. Selective Repeat ARQ
A highly optimized sliding window protocol where only the specific frame that was lost or corrupted is retransmitted. The receiver actively buffers out of order frames until the missing piece arrives.
- Example: Sender transmits frames 0, 1, 2, 3. Frame 1 is lost. The receiver buffers frames 2 and 3 safely and sends NAK 1. The sender retransmits only Frame 1. The receiver then processes 0, 1, 2, 3 in perfect order.
- Advantages: Maximum efficiency. No bandwidth is wasted retransmitting valid frames.
- Disadvantages: Requires highly complex logic and significant memory buffers at both ends.
Part B: Flow Control
Flow control is the strict regulation of the data transmission rate. Its primary goal is to completely prevent the receiver's memory buffer from overflowing when dealing with a fast sender.
1. Stop and Wait Flow Control
Identical to its ARQ counterpart, the sender transmits one frame and completely stops until the receiver explicitly grants permission to send the next.
- Efficiency Formula: Efficiency = 1 / (1 + 2a), where a is the ratio of Propagation Delay to Transmission Time. If propagation delay is high, efficiency plummets.
- Conclusion: Perfect for completely preventing buffer overflow, but terribly inefficient over long distance networks.
2. Sliding Window Flow Control
The sender maintains a logical window of size W, representing the maximum number of frames it can send continuously. As acknowledgements arrive, the window slides forward, granting permission to send new frames without ever stopping.
- Example: With a window of 4, the sender blasts out frames 0, 1, 2, 3. As soon as ACK 0 arrives, the window slides, allowing the sender to instantly transmit Frame 4 without pausing.
- Efficiency Formula: If W >= 1 + 2a, efficiency is 100%. If W < 1 + 2a, Efficiency = W / (1 + 2a). A larger window size directly results in vastly superior channel utilization.
Comparing the ARQ Protocols
| Feature | Go Back N ARQ | Selective Repeat ARQ |
|---|---|---|
| Retransmission Scope | The erroneous frame plus all frames sent after it. | Strictly only the erroneous frame. |
| Receiver Buffer | Not required. | Strictly required to hold out of order frames. |
| Maximum Window Size | N - 1 | N / 2 |
| Overall Efficiency | Low in noisy networks. | Extremely high in all networks. |