Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Flow control: stop-and-wait

Stop-and-wait is the simplest flow-control protocol in which the sender sends one frame and waits for its acknowledgment before sending the next; it is used where simplicity and correctness matter more than efficiency, and it is the starting point to understand sliding-window protocols like Go-Back-

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Stop-and-wait flow control is the simplest method to ensure reliable, ordered delivery of frames between a sender and a receiver. In practice, this reliability comes from combining flow control with error detection and retransmission (stop-and-wait ARQ, also called the alternating-bit protocol). An engineer uses it when designing or debugging simple data links, teaching basic concepts of reliability, or as the conceptual basis before moving to sliding-window protocols (Go-Back-N, Selective Repeat).

Key ideas

Start by defining terms (every term is defined before first use):

  • Frame: a unit of data sent on the data link layer; it contains payload plus header and trailer. Measured in bits (b) or bytes (B).
  • Acknowledgment (ACK): a short control frame sent by the receiver to tell the sender that a specific frame was received correctly.
  • Transmission time (T_f): the time to put all bits of a frame on the wire; T_f = frame size (bits) / link rate (bits/s). Unit: seconds (s).
  • Propagation delay (T_p): the time for a bit to travel from sender to receiver across the physical medium (one-way). Unit: seconds (s).
  • ACK transmission time (T_a): the time to transmit the bits of the ACK frame on the reverse link; unit: seconds (s).
  • Timeout: a timer at the sender started when a frame is sent; if an ACK is not received before the timeout expires, the sender retransmits the frame. In practice, set the timeout slightly above the estimated RTT to avoid unnecessary retransmissions.
  • Sequence number: a small integer carried in each frame so the receiver and sender can detect duplicates. In stop-and-wait a 1-bit sequence number (values 0 or 1) suffices.
  • Round-Trip Time (RTT): time from start of sending a frame until the sender receives the corresponding ACK; approximately RTT ≈ T_f + 2·T_p + T_a under the usual assumptions.
  • Utilization (U): fraction of time the sender actually transmits useful data (frames) rather than waiting.

Protocol operation (plain steps):

  1. Sender transmits a frame containing a sequence number (0 or 1).
  2. Sender starts a timeout timer.
  3. Receiver, on receiving a correct new frame, delivers payload to higher layer and sends an ACK containing the sequence number (or the next expected number).
  4. If sender receives the correct ACK before timeout, it sends the next frame with the alternate sequence number.
  5. If sender's timer expires (ACK lost or frame lost), sender retransmits the same frame. The receiver uses the sequence number to discard duplicates and re-ACK.

Assumptions usually made in derivations you will be asked for in exams:

  • Propagation delay is symmetric and denoted T_p (one-way).
  • Processing time at sender/receiver is negligible or included separately if specified.
  • Channel may lose or corrupt frames or ACKs; retransmission handles these. Frames include an error-detection code (e.g., CRC), and corrupted frames are detected and discarded; correctness relies on this.
  • ACK frames are much smaller than data frames; many simplifications neglect T_a when deriving compact formulas.

Why 1-bit sequence numbers work: Because only one frame may be outstanding at any time, the receiver only needs to know whether the arriving frame is the same as the last accepted (duplicate) or the next new frame. Values 0 and 1 suffice.

Diagram (what to draw on exam paper):

  • Draw a horizontal time axis. On the left put a vertical line labeled Sender; on the right a vertical line labeled Receiver.
  • Draw an arrow from Sender to Receiver labeled "Frame(seq = 0)"; place its left end at time t=0 and show the arrow occupying T_f in horizontal length and then add a propagation segment of length T_p (you can represent both but annotate T_f and T_p separately).
  • After the frame reaches receiver, draw an arrow back labeled "ACK(seq = 0)" occupying T_a and propagation T_p back.
  • Label the total cycle time from frame start to ACK arrival as RTT ≈ T_f + 2·T_p + T_a.

Comparison with sliding-window (brief): Stop-and-wait keeps only one un-ACKed frame in flight, so the pipe is mostly empty if RTT ≫ T_f. Sliding-window protocols (Go-Back-N, Selective Repeat) allow multiple outstanding frames and improve utilization; see those topics for full design.

Formulas

T_f = L / R — where L is frame size in bits (b), R is link rate in bits per second (b/s); unit: seconds (s). Applies whenever frame size and link rate are known.

RTT ≈ T_f + 2·T_p + T_a — where T_p is one-way propagation delay (s) and T_a is ACK transmission time (s). This is the time from start of frame transmission until the sender receives the ACK, under the common assumption of immediate ACK.

U = T_f / (T_f + 2·T_p + T_a) — utilization (dimensionless fraction, 0..1). This is the fraction of the cycle when the sender is actually transmitting data. Effective data throughput S = U · R (b/s). If asked for payload throughput, use S_payload = U · R · (L_payload/L).

