Flow & Error Control
Ensuring reliable and paced data transmission.
Where does this happen? structure
In the Data Link Layer, these responsibilities generally fall under the Logical Link Control (LLC) sublayer (the upper sublayer of DLL), while the MAC sublayer handles media access.
Flow Control
What is Flow Control?
Flow control is a set of procedures that tells the sender how much data it can transmit before it must wait for an acknowledgment from the receiver.
The Why: Speed Mismatch
If the sender transmits data faster than the receiver can process/buffer it, the receiver's buffer will overflow, and data will be lost. Flow control prevents this by ensuring the sender respects the receiver's pace.
(Fast)
(Slow/Busy)
Error Control
What is Error Control?
Error control includes both error detection and error correction. In the Data Link Layer, this is largely achieved through checks (like CRC) and retransmission schemes generally referred to as ARQ (Automatic Repeat Request).
Identifying that a frame has been corrupted or lost during transmission (e.g., via checksums or CRC).
Recovering lost/damaged data by asking the sender to retransmit (Retransmission).
Crucial Distinctions
Crucial Distinctions
Flow Control
Concerned with the Rights of the Receiver.
"I only have x amount of buffer memory left, please don't send more than x."
Congestion Control
Concerned with the Rights of the Medium (Network).
"The network links are too busy/congested, we must slow down to prevent packet drops in the routers."
Classification of Flow Control
Flow and Error control protocols are categorized based on the nature of the channel (Ideal/Noiseless vs. Real/Noisy).
For Noiseless Channel (Ideal)
Assumes a perfect channel where no frames are lost, duplicated, or corrupted. (Theoretical).
Simplest Protocol
Unrestricted Simplex. Sender sends as fast as it can. No flow control.
Stop-and-Wait
Sender sends one frame, then stops and waits for ACK before sending the next. (Flow Control added).
For Noisy Channel (Real World)
Real channels have noise. Frames can be damaged or lost. Uses ARQ (Automatic Repeat Request) for Error Control.
Stop-and-Wait ARQ: Deep Dive
In a noisy channel, we need to handle lost or corrupted frames. Stop-and-Wait ARQ adds three key elements to the basic Stop-and-Wait protocol:
- Sequence Numbers: Frames are numbered 0 and 1 alternately to detect duplicates.
- Acknowledgments (ACK): The receiver sends an ACK number (e.g., ACK 1 means "I expect frame 1 next").
- Time-out Timer: The sender starts a timer after sending. If it expires before ACK arrives, the frame is retransmitted.
Protocol Scenarios
Measuring Performance
1. Total Time Calculation
The total time to complete one transaction is theoretically:
Assumptions for Simplification:
- Queuing & Processing Delays are generally considered 0.
- ACK Transmission Time (Tt(ack)) is negligible (very small size).
- Propagation Time is same for Data and ACK (Tp(data) ≈ Tp(ack) = Tp).
Applying these assumptions gives the simplified formula:
(Note: 2 × Tp is often called the Round Trip Time (RTT))
2. Delay Definitions
- Processing Delay (Delaypro)Time required for the receiver/destination to process the packet header, perform error detection, and deliver to the upper layer.
- Queuing Delay (Delayque)Time a packet waits in the input and output queues of a router.
3. Efficiency (η) Derivation
Useful time is Tt (Transmission Time). This is the only time we are actually putting data onto the link.
For the rest of the cycle ($2 \times T_p$), we are just waiting for the signal to propagate and the ACK to return. Ideally, we could have used this waiting time to send more packets.
4. Effective Bandwidth / Throughput
Throughput is the valid amount of data that the receiver actually receives and processes per second.
Since the sender has to wait for ACKs and transmission delays, we cannot use the full link capacity (Bandwidth) continuously. Thus, Throughput ≤ Bandwidth.
Efficiency Limitations
The Bandwidth-Delay Product (Capacity)
The Bandwidth-Delay Product (B × Delay) represents the volume of the link in bits—how many bits can fill the pipe from sender to receiver.
The Pipe Analogy: High Speed Link
Imagine a Thick Pipe (High Bandwidth) that is very Long (High Delay/Distance).
This pipe has a huge volume (Capacity).
Stop-and-Wait sends 1 frame and waits. The huge capacity is wasted.
Summary: Stop-and-Wait ARQ fails to utilize the full capacity of high-speed, long-distance channels, leading to very low efficiency in modern networks.
Go-Back-N Automatic Repeat Request
Need for Pipelining
Go-Back-N ARQ significantly enhances transmission efficiency over Stop-and-Wait by using the concept of Pipelining. It allows multiple frames to be in transit (sent but not yet acknowledged) at the same time, keeping the channel busy.
Sending Multiple Frames
Several frames can be sent one after another without waiting for individual ACKs. The sender keeps copies of all outstanding frames until they are acknowledged.
Cumulative ACK
The receiver sends a Cumulative Acknowledgment. ACK n means "I have correctly received all frames before n, and I am expecting frame n next."
The Sliding Window Concept
The receiver is simple. It looks for exactly one sequence number (Rn). If the arriving frame matches Rn, it takes it, slides the window, and updates Rn. Any out-of-order frame is discarded.
Control Variables
- SfSequence number of the First outstanding frame. The window starts here.
- SnSequence number of the Next frame to be sent.
- RnSequence number of the frame expected by the receiver.
- Timer ManagementThere is only ONE timer running at any time, typically for the oldest outstanding frame (Sf). If it expires, all outstanding frames are resent.
Sequence & Windows
Since Wr (Receive Window) is always 1 in Go-Back-N:
If the window size equaled the sequence space range, the receiver couldn't distinguish between new frames and duplicates after an ACK loss scenario. We must leave at least 1 sequence number unused to avoid ambiguity.
Mathematical Analysis (Efficiency)
1. Efficiency (η)
Unlike Stop-and-Wait, we send N frames in one RTT.
(where a = Tp / Tt)
- If Ws ≥ 1 + 2a, then η = 1 (100% utilization).
- Otherwise, efficiency is limited by the window size.
2. Optimal Window Size
To fill the pipe completely (100% Efficiency):
3. Sequence Number Bits (m)
To support the optimal window size:
Since Ws = 2m - 1, we need enough bits to cover the optimal window.
Error Handling: The "Go-Back-N"
The name Go-Back-N clearly describes the error handling strategy:
- If a frame is damaged or lost, the receiver discards it and all subsequent frames (since it only accepts orderly data).
- The receiver sends no ACK (or sometimes a NAK/ACK for the last good frame).
- The Sender's timer for the oldest frame expires.
- The Sender Goes Back to the lost frame and resends N frames (all frames currently in the window).