Automatic Repeat reQuest. Any protocol that uses positive and negative acknowledgements with retransmission techniques to ensure reliablity. The sender automatically repeats the request if it does not receive an answer.

Automatic Repeat reQuest (ARQ) is a classification of communications protocols which allow recovery from packet loss or corruption by requesting retransmission of missing packets.

Error Recovery

Error recovery techniques fall into three classes: error concealment, forward error correction (FEC), and backward error correction (BEC). Error concealment repeats previous data to mask small errors; this is used to great effect in audio compact disc players. Forward error correction uses a redundant coding scheme to reconstruct damaged messages. Backward error correction copes with lost or damaged packets by simply retransmitting them; ARQ describes a group of protocols which request retransmissions in different ways.

Acknowledgement messages are a requirement for any ARQ protocol; such packets may be positive (ACK) or negative (NAK). Positive acknowledgements are sent to indicate correct reception of a message, whereas negative acknowledgements are sent when an expected message has not been received. Implicit negative acknowledgements can be made using timers; if the receiver hasn't replied within a set time period, the transmitter assumes that no packet was received. In practice, any combination of these acknowledgement types may be used, but timers are a must if explicit acknowledgements may be lost: otherwise, both ends of the communication link could wait forever for a packet to arrive.

ARQ Protocols

There are three commonly used ARQ protocols: stop and wait, go-back N, and selective retransmission. Stop and wait is the simplest: the transmitter sends data, and waits for an acknowledgement before sending any further data. This requires no buffering of data, but is inefficient when link propagation time is high.

Go-back N uses negative acknowledgements: for example, if packets 1 through 4 are received, then packet 6 arrives, the receiver sends a NAK for packet 5. The transmitter must then restart from packet 5, resending packet 6 even though it had been received already. This is used to make the receiving side simpler, as no re-ordering of packets is required.

Selective retransmission is the most complicated of the three to implement, but the most bandwidth efficient. In the example above, a NAK would be sent for packet 5, and only packet 5 would be retransmitted. The receiver must then re-order its buffer to slot in the newly received packet.

Common Implementations

The commonly used Transport Control Protocol (TCP, from TCP/IP) is often described as using go-back N. TCP uses cumulative acknowledgements: every packet has a header ACK number, which means, "yep, got all packets up to N, send me number N". If packet N is then lost, and further packets received, this ACK number cannot be updated to reflect this; when the receiving side notices that packet N has timed out, it will retransmit.

Looking simplistically at TCP, this would imply that several packets are likely to time out before the receiver is able to acknowledge the retransmitted packet. However, TCP uses a congestion avoidance algorithm to negate this problem, and in most cases only one packet is retransmitted. Therefore, while TCP appears to use go-back N, it in fact effectively functions as if it used selective retransmission.

References:

"TCP/IP Illustrated Volume 1", Stevens, Addison-Wesley, 1994
"Data Communications and Networks: An Engineering Approach", Irvine/Harle, Wiley, 2000

Log in or register to write something here or to contact authors.