If ACK transmission time is negligible (T_a ≈ 0), define a = T_p / T_f (dimensionless) and then:

U ≈ 1 / (1 + 2·a) — applies when T_a is negligible and processing delays are ignored. Here a measures the ratio of one-way propagation delay to frame transmission time.

Note on symbols: L (bits), R (bits/s), T_f (s), T_p (s), T_a (s), RTT (s), U (unitless), a (unitless).

Worked examples

Example 1 — numerical: compute utilization on a 1 Mbps link. Given: link rate R = 1·10^6 b/s, one-way propagation delay T_p = 50 ms = 0.05 s, data frame size = 1000 B = 1000·8 = 8000 b, ACK size = 40 B = 320 b. Step 1: T_f = L / R = 8000 / 1e6 = 0.008 s. Step 2: T_a = 320 / 1e6 = 0.00032 s. Step 3: RTT ≈ T_f + 2·T_p + T_a = 0.008 + 2·0.05 + 0.00032 = 0.10832 s. Step 4: U = T_f / (T_f + 2·T_p + T_a) = 0.008 / 0.10832 = 0.0739. Final answer: Utilization ≈ 7.39%.

Interpretation: With these numbers the sender transmits useful data only ~7.4% of the time; the rest it is idle waiting for ACKs.

Example 2 — effect of larger frame size (same link): Given same R and T_p but frame size = 10000 B = 80000 b. Step 1: T_f = 80000 / 1e6 = 0.08 s. Step 2: T_a still = 0.00032 s. Step 3: RTT ≈ 0.08 + 2·0.05 + 0.00032 = 0.18032 s. Step 4: U = 0.08 / 0.18032 = 0.4437. Final answer: Utilization ≈ 44.37%.

Observation: Increasing frame size increases utilization because the sender spends more time transmitting relative to waiting.

Example 3 — protocol trace (algorithmic small example): Initial state: Sender seq=0, Receiver expects seq=0.

  1. Sender sends Frame(seq=0). Sender starts timer.
  2. Receiver receives Frame(seq=0), checks sequence number: it matches expected. Receiver delivers payload, sends ACK(seq=0), sets expected=1.
  3. ACK arrives at sender; sender stops timer, sends next Frame(seq=1).
  4. Suppose ACK for Frame(seq=1) is lost. Sender's timer expires and sender retransmits Frame(seq=1).
  5. Receiver receives retransmitted Frame(seq=1). Because it already accepted seq=1 and now expects seq=0, it discards the duplicate and re-sends ACK(seq=1).
  6. If instead the original Frame(seq=1) had been lost (not the ACK), the receiver would still be expecting seq=1 and would accept the retransmission and send ACK(seq=1).

This trace shows why the sequence number must be used and how duplicates are handled.

Common mistakes

  • Using U = 1/(1 + 2a) without stating the assumption that T_a and processing delays are negligible.
  • Thinking stop-and-wait guarantees zero loss; it only guarantees eventual delivery if retransmissions succeed and channel eventually delivers (it cannot create data that was never sent).
  • Forgetting to mention sequence numbers and duplicate-frame handling when asked to describe correctness.
  • Incorrectly using bytes and bits interchangeably without converting (B vs b).

For your exam

Types of questions you may get:

  • Definitions and short notes: define stop-and-wait, ACK, timeout, sequence number, utilization.
  • Derivation: derive U = T_f / (T_f + 2·T_p + T_a) from a timing diagram. State assumptions clearly (T_p one-way, immediate ACK, processing negligible).
  • Numerical: compute T_f, RTT, and utilization given L, R, T_p, ACK size. Convert B→b correctly and give units.
  • Protocol trace: show sender and receiver steps on transmission, retransmission, duplicate frames; include sequence numbers.
  • Comparison/short essay: compare stop-and-wait with Go-Back-N or Selective Repeat (mention window size, utilization, buffer requirements).

What a full-marks answer includes:

  • Clear definitions of terms used.
  • A correctly-labeled timing diagram showing T_f and T_p and ACK path.
  • Step-by-step derivation of utilization with assumptions stated.
  • For numericals: show unit conversions, intermediate values, formulas used, and final answer with units.
  • For trace/algorithm questions: show sequence numbers, timers, and what both endpoints do on loss or duplicate.

Quick check

  1. In stop-and-wait, what minimum number of bits is needed for the sequence number field?
  2. If T_p = 10 ms and T_f = 2 ms and ACK time negligible, what is utilization U?
  3. Why does increasing frame size improve utilization on a high-latency link?

Answers: 1. 1 bit (values 0 and 1 suffice). 2. a = T_p / T_f = 10/2 = 5, so U ≈ 1/(1 + 2·5) = 1/11 ≈ 9.09%. 3. Because larger frame size increases T_f, so the sender spends more time transmitting per RTT and less time waiting, raising U.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?