Go-Back-N ARQ

Go-Back-N ARQ (Automatic Repeat reQuest) is a specific type of sliding window protocol used in data communication. It is a more efficient protocol compared to Stop-and-Wait ARQ, as it allows the sender to transmit multiple frames before receiving an acknowledgment, thereby improving channel utilization.

What is Go-Back-N ARQ?

Go-Back-N 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. If an error is detected in a frame, the receiver discards that frame and all subsequent frames, even if they are received correctly. The sender must then "go back" to the frame where the error was detected and retransmit it along with all subsequent frames.

How Go-Back-N ARQ Works

The operation of Go-Back-N 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 slides the window forward, allowing new frames to be transmitted.

5. Timeout: If the sender does not receive an acknowledgment for a frame within a specified timeout period, it retransmits all unacknowledged frames, starting from the oldest unacknowledged frame.

Receiver's Perspective

1. In-Order Delivery: The receiver expects to receive frames in order, starting from a specific sequence number.

2. Acknowledgment: If a frame is received correctly and in order, the receiver sends an acknowledgment (ACK) for the next expected frame.

3. Error Handling: If a frame is received with errors or out of order, the receiver discards it and all subsequent frames, even if they are received correctly. It continues to send an ACK for the last correctly received frame.

Sequence Numbers in Go-Back-N ARQ

In Go-Back-N 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.

No of bits = ⌈log2(N + 1)⌉

However, in practice, the number of bits used is often larger to allow for a larger range of sequence numbers.

Example Scenario

Let's walk through an example to understand how Go-Back-N 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 ACK 4, indicating it has received all frames up to 3 and expects frame 4 next.
5. Sender receives ACK 4, 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.
4. Receiver discards frame 1 and all subsequent frames (2 and 3), even if they are received correctly.
5. Receiver sends ACK 1, indicating it has received frame 0 correctly and expects frame 1 next.
6. Sender receives ACK 1, slides the window to start from frame 1, and retransmits frames 1, 2, and 3.

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 ACK 4, but the acknowledgment is lost in transit.
5. Sender's timer for frame 0 expires, so it retransmits frames 0, 1, 2, and 3.
6. Receiver receives the duplicate frames, recognizes them as duplicates (because it's expecting frame 4), and discards them.
7. Receiver sends ACK 4 again.
8. Sender receives ACK 4, slides the window forward, and can now transmit frames 4, 5, 6, and 7.

Important Parameters in Go-Back-N 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 the sender.

2. Timeout Period

The timeout period is the maximum time the sender waits for an acknowledgment before retransmitting frames. 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 the window size and prevent ambiguity in identifying frames.

Efficiency of Go-Back-N ARQ

The efficiency of Go-Back-N 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.

However, in the presence of errors, the efficiency decreases because the sender must retransmit multiple frames when an error occurs. The efficiency in this case depends on the error rate and the window size.

Advantages of Go-Back-N ARQ

1. Improved Efficiency: Go-Back-N ARQ is more efficient than Stop-and-Wait ARQ, especially over long-distance networks or high-bandwidth channels, because it allows multiple frames to be in transit simultaneously.

2. Simple Receiver: The receiver in Go-Back-N ARQ is relatively simple, as it only needs to keep track of the next expected frame and does not need to buffer out-of-order frames.

3. In-Order Delivery: Go-Back-N ARQ guarantees in-order delivery of frames to the higher layers, which simplifies the design of higher-layer protocols.

Disadvantages of Go-Back-N ARQ

1. Wasted Bandwidth on Errors: When an error occurs, all frames from the error onwards must be retransmitted, even if they were received correctly. This can waste bandwidth, especially in high-error environments.

2. Limited by Window Size: The efficiency of Go-Back-N ARQ is limited by the window size. If the window size is too small, the protocol may not fully utilize the available bandwidth.

3. Requires Larger Buffer at Sender: The sender must buffer all unacknowledged frames, which requires more memory compared to Stop-and-Wait ARQ.

Applications of Go-Back-N ARQ

Go-Back-N ARQ is used in various applications:

1. Data Link Layer Protocols: Many data link layer protocols, such as HDLC (High-Level Data Link Control), use Go-Back-N ARQ for error control.

2. Transport Layer Protocols: Some transport layer protocols, such as early versions of TCP (Transmission Control Protocol), used Go-Back-N ARQ for reliable data transfer.

3. Satellite Communications: Go-Back-N ARQ is used in satellite communications, where the propagation delay is significant.

4. Wireless Networks: Go-Back-N ARQ is used in some wireless networks, although Selective Repeat ARQ is often preferred due to its better handling of errors.

Comparison with Other ARQ Protocols

Go-Back-N ARQ vs. Stop-and-Wait ARQ

Go-Back-N ARQ vs. Selective Repeat ARQ

Conclusion

Go-Back-N ARQ is a sliding window protocol that improves upon Stop-and-Wait ARQ by allowing multiple frames to be in transit simultaneously. It provides a good balance between efficiency and complexity, making it suitable for various applications in data communication.

While it has limitations, particularly in high-error environments where it may waste bandwidth by retransmitting correctly received frames, it remains an important protocol in the field of data communication and serves as a foundation for more advanced protocols like Selective Repeat ARQ.

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