12. Reliable Data Transfer - ARQ Protocols

Lost packets and out of order packets: acknowledgement and retransmission required.

Reliable data transfer protocols based on retransmission are known as Automatic Repeat reQuest (ARQ) Protocols. These include:

• Alternating Bit Protocol
• Go-Back-N
• Selective Repeat (Selective Reject)

Reliable Data Transfer (RDT) Protocols

RDT 1.0: Perfectly-Reliable

A perfectly reliable channel with:

• No bit errors
• No buffer overflows
• No out-of-order packets
• No packet loss

RDT 2.0: Bit Errors

All packets will arrive at the receivers, but the packet may be corrupted. Checksumming/CRC required for error detection.

Once the sender transmits a packet, it waits for a NAK/ACK from the receiver:

• If NAK, retransmit the packet
• If ACK, send the next packet once it is received from the higher layer

This is known as a stop-and-wait protocol as the sender must wait for the NAK/ACK.

RDT 2.1: Handles Corrupted ACK/NACK

In RDT2.0, if the response is corrupted, the sender does not know if the receiver got a corrupted packet.

In this case, the sender will retransmit the packet. As the receiver does not know if it is a new transmission or a retransmission, RDT 2.0 requires sequence numbers.

As there is a response after every single packet, only a single bit is required for the sequence number. If it is a retransmission, it will use the same value but if it is a transmission, it will flip the bit.

RDT 2.2: NAK-Free Protocol

The receiver only sends ACK messages, but it also sends a sequence number along with it.

The ACK sequence number is the sequence number of the last packet that was received successfully.

RDT 3.0: Lossy Channel with Bit Errors

Packets can get lost and bits can get flipped.

If ACK does not arrive after a timeout, the sender should retransmit the packet. Hence, the sender retransmits on both packet/ACK loss or delay.

If the timeout is too long, performance decreases, but if it is too short, duplicate data packets get sent.

This is also known as the alternating-bit protocol.

There are four cases:

• No loss
• Lost packet
• Lost ACK
• Premature timeout (ACK received after timeout)

Pipelined Protocols

RDT 3.0 is a stop-and-wait-protocol, so the sender spends most of its time waiting rather than transmitting. If RTT is the round trip time, L is the packet size and R is the transmission rate, then the sender utilization is U_sender = (L/R) / (RTT + L/R) (add L/R on denominator as the entire packet must be received before the ACK can be sent).

Pipelining allows the sender to send multiple packets without waiting for an ACK to arrive. This requires the sequence number to occupy more than one bit, and forces the sender and receiver to buffer more than one packet. There are two basic approaches:

Go-Back-N Protocol

The sender can send multiple packets but can have no more than N unacknowledged packets in the pipeline.

These protocols are sometimes called sliding-window protocols: there is a window of size N that must contain all the unacknowledged packets.

Packets to the left of the window are acknowledged and packets to the left are not yet sent. Inside the window is unacknowledged packets or packets that can be sent immediately.

The window size is related to flow and congestion control.

The protocol uses cumulative acknowledgement: an ACK with sequence number n acknowledges all packets with sequence numbers <= n. If any unexpected packets arrive (e.g. out-of-order), they are discarded and an ACK with the most recently received valid packet is sent.

On timeout, all packets in the window are resent.

Performance problem: if the transmission rate is high, there will be a lot of unacknowledged packets, so if the first packet is corrupted, all the following packets will be discarded.

Sender events:

• The sender has data to send or it receives an ACK:
  • If there are less than N unacknowledged packets, send the next packet (and slide the window right)
• It reaches a timeout:
  • Resend all packets in the window

Receiver events:

• An invalid or unexpected (e.g. sequence number already received) packet arrives:
  • Send an ACK for the most recently received valid packet
• A good packet arrives:
  • Move the window right and send an ACK for that packet

In the quiz:

• Base: first sequence number in the window
• Next sequence number: sequence number for next packet to send
• Usable sequence numbers: sequence numbers for frames that can be sent immediately

Selective Repeat/Reject

The receiver individually acknowledges all correctly received packets, buffering packets as needed for in-order delivery to the higher layer.

The sender only resends the oldest packet for which the ACK is not received (timeout).

The receiver’s window can have:

• Expected packets, not yet received
• Buffered packets that arrived out of order
• Usable sequence numbers, not yet received

If a packet is re-received, this means the ACK for the packet was lost, and so the receiver should send an ACK for that packet again. If the packet was near the base of the window before the receiver sent the original ACK, this could mean that the receiver window is now ahead of the sender window.

The worst case scenario for window size is:

• All but the first packet in the window arrives. ACKs arrive
• First packet resent, ACK lost
• Receiver window moves forward by $N - 1$ sender does not move
  • Sender window is $[base, base + N - 1]$
  • Receiver window is $[base + N, base + 2N - 1]$
• Sender sends first packet again

To prevent this from being interpreted as a new packet, the sender base number must not be in the receiver window. Hence, the window size must be larger than $2N - 1$; in other words, the window size is at maximum half the sequence space.

Hidden assumption: the packets will NOT be reordered within the channel between the sender and receiver - this is reasonable for a single link, but could be broken in an multi-hop network.

If this assumption is broken, old copies of a packet with a sequence number not in either the sender or receiver’s window can arrive. One solution is to have a live time for every packet to ensure it will not stay in the network for very long - ideally, the sequence space will be large enough that it is impossible to fully cycle through the sequence numbers within this time. Note that the receiver will ignore these packets regardless.