Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 79 ยท Data Link Layer

Flow Control and ARQ

Learn flow control and ARQ: stop-and-wait, Go-Back-N and selective repeat, window sizes, link utilization formulas and piggybacking, with a live simulation.

A fast sender can easily swamp a slow receiver. A server on a 10 Gbit/s link can push frames faster than an old printer can accept them, and the extra frames would be dropped when the receiver's buffer fills. Flow control is the set of rules that stops a sender from overrunning its receiver. A related problem is that frames get damaged or lost, so the receiver must be able to say "that one did not arrive" and the sender must send it again. The family of methods that does this is called ARQ, for Automatic Repeat reQuest.

This lesson walks through the three classic protocols: stop-and-wait, Go-Back-N and selective repeat. They all combine flow control with error recovery, they are all built on the error detection from Framing and Error Detection, and the same ideas return at larger scale in TCP, covered in TCP Reliability and TCP Flow Control. Here the model is a single link between a sender and a receiver, as at the data link layer.

The ingredients of ARQ

Every ARQ protocol uses the same few tools:

  • Sequence numbers in each frame, so the receiver can tell a new frame from a retransmitted copy and can put frames in order.
  • Acknowledgments (ACKs) that the receiver sends back to say what arrived.
  • A timer at the sender. If no ACK arrives in time, the frame is assumed lost and is sent again. The timeout must be a little longer than a round trip.
  • Error detection (a CRC) so that damaged frames are treated like lost ones: the receiver silently drops them.

Some protocols add a negative acknowledgment (NAK) to report a gap quickly, without waiting for the timer.

Stop-and-wait

The simplest protocol sends one frame, then waits for its ACK before sending the next. A single bit of sequence number (0 or 1, alternating) is enough, because only one frame is ever outstanding: it tells the receiver whether a frame is new or a duplicate caused by a lost ACK.

Stop-and-wait is correct, easy to build and terrible on long links. While the frame crosses the wire and the ACK returns, the sender sits idle. To see how idle, define:

  • Tt, the transmission time: frame size divided by bit rate.
  • Tp, the propagation time: distance divided by signal speed (about 2 ร— 10โธ m/s in cable and fiber).
  • a = Tp / Tt, how many frame times fit in one direction of the wire.

The sender is busy for Tt out of every Tt + 2Tp (ignoring ACK size and processing time), so

U = Tt / (Tt + 2Tp) = 1 / (1 + 2a).

For a 12,000-bit frame on a 10 Mbit/s link that is 2,000 km long, Tt = 1.2 ms and Tp = 10 ms. Then a โ‰ˆ 8.33 and U โ‰ˆ 5.7%. Over 94% of the capacity goes to waiting.

Sliding windows: keep the pipe full

The fix is to allow several frames in flight without waiting. The sender may transmit up to W frames before it must stop; it keeps a window of sequence numbers that are sent but not yet acknowledged, and the window slides forward as ACKs arrive. If a sender can send W frames per round trip:

U = min(1, W / (1 + 2a)).

On the example link, W = 1 gives 5.7%, W = 10 gives 56.6%, and W = 20 already gives 100%. The smallest window that fills the pipe is 1 + 2a, about 17.7, so in practice 18 frames. This is the same quantity as the bandwidth-delay product from Bandwidth, Latency, Throughput and Loss, counted in frames.

Python Utilization of stop-and-wait and sliding windows

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Change distance to 100 meters and run it again: a collapses toward zero and even stop-and-wait reaches nearly full utilization. That is why stop-and-wait is acceptable on a short LAN link and unusable across a continent or a satellite hop.

Go-Back-N

In Go-Back-N (GBN) the sender keeps a window of up to W unacknowledged frames, and the receiver is as simple as possible: it accepts frames only in order. If frame 3 is lost, then frames 4, 5 and 6 arrive out of order and the receiver discards them. It keeps re-acknowledging the last good frame.

The ACKs are cumulative: "ACK n" means "everything before n arrived". When the timer for the oldest unacknowledged frame fires, the sender goes back and retransmits that frame and everything sent after it. The receiver needs just one buffer slot (a receive window of size 1), but the sender may resend many perfectly good frames. Go-Back-N wastes bandwidth when the loss rate is high, and it is a good fit when losses are rare.

Selective Repeat

Selective Repeat (SR) removes that waste. The receiver also has a window: it buffers out-of-order frames and acknowledges each one individually. The sender keeps a timer per frame and retransmits only the frame that is missing. When the gap is filled, the receiver delivers the buffered frames in order. The price is more memory and more bookkeeping.

