Go-Back-N Error Recovery

Go-Back-N error recovery is a procedure which is implemented in some communications protocols to provide reliability. Go-Back-N ARQ (is one of a number of error recovery procedures to detect and retransmit I-frames which have been corrupted due to errors in the physical link (c.f. saw, polling, selective repeat).

Features required for Go-Back-N ARQ

• To support Go-Back-N ARQ, a protocol must number each PDU which is sent. (PDUs are normally numbered using modulo arithmetic, which allows the same number to be re-used after a suitably long period of time. The time period is selected to ensure the same PDU number is never used again for a different PDU, until the first PDU has "left the network" (e.g. it may have been acknowledged)).
• The local node must also keep a buffer of all PDUs which have been sent, but have not yet been acknowledged.
• The receiver at the remote node keeps a record of the highest numbered PDU which has been correctly received. This number corresponds to the last acknowledgement PDU which it may have sent.

Recovery of lost PDUs using Go-Back-N.

The recovery of a corrupted PDU proceeds in three stages:

• First, the corrupted PDU is discarded at the remote node's receiver.
• Second, the remote node requests retransmission of the missing PDU using a control PDU (sometimes called a NACK or REJECT). The receiver discards all PDUs which do not have the number of the requested PDU.
• The final stage consists of retransmission of the lost PDU(s).

Retransmission using Go-Back-N

A remote node may request retransmission of corrupted PDUs by initiating Go-Back-N error recovery by sending a control PDU indicating the last successfully received PDU. This allows the remote node to instruct the sending node where to begin retransmission of PDUs. The remote node does not store any out-of-sequence PDUs and therefore must discard all received PDUs until one is received with the expected sequence number.

Upon receipt of a Go-Back-N control PDU (by the local node), the transmitter winds-back the sequence of PDUs pending transmission to the indicated PDU in its buffer of unacknowledged PDUs. The transmitter then retransmits (Goes Back-to-N) the requested PDU followed by all successive PDUs. This is sometimes known as "wind back" of the transmitter.

Example of Go-Back-N. The sender in this example transmits four PDUs (1-4) and the first one (1) of these is not successfully received. The receiver notes that it was expecting a PDU numbered 1 and actually receives a PDU numbered 2. It therefore deduces that (1) was lost. It requests retransmission of the missing PDU by sending a Go-Back-N request (in this case N=1), and discards all received PDUs with a number greater than 1.The sender receives the Go-Back-N request and retransmits the missing PDU (1), followed by all subsequently sent PDUs (2-4) which the receiver the correctly receives and acknowledges.

If the retransmission is not successful, the protocol relies upon a protocol timer in the local node to detect that no acknowledgment was received. The lost PDUs may then be recovered by Polling.

See also

Reliability

Stop and Wait ARQ

Polling

Go-Back-N ARQ (this page)

Selective Repeat ARQ

For further information see:

HDLC Reject Procedure