Stop-and-Wait Protocol and Stop-and-Wait ARQ

---

1. Concept of Flow Control and ARQ

Flow Control coordinates the rate of data transmission between a sender and receiver, ensuring that a fast sender does not swamp a slow receiver with more packets than its internal buffer memory can hold.

When flow control is combined with error control (retransmission on error/loss), the mechanism is called Automatic Repeat Request (ARQ).

       SENDER                                              RECEIVER
         |                                                    |
         |---------------- Frame 0 -------------------------->| (Buffer stored)
         |                                                    |
         |<--------------- ACK 1 -----------------------------| (Acknowledged)
         |                                                    |
         |---------------- Frame 1 -------------------------->|
         |                                                    |
         |<--------------- ACK 0 -----------------------------|

---

2. Stop-and-Wait ARQ Mechanism

In Stop-and-Wait ARQ, the sender transmits one single frame and stops all further transmissions, waiting for an acknowledgment (ACK) from the receiver before sending the next frame.

Key Operational Rules:

1. 1-Bit Sequence Numbers ($0$ and $1$):
   • Frames are numbered alternately as Frame 0, Frame 1, Frame 0, Frame 1 ($m = 1\text{ bit}$, sequence modulo $2$).
   • Distinguishes duplicate retransmitted frames from new frames.
2. Acknowledgment Numbers:
   • The ACK carries the sequence number of the next expected frame.
   • ACK 1 indicates that Frame 0 was received correctly and the receiver is now waiting for Frame 1.
3. Retransmission Timer:
   • When the sender transmits a frame, it starts a countdown timer.
   • If a valid ACK does not return before the timer expires (Timeout), the sender automatically retransmits the same frame.

---

3. Error Scenarios Handled by Stop-and-Wait ARQ

Scenario A: Lost Frame             Scenario B: Lost ACK               Scenario C: Delayed ACK
  Sender          Receiver           Sender          Receiver           Sender          Receiver
    |                |                 |                |                 |                |
    |-- Frame 0 ---->|                 |-- Frame 0 ---->|                 |-- Frame 0 ---->|
    |       X (Lost) |                 |                | (Stored)        |                |
    | (Timer expires)|                 |<-- ACK 1 - X   | (Lost)          |    (Delayed)   |
    |-- Frame 0 ---->|                 | (Timer expires)|                 | (Timeout)      |
    |                | (Received)      |-- Frame 0 ---->| (Duplicate!)    |-- Frame 0 ---->|
    |<-- ACK 1 ------|                 |                | Discard dup     |                | Discard dup
    |                |                 |<-- ACK 1 ------| Re-send ACK     |<-- ACK 1 (old)-|

1. Lost Frame: The timer expires at the sender; the sender retransmits the original frame.
2. Damaged Frame: The receiver detects a CRC error and discards the frame silently. The sender times out and retransmits.
3. Lost ACK: The sender retransmits Frame 0. The receiver receives a duplicate Frame 0, discards the duplicate to prevent duplicate data, and re-sends ACK 1.
4. Delayed ACK: If an ACK arrives after timeout, the sequence number prevents the sender from confusing it with the ACK for the retransmitted frame.

---

4. Performance & Efficiency Analysis

The total time required to successfully transmit one frame and receive its ACK is:

(Where $T_t = \frac{\text{Frame Size}}{\text{Bandwidth}}$ is Transmission Time, $T_p = \frac{\text{Distance}}{\text{Propagation Speed}}$ is Propagation Delay).
Assuming processing and ACK transmission times are negligible ($T_{\text{proc}} \approx 0, T_{\text{ack}} \approx 0$):

Parameter $a$:

The ratio of propagation delay to transmission delay is defined as:

Efficiency ($\eta$) and Throughput ($S$):

---

5. Solved Numerical Example

• Problem: A $1\text{ Gbps}$ satellite link has a distance of $36{,}000\text{ km}$. Signal propagation speed is $3 \times 10^8\text{ m/s}$. The frame size is $1{,}000\text{ bytes}$ ($8{,}000\text{ bits}$). Calculate:
  1. Transmission time ($T_t$).
  2. Propagation delay ($T_p$).
  3. Efficiency of Stop-and-Wait protocol.
• Solution:
  1. $T_t = \frac{8{,}000\text{ bits}}{10^9\text{ bps}} = 8 \times 10^{-6}\text{ s} = 0.008\text{ ms} = 8\text{ }\mu\text{s}$.
  2. $T_p = \frac{36{,}000 \times 10^3\text{ m}}{3 \times 10^8\text{ m/s}} = 0.12\text{ s} = 120\text{ ms}$.
  3. $a = \frac{T_p}{T_t} = \frac{120\text{ ms}}{0.008\text{ ms}} = 15{,}000$.
  4. Efficiency:

Conclusion: Stop-and-Wait is catastrophically inefficient on links with a large Bandwidth-Delay Product (BDP) because the sender spends $99.99\%$ of its time idling, waiting for the round-trip acknowledgment. This motivates the need for Sliding Window Protocols (Go-Back-N and Selective Repeat).

---

6. Key Exam Questions & Takeaways

1. Why does Stop-and-Wait ARQ require sequence numbers?
   • Without sequence numbers, if an ACK is lost or delayed, the sender will retransmit the frame, and the receiver cannot distinguish whether the newly arrived frame is a retransmission of the previous frame or a completely new frame with identical contents.
2. What is the maximum window size in Stop-and-Wait?
   • Sender Window Size $W_s = 1$, Receiver Window Size $W_r = 1$.
3. What is the formula for Stop-and-Wait efficiency in terms of $a$?
   • $\eta = \frac{1}{1 + 2a}$, where $a = \frac{T_p}{T_t}$.
4. Why is Stop-and-Wait inefficient for satellite links?
   • Satellite links have high propagation delay ($T_p \approx 120 - 250\text{ ms}$), making $a \gg 1$. Since only 1 frame is allowed in transit, the link pipe remains empty almost all the time.