sequenceDiagram
    participant S as Sender
    participant R as Receiver
    S->>R: frame 0
    S->>R: frame 1
    S-xR: frame 2 (lost)
    S->>R: frame 3
    R-->>S: ACK 0
    R-->>S: ACK 1
    Note over R: SR buffers frame 3<br/>GBN discards it
    S->>R: frame 2 again (timeout)
    Note over S: GBN would now also resend 3, 4, 5...

One lost frame: Go-Back-N resends everything after it, selective repeat sends only the lost one.

Window sizes and sequence numbers

Sequence numbers are carried in a field of m bits, so they repeat every 2m frames. The window must be small enough that an old frame can never be mistaken for a new one:

  • Go-Back-N: window size W โ‰ค 2m - 1.
  • Selective Repeat: window size W โ‰ค 2m / 2 (half the number space), because both windows move and must never overlap ambiguously.

With 8-bit numbers, GBN can have 255 frames in flight and SR only 128. The usual cost of making the number space too small is silent data corruption: an old duplicate gets accepted as new.

Protocol Sender window Receiver window Resends after a loss ACKs
Stop-and-wait 1 1 the one frame per frame
Go-Back-N up to 2m - 1 1 the lost frame and all after it cumulative
Selective Repeat up to 2m / 2 same as sender only the lost frame individual

Simulate all three

The simulator below sends 12 frames over a link with a one-way delay of 4 ticks. The sender can transmit one frame per tick. Frame 2 is lost the first time it is sent. Stop-and-wait is Go-Back-N with a window of 1, so the same code covers it.

Python Stop-and-wait, Go-Back-N and selective repeat compared

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The results make the trade-offs concrete. Stop-and-wait needs about 100 ticks because it idles for a whole round trip per frame, while both windowed protocols finish in about 20 to 30. With the loss, Go-Back-N sends 18 frames to deliver 12, because after the timeout it resends frame 2 and the four frames that followed it. Selective repeat sends just 13, resending only the missing frame. Both windowed protocols finish at the same tick here, but selective repeat gets there with far less retransmitted traffic. Try lose_first=(2, 5) or a smaller window to see how the numbers change.

Piggybacking and NAKs

In two-way traffic the receiver also has data to send. Instead of a separate ACK frame, it can attach the acknowledgment number to the header of an outgoing data frame. This is piggybacking, and it saves one frame per exchange. If the receiver has nothing to send, it waits briefly for outgoing data and then sends a bare ACK. TCP does the same with its delayed ACK.

Selective repeat protocols often add a NAK: when the receiver notices a gap, it asks for the missing frame at once instead of letting the sender's timer run out. The Internet's TCP uses the cousin of this idea, duplicate ACKs, to trigger a "fast retransmit".

Flow control versus congestion control

The windows in this lesson protect the receiver. They say nothing about the network between sender and receiver, which may be overloaded even when the receiver is idle. Controlling that is a separate job, handled at the transport layer by TCP congestion control. A modern link layer such as Ethernet often does little ARQ at all, because errors are rare. Wi-Fi, which loses frames to interference, still uses stop-and-wait ARQ with a per-frame ACK. See Medium Access Control for how the link shares the wire in the first place.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A link has a = Tp / Tt = 4. What is the utilization of stop-and-wait?

    U = 1 / (1 + 2a) = 1 / 9, which is about 11%. The sender is busy for one frame time out of nine.
  2. 2. In Go-Back-N, frame 3 is lost but frames 4, 5 and 6 arrive. What does the receiver do with them?

    A Go-Back-N receiver only accepts the next expected frame. Out-of-order frames are dropped, so the sender must resend frame 3 and everything after it.
  3. 3. With 4-bit sequence numbers, what is the largest allowed window for selective repeat?

    Selective repeat needs W <= 2^m / 2 = 8. Go-Back-N could use 15. A larger SR window lets an old duplicate be mistaken for a new frame.
  4. 4. What is piggybacking?

    When traffic flows both ways, the acknowledgment number can ride in the header of a data frame, which saves a frame.

Summary

  • Flow control stops a fast sender from overrunning a slow receiver; ARQ recovers from lost or damaged frames using sequence numbers, ACKs and timers.
  • Stop-and-wait has utilization 1 / (1 + 2a), where a = Tp / Tt, and wastes long links.
  • Sliding windows keep several frames in flight: U = min(1, W / (1 + 2a)).
  • Go-Back-N has a receive window of 1 with cumulative ACKs and resends everything after a loss; selective repeat buffers out-of-order frames and resends only the lost one.
  • Window limits: W โ‰ค 2m - 1 for Go-Back-N, W โ‰ค 2m / 2 for selective repeat. Piggybacking merges ACKs into data frames.

Next: Medium Access Control