Selective Repeat ARQ

There are many challenges in data transmission and unreliable channels, error correction and reliable delivery are crucial concerns for professionals in my domain. According to me and many other individuals in my field, the Selective Repeat ARQ (Automatic Repeat Request) protocol stands out as an efficient solution.

How? It gracefully addresses these challenges while offering significant advantages over simpler protocols like Stop-and-Wait ARQ.

I will dive deep into the Selective Repeat ARQ protocol in this tutorial and we will explore its implementation details. I will also highlight the benefits it brings to the world of computer networks and discuss some real-world applications.

Why Selective Repeat ARQ?

I've been working with network protocols for years, and I can confidently say that Selective Repeat ARQ is a game-changer when reliability is non-negotiable. Its ability to handle lost or corrupted packets efficiently while optimizing data flow is what makes it stand out from the crowd.

Imagine you're sending an important document over a spotty internet connection. Packets of data get lost like stray puzzle pieces, preventing you from reconstructing the whole picture.  That's where error correction protocols and reliable data delivery come into play. The Selective Repeat ARQ protocol is one of the most efficient solutions to this problem, ensuring your document arrives intact, no matter what disruptions occur during transmission.

How Does Selective Repeat ARQ Work?

I've always found that breaking down complex protocols into their core concepts makes them much easier to grasp. Here's a breakdown of how Selective Repeat ARQ works:

• Sliding window: Both the sender and receiver use sliding windows to manage data flow. The sender's window limits how many unacknowledged packets can be "in flight" at once. The receiver's window indicates which packets it's prepared to accept, even if some arrive out of order.
• Individual Acknowledgments (ACKs): Unlike some simpler protocols, Selective Repeat ARQ sends individual acknowledgments for each correctly received packet. This pinpoints lost or corrupted packets, ensuring that only the missing data needs to be retransmitted.
• Negative Acknowledgments (NAKs): When a packet goes missing, the receiver sends an NAK to signal the error. Think of this as a faster alternative to waiting for a timeout, the receiver proactively asks for the missing piece.
• Out-of-order handling: Selective Repeat ARQ's receiver window allows it to buffer packets that arrive out of order. This prevents unnecessary retransmissions and ensures data is delivered in the correct sequence.
• Timeout-based retransmissions: The sender maintains a timer for each unacknowledged packet. If a timeout occurs, it assumes the packet was lost and retransmits it. Timeouts serve as a safety net when ACKs or NAKs might also get lost in the channel.

Selective Repeat ARQ in Action: A Step-by-Step Example

Consider a scenario where the sender has a window size of 4:

1. Transmission: The sender transmits packets 0, 1, 2, and 3.
2. Loss: Let's say packet 2 is lost in transit.
3. Reception: The receiver gets packets 0, 1, and 3. It buffers packet 3 while sending:

• ACKs for packets 0 and 1
• A NAK for packet 2

4. Retransmission: Upon receiving the NAK, the sender retransmits only packet 2.
5. Timeout: As an alternative, if the sender's timer for packet 2 expires, it will retransmit packet 2 without needing the NAK.
6. Delivery: Once all packets are received in order, the receiver delivers them to the upper layer.

Expert Tip: The optimal Selective Repeat ARQ window size is a careful balance between throughput and buffer requirements. Larger windows can increase potential throughput (think: sending more packets at once), but this also requires more space to store packets at the receiver.

You can enroll in the Master of Science in Computer Science program (with cybersecurity specialization) by upGrad and Liverpool John Moores University to learn all about network security and network engineering.

Selective Repeat ARQ vs. Other Protocols

Here are the differences between Selective Repeat ARQ against other ARQ protocols and some other modern approaches:

Stop-and-Wait ARQ

In Stop-and-Wait, the sender must pause after transmitting each packet and wait for an ACK before sending the next one. While simple, this leads to significant idle time on channels with long delays, making Selective Repeat ARQ's pipelining approach much more efficient.

Go-Back-N ARQ

