Flow Control & ARQ Protocols: Stop-and-Wait, Go-Back-N, Selective Repeat

TAKEAWAYS:

• Flow control prevents sender overload by regulating data rate via feedback (ACK/NACK) and window sizes.
• Stop-and-Wait ARQ sends one frame at a time, waiting for ACK before proceeding (inefficient for high-speed links).
• Go-Back-N ARQ uses a sliding window to send multiple frames without waiting, discarding all frames after the first error (simpler but wasteful).
• Selective Repeat ARQ retransmits only corrupted frames using cumulative/individual ACKs (most efficient but complex).
• Real-world applications include eSewa’s transaction confirmation (Stop-and-Wait for critical steps) and Ncell’s bulk data transfers (Go-Back-N for speed).
• Key metrics: Throughput = $\frac{\text{Window Size}\times \text{Frame Size}}{\text{RTT}+\text{Transmission Time}}$.

1. Why Flow Control?

Flow control ensures the sender does not overwhelm the receiver by managing the rate of data transmission. Without it:

• Receiver buffers overflow → data loss.
• Network congestion → packet drops.
• Retransmissions → wasted bandwidth.

Real-world analogy: When ordering food via Pathao, the app waits for your "confirm order" (ACK) before sending the next request. If you’re slow to respond (slow receiver), the app doesn’t spam you with orders (flow control).

2. Flow Control Mechanisms

Two primary methods regulate data flow:

A. Stop-and-Wait (SW) Protocol

• How it works:
  1. Sender transmits one frame and waits for an ACK (acknowledgment).
  2. If ACK arrives → sends next frame.
  3. If NACK (negative ACK) or timeout → retransmits.
• Visual:

  sequenceDiagram
    participant Sender as Sender
    participant Receiver as Receiver
    Sender->>Receiver: Frame 1
    Receiver->>Sender: ACK (if OK) / NACK (if error)
    alt ACK
      Sender->>Receiver: Frame 2
    else NACK/Timeout
      Sender->>Receiver: Frame 1 (retransmit)
    end

• Advantages:
  • Simple to implement.
  • Guarantees in-order delivery.
• Disadvantages:
  • Low throughput (idle time waiting for ACK).
  • Inefficient for high-speed links (e.g., fiber optics).
• Throughput: $\text{Throughput}=\frac{1}{2T_p+T_p}=\frac{1}{2T_p}$ (where $T_p$ = propagation delay). Example: If $T_p=10$ ms, throughput = 50 frames/sec.

B. Sliding Window Protocols

To improve efficiency, multiple frames are sent before waiting for ACKs. Two types:

1. Go-Back-N (GBN)
2. Selective Repeat (SR)

3. Go-Back-N (GBN) ARQ Protocol

Key Idea: Sender transmits up to N frames without waiting for ACKs. If any frame is corrupted, all subsequent frames are discarded, and the sender goes back to the corrupted frame.

How GBN Works

1. Sender:
   • Maintains a window of N frames (e.g., N=4).
   • Sends frames 1–4, then waits for ACK.
   • If ACK 3 arrives → slides window to frames 5–8.
   • If ACK 2 arrives → retransmits frames 2–8 (goes back to frame 2).
2. Receiver:
   • Accepts frames in order.
   • Discards out-of-order frames (e.g., if frame 5 arrives before 4, it’s dropped).
   • Sends cumulative ACK (highest in-order frame received).

Visual:

sequenceDiagram
  participant Sender as Sender (Window=4)
  participant Receiver as Receiver
  Sender->>Receiver: Frame 1
  Sender->>Receiver: Frame 2
  Sender->>Receiver: Frame 3
  Sender->>Receiver: Frame 4
  Receiver->>Sender: ACK 2 (frame 2 corrupted)
  Sender->>Receiver: Frame 2 (retransmit)
  Sender->>Receiver: Frame 5
  Sender->>Receiver: Frame 6
  Sender->>Receiver: Frame 7
  Sender->>Receiver: Frame 8
  Receiver->>Sender: ACK 4 (frames 1-4 OK)

GBN Parameters

Example: GBN in Ncell Data Transfer

• Scenario: Your phone downloads a 100 MB file via Ncell’s 4G network using GBN (N=5).
• Steps:
  1. Phone sends frames 1–5.
  2. Frame 3 is lost → tower sends ACK 2 (cumulative).
  3. Phone discards frames 4–5 and retransmits frames 3–7.
  4. Process repeats until all frames are ACK’d.
• Why GBN?
  • Faster than Stop-and-Wait (parallel transmission).
  • Simpler than Selective Repeat (no per-frame ACKs).

Advantages/Disadvantages

4. Selective Repeat (SR) ARQ Protocol

Key Idea: Only corrupted frames are retransmitted. Receiver sends individual ACKs/NACKs for each frame.

How SR Works

1. Sender:
   • Sends up to N frames.
   • Uses individual ACKs (e.g., ACK 3 means only frame 3 was received).
   • Retransmits only lost/corrupted frames.
2. Receiver:
   • Buffers out-of-order frames.
   • Sends ACK/NACK for each frame.

Visual:

sequenceDiagram
  participant Sender as Sender (Window=4)
  participant Receiver as Receiver
  Sender->>Receiver: Frame 1
  Sender->>Receiver: Frame 2
  Sender->>Receiver: Frame 3
  Sender->>Receiver: Frame 4
  Receiver->>Sender: ACK 1, NACK 3
  Sender->>Receiver: Frame 3 (retransmit)
  Receiver->>Sender: ACK 3
  Sender->>Receiver: Frame 5

SR vs. GBN

