A link numbers its packets with a 3-bit counter, 0 to 7, wrapping back to 0. The sender is allowed 8 packets outstanding. One day the receiver gets packet 3, expects 4, and receives "0". Is that the new packet 0 after a wrap, meaning 4 to 7 were lost? Or an old packet 0 being resent? The receiver cannot tell, and either guess can deliver wrong data. The counter was one bit too short.
What do sequence numbers detect, and how many bits do they need?
The obvious answer is a counter on every packet, wide enough that it rarely wraps. But any finite counter wraps, and on a fast link even a 16-bit counter wraps many thousands of times per second. What matters is not how often it wraps, but whether, at any moment, two packets that could both still be in flight can carry the same number. That depends on the window, not on time.
The receiver sees | Means | Action |
|---|---|---|
The number it expects | In order | Accept; expect the next |
A number already received | A duplicate (a resend after a lost ACK) | Discard; acknowledge again |
A number ahead of the expected one | One or more packets were lost (or reordered) | NAK, or buffer it (selective repeat, lesson 10.12) |
Numbers are taken modulo 2^n for an n-bit field. For that to be unambiguous, the set of numbers that can be in flight at once must never contain the same value twice, including old packets that might be resent.
For a sender that may have up to W packets unacknowledged:
Go-back-N (the receiver accepts only the next expected packet): W ≤ 2^n − 1. With 3 bits, at most 7 outstanding. With 8 outstanding, a full window of new packets 0 to 7 is indistinguishable from all eight being lost and resent.
Selective repeat (the receiver buffers out-of-order packets): the receiver's window and the sender's can be offset by up to W, so the numbers must cover 2W: W ≤ 2^(n−1).
Window needed (from lesson 10.11): bandwidth x ACK round trip
e.g. 14.3 million packets/s x 500 ns ~ 7 packets; design for bursts and delays: say 64
Go-back-N: 64 <= 2^n - 1 -> n = 7 bits (127)
Selective repeat: 64 <= 2^(n-1) -> n = 7 bits (64)
The opening link: 8 outstanding with 3 bits breaks go-back-N's rule (8 > 7): one bit too fewProtocol | Sequence numbers |
|---|---|
PCI Express data link layer | 12-bit sequence numbers with go-back-N replay, so at most 4,095 TLPs may be unacknowledged. |
TCP | 32-bit byte sequence numbers, with extensions for very fast links where even 32 bits wrap quickly. |
DCLink (step 9) | 8-bit sequence numbers with go-back-N, so at most 255 packets unacknowledged. |
The opening link (illustrative) allowed 8 outstanding packets with a 3-bit number. A burst of errors caused all eight to be lost and resent; the receiver, expecting a new 0, accepted the resent old 0 as new, and from then on delivered every packet one window late, with no error. Limiting the window to 7 (or widening the field to 4 bits) made the ambiguity impossible.
2^5 − 1 = 31 packets.
Ambiguity arises only if two packets that could both be in flight (including resends) share a number; the window bounds how many that can be.
Sequence numbers let the receiver detect duplicates, losses and reordering.
Go-back-N needs W ≤ 2^n − 1; selective repeat needs W ≤ 2^(n−1).
Size n from the window, enforce the window in hardware, and test windows that straddle the wrap.