Selective Repeat ARQ

Selective Repeat ARQ (Automatic Repeat reQuest) is an advanced sliding window protocol used in data communication. It addresses the inefficiency of Go-Back-N ARQ by allowing the receiver to accept and buffer frames received out of order, and by having the sender retransmit only the frames that are actually lost or corrupted.

What is Selective Repeat ARQ?

Selective Repeat ARQ is a protocol where the sender can transmit multiple frames before receiving an acknowledgment, up to a maximum number of unacknowledged frames, known as the window size. Unlike Go-Back-N ARQ, if an error is detected in a frame, the receiver does not discard subsequent frames. Instead, it buffers correctly received frames and requests retransmission only for the frames that are lost or corrupted.

How Selective Repeat ARQ Works

The operation of Selective Repeat ARQ can be described as follows:

Sender's Perspective

1. Window Size: The sender maintains a window of up to N frames that can be transmitted without receiving an acknowledgment.

2. Sequence Numbers: Each frame is assigned a sequence number, which helps in identifying frames and their corresponding acknowledgments.

3. Transmission: The sender can transmit frames as long as the number of unacknowledged frames is less than the window size.

4. Acknowledgment: When the sender receives an acknowledgment for a frame, it marks that frame as acknowledged. If the acknowledged frame is the oldest unacknowledged frame, the sender slides the window forward.

5. Negative Acknowledgment (NAK): If the sender receives a negative acknowledgment (NAK) for a frame, it retransmits only that specific frame.

6. Timeout: If the sender does not receive an acknowledgment for a frame within a specified timeout period, it retransmits only that specific frame.

Receiver's Perspective

1. Window Size: The receiver also maintains a window of up to N frames that it expects to receive.

2. Buffering: The receiver can accept and buffer frames that are received out of order, as long as they fall within its window.

3. Acknowledgment: For each correctly received frame, the receiver sends an acknowledgment (ACK) for that specific frame.

4. Negative Acknowledgment: If the receiver detects an error in a frame, it sends a negative acknowledgment (NAK) for that specific frame.

5. In-Order Delivery: The receiver delivers frames to the higher layer in order, which may require reordering of the buffered frames.

Sequence Numbers in Selective Repeat ARQ

In Selective Repeat ARQ, sequence numbers are used to identify frames and their corresponding acknowledgments. The sequence numbers are typically represented using a fixed number of bits, which limits the range of sequence numbers.

For a window size of N, the minimum number of bits required for sequence numbers is:

Number of bits = ⌈log₂(2N)⌉

This is because the sender and receiver windows can be at different positions in the sequence number space, and we need to ensure that there is no ambiguity in identifying frames.

Example Scenario

Let's walk through an example to understand how Selective Repeat ARQ works:

Successful Transmission

1. Sender has a window size of 4 and frames 0, 1, 2, and 3 to send.
2. Sender transmits frames 0, 1, 2, and 3.
3. Receiver receives frames 0, 1, 2, and 3 correctly and in order.
4. Receiver sends ACKs for frames 0, 1, 2, and 3.
5. Sender receives ACKs for frames 0, 1, 2, and 3, slides the window forward, and can now transmit frames 4, 5, 6, and 7.

Error in Transmission

1. Sender has a window size of 4 and frames 0, 1, 2, and 3 to send.
2. Sender transmits frames 0, 1, 2, and 3.
3. Receiver receives frame 0 correctly, but frame 1 is corrupted. Frames 2 and 3 are received correctly.
4. Receiver sends an ACK for frame 0, a NAK for frame 1, and ACKs for frames 2 and 3.
5. Receiver buffers frames 2 and 3, as they are received correctly but out of order.
6. Sender receives the ACK for frame 0, the NAK for frame 1, and the ACKs for frames 2 and 3.
7. Sender retransmits only frame 1.
8. Receiver receives frame 1 correctly, sends an ACK for frame 1, and can now deliver frames 0, 1, 2, and 3 in order to the higher layer.

Lost Acknowledgment

