Selective Repeat Error Recovery

Selective Repeat error recovery is a procedure which is implemented in some communications protocols to provide reliability. It is the most complex of a set of procedures which may provide error recovery, it is however the most efficient scheme. Selective repeat is employed by the TCP transport protocol.

Features required for Selective Repeat 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.

The above features are also required for Go-Back-N, however for selective repeat, the receiver must also maintain a buffer of frames which have been received, but not acknowledged.

Recovery of lost PDUs using Selective Repeat ARQ

The recovery of a corrupted PDU proceeds in four 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 Selective Reject). The receiver then stores all out-of-sequence PDUs in the receive buffer until the requested PDU has been retransmitted.
• The sender receives the retransmission request and then transmits the lost PDU(s).
• The receiver forwards the retransmitted PDU, and all subsequent in-sequence PDUs which are held in the receive buffer.

Retransmission using Selective Repeat

A remote node may request retransmission of corrupted PDUs by initiating Selective Repeat error recovery by sending a control PDU indicating the missing PDU. This allows the remote node to instruct the sending node where to retransmit the PDU which has not been received. The remote stores any out-of-sequence PDUs (i.e. which do not have the expected sequence number) until the retransmission is complete.

Upon receipt of a Selective Repeat control PDU (by the local node), the transmitter sends a single PDU from its buffer of unacknowledged PDUs. The transmitter then continues normal transmission of new PDUs until the PDUs are acknowledged or another selective repeat request is received.

Operation of Selective Repeat. The sender transmits four PDUs (1-4). The first PDU (1) is corrupted and not received. The receiver detects this when it receives PDU(2), which it stores in the receive buffer and requests a selective repeat of PDU(1). The sender responds to the request by sending PDU(1), and then continues sending PDUs (5-7). The receiver stores all subsequent out-of-sequence PDUs (3-4), until it receives PDU(1) correctly. The received PDU (1) and all stored PDUs (2-4) are then forwarded, followed by (5-7) as each of these is received in turn.

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.

Comparison of ARQ Methods

The table below provides a comparison of the various ARQ methods described. (W is the window size, or number of PDUs which may be in transit at any one time).

ARQ Method	Sender Buffer	Receiver Buffer	Control PDUs
Stop-and-Wait	1 PDU	1 PDU	ACK
Polling	W PDUs	1 PDU	ACK, Poll, Response
Go-Back-N	W PDUs	1 PDU	ACK, Go-Back-N
Selective Repeat	W PDUs	W PDUs	ACK, Selective Repeat

See also

Reliability

Stop and Wait ARQ

Polling

Go-Back-N ARQ

Selective Repeat ARQ (this page)