Automatic repeat request

In networked distributed systems, automatic repeat request (ARQ) is the process of repeating a lost (i.e., it doesn’t make it to the destination) or errored (i.e., some bits are flipped) packet.

We first introduce a handshaking mechanism.

• Acknowledgements (ACK) are sent by the receiver to explicitly tell the sender that a packet has been received okay.
• NAKs are sent when the packets have errors. Upon receipt of a NAK, the sender will re-transmit the packet.

There are also a few other parameters:

• A sequence number (or operation ID) can be used to uniquely identify a packet and ensure linearisability.
• Time outs are often used to determine whether an operation should be redone.
  • The timeout should be greater than the round-trip time.
  • If the RTT is a random variable, then we have the time-out be $E(\text{RTT})+4\sigma (\text{RTT})$.

Stop-and-wait

Stop-and-wait (SW) is a NAK-free implementation. Instead of NAK, the receiver sends an ACK for the last packet received OK. The receiver must explicitly include the sequence number of the packet being ACKed (an acknowledgement number). Note that we need to detect duplicates on receiver-side (to prevent duplicate operations). Basically to ensure linearisability.

The utilisation is given by:

$$U_{\text{stop-wait}}=\frac{L/R}{L/R+\text{RTT}}$$

which is quite low compared to the RTT.

Go-back n

This is a pipelined implementation. Packets are buffered and packets in a buffer are sent/received all at once. If we buffer $n$ packets, then we should also receive $n$ ACK signals.

This vastly improves the utilisation:

$$U_{\text{GBN}}=n\frac{L/R}{L/R+\text{RTT}}$$

The sender maintains a window of size $n$ that it sends. If a packet is dropped, the receiver will resend the last packet ACK before the dropped packet. GBN is allowed to transmit up to $n$ unacked packets. It has to retransmit all $n$ packets if the first one is lost. Trivially, the number of bits in the sequence window $m$ is determined by the window size $n$ (or it goes the other way around), i.e.,

$$n\le 2^m-1$$

The key problem with GBN is that we can’t get high utilisation without a similarly high window size. Because many packets have to be retransmitted, it’s also inefficient on long-haul transmission links with a high bandwidth.

Selective repeat

Selective repeat allows the sender to retransmit only the lost packets. There is a timer maintained for each unacked packet. If the timer expires, then only the unacked packet is retransmitted.

The receiver then must individually acknowledge all correctly received packets. It will buffer packets as needed, for eventual in-order delivery to upper layer. Note that the timeout is the only way to find out about a lost packet.