1. Sender has a window size of 4 and frames 0, 1, 2, and 3 to send.
2. Sender transmits frames 0, 1, 2, and 3.
3. Receiver receives frames 0, 1, 2, and 3 correctly and in order.
4. Receiver sends ACKs for frames 0, 1, 2, and 3, but the ACK for frame 1 is lost in transit.
5. Sender receives ACKs for frames 0, 2, and 3, but not for frame 1.
6. Sender's timer for frame 1 expires, so it retransmits only frame 1.
7. Receiver receives the duplicate frame 1, recognizes it as a duplicate, and sends an ACK for frame 1 again.
8. Sender receives the ACK for frame 1, and now all frames 0, 1, 2, and 3 are acknowledged.

Important Parameters in Selective Repeat ARQ

1. Window Size (N)

The window size determines the maximum number of frames that can be transmitted without receiving an acknowledgment. A larger window size can improve channel utilization, especially over long-distance networks or high-bandwidth channels, but it also requires more buffer space at both the sender and the receiver.

2. Timeout Period

The timeout period is the maximum time the sender waits for an acknowledgment before retransmitting a frame. It should be set to at least the round-trip time (RTT), which is the time it takes for a frame to reach the receiver plus the time it takes for an acknowledgment to return to the sender.

3. Sequence Number Size

The sequence number size determines the range of sequence numbers that can be used. It should be large enough to accommodate twice the window size to prevent ambiguity in identifying frames.

Efficiency of Selective Repeat ARQ

The efficiency of Selective Repeat ARQ depends on several factors, including the window size, the probability of errors, and the propagation delay.

Under ideal conditions (no errors), the efficiency can be calculated as:

Efficiency = N / (1 + 2a)

Where:

• N is the window size
• a is the ratio of propagation time to transmission time

As N approaches infinity, the efficiency approaches 1, which means that the channel is fully utilized.

In the presence of errors, Selective Repeat ARQ is more efficient than Go-Back-N ARQ because it only retransmits the frames that are actually lost or corrupted, rather than all frames from the error onwards.

Advantages of Selective Repeat ARQ

1. Improved Efficiency: Selective Repeat ARQ is more efficient than Go-Back-N ARQ, especially in high-error environments, because it only retransmits the frames that are actually lost or corrupted.

2. Better Bandwidth Utilization: By allowing the receiver to accept and buffer frames received out of order, Selective Repeat ARQ makes better use of the available bandwidth.

3. Reduced Retransmission Overhead: The selective retransmission of only the lost or corrupted frames reduces the overhead associated with retransmissions.

Disadvantages of Selective Repeat ARQ

1. Complex Receiver: The receiver in Selective Repeat ARQ is more complex than in Go-Back-N ARQ, as it needs to buffer out-of-order frames and potentially reorder them before delivery to the higher layer.

2. Larger Buffer Requirements: Both the sender and the receiver need to buffer frames, which requires more memory compared to Go-Back-N ARQ.

3. Sequence Number Limitations: The sequence number space must be at least twice the window size to prevent ambiguity, which can be a limitation in some implementations.

Applications of Selective Repeat ARQ

Selective Repeat ARQ is used in various applications:

1. Data Link Layer Protocols: Some advanced data link layer protocols use Selective Repeat ARQ for error control.

2. Transport Layer Protocols: Modern transport layer protocols, such as TCP (Transmission Control Protocol), use variants of Selective Repeat ARQ for reliable data transfer.

3. Satellite Communications: Selective Repeat ARQ is particularly useful in satellite communications, where the propagation delay is significant and retransmitting all frames from an error onwards (as in Go-Back-N ARQ) would be inefficient.

4. Wireless Networks: Selective Repeat ARQ is often used in wireless networks, where the error rate can be high and retransmitting only the lost or corrupted frames is more efficient.

Comparison with Other ARQ Protocols

Selective Repeat ARQ vs. Stop-and-Wait ARQ

Selective Repeat ARQ vs. Go-Back-N ARQ

Conclusion

Selective Repeat ARQ is an advanced sliding window protocol that improves upon Go-Back-N ARQ by allowing the receiver to accept and buffer frames received out of order, and by having the sender retransmit only the frames that are actually lost or corrupted. This makes it more efficient, especially in high-error environments, but also more complex and requiring more buffer space.

While it has some limitations, particularly in terms of complexity and buffer requirements, Selective Repeat ARQ is widely used in modern data communication systems, especially in environments where the error rate is high or the propagation delay is significant.

Understanding Selective Repeat ARQ is essential for anyone working in the field of data communication, as it provides insights into the trade-offs involved in designing reliable and efficient data transfer protocols.