While Go-Back-N improves on Stop-and-Wait by allowing multiple packets in flight, it suffers when individual packets are lost. In this case, all packets from the lost one onward need to be retransmitted, even if some were received correctly. This is where Selective Repeat ARQ's individual ACKs make a substantial difference.

Fountain Codes

In extremely unreliable channels with high packet loss rates, traditional ARQ protocols like Selective Repeat can struggle due to a barrage of retransmission requests. Each lost segment triggers more transmissions, potentially congesting the network further.

Fountain codes take a radically different approach. The sender continuously generates a stream of encoded packets from the original data. The goal is for the receiver to collect enough distinct droplets to reconstruct the original data.

Hybrid ARQ

Hybrid ARQ schemes strategically merge traditional ARQ with Forward Error Correction (FEC). FEC adds redundant information to the data, calculated in a way that allows the receiver to proactively correct a limited number of errors within a block of data, even without retransmissions.

ARQ is still used when the number of errors exceeds the FEC's capability. However, the FEC reduces the reliance on retransmissions. Hybrid ARQ systems can be tuned based on channel conditions. If the channel is relatively good, favor FEC for quick recovery. If the channel degrades, rely more heavily on ARQ's retransmission mechanism.

Network Coding

In traditional networks, intermediate nodes (like routers) simply forward packets along. With network coding, these nodes can intelligently mix and re-encode packets they receive before forwarding them. If one path between sender and receiver is disrupted, innovative combinations along other paths can still potentially deliver the information.

Network coding can sometimes maximize the use of network capacity in complex multi-path scenarios. However, network coding brings added complexity to routing and decoding processes. Its benefits are most pronounced in specific network scenarios.

Advantages of Selective Repeat ARQ

Here are the benefits of using the Selective Repeat protocol:

• Optimized throughput: Especially on channels with higher latency (the time it takes for data to travel between points), the ability to send multiple packets without waiting for individual ACKs significantly improves throughput compared to protocols like Stop-and-Wait.
• Reduced retransmissions: Pinpointing exactly which packets need to be retransmitted reduces unnecessary network traffic and improves overall efficiency. This is especially valuable when error rates are relatively low, but individual errors still need swift correction.
• Robustness in noisy environments: Selective Repeat ARQ's ability to handle out-of-order delivery and buffer packets makes it highly adaptable to environments with fluctuating channel conditions.

Real-World Applications of Selective Repeat ARQ

Here are some real-world Selective Repeat ARQ examples and use cases of the Selective Repeat ARQ protocol:

1. Selective Repeat ARQ in TCP: TCP uses a modified version of Selective Repeat ARQ that includes:

• Cumulative ACKs: For efficiency, ACKs acknowledge the last correctly received byte, not just individual packets.
• SACKs (Selective ACKs): Allow the receiver to signal out-of-order, but correctly received segments.
• Congestion control: Incorporates mechanisms like slow start and congestion avoidance to adapt its sending rate to network conditions. This is crucial to prevent Selective Repeat ARQ's retransmissions from making congestion worse.

2. Satellite communications: Selective Repeat ARQ is particularly well-suited for satellite links due to:

• Long propagation delays: Its ability to pipeline multiple packets without stalling after each transmission is essential to maximize throughput given the high round-trip times (RTT).
• Potential error bursts: Satellite links can experience fading and temporary interference, leading to bursts of packet losses. Selective Repeat ARQ's targeted retransmissions efficiently handle these bursts.

3. Wireless protocols: Selective Repeat ARQ is integrated into wireless protocols to ensure reliable data transmission over error-prone wireless channels such as LTE and WiFi:

• Cellular Networks (LTE, 5G): The Selective Repeat protocol operates within the Radio Access Network (RAN), responsible for the link between the user equipment (your phone) and the base station. 
• WiFi: Modern WiFi standards (802.11n and onwards) already implement a basic form of ARQ at the link layer (between your device and the WiFi access point). Selective Repeat ARQ could be layered on top of this if end-to-end reliability is required over multiple WiFi hops or across the wider internet.

Mathematical Analysis of Selective Repeat ARQ

