Go-back N is a window-based ARQ protocol, used to request in-order retransmission of lost or corrupted packets in a communications network.
Protocol Operation
The middle of the three classes of ARQ protocols, go-back N is more efficient than stop and wait, but requires more resources to implement, and is less efficient than selective retransmission. Several packets are normally in transit at all times, and the packets are therefore numbered. When retransmission is required, the transmitting side resends all currently unacknowledged packets -- going back to N, the oldest unacknowledged packet.
Sequence Numbering
In order to improve efficiency compared to stop and wait, go-back N sends several packets without waiting for individual acknowledgements. Since the receiver must be able to distinguish these packets from each other, a numbering scheme must be used. Each packet has a sequence number, which is part of the packet header. The header will normally have a fixed-size sequence number field of S bits; to be able to send more than 2S packets in one transaction, the numbers are considered modulo 2S.
The sequence number will increment with each packet sent: from 0 to 1, 2, ..., 2S-1, and to 0 again. This means that two different packets may have the same sequence number. If these two packets are in transit at the same time, the receiver will be unable to tell which is the first of the two, and therefore also unable to reassemble the original message. Therefore, a limit on the number of unacknowledged packets in flow must be made.
Sliding Window
This limit is known as the window size of the protocol, and for go-back N it is simply 2S-1. The window has a lower and an upper limit, which define the sequence numbers which match currently valid packets. The window is so-called because it is imagined as a view into the overall sequence number space. When the leftmost packet is acknowledged, the window slides right one place. Below is an example of a sliding window of size four, with a sequence number space of size eight.
| Sliding Window |
-----------------------------------
| ::::::::::::::::: |
| 0 ::1:::2:::3:::4:: 5 6 7 |
| ::::::::::::::::: |
-----------------------------------
| Sliding Window |
-----------------------------------
Sequence | ::::::::::::::::: |
Number | 0 1 ::2:::3:::4:::5:: 6 7 |
Space | ::::::::::::::::: |
-----------------------------------
| Sliding Window |
-----------------------------------
| ::::::::::::::::: |
| 0 1 2 ::3:::4:::5:::6:: 7 |
| ::::::::::::::::: |
-----------------------------------
Example Operation
Go-back N is best described with an example, and preferably a diagram. Below is a representation of a transaction using go-back N, in which packet number 2 is lost between the transmitter (TX) and the receiver (RX).
------------------------------------------------------> Time
(Lost) (Retransmission)
---- ---- ---- ---- ---- ---- ----
TX | D0 | | D1 | | D2 | | D3 | | D4 | | D2 | | D3 | ...
----. ---- ---- ---- ---- ---- ----
. ---- ---- ---- ---- ----
RX . | A0 | | A1 | | N2 | | A2 | | A3 | ...
. .---- ---- ---- ---- ----
. .
Link
propagation
delay
As can be seen from the diagram, data packets numbered 0 and 1 are received correctly, and acknowledged with ACKs A0 and A1. However, packet 2 is lost in the communication channel, and so the next packet the receiver sees is D3. It notices that the previous packet is missing, and so sends a NAK (negative acknowledgement) indicating that the sender should retransmit from packet 2 onward.
Due to the latency in the network, the transmitted has already sent data packet number 4 when it receives this NAK. However, it immediately goes back to the lost packet number 2, and continues in-order transmission.
Efficiency
Window size plays a crucial role in the efficiency of sliding window protocols. There are two cases which need to be considered: a "small" window, and a "large" window. A protocol is considered to have a large window if it is able to continuously transmit; that is, it doesn't need to stop and wait for the other side to catch up.
Calculating Window Size
Let the data payload size be D bits, the associated header overhead be H bits, and let the the acknowledgement packet be A bits long. Further, let the bit rate of the communications link be B bits/s, and the propagation delay be T seconds. Finally, let the protocol's window size be denoted as W packets.
Then, continuous transmission occurs when the window size is large enough that we can continue to transmit packets while waiting for an acknowledgement of the first packet. Therefore, the time taken to transmit a full window of packets must be at least equal to the time taken to send and acknowledge one packet. The former is given by:
Twindow = W(D + H) / B
The other term in the inequality is the sum of time to send the packet, the time to send the ACK, and the propagation delay in both directions. Therefore:
Tsingle = (D + H) / B + A/B + 2T
And therefore, for a large window size, we have:
W(D + H) / B ≥ (D + H) / B + A / B + 2T
W(D + H) ≥ D + H + A + 2TB
W ≥ 1 + (A + 2TB) / (D + H)
A small window size is obviously the case when this inequality is not satisfied.
Continuous Transmission Efficiency
If the protocol and link parameters mean that a large window size is used, the transmitter need only stop sending data when it is complete. Therefore, the only inefficiency is caused by the header protocol overhead, and the efficiency is:
η = D / (D + H)
Small Window Size Efficiency
However, if the window size is small, the protocol becomes far less efficient. In fact, it simulates a stop and wait protocol which can send several frames at once: there is significant idle time on the link, which is very wasteful. The efficiency is similar to that of stop and wait, given by:
η = D / (D + H) × W / (1 + 2TB / (D + H))
The parameter most likely to cause a small window size is the 2TB term in the equation above. Therefore, as links get longer or have higher bit rate capacity, the window size must be raised. This is the reason behind IETF's long fat pipe TCP/IP extension: without increasing the window size, TCP's performance over the large transatlantic links would be reduced to that of a simple stop and wait protocol.
Protocols Using Go-back N
The advantage of go-back N over the other sliding window protocol, selective retransmission, is that no re-ordering of received packets is ever required. This is most useful in high-speed protocols which are often implemented in hardware for performance reasons. One example of such a protocol is High-level Data Link Control (HDLC).
Go-back N is also occasionally supported in protocols which also use selective retransmission. For example, GSM/GPRS LLC encourages go-back N to be used when only a few packets will be retransmitted, to save the large overhead of calculating and sending a selective acknowledgement bitmap.
References:
"Data Communications and Networks: An Engineering Approach", Irvine/Harle, Wiley, 2000
"RFC 1323: TCP Extensions for High Performance", Jacobsen/Braden/Borman, IETF, 1992
"GSM 04.64: General Packet Radio Service (GPRS) Logical Link Control (LLC) Layer Specification", ETSI, 1997