§3.4.3Go-Back-N (GBN)

Transport layer Kurose & Ross pp. 215–219 · ~9 min read

  • go-back-n
  • sliding-window protocol
  • sender window
  • window size
  • cumulative acknowledgement
  • event-based programming

Where you are

  • Application layer
  • Transport layer you are here
  • Network layer
  • Link layer
  • Physical layer

Go-Back-N lets the sender keep N packets in flight. When one is lost it resends that packet and every one after it, which keeps the receiver trivially simple and throws away a great deal of good work.

Words you will meet

  • Go-Back-N — resend the lost packet and everything after it.
  • Sender window — the stretch of sequence numbers the sender may currently use.
  • base — the sequence number of the oldest unacknowledged packet.
  • nextseqnum — the smallest unused sequence number.
  • Cumulative acknowledgement — an ACK for packet n that also means “everything before n arrived”.

Why this matters

Section 3.4.2 established that a sender must pipeline, and that pipelining forces a choice about how to recover from loss. This is the first of the two answers.

It is also the one closest to TCP (Transmission Control Protocol) . Section 3.5.4 will find that TCP uses almost everything here — sequence numbers, cumulative acknowledgements, checksums, a single timer and timeout-driven retransmission — and then differs in one important way.

The window, and the four bands

In a Go-Back-N protocol the sender may transmit multiple packets without waiting for an acknowledgement. It is constrained to have no more than N unacknowledged packets outstanding.

Two variables define the state. base is the sequence number of the oldest unacknowledged packet, and nextseqnum is the smallest unused sequence number. Between them they cut the sequence-number space into four bands.

Figure 3.19 — the sender’s view of the sequence numbers
step 1/26 · t = 0⏱ timer running

send pkt0

Sender — Figure 3.19

012345windowbase
Delivered
0/6
First transmissions
6
Retransmissions
0
Wasted
—
The whole trace as text
  1. t= 0 · send pkt0
  2. t= 1 · send pkt1
  3. t= 2 · send pkt2
  4. t= 3 · rcv pkt0, deliver
  5. t= 3 · send ACK0
  6. t= 3 · send pkt3
  7. t= 3 · window full — the sender must wait
  8. t= 4 · rcv pkt1, deliver
  9. t= 4 · send ACK1
  10. t= 5 · rcv pkt2, deliver
  11. t= 5 · send ACK2
  12. t= 6 · rcv ACK0 — window slides to 1
  13. t= 6 · rcv pkt3, deliver
  14. t= 6 · send ACK3
  15. t= 6 · send pkt4
  16. t= 6 · window full — the sender must wait
  17. t= 7 · rcv ACK1 — window slides to 2
  18. t= 7 · send pkt5
  19. t= 8 · rcv ACK2 — window slides to 3
  20. t= 9 · rcv ACK3 — window slides to 4
  21. t= 9 · rcv pkt4, deliver
  22. t= 9 · send ACK4
  23. t=10 · rcv pkt5, deliver
  24. t=10 · send ACK5
  25. t=12 · rcv ACK4 — window slides to 5
  26. t=13 · rcv ACK5 — window slides to 6

Four bands, two markers, one window. Step forward to watch the window slide, and notice that it only ever moves when the oldest unacknowledged packet is acknowledged.

The range of permissible sequence numbers for transmitted-but-unacknowledged packets can be seen as a window of size N over the sequence-number space. N is the window size .

As the protocol runs, that window slides forward over the sequence-number space, which is why GBN is called a sliding-window protocol .

In plain words

The window moves for exactly one reason: the oldest unacknowledged packet gets acknowledged.

Not when a packet is sent — that moves nextseqnum, not base. Not when some later packet is acknowledged. Only when the left-hand edge is cleared. That is why a single lost packet can stall a sender with a full window: everything behind it is waiting on one gap.

Why limit it to N at all?

Why not let the sender have an unlimited number of unacknowledged packets in flight?

Two answers, both later in the chapter. Section 3.5.5 gives the first: flow control — the receiver has a finite buffer and can be overrun. Section 3.7 gives the second: congestion control — the network between them has finite capacity too.

For now, N is simply a number the protocol is given.

Sequence numbers are finite

In practice a sequence number is carried in a fixed-length header field. If that field is k bits, the range is [0,2k−1][0, 2^k - 1] and all arithmetic on sequence numbers is done modulo 2k2^k. The space is a ring, where the number after 2k−12^k - 1 is 0 again.

