Selective repeat resends only what was actually lost. That costs the receiver a buffer and the sender a timer per packet, and it quietly halves the largest sender window the protocol may use.
Words you will meet
- Selective repeat — resend only the packets believed lost.
send_base/rcv_base— the lowest unacknowledged packet, and the lowest one not yet delivered.- Receiver window — the range of packets the receiver will accept and buffer.
- Maximum packet lifetime — how long a packet is assumed able to survive in the network.
Why this matters
Go-Back-N works, and section 3.4.3 counted its bill: ten transmissions to deliver six packets, because three good packets were thrown away. That waste grows with the window, and from section 3.4.2 a large window is exactly what a fast, long path needs.
Selective repeat fixes it, and the fix is more subtle than it looks. The last part of this section contains the one idea in the chapter that genuinely cannot be explained without a picture.
Fixing the waste
When the window size and the bandwidth-delay product bandwidth-delay product Simple How many bits fit in the pipe at once: link rate multiplied by round-trip time. Precise The product of a path’s link rate and its round-trip time, giving the number of bits that can be in flight at one instant. It is the window size a pipelined protocol needs in order to keep the sender busy. When both the window and this product are large, a single lost packet can force Go-Back-N to retransmit a great many packets unnecessarily. introduced in ch. 3 — open in glossary are both large, many packets can be in the pipeline. A single packet error can then cause Go-Back-N to retransmit a great many of them, most unnecessarily. As the probability of channel errors rises, the pipeline fills with these useless retransmissions.
Everyday picture
Back to dictating a message over the phone. Imagine that every time a single word was garbled, the surrounding thousand words had to be repeated.
The dictation would be slowed by all the reiterated words — and the longer your sentences, the worse it would get.
Where the picture breaks: a listener repeating a thousand words is merely bored. A network repeating a thousand packets is also causing congestion, which makes further loss more likely. Section 3.6 shows that this feedback loop is real and that it can collapse a network.
Selective-repeat selective repeat Simple A pipelined protocol that resends only the packets it believes were actually lost. Precise SR: the receiver acknowledges every correctly received packet individually, whether or not it is in order, and buffers out-of-order packets until the gaps are filled. The sender keeps a separate logical timer per packet and retransmits only the packet that timed out. It avoids Go-Back-N’s wasted retransmissions, at the cost of buffering at the receiver and the window rule below. introduced in ch. 3 — open in glossary protocols avoid unnecessary retransmissions by having the sender retransmit only those packets it suspects were received in error. That individual, as-needed retransmission requires the receiver to individually acknowledge correctly received packets — which is the first departure from Go-Back-N.
A sender window of size N still limits the number of outstanding unacknowledged packets. But unlike Go-Back-N, the sender will already have received acknowledgements for some of the packets inside its window. The receiver keeps a window of its own too — the receiver window receiver window Simple The stretch of sequence numbers a selective-repeat receiver is willing to accept. Precise In selective repeat, the range [rcv_base, rcv_base+N−1] of packets the receiver will accept and buffer. Packets in [rcv_base−N, rcv_base−1] are acknowledged again even though they were already delivered, because otherwise the sender’s window could never advance. This is distinct from TCP’s **receive window** (`rwnd`), which is a flow-control number in the segment header. introduced in ch. 3 — open in glossary , the range of packets it is willing to accept and buffer.
send pkt0
Sender — Figure 3.19
Receiver — out-of-order packets are buffered
- Delivered
- 0/6
- First transmissions
- 6
- Retransmissions
- 1
- Wasted
- 0 packets
The whole trace as text
- t= 0 · send pkt0
- t= 1 · send pkt1
- t= 2 · send pkt2
- t= 5 · pkt2 lost in the channel
- t= 3 · rcv pkt0, deliver
- t= 3 · send ACK0
- t= 3 · send pkt3
- t= 3 · window full — the sender must wait
- t= 4 · rcv pkt1, deliver
- t= 4 · send ACK1
- t= 6 · rcv ACK0 — window slides to 1
- t= 6 · rcv pkt3, buffer it — pkt2 is still missing
- t= 6 · send ACK3
- t= 6 · send pkt4
- t= 6 · window full — the sender must wait
- t= 7 · rcv ACK1 — window slides to 2
- t= 7 · send pkt5
- t= 8 · pkt2 timeout — resend only pkt2
- t= 8 · resend pkt2
- t= 9 · rcv ACK3 — marked, window stays at 2
- t= 9 · rcv pkt4, buffer it — pkt2 is still missing
- t= 9 · send ACK4
- t=10 · rcv pkt5, buffer it — pkt2 is still missing
- t=10 · send ACK5
- t=11 · rcv pkt2, deliver it and 3 buffered packets
- t=11 · send ACK2
- t=12 · rcv ACK4 — marked, window stays at 2
- t=13 · rcv ACK5 — marked, window stays at 2
- t=14 · rcv ACK2 — window slides to 6
The same loss as the Go-Back-N run in section 3.4.3: packet 2. Compare the two retransmission counts, then look at the receiver strip while packet 2 is missing.
Seven transmissions instead of ten
The same loss, the same window, the same six packets. Go-Back-N needed ten transmissions; selective repeat needs seven.
Watch the receiver strip while packet 2 is missing. Packets 3, 4 and 5 arrive and are kept, not discarded. Then packet 2 finally arrives and all four go up to the application together, and the receive window jumps four places at once.
That bulk delivery is the visible signature of selective repeat.
| Action | |
|---|---|
Cells marked ⓘ have an explanation — click to read it. Sortable columns have a ↕ in the heading.
Three events, and the second one is where selective repeat earns its name.
| Action | |
|---|---|
Cells marked ⓘ have an explanation — click to read it. Sortable columns have a ↕ in the heading.
The second row looks pointless and is not. Read its explanation before moving on.
Why acknowledge a packet you delivered long ago?
The second receiver rule looks like wasted effort. It is not, and the reason is the most important sentence in this section.
Suppose there is no acknowledgement for send_base propagating back to the
sender. Eventually the sender will retransmit send_base — even though it is
obvious to us that the receiver already has it. If the receiver does not
acknowledge that retransmission, the sender’s window will never move forward,
and the connection stalls permanently.
This illustrates something that will matter again and again:
The sender and the receiver will not always have an identical view of what has been received. For selective repeat, this means the sender window and the receiver window will not always coincide.
The trap
That lack of synchronisation has a consequence once you remember that the range of sequence numbers is finite.
Take a sequence-number space of four — 0, 1, 2, 3 — and a window size of three. Suppose packets 0 through 2 are transmitted, correctly received and acknowledged. The receiver’s window is now over the fourth, fifth and sixth packets, which carry sequence numbers 3, 0 and 1.
The first three packets arrive perfectly. All three acknowledgements die on the way back, so the sender times out and resends its first packet.
Click any arrow to see what that message says and why it is sent.
Four sequence numbers, a window of three. Switch between the two runs and look only at what crosses the curtain — that is all the receiver ever sees.
Read this diagram as text
- Sender sends pkt0 to Receiver. Sender window covers sequence numbers 0, 1, 2.
- Receiver sends ACK0 to Sender — lost. The receiver delivered the data and moved its window on to 1, 2, 3. The sender never finds out.
- Sender sends pkt1 to Receiver.
- Receiver sends ACK1 to Sender — lost.
- Sender sends pkt2 to Receiver.
- Receiver sends ACK2 to Sender — lost. The receiver’s window is now over the fourth, fifth and sixth packets — sequence numbers 3, 0 and 1.
- Sender sends pkt0 (retransmission) to Receiver — retransmission. The sender heard nothing, so it retransmits its oldest unacknowledged packet — the very first one. It carries sequence number 0.
Lifelines, left to right: Sender (host), Receiver (host).
There is a curtain between the two hosts
The book draws it literally, and it is worth taking seriously. The receiver cannot see the sender’s actions. All it observes is the sequence of messages it receives from the channel and the sequence it sends into the channel.
As far as the receiver is concerned the two scenarios above are identical. In the first, a packet labelled 0 is a retransmission of the very first packet. In the second, a packet labelled 0 is brand-new data — the fifth packet. There is no way to tell them apart.
So a window size one less than the sequence-number space does not work. How small must it be?
send pkt0
Sender — Figure 3.19
Receiver — out-of-order packets are buffered
- Delivered
- 0/7
- First transmissions
- 7
- Retransmissions
- 0
- Wasted
- —
The whole trace as text
- t= 0 · send pkt0
- t= 1 · send pkt1
- t= 2 · send pkt2
- t= 2 · window full — the sender must wait
- t= 3 · rcv pkt0, deliver
- t= 3 · send ACK0
- t= 4 · rcv pkt1, deliver
- t= 4 · send ACK1
- t= 5 · rcv pkt2, deliver
- t= 5 · send ACK2
- t= 6 · rcv ACK0 — window slides to 1
- t= 6 · send pkt3
- t= 6 · window full — the sender must wait
- t= 7 · rcv ACK1 — window slides to 2
- t= 7 · send pkt4
- t= 7 · window full — the sender must wait
- t= 8 · rcv ACK2 — window slides to 3
- t= 8 · send pkt5
- t= 8 · window full — the sender must wait
- t= 9 · rcv pkt3, deliver
- t= 9 · send ACK3
- t=10 · rcv pkt4, deliver
- t=10 · send ACK4
- t=11 · rcv pkt5, deliver
- t=11 · send ACK5
- t=12 · rcv ACK3 — window slides to 4
- t=12 · send pkt6
- t=13 · rcv ACK4 — window slides to 5
- t=14 · rcv ACK5 — window slides to 6
- t=15 · rcv pkt6, deliver
- t=15 · send ACK6
- t=18 · rcv ACK6 — window slides to 7
The labels on the cells are the sequence numbers actually carried in the header; the small number underneath is which packet it really is. Watch the label 0 come round again while the window still remembers the first one.
In plain words
The rule, which one of the chapter’s problems asks you to prove, is:
For selective repeat, the window size must be at most half the size of the sequence-number space.
Half, and no more. With a k-bit sequence number field the space is and the largest safe window is .
Go-Back-N is less demanding: it can use a window of . Its cumulative acknowledgements leave the receiver with only one number to track, so there is no second window to fall out of step with the first.
| Go-Back-Ndiscard out of order | Selective repeatbuffer out of order | |
|---|---|---|
| Acknowledgements | ||
| Receiver buffering | ||
| Timers at the sender | ||
| On a timeout, resend | ||
| Cost of one loss (the run above) | ||
| Largest safe window | ||
| Receiver state |
Cells marked ⓘ have a reason behind them — click to read it.
Both are sliding-window protocols. Every row below is a consequence of one decision: whether the receiver keeps out-of-order packets.
One assumption left to remove
Everything in section 3.4 has assumed the channel does not reorder packets. That is reasonable when sender and receiver are joined by a single physical wire. When the “channel” is a network, it is not true at all.
A packet can arrive from the past
With reordering, think of the channel as able to buffer packets and emit them spontaneously at any point in the future.
Now the danger is clear. Sequence numbers are reused. So an old copy of a packet carrying sequence number x can surface long after the sender window has moved past it, and the receiver window with it. It will look perfectly valid.
The defence used in practice is not clever, and it is not a protocol mechanism at all. A sequence number is not reused until the sender is sure that any earlier packet carrying it is no longer in the network. That requires assuming a maximum packet lifetime maximum packet lifetime Simple The longest a packet is assumed to be able to survive inside the network. Precise The assumption that lets a protocol safely reuse a sequence number: no previously sent packet carrying that number can still be wandering in the network. The TCP extensions for high-speed networks [RFC 7323] assume roughly three minutes. Without such an assumption, packet reordering could make an old copy indistinguishable from new data. introduced in ch. 3 — open in glossary , and the TCP (Transmission Control Protocol) Transmission Control Protocol The Internet transport protocol that delivers data reliably and in order, with flow control and congestion control. introduced in ch. 1 extensions for high-speed networks assume roughly three minutes [RFC 7323].
Section 3.5.2 puts a number on how much that assumption buys. TCP’s 32-bit sequence space wraps in about 344 seconds at 100 Mbps, comfortably longer than three minutes. At 10 Gbps it wraps in 3.4 seconds, which is not comfortable at all.
What section 3.4 built
| Use, comments | |
|---|---|
Cells marked ⓘ have an explanation — click to read it. Sortable columns have a ↕ in the heading.
Nothing in this table appeared before the channel forced it. Everything in it reappears in TCP.
In plain words
Six mechanisms, developed over four protocols, each one added at the moment the channel made it unavoidable.
Section 3.5 now takes the whole toolkit and asks a different question. Not “what would you build?” but “what did they actually build?” The answer, TCP, turns out to be neither Go-Back-N nor selective repeat.
Check yourself
Check yourself
0 of 6 answered1.predictThe selective-repeat run loses packet 2, exactly as the Go-Back-N run did. How many packets does the sender transmit in total?
2.Why must a selective-repeat sender keep a separate timer for each packet?
3.A packet arrives whose sequence number falls below the receive window — one the receiver has already delivered and acknowledged. What must it do?
Think about what the sender must be believing, for it to have sent this.
4.predictIn Figure 3.27, both scenarios end with the receiver getting a packet labelled with sequence number 0. What is different about the two, from the receiver's point of view?
5.With a sequence-number space of size 8, what is the largest safe selective-repeat window?
6.Section 3.4 assumed the channel never reorders packets. What breaks when it does, and how is it handled in practice?
What to remember
- Selective repeat resends only what was lost. Seven transmissions for six packets, against Go-Back-N’s ten.
- A packet below the receive window must still be acknowledged, or the sender’s window may never move and the connection stalls.
- The sender’s and the receiver’s windows do not always coincide, and that is not a bug. Because of it the SR window must be at most half the sequence-number space, where Go-Back-N may use one less than the whole space.