Let's introduce some mathematical models to quantify Selective Repeat ARQ performance:

Throughput Model

Under some simplifying assumptions, we can derive a closed-form expression for the throughput of Selective Repeat ARQ. Let's define the following variables:

W: Window size

RTT: Round-trip time

BER: Bit Error Rate

T: The time it takes to transmit the payload of a single packet and receive the ACK (depends on packet size and data rate)

A simplified formula for throughput (bits per second) might look like this:

Throughput = (W / (RTT + W * T * BER)) * Payload Size

Assumptions

This model assumes:

• Errors in ACK packets are negligible.
• Every packet loss results in a timeout (no fast retransmits for simplicity).

Example Plot

Using this formula, we can plot throughput vs. window size for different BER values. Typical graphs would demonstrate:

• Increasing throughput: Initially, throughput increases as the window size grows.
• Plateau: Eventually, throughput reaches a plateau as retransmissions due to errors start to dominate (higher BER leads to a plateau at a lower window size).

Implementation notes: These plots help visualize how protocol parameters should be tuned based on channel conditions. For example:

• Channels with low BER can benefit from larger window sizes.
• High-latency channels need careful consideration, i.e., a large window size might inflate the RTT term too much.

Wrapping Up

Selective Repeat ARQ's core concepts are robust, but successful implementations require fine-tuning the parameters to match the specific characteristics of the communications channel. In complex network stacks, Selective Repeat ARQ often interacts with other error correction and retransmission mechanisms at different layers. Proper coordination is crucial in creating a reliable end-to-end solution.

You can check out upGrad’s Advanced Certificate Program in Cyber Security to learn everything about network security, network engineering, etc. as well as acquire all the skills needed to become a cyber security expert. 

Frequently Asked Questions

What is the selective rejection of ARQ in error control?

Selective Reject ARQ is a variation where the receiver only requests retransmission of the specific packet(s) that were received with errors, instead of retransmitting a whole group of packets.

What is the efficiency of Selective Repeat ARQ?

Selective Repeat ARQ is generally more efficient than Stop-and-Wait or Go-Back-N ARQ, especially on channels with long delays or where error rates are relatively low but not negligible.

How do you calculate window size in Selective Repeat ARQ?

The ideal window size in Selective Repeat ARQ depends on channel characteristics like round-trip time (RTT), bit error rate (BER), and bandwidth. There's no single formula, but simulations or simplified throughput models can help determine a suitable range.

What is Selective Repeat ARQ data flow control?

Selective Repeat ARQ's sliding windows inherently provide flow control, preventing the sender from overwhelming the receiver and adapting the sending rate indirectly based on acknowledgments or timeouts.

What is the formula for selective repeat utilization?

Utilization refers to the percentage of time the channel is used for transmitting useful data. A basic formula for Selective Repeat ARQ's utilization would be:

• Utilization = (Payload size * Window size) / (Round Trip Time + (Window size * Transmission Time * BER))

What protocols are FEC and ARQ?

FEC (Forward Error Correction) and ARQ (Automatic Repeat Request) are not single protocols but error control strategies. Protocols like TCP or those used in cellular networks often combine them as Hybrid ARQ.

What are the three types of ARQ techniques?

The three main types of ARQ techniques are:

• Stop-and-Wait ARQ
• Go-Back-N ARQ
• Selective Repeat ARQ

What are the advantages of Selective Repeat ARQ?

1. Efficiency: Reduces unnecessary retransmissions compared to simpler ARQ protocols.
2. Out-of-order handling: Ensures smooth data delivery even if packets arrive out of order.
3. Throughput: Often provides better throughput than Stop-and-Wait, especially on high-latency channels.

What is the disadvantage of Selective Repeat ARQ?

Selective Repeat ARQ is slightly more complex to implement than Stop-and-Wait ARQ, as both sender and receiver need to manage buffers for out-of-order packets.

What is the maximum window size in selective repeat?

Theoretically, there's no hard limit, but the sequence number field size dictates the maximum. Practically, the window size is tuned based on channel conditions to avoid excessive buffering requirements.