Example: SR in eSewa Transactions

• Scenario: You pay a bill via eSewa using SR (N=3).
• Steps:
  1. eSewa sends transaction request frames 1–3.
  2. Frame 2 fails → bank sends NACK 2.
  3. eSewa retransmits only frame 2.
  4. Bank confirms with ACK 2, then processes payment.
• Why SR?
  • Avoids retransmitting successful frames (e.g., frame 1).
  • Critical for financial transactions where speed and accuracy matter.

5. Performance Comparison

Where:

• $T_p$ = Propagation delay (time for signal to travel).
• $T_t$ = Transmission time (time to send one frame).
• $N$ = Window size.

Example Calculation:

• Link: $T_p=20$ ms, $T_t=1$ ms, $N=4$.
• GBN Throughput: $\frac{4}{2\times 20+1}=\frac{4}{41}\approx 0.0976$ frames/ms.
• SR Throughput (ideal): $\frac{4}{20+1}=\frac{4}{21}\approx 0.19$ frames/ms.

6. Real-World Applications

A. eSewa (Financial Transactions)

• Protocol Used: Stop-and-Wait for critical steps (e.g., OTP verification).
• Why?
  • Ensures no duplicate payments (each step waits for confirmation).
  • Prevents race conditions in banking.

B. Ncell 4G Data Transfer

• Protocol Used: Go-Back-N (N=8).
• Why?
  • Balances speed (parallel transmission) and simplicity.
  • Handles occasional packet loss in mobile networks.

C. YouTube Video Streaming (Global)

• Protocol Used: Selective Repeat (TCP variant).
• Why?
  • Retransmits only corrupted video chunks.
  • Minimizes buffering (high throughput).

D. Kathmandu Traffic Lights (Analogy)

• Protocol: Stop-and-Wait (like cars waiting for green light).
• GBN Analogy: If a car is hit (error), all cars behind must stop (go back).
• SR Analogy: Only the hit car is removed; others proceed.

7. Exam Tip: How to Score Full Marks

1. Define Clearly:
   • Start with precise definitions (e.g., "Flow control is a mechanism to regulate data transmission rate between sender and receiver to prevent buffer overflow.").
2. Draw Diagrams:
   • Always include sequence diagrams for protocols (Stop-and-Wait, GBN, SR).
   • Label frames, ACKs, timeouts, and retransmissions.
3. Compare Protocols:
   • Use a table (like above) to contrast GBN vs. SR.
   • Highlight key differences (e.g., "GBN wastes bandwidth; SR does not").
4. Worked Examples:
   • Solve throughput calculations step-by-step.
   • Relate to real-world scenarios (e.g., "In Ncell’s GBN, if frame 3 is lost, frames 4–7 are discarded").
5. Common Pitfalls:
   • ❌ Saying GBN retransmits only the corrupted frame (it retransmits all after it).
   • ❌ Forgetting to mention cumulative ACKs in GBN.
   • ❌ Ignoring window size in throughput formulas.

Sample Answer Structure:

Question: Explain Go-Back-N ARQ with a diagram. Answer:

1. Definition: Go-Back-N is a sliding window protocol where the sender transmits up to N frames without waiting for ACKs. If any frame is corrupted, all subsequent frames are discarded, and the sender goes back to the corrupted frame.
2. Diagram: [Insert sequence diagram showing frames 1–4 sent, ACK 2 received, and frames 2–5 retransmitted].
3. Example: In a Ncell 4G download, if frame 3 is lost, the phone retransmits frames 3–7 (assuming window size = 5).
4. Advantages/Disadvantages: [Bullet points as above].
5. Throughput: Derive formula $\frac{N}{2T_p+T_t}$ and plug in values.

8. Key Formulas to Memorize

1. Stop-and-Wait Throughput: $\text{Throughput}=\frac{1}{2T_p+T_t}$.
2. Go-Back-N Throughput: $\text{Throughput}=\frac{N}{2T_p+T_t}$.
3. Selective Repeat Throughput (ideal): $\text{Throughput}=\frac{N}{T_p+T_t}$.
4. Window Size (N): $N=2^{\text{bit length}}$ (e.g., 3-bit sequence numbers → N=8).

9. Practical Exercise

Scenario: You’re designing a flow control protocol for Daraz’s order processing system.

• Constraints:
  • Orders arrive at 100/sec.
  • ACK takes 50 ms.
  • Frame size = 1 KB.
• Questions:
  1. Which protocol (SW, GBN, SR) would you choose? Why?
  2. Calculate the maximum window size (N) if the link speed is 1 Mbps.
  3. Draw a sequence diagram for GBN with N=4 when frame 2 is lost.

Solution Outline:

1. Protocol: Go-Back-N (balance of speed and simplicity).
2. Window Size:
   • Link speed = 1 Mbps → Transmission time $T_t=\frac{1\text{ KB}}{1\text{ Mbps}}=0.008$ ms.
   • Propagation delay $T_p=50$ ms (ACK time).
   • For GBN: $N=\frac{2T_p+T_t}{T_t}\approx 10,000$ (but limited by sequence bits; e.g., 10-bit → N=1024).
3. Diagram:

   sequenceDiagram
     participant Daraz as Daraz (Sender)
     participant Customer as Customer (Receiver)
     Daraz->>Customer: Order 1
     Daraz->>Customer: Order 2
     Daraz->>Customer: Order 3
     Daraz->>Customer: Order 4
     Customer->>Daraz: ACK 1 (Order 2 lost)
     Daraz->>Customer: Order 2 (retransmit)
     Daraz->>Customer: Order 5