rdt3.0 had a 1-bit sequence number and a range of [0,1][0, 1]. TCP has a 32-bit field, and section 3.5.2 will show that it counts bytes rather than packets.

The consequences of a finite ring are not obvious, and section 3.4.4 is largely about one of them.

Watching it run

Figure 3.22 — Go-Back-N in operation, window size 4
step 1/41 · t = 0⏱ timer running

send pkt0

Sender — Figure 3.19

012345windowbase

Receiver — nothing is kept out of order

012345expectedseqnum
Delivered
0/6
First transmissions
6
Retransmissions
4
Wasted
3 packets
Lose a packet
The whole trace as text
  1. t= 0 · send pkt0
  2. t= 1 · send pkt1
  3. t= 2 · send pkt2
  4. t= 5 · pkt2 lost in the channel
  5. t= 3 · rcv pkt0, deliver
  6. t= 3 · send ACK0
  7. t= 3 · send pkt3
  8. t= 3 · window full — the sender must wait
  9. t= 4 · rcv pkt1, deliver
  10. t= 4 · send ACK1
  11. t= 6 · rcv ACK0 — window slides to 1
  12. t= 6 · rcv pkt3, discard
  13. t= 6 · send ACK1
  14. t= 6 · send pkt4
  15. t= 6 · window full — the sender must wait
  16. t= 7 · rcv ACK1 — window slides to 2
  17. t= 7 · send pkt5
  18. t= 9 · rcv ACK1 again — nothing new
  19. t= 9 · rcv pkt4, discard
  20. t= 9 · send ACK1
  21. t=10 · rcv pkt5, discard
  22. t=10 · send ACK1
  23. t=12 · rcv ACK1 again — nothing new
  24. t=13 · rcv ACK1 again — nothing new
  25. t=13 · pkt2 timeout — go back to 2
  26. t=13 · resend pkt2
  27. t=14 · resend pkt3
  28. t=15 · resend pkt4
  29. t=16 · rcv pkt2, deliver
  30. t=16 · send ACK2
  31. t=16 · resend pkt5
  32. t=17 · rcv pkt3, deliver
  33. t=17 · send ACK3
  34. t=18 · rcv pkt4, deliver
  35. t=18 · send ACK4
  36. t=19 · rcv ACK2 — window slides to 3
  37. t=19 · rcv pkt5, deliver
  38. t=19 · send ACK5
  39. t=20 · rcv ACK3 — window slides to 4
  40. t=21 · rcv ACK4 — window slides to 5
  41. t=22 · rcv ACK5 — window slides to 6

Packet 2 is lost. Step through it, then use the buttons to lose a different packet — or none at all — and watch the retransmission count change.

Count the arrows before you move on

With packet 2 lost, the sender transmits ten packets to deliver six.

Packets 3, 4 and 5 crossed the network intact, arrived at a receiver that was working perfectly, and were thrown away — then sent again. Three wasted crossings out of ten.

Now press the button to lose packet 2 again, un-losing it, and watch the count drop to six. Then lose two packets and watch it climb.

This is the cost of Go-Back-N, and it grows with the sender window. When that window and the bandwidth-delay product are both large, a single error can force the retransmission of a great many packets, most of them unnecessarily. And from section 3.4.2, that is exactly the case where pipelining was worth doing.

The two machines

Figure 3.20 — the GBN sender, as an extended FSM
rdt_send(data)if(nextseqnum<base+N){ sndpkt[nextseqnum]=make_pkt(nextseqnum,data,chksum) udt_send(sndpkt[nextseqnum]) if(base==nextseqnum) start_timer nextseqnum++}else refuse_data(data)timeoutstart_timerudt_send(sndpkt[base])udt_send(sndpkt[base+1])...udt_send(sndpkt[nextseqnum-1])rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)base=getacknum(rcvpkt)+1If(base==nextseqnum) stop_timerelse start_timerrdt_rcv(rcvpkt)&& corrupt(rcvpkt)ΛWait
Fire an event

Outlined buttons are the events this state can actually handle. Try the others too — what cannot happen is as much of the protocol as what can.

One state, and all the work in the transitions. It is called an *extended* FSM because it carries variables — base and nextseqnum — and takes conditional actions on them.
The three events a GBN sender must handle
What the sender does

Cells marked ⓘ have an explanation — click to read it. Sortable columns have a ↕ in the heading.

The book’s own list. An implementation is usually written exactly this way — a procedure per event — which is why the extended FSM reads almost like code.
Figure 3.21 — the GBN receiver, as an extended FSM
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && hasseqnum(rcvpkt,expectedseqnum)extract(rcvpkt,data)deliver_data(data)sndpkt=make_pkt(expectedseqnum,ACK,chksum)udt_send(sndpkt)expectedseqnum++defaultudt_send(sndpkt)Wait
Fire an event

Outlined buttons are the events this state can actually handle. Try the others too — what cannot happen is as much of the protocol as what can.

Simpler than the sender, and deliberately so. One variable, expectedseqnum, and a default action that repeats the last acknowledgement.

The receiver’s whole job is one variable

Suppose a packet with sequence number n arrives correctly and in order, meaning the data last delivered came from packet n − 1. The receiver sends an ACK for n and delivers the data upward.

In every other case it discards the packet and re-sends an ACK for the most recently received in-order packet.

Because packets are delivered one at a time and in order, if packet k has been delivered then so has everything below k. That is what makes a cumulative acknowledgement the natural choice here. It also means the receiver needs to remember exactly one number, expectedseqnum.

Discarding a good packet is a deliberate trade, not an oversight

It looks wasteful, and it is. The justification is worth following.

Suppose packet n is expected and packet n + 1 arrives. The receiver could buffer it and deliver it later, once n has arrived. But if n was lost, the Go-Back-N rule means n and n + 1 will both be retransmitted anyway. So buffering n + 1 gains nothing.

What discarding buys is simplicity: the receiver need not buffer any out-of-order packet. The sender maintains the window bounds and nextseqnum; the receiver maintains one variable.

What it costs is the obvious thing, plus one less obvious. A correctly received packet is thrown away — and the retransmission that replaces it might itself be lost or garbled, forcing yet more retransmissions.

Try the awkward corner

In the simulation above, un-lose packet 2 and lose packet 0 instead. Step to the receiver’s first arrival.

Packet 1 turns up, out of order, and is discarded. Now the receiver is supposed to “re-send an ACK for the most recently received in-order packet”, except there isn’t one. It has nothing to say, and says nothing. Only the sender’s timeout rescues the connection.

The book steps around this by numbering packets from 1 and initialising the receiver’s stored acknowledgement to make_pkt(0,ACK,checksum). That is an ACK for a packet which does not exist, whose only job is to be there before anything else is. Real protocols carry a fair amount of this sort of thing.

How it is really written

An implementation would likely look much like the extended FSM (finite-state machine) : procedures invoked in response to events, either by other procedures in the stack or by an interrupt. This is event-based programming . For the sender the events are precisely the three in the table above. A call from the layer above, a timer interrupt, and a call from the layer below when a packet arrives.

In plain words

Go-Back-N already contains almost everything TCP does for reliable transfer: sequence numbers, cumulative acknowledgements, checksums, and timeout-driven retransmission.

Keep that in mind through the next section. Selective repeat will look like a strict improvement, and TCP will turn out not to be either one.

Check yourself

Check yourself

0 of 6 answered

  1. 1.predictIn the Go-Back-N simulation with window 4, packet 2 is lost. How many packets does the sender end up transmitting in total?

    Count the retransmission burst, not just the lost packet.

  2. 2.Why does the Go-Back-N receiver throw away a correctly received out-of-order packet?

  3. 3.The sender receives ACK5 while packets 3 through 8 are unacknowledged. What does it mean?

  4. 4.predictMark packet 0 as lost instead of packet 2, and step to the receiver's first arrival. What does the receiver do?

  5. 5.How many timers does a Go-Back-N sender need?

  6. 6.With a k-bit sequence-number field, what is the range of sequence numbers?

What to remember

  • The sender window slides only when base is acknowledged — not when a packet is sent, and not when a later packet is acknowledged.
  • ACKs are cumulative: ACK n means everything up to n arrived. A lost ACK is often harmless.
  • One timer, for the oldest unacknowledged packet, and on timeout the sender resends everything outstanding. The receiver discards everything out of order, so a single loss costs several retransmissions: six packets took ten transmissions above.