Go-Back-N Protocol

What is Go Back N?

The Go-Back-N protocol is a sliding window protocol where multiple packets can be sent in a row, with a maximum of N packets, without waiting for acknowledgements. In order to understand where the term sliding window comes from, observe Figure 1 below.

Figure 1. Sequence numbers in Go-Back-N

There are 16 packets in the image, divided in four groups. The first four packets in the interval [0, base - 1], green group, are packets that have been sent successfully and the sender has received ACK's for all of them. The next four packets in the interval [base, nextseq - 1], blue group (nextseq stands for next sequence number), have been sent but not yet received acknowledgements. The brown group, [nextseq, base + N - 1], have not been sent yet but they are ready to be sent. The gray (grey?) group, where the sequence numbers are greater than or equal to base + N can't be used until base has been acknowledged.

Window size in the image covers the blue and brown groups, i.e the packets which are either sent but not acknowledged yet or ready to be sent. When the base has been acknowledged, this window slides to the right over the sequence number space, hence the name sliding window protocol.

A sequence number is stored in a fixed-length field in every packet's header, containing k bits. The range of sequence numbers is $[0, 2^k-1]$ , where $2^k-1$ is followed by 0. Since it's the sequence numbers are in a finite range, all arithmetic involving sequence numbers must be done using modulo $2^k$ .

Go-Back-N works as follows. When the sender gets an invocation from the upper layer, it first needs to check if the window is full. If it is, the sender tells the upper layer that it's full, otherwise it creates packets, sends them out and update all variables. The receiver then sends an ACK to the sender with the sequence number it's acknowledging. This ACK indicates that all of the packets up to the sequence number of the ACK has been received successfully.

When the sender transmits a packet, it starts a timer. This timer restarts every time the sender receives an acknowledgement, and sends the next packet. If a transmitted packet is lost, say packet with sequence number 2, the receiver discards every packet with sequence numbers greater than 2. Since the receiver didn't get a packet with sequence number 2, it won't send an ACK2 to the sender. The timer will eventually reach timeout. When that happens the sender resends all of the packets from the one missing. This idea is expressed in Figure 2, where the window size is 3, meaning there are three packets within a window.

Figure 2. Go-Back-N protocol with a lost packet