Core CS · Computer Networks
One frame at a time is correct, and it wastes ninety-seven per cent of the link
Send a frame, wait for its acknowledgement, send the next. Nothing is ever lost and nothing overruns the receiver. On a 1 Mbps link with a 20 ms delay it moves 24 kbps, and buying ten times the bandwidth changes that to 25 kbps. The fix is a window, and the two ways of repairing a hole in that window are the pair every interviewer reverses.
Lose the same frame under Go-Back-N and Selective Repeat, side by side →01 The idea
Protect the receiver, not the network
A server with 32 GB of memory sends to a sensor with 8 KB of buffer. The link is fine, the routers are idle, nothing is congested, and the sensor still loses data, because bytes arrive faster than its application reads them and the buffer fills. That is the problem flow control solves, and it is worth being blunt about the boundary before anything else. Flow control is end to end: the receiver tells the sender how much it may send, and the sender obeys. Congestion control is a different problem with an identical symptom. There the receiver is perfectly happy and the queue inside some router along the path is overflowing, so the sender has to infer the limit from lost packets and rising delay, because no router sends it a message. TCP runs both at once and keeps two separate numbers for them. A sender that respects only the receiver will melt the network; a sender that respects only the network will still overrun the receiver.
The simplest protocol that does flow control correctly is stop-and-wait. Send one frame. Do nothing until its acknowledgement comes back. Then send the next. The receiver controls the sender exactly, because the sender cannot move without permission, and one buffer is enough at each end. It is correct, it is three lines long, and on any link with real distance in it the sender spends almost all of its time doing nothing. Section 02 puts numbers on that, and the numbers are worse than most students expect.
The repair is pipelining: allow several frames to be unacknowledged at the same time, so the sender keeps transmitting while the earlier frames are still in the air. How many? Exactly enough to keep sending until the first acknowledgement gets back, which is the bandwidth-delay product from the earlier module, measured in frames rather than bits. That number is the window size, and it is the whole reason the window exists. Nothing about pipelining is a performance trick bolted on afterwards; it is the direct answer to the question “how much data fits in the pipe”.
A sliding window is how that allowance is bookkept. The sender keeps a range of sequence numbers it is allowed to transmit without waiting, from the oldest unacknowledged frame up to the window size. The receiver keeps a range it is willing to accept. When an acknowledgement arrives the sender’s range slides forward past the frames now known to be safe, which is where the name comes from: the window never grows or shrinks on its own, it moves.
Then one frame goes missing, and the protocol has to decide what to do about everything that was already in flight behind it. There are exactly two sane answers, and they are the two protocols this lesson is really about. Go-Back-N makes the receiver simple and the sender wasteful: the receiver refuses anything out of order, so the sender resends the lost frame and every frame after it. Selective Repeat makes the receiver clever and the sender frugal: the receiver holds the out-of-order frames in a buffer, so only the lost frame is sent again. Both are called ARQ, Automatic Repeat reQuest, meaning loss is repaired by retransmission driven by acknowledgements and timers rather than by adding redundancy to the data.
02 Worked example
Forty-one milliseconds, of which the sender works for one
One link, worked end to end. This is the scene for the rest of the lesson. Bandwidth 1 Mbps, frames of 1,000 bits, one-way propagation delay 20 ms. Acknowledgements are tiny, so their own transmission time is ignored, which is the standard assumption and the one every exam question makes. Read left to right and check each arithmetic step as you go.
The highlighted node is the one to slow down on, because it is where the formula stops being something to memorise. U = Tt / (Tt + 2Tp) is nothing more than “busy time over cycle time”. Divide the top and bottom by Tt and you get 1 / (1 + 2Tp/Tt), which is 1 / (1 + 2a). That is the entire derivation, and it means a is the only thing that matters: a is how many frame-times fit into one one-way flight, so 2a is how many frame-times the sender wastes staring at the wire per frame it sends.
Now do the thing that makes the point land. Keep the same frames and the same 20 ms, and upgrade the link to 10 Mbps. Tt falls to 1000 / 10,000,000 s = 0.1 ms, so a = 20 / 0.1 = 200 and U = 1/401 = 0.249%. Throughput is 1000 bits / 40.1 ms = 24.94 kbps. You paid for ten times the bandwidth and moved from 24.4 kbps to 24.9 kbps, a gain of two per cent. Under stop-and-wait the sender is not limited by bandwidth at all. It is limited by how long it agrees to wait, and no cheque you write changes 20 ms of physics.
Node 5 is the fix, and the number in it is the bandwidth-delay product wearing different clothes. The round trip is 2 × 20 = 40 ms, and 1 Mbps × 40 ms = 40,000 bits of link standing empty. At 1,000 bits per frame that is 40 frames of empty pipe, so the sender needs 40 more frames in flight plus the one it is currently transmitting: N = 41, which is exactly 1 + 2a. The two routes to 41 are the same statement, and being able to produce it either way is what an interviewer is checking.
Hold on to 41. Section 03 needs a sequence number field wide enough to label 41 outstanding frames, and it turns out that Go-Back-N and Selective Repeat need different widths for the same window, which is the single most reversible fact in this topic. The console in section 04 shrinks the scene to a window of 4 over eight frames so that you can count every transmission by hand; the mechanism is identical, only the numbers are small enough to check.
03 Mechanics
The two ARQ strategies, and where their window limits come from
Four tables, in the order the questions come. First the three protocols side by side. Read the last two columns together, because they are the trade: Go-Back-N buys a one-frame receiver by spending link capacity on every loss, and Selective Repeat buys minimal retransmission by spending memory on every connection whether it loses anything or not.
| Protocol | Sender window | Receiver window | Acknowledgement | On one lost frame | Receiver buffer | Utilisation |
|---|---|---|---|---|---|---|
| Stop-and-wait | 1 | 1 |
One per frame | Resend that frame | 1 frame | 1 / (1 + 2a) |
| Go-Back-N | W ≤ 2ᵐ − 1 | 1 |
Cumulative | resend it and every frame after it |
1 frame | min(1, W / (1 + 2a)) |
| Selective Repeat | W ≤ 2ᵐ / 2 | W |
Individual | resend only that frame |
W frames, plus sorting |
min(1, W / (1 + 2a)) |
The acknowledgement convention, stated once so nothing later is ambiguous. In this lesson a Go-Back-N ACK n means everything up to and including frame n has arrived, which is why one acknowledgement can cover several frames and why a lost acknowledgement is harmless as long as a later one gets through. A Selective Repeat ACK n means frame n specifically has arrived and says nothing about its neighbours, so every acknowledgement matters and a lost one costs a retransmission. Some textbooks number the Go-Back-N acknowledgement by the frame the receiver wants next rather than the last one it got, which shifts every number by one. TCP does it that way: its acknowledgement number is the next byte expected, so an ACK of 5001 means bytes up to 5000 arrived. Say out loud which convention you are using and no interviewer will mark you down; assume silently and you will be told you are off by one.
Second, the utilisation numbers, because “stop-and-wait is bad” is not an answer and “a is 200 so you get a quarter of one per cent” is. Every row is computed from Tt = frame bits / bandwidth and U = 1/(1 + 2a), and the last column is the window that would make U = 1.
| Link | Frame | Tt | Tp | a | Stop-and-wait U | Throughput | Window to fill it |
|---|---|---|---|---|---|---|---|
| 1 Gbps LAN, 1 km | 12,000 bits | 12 µs | 5 µs | 0.42 |
54.5% | 545 Mbps | 2 frames |
| 1 Mbps, 20 ms (section 02) | 1,000 bits | 1 ms | 20 ms | 20 |
2.44% | 24.4 kbps | 41 frames |
| Same link at 10 Mbps | 1,000 bits | 0.1 ms | 20 ms | 200 |
0.249% | 24.9 kbps | 401 frames |
| Geostationary satellite, 1 Mbps | 1,000 bits | 1 ms | 270 ms | 270 |
0.185% | 1.85 kbps | 541 frames |
Read row one against row three. On the 1 Gbps LAN one kilometre long, stop-and-wait already reaches 54.5 per cent, because a is below 1: the frame takes longer to push onto the wire than it takes to cross it, so the link is genuinely busy most of the time and a window of 2 finishes the job. Now take a link a hundred times slower, 10 Mbps, and stretch it over 20 ms. The same protocol reaches a quarter of one per cent and needs 401 frames in flight to recover, which is worse by a factor of more than two hundred. Bandwidth went down and the problem got dramatically worse, so bandwidth is not what decides this. The interesting question is never “is stop-and-wait slow” but “what is a here”.
Third, the sequence-number limits, which are the two facts students most often reverse and most often assert without a reason. A sequence number field of m bits can only count 0 to 2ᵐ − 1 and then wraps. The table walks the exact failure that follows if the window is one too wide, using m = 2 so the whole sequence space is 0 1 2 3 and you can hold it in your head.
| Step | Go-Back-N with m = 2, W = 4 | Selective Repeat with m = 2, W = 3 |
|---|---|---|
| 1 Sender fills its window | Sends frames 0 1 2 3 | Sends frames 0 1 2 |
| 2 They all arrive | Receiver delivers all four, now expects sequence number 0 again | Receiver delivers all three, receive window becomes {3, 0, 1} |
| 3 Every acknowledgement is lost | sender learns nothing | sender learns nothing |
| 4 Timer expires, sender retransmits | Resends the old frame 0 | Resends the old frame 0 |
| 5 The receiver decides | it was expecting 0, so it accepts the duplicate as new data | 0 is inside {3, 0, 1}, so it buffers the duplicate as new data |
| The fix | W ≤ 2ᵐ − 1 = 3, so the receiver is expecting 3 and rejects the old 0 | W ≤ 2ᵐ / 2 = 2, so the window is {2, 3} and the old 0 is outside it |
Why the two limits differ, in one sentence each. Go-Back-N has a receive window of one, so the only thing that must stay unambiguous is the single number the receiver is waiting for. Leaving one sequence number unused is enough to guarantee that a stale frame never equals it, hence 2ᵐ − 1. Selective Repeat has a receive window of W, and after the receiver slides forward its new window can overlap the sender’s old one in sequence space; keeping the two disjoint requires the old and new windows together to fit in 2ᵐ, which is W + W ≤ 2ᵐ, hence W ≤ 2ᵐ/2. Apply this to section 02: a window of 41 needs m = 6 under Go-Back-N, because 2⁶ − 1 = 63 ≥ 41 while 2⁵ − 1 = 31 is too small, and it needs m = 7 under Selective Repeat, because 2⁶/2 = 32 is too small and 2⁷/2 = 64 ≥ 41. Same window, one more bit of header, purely because the receiver buffers.
The failure is silent, which is what makes it an interview question. Nothing in step 5 raises an error. The frame is not corrupt, the checksum passes, the sequence number is one the receiver was willing to accept. The application receives a byte range twice, or receives old data in the middle of new data, and the bug surfaces days later as corrupted content with no packet loss anywhere in the logs. A protocol that is one off in its window bound looks perfect until the exact combination of a full window and a lost acknowledgement batch occurs.
Fourth, what TCP actually does, because everything above is the frame-level model and TCP is the thing you will be asked about. TCP counts in bytes, not frames, and its window is advertised by the receiver rather than agreed in advance.
| Mechanism | What it is | The number | What goes wrong without it |
|---|---|---|---|
| Receive window (rwnd) | The receiver puts its current free buffer space in the Window field of every segment it sends, so the allowance is refreshed on every acknowledgement rather than fixed at setup. | 16-bit field, 0 to 65,535 bytes |
The sender guesses, and a slow application on the receiving side loses data. |
| The sender’s real limit | Two independent limits apply at once and the tighter one wins. The receive window is flow control; the congestion window is congestion control; unacknowledged bytes already on the wire count against both. | usable = min(rwnd, cwnd) − bytes in flight |
Obeying only rwnd floods the network; obeying only cwnd floods the receiver. |
| Zero window and the probe | A full receiver advertises 0 and the sender stops. The window update that reopens it is a pure acknowledgement, which is never retransmitted, so if it is lost both ends wait forever. The sender therefore runs a persist timer and sends a window probe, a segment carrying one byte, purely to force a fresh advertisement back. | rwnd = 0 stops the sender dead |
a permanent deadlock on a healthy connection |
| Silly window syndrome | The connection settles into moving a handful of bytes per segment, so the headers cost far more than the data. Fixed from both ends: the receiver refuses to advertise a window until it can offer a full segment or half its buffer, and the sender holds a small write back while earlier small data is still unacknowledged, which is Nagle’s algorithm. | 40 bytes of TCP and IPv4 header for 1 byte of data |
The link is busy and almost nothing useful crosses it. |
| Window scale option | A 16-bit field cannot express a modern pipe, so RFC 7323 adds a left-shift factor negotiated in the opening handshake and applied to every later advertisement. | shift 0 to 14, up to 1,073,725,440 bytes |
Throughput caps at 65,535 bytes per RTT however fast the link is. |
Where TCP sits between the two protocols. Plain TCP acknowledges cumulatively, exactly like Go-Back-N, and a strict Go-Back-N sender would retransmit the whole window on a loss. Real stacks do not, because the selective acknowledgement option, RFC 2018, lets the receiver report the blocks it did receive above the gap, so the sender resends only the hole. That makes deployed TCP behave like Selective Repeat over a Go-Back-N-shaped acknowledgement format. It is worth saying in an interview in one clause: the exam answer is that TCP acknowledgements are cumulative, and the honest addition is that SACK is negotiated on essentially every connection you will ever open.
05 Cheat sheet
Everything you can be asked to state in ten seconds
Every row is something you either compute in your head or say out loud without hesitating. The right-hand column is the specific wrong answer that gets written down, not a general caution.
| What they ask | The answer | The trap |
|---|---|---|
| Flow control versus congestion control | receiver’s buffer versus the network in between | treating them as one mechanism — TCP keeps two separate windows |
| Stop-and-wait utilisation | U = 1 / (1 + 2a), a = Tp / Tt | putting the RTT into a — a uses the one-way delay; the 2 supplies the round trip |
| Utilisation with a window of W | U = min(1, W / (1 + 2a)) | Forgetting the cap and reporting a utilisation above 1. |
| Window that fills the pipe | W ≥ 1 + 2a, or BDP / frame size, plus 1 | dropping the +1 — the frame being transmitted is not in the pipe yet |
| Go-Back-N sender window | at most 2ᵐ − 1 | 2ᵐ — a full sequence space lets a stale frame be accepted as new |
| Go-Back-N receiver window | exactly 1 | Saying it buffers out-of-order frames. It does not; that is the whole difference. |
| Selective Repeat windows | sender and receiver both at most 2ᵐ / 2 | reusing 2ᵐ − 1 — the Go-Back-N bound is not valid here |
| Acknowledgement style | Go-Back-N cumulative, Selective Repeat individual | Assuming a cumulative acknowledgement is always worse. A lost one costs nothing. |
| What gets retransmitted | GBN: the lost frame and every frame after it. SR: only the lost frame. | swapping the two — the single most reversed pair in this topic |
| Receiver memory | GBN 1 frame, SR W frames plus reordering | Forgetting that the sender buffers W frames in both. |
| TCP flow-control field | 16-bit Window in every segment, scaled per RFC 7323 | naming the congestion window — cwnd is never sent on the wire |
| What bounds a TCP sender | min(rwnd, cwnd) − bytes in flight | Quoting rwnd alone, or forgetting to subtract what is already unacknowledged. |
| Escaping a zero window | persist timer, then a window probe | waiting for the receiver to re-advertise — that update is a pure ACK and is never retransmitted |
| TCP header size | 20 bytes without options, up to 60 with | Quoting UDP’s 8 bytes, or forgetting the 20-byte IPv4 header underneath. |
06 Where & why
The window is a live value in systems you already use
None of this is a teaching abstraction. Each of these four is a window you can print, tune, or be paged about, and two of them exist specifically because one TCP window underneath is not enough.
Run ss -ti on an open socket and you see rcv_space, wscale, cwnd and the current round-trip estimate together, which is this whole lesson printed on one line. The advertised window is derived from the receive buffer, and Linux auto-tunes that buffer between the bounds in net.ipv4.tcp_rmem as it learns the bandwidth-delay product. The classic failure is a middlebox stripping the window scale option from the handshake: the connection works, and it silently caps at 65,535 bytes per round trip forever.
HTTP/2 multiplexes many requests over one TCP connection, and TCP has exactly one window for the lot, so a large download would starve everything else sharing it. HTTP/2 therefore runs its own flow control per stream and per connection, with the initial window set to 65,535 octets and credit returned by explicit WINDOW_UPDATE frames. Same mechanism as section 01, one layer up, for a problem the layer below cannot see.
An SSH connection carries several channels at once: your shell, a port forward, an scp transfer. RFC 4254 gives each channel its own window, advertised at channel open and topped up with SSH_MSG_CHANNEL_WINDOW_ADJUST messages, so a bulk file copy cannot make your interactive shell unresponsive. If you have ever wondered why typing stays smooth during an scp over the same session, that is the reason.
Wi-Fi aggregates many subframes into one long transmission and acknowledges them with a Block Ack: a bitmap with one bit per subframe, 64 bits in the compressed form and wider in 802.11ax. That is individual acknowledgement, so only the subframes that actually failed are sent again, which is Selective Repeat with a fixed hardware window. Go-Back-N would be unusable here, because on radio a few subframes of a burst fail routinely and resending the whole burst each time would collapse the throughput.
07 Interview questions
What they ask, and the pair they expect you to reverse
The reliable pattern here is a definition question, then a number, then Go-Back-N against Selective Repeat, then one deliberate trap on the window bounds. If you can say which side pays for what in each protocol, most follow-ups answer themselves. Give the reason with the rule every time; both bounds sound arbitrary until you say what would break.
What is flow control, and how is it different from congestion control?
Explain stop-and-wait, and why nobody uses it on a long link.
How do you choose the window size, and what happens if it is too big?
Go-Back-N against Selective Repeat, in one minute.
Why is the Go-Back-N sender window at most 2 to the power m minus 1?
And why is the Selective Repeat window at most half the sequence space?
Is a cumulative acknowledgement better or worse than an individual one?
How does TCP actually do flow control, and where does the value live?
A receiver advertises a window of zero. What happens, and what breaks if that mechanism is missing?
The window field is only 16 bits. Is that not a problem on a fast link?
Do you ever deal with any of this directly?
08 Practice problems
Six to work on paper
Write the units next to every number in these, because bits against bytes and milliseconds against seconds is where the marks actually go. Two of the six turn on counting transmissions rather than frames, and one of them has a total that is nearly forty times the ideal.