Go-Back-N ARQ Protocol

Go-Back-N (GBN) ARQ Protocol allows the sender to send multiple frames before receiving individual acknowledgments. It is a flow control protocol used in the data link layer to achieve reliable and efficient data transmission between a sender and a receiver over a noisy channel.

Sender Window Size and Sequence Numbers

Go-Back-N ARQ is a sliding window protocol. It allows multiple frames to be sent by the sender at a time. Let’s look at the sender’s window size and how they are numbered:

In Go-Back-N ARQ, ‘N’ stands for the sender window size. Sender window size simply means how many frames can be sent at a time by the sender. So in case of Go-Back-3, the sender window size is 3. This means that the sender can send 3 frames at a time.

The sender window size is always less than 2^m ,where m is the number of bits that can be used to represent the frame numbers.

$Window Size(N) < 2^m$

Let’s take an example, suppose m = 3 and we have to transmit 20 frames. This means we have 3 bits available to number our frames. This is how these 3 bits can represent the frames:

Bit Representation	Frame Number
000	0
001	1
010	2
011	3
100	4
101	5
110	6
111	7

3 Bits can represent sequence numbers 0-7. These sequence numbers are then wrapped to represent all the frames. In this case, 20 frames would be numbered like this

Frame Serial Number:	20	19	18	17	16	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1
Frame Seq Number:	3	2	1	0	7	6	5	4	3	2	1	0	7	6	5	4	3	2	1	0

The sender window size is always less than 2^m. ‘m’ is 3, so the maximum window size in this case would be 7. This can thus be called an example of Go-Back-7.

$Maximum Window Size(N) = 2^3 -1 = 7$

The Sender Window

The sender window in the Go-Back-N Protocol can be broadly divided into 3 major regions:

The first region is that of the frames that have already been sent and acknowledged by the receiver.

The second is the window. These frames are currently being sent.

The third region consists of the frames waiting to be sent.

In this example, we have a sender window with a window size of 3 and m =2. We can see the three regions in this sender window

Go-Back-N Sender Window — Fig 1( Sender Window )

The Receiver Window

In Go-Back-N, the size of the receiver side sliding window is 1. Also the receiver only accepts frames sequentially. It can’t accept out of order frames. This means if it accepted a frame with a sequence number 0, then it would wait for the frame numbered 1.

Working of Go-Back-N ARQ Protocol

Now let’s go back to our sender window(Fig 1) example. The current window is at frames numbered 1, 2 and 3.

This means the sender would send these frames to the receiver and start the timer. Ideally all these three frames should reach the receiver sequentially. The receiver should accept them and send their acknowledgement to the sender.

Let’s look at frame 1. In the first situation, let us assume that the Frame 1 is successfully transmitted to the receiver

If sender receives acknowledgement for frame numbered 1

The sender window would slide and the sender would send a new frame. In this case, frame numbered 0.

If Sender Receives acknowledgement for frame 1

If sender doesn‘t receives acknowledgement for frame numbered 1

This situation can arrive due to either of these two cases:

CASE 1:

The frame reaches the receiver. The receiver sends the acknowledgement. This acknowledgement gets lost in transmission.

In our example, let’s assume frame 1 is received by the receiver and it’s acknowledgment is sent. This is lost in transmission. Now, the receiver will receive frame 2 and 3 and send their acknowlegdements. If the acknowledgements of frame 2 and 3 reach the sender successfullly, the sender would assume that the receiver has also received frame 1. This concept is known as cumulative acknowledgement.

CASE 2:

The frame doesn’t reaches the receiver.

In our example, let’s assume frame 1 is lost in transmission and doesn’t reach the receiver. The frames 2 and 3 reach the receiver. But receiver has a window size of 1. It only accepts frames sequentially and does not accept out of order frames. So, the receiver would continue to wait for frame 1.

The sender would keep waiting till it’s timeout period expires. After the timeout period expires the sender would transmit all 3 frames (in this case, frame 1,2 and 3) in the window once again.

Characteristics of the Go-Back-N ARQ Protocol:

Go-Back-N is a sliding window protocol used to transmit data over noisy channels.

The receiver in the Go-Back-N protocol sends cumulative acknowledgments, indicating the next expected sequence number. This simplifies the acknowledgment process and reduces the overhead of individually acknowledging each frame.

Automatic Retransmission: When the sender detects a timeout it automatically retransmits all the unacknowledged frames within the window, ensuring reliable delivery of data.

Sender Window Size(N)

Sender window size is calculated as :

$Maximum Window Size(N) = 2^m -1$

m is the number of bits that can be used to represent the frame numbers.

Round-Trip Time (RTT):

This is the total time taken for a frame to be transmitted, acknowledged, and the ACK received by the sender. RTT depends on the transmission time (Tt) and propagation time (Tp).

$RTT= Tt + Tp$

Efficiency:

Efficiency (η) measures the utilization of the communication channel.

$Efficiency= (N * Tt) / RTT$

Where Tt is the Transmission time, Rtt is the Round Trip Time and N is the Window Size.

Maximum Retransmissions:

The maximum number of retransmissions allowed in the Go-Back-N ARQ protocol determines the limit for retransmitting frames in case of failures.

$Maximum Retransmissions = (N - 1)$

Here, ‘N’ represents the total frames sent.

Advantages of the Go-Back-N ARQ Protocol

Increased Efficiency

The Go-Back-N protocol allows for pipelining, which means multiple frames can be transmitted before waiting for acknowledgments. This improves overall efficiency and throughput in the network.

Automatic Retransmission

In case of lost or corrupted frames, the Go-Back-N protocol automatically triggers retransmission of all unacknowledged frames within the sender’s window. This ensures reliable data delivery without the need for complex error recovery mechanisms.

Simple Implementation

The Go-Back-N protocol is relatively simple to implement compared to other error control protocols. It requires minimal buffering and processing at the receiver, making it suitable for resource-constrained devices.

Minimal Receiver Complexity

The receiver in the Go-Back-N protocol only needs to process in-order frames and discard out-of-order or duplicate frames. This simplifies the receiver’s operation and reduces the processing overhead.

Limitations of the Go-Back-N ARQ Protocol

Increased Latency

The Go-Back-N protocol causes latency in the network due to the sender’s need to wait for acknowledgments before sliding the window and sending new frames. This latency is especially significant in high-delay networks.

Limited Receiver Buffering

The receiver in the Go-Back-N protocol typically has a limited buffer to hold out-of-order frames. If the buffer fills up, subsequent out-of-order frames may be discarded. This may lead to data loss.

Wasted Bandwidth

In case of high error rate or congestion, the Go-Back-N protocol may result in wasted bandwidth.

In summary we can say that the Go-Back-N protocol offers improved efficiency compared to the stop-and-wait protocol by allowing the sender to transmit multiple frames before waiting for acknowledgments. However, it can still suffer from inefficiencies and increased latency when errors or losses occur frequently, leading to retransmissions of large portions of the data.