Error Control & Flow Control: ARQ, CRC, Sliding Windows, Congestion Handling

TAKEAWAYS:

• Error detection uses CRC to generate checksums that catch transmission errors without retransmitting data.
• Stop-and-Wait ARQ pauses after each frame to confirm receipt, while Selective Repeat ARQ allows overlapping retransmissions for efficiency.
• Sliding window flow control dynamically adjusts the sender’s buffer size to match receiver capacity, preventing overflow.
• Congestion control (e.g., TCP’s slow start) detects network overload via packet loss or delay and throttles traffic to avoid collapse.
• Hybrid ARQ combines error correction and retransmission for real-time apps like video calls.
• Flow control vs. congestion control: flow control is sender-receiver coordination; congestion control is network-wide traffic management.

1. Error Detection: Cyclic Redundancy Check (CRC)

Error detection ensures data arrives intact. CRC adds redundancy bits to detect errors without retransmitting the entire message.

How CRC Works

1. Divide the data frame by a predefined generator polynomial (e.g., G(x) = x³ + x + 1).
2. Compute remainder (CRC bits) and append it to the frame.
3. Receiver divides the incoming frame by the same G(x); if remainder ≠ 0, an error occurred.

sequenceDiagram
    participant Sender
    participant Channel
    participant Receiver
    Sender->>Channel: Data || CRC bits
    Channel->>Receiver: Data (possibly corrupted)
    Receiver->>Receiver: Divide by G(x)
    alt No remainder
        Receiver->>Sender: ACK
    else Remainder ≠ 0
        Receiver->>Sender: NAK
    end

Example: CRC-16 Calculation

Data: 10110100 (8 bits) Generator: G(x) = x¹⁶ + x¹⁵ + ... + x¹ + 1 (CRC-16 polynomial)

1. Append 16 zeros: 10110100 0000000000000000
2. Divide by G(x); remainder becomes CRC: 1101001000101101
3. Final frame: 10110100 1101001000101101

Advantages:

• Detects burst errors (multiple consecutive bits flipped).
• Simple to implement in hardware.

Disadvantages:

• Cannot correct errors (only detect).
• Overhead of CRC bits (e.g., CRC-16 adds 2 bytes).

2. Automatic Repeat Request (ARQ) Protocols

ARQ protocols use acknowledgments (ACK) and negative acknowledgments (NAK) to retransmit lost/corrupted frames.

A. Stop-and-Wait ARQ

• Sender sends one frame, waits for ACK/NAK.
• If no ACK within timeout, retransmits.

sequenceDiagram
    participant S as Sender
    participant R as Receiver
    participant C as Channel
    S->>C: Frame 1
    C->>R: Frame 1
    R->>R: CRC check
    alt Success
        R->>C: ACK 1
        C->>S: ACK 1
    else Error
        R->>C: NAK 1
        C->>S: NAK 1
        S->>C: Frame 1 (retransmit)
    end

Worked Example: eSewa Transaction

• When you pay via eSewa, the payment request frame (e.g., "Transfer ₹500 to ABC Bank") is sent with CRC.
• If the bank’s server NAKs due to network glitches, eSewa retransmits the frame until ACK is received.

Advantages:

• Simple to implement.
• Guarantees in-order delivery.

Disadvantages:

• Low efficiency: sender idles while waiting for ACK (100% channel utilization if ACK delay = propagation time).

B. Go-Back-N ARQ

• Sender can send N frames before waiting for ACK.
• On ACK for frame k, resends all frames ≥ k (even if earlier frames were lost).

sequenceDiagram
    participant S as Sender
    participant R as Receiver
    participant C as Channel
    loop Send N frames
        S->>C: Frame 1
        S->>C: Frame 2
        S->>C: Frame 3
    end
    C->>R: Frame 1 (corrupted), Frame 2, Frame 3
    R->>R: CRC check fails on Frame 1
    R->>C: NAK 1
    C->>S: NAK 1
    S->>C: Frame 1 (retransmit)
    S->>C: Frame 2 (already sent)
    S->>C: Frame 3 (already sent)
    R->>C: ACK 2
    S->>C: Frame 4

Worked Example: Daraz Order Processing

• When you order items on Daraz, the order confirmation frame (e.g., "Order #12345: 2 shirts") is part of a batch of frames.
• If the warehouse server NAKs Frame 3 (due to a server crash), Daraz goes back to Frame 3 and retransmits all subsequent frames (e.g., Frame 4, 5) until ACK is received.

Advantages:

• Higher throughput than Stop-and-Wait.
• No need for selective retransmission logic.

Disadvantages:

• Wastes bandwidth: retransmits already-ACKed frames.
• Out-of-order delivery possible if frames arrive in wrong order.

C. Selective Repeat ARQ

• Sender sends N frames, but only retransmits lost/corrupted frames.
• Receiver buffers frames until the first missing frame arrives.

sequenceDiagram
    participant S as Sender
    participant R as Receiver
    participant C as Channel
    loop Send N frames
        S->>C: Frame 1
        S->>C: Frame 2
        S->>C: Frame 3
    end
    C->>R: Frame 1 (lost), Frame 2, Frame 3 (corrupted)
    R->>R: Buffers Frame 2
    R->>C: NAK 1, NAK 3
    C->>S: NAK 1, NAK 3
    S->>C: Frame 1 (retransmit)
    S->>C: Frame 3 (retransmit)
    R->>C: ACK 2

Worked Example: Pathao Ride Coordination

• When you book a Pathao ride, the ride confirmation frame (e.g., "Driver XYZ assigned to your ride") is part of a sliding window of frames.
• If the driver’s app NAKs Frame 5 (due to a GPS signal drop), Pathao selectively retransmits only Frame 5, while Frame 6 (next ride update) proceeds.

Advantages:

• Efficient: only retransmits lost frames.
• Higher throughput than Go-Back-N.

Disadvantages:

• Complex: requires receiver buffering and sender tracking.
• Window size limits: if window > 2ⁿ⁻¹, frames may overlap and cause confusion.

3. Flow Control Mechanisms

Flow control ensures the receiver’s buffer isn’t overwhelmed by the sender’s speed.

A. Stop-and-Wait Flow Control

• Sender stops after sending one frame until ACK is received.
• No buffer management: simple but inefficient.

B. Sliding Window Flow Control

• Sender can send up to W frames before waiting for ACK.
• Receiver advertises its available buffer space via ACK (e.g., ACK 5 (window=3) means "I can receive 3 more frames after Frame 5").

sequenceDiagram
    participant S as Sender
    participant R as Receiver
    participant C as Channel
    S->>C: Frame 1 (window=3)
    S->>C: Frame 2 (window=3)
    S->>C: Frame 3 (window=3)
    C->>R: Frame 1, Frame 2, Frame 3
    R->>C: ACK 3 (window=2)  # "I can take 2 more frames"
    S->>C: Frame 4 (window=2)
    S->>C: Frame 5 (window=2)

Worked Example: NTC Call Center Queue

• When you call NTC for a complaint, the call handler’s "window" is their ability to process 3 calls at once.
• If the queue exceeds their window (e.g., 5 calls arrive), NTC slows down new calls (flow control) to avoid dropping calls (congestion).

Advantages:

• Balances sender/receiver speeds.
• Works with ARQ protocols.

Disadvantages:

• Window size tuning is critical (too small = underutilization; too large = overflow).

4. Congestion Control

Congestion occurs when too many packets flood the network, causing delays or drops. Unlike flow control (sender-receiver), congestion control is network-wide.

A. Causes of Congestion

• Too many sources sending data (e.g., sudden surge in Daraz orders during a sale).
• Link capacity exceeded (e.g., Ncell tower overwhelmed during a match).
• Packet loss due to buffer overflow in routers.

B. Congestion Control Techniques

Example: TCP’s Congestion Control

1. Slow Start: Start with window size = 1 MSS (Maximum Segment Size). Double it every RTT (Round-Trip Time) until loss.
2. Congestion Avoidance: After threshold, increase window by 1 MSS per RTT.
3. Fast Recovery: If 3 duplicate ACKs arrive (indicating loss), halve the window and enter congestion avoidance.

stateDiagram-v2
    [*] --> SlowStart: Window = 1 MSS
    SlowStart --> SlowStart: Double window (until loss)
    SlowStart --> CongestionAvoidance: Loss detected
    CongestionAvoidance --> CongestionAvoidance: Increase window by 1 MSS
    CongestionAvoidance --> FastRecovery: 3 duplicate ACKs
    FastRecovery --> CongestionAvoidance: Halve window, enter avoidance

Worked Example: Kathmandu Traffic Jam

• Imagine Kathmandu’s roads as a network link. During peak hours, too many cars (packets) enter the city (router buffer fills).
• Congestion control would:
  1. Slow down entry (reduce window size) if traffic (packet loss) increases.
  2. Redirect routes (like TCP’s alternative paths) to balance load.
  3. Drop some cars (packet discarding) if buffers are full (RED policy).

5. Hybrid ARQ (HEC + ARQ)

Combines error correction (Forward Error Correction, FEC) and ARQ for real-time apps.

• FEC: Adds redundancy to correct errors (e.g., Reed-Solomon codes).
• ARQ: Retransmits if correction fails.

Example: YouTube Video Streaming

• YouTube uses HEC to correct minor packet losses (e.g., due to Wi-Fi interference).
• If the error is too large, it retransmits the segment (ARQ).

Comparison Table: ARQ Protocols

In the Real World

1. eSewa’s Transaction Security

   • Uses CRC-32 to detect corrupted payment frames during bank transfers.
   • Implements Stop-and-Wait ARQ for critical transactions (e.g., loan repayments) to ensure no data loss.

2. Daraz’s Order Fulfillment

   • Employs Selective Repeat ARQ to retransmit only failed order confirmations (e.g., if a warehouse server crashes mid-processing).
   • Uses sliding window flow control to match warehouse capacity (e.g., 500 orders/hour) with server speed.

3. Ncell’s 5G Network

   • Deploys TCP’s congestion control to dynamically adjust data rates during peak hours (e.g., during the IPL match).
   • Uses RED (Random Early Detection) to drop packets proactively when buffers fill, preventing total collapse.

Exam Tip

• For ARQ diagrams: Always label sequence numbers, ACK/NAK, and timeout events. Use timelines to show retransmissions.
  • Example: In Selective Repeat, show how Frame 3 is retransmitted while Frame 4 proceeds.
• For CRC: Memorize common polynomials (e.g., CRC-8 = x⁸ + x² + x + 1).
• For congestion control: Link TCP’s slow start to real-world scenarios (e.g., "Why does YouTube buffer during peak hours?").
• Compare Stop-and-Wait vs. Go-Back-N vs. Selective Repeat in a table with throughput, buffer needs, and use cases.
• Hybrid ARQ is often asked in practicals—mention FEC + ARQ and give an example like video streaming.

Key Formula to Remember

• CRC remainder: Data(x) * xᵏ + CRC(x) ≡ 0 mod G(x)
• Sliding window efficiency: Throughput = (Window size) / (RTT)