Go-Back-N Protocol ARQ

Go-back N ARQ (Automatic Repeat Request)protocol is a practical implementation of the sliding window protocol. Well, there are two practical implementations of sliding window protocol, go-back-n and selective repeat. But in this section, we will be concentrating on the go-back-n protocol.

Content: Go-Back-N Protocol

1. Introduction
2. Go-Back-N Definition
3. Working with Example

Introduction

Go-back-n was introduced because the ‘stop-and-wait protocol’ was not that efficient as the sender can send only one packet at a time and has to wait to transmit the next frame until the previous frame is acknowledged. In this way, the stop-and-wait protocol wastes the channel bandwidth and even increase the round trip delay.

This is because the stop-and-wait protocol does not use the concept of pipelining. Pipelining is a general concept where the processing of the next task starts before the ending of the previous task. In networking, the concept of pipelining specify that the source can send multiple frames before receiving the acknowledgement for the first transmitted frame.

Go-Back-N ARQ Definition

Go-back-n ARQ protocol is a sliding window protocol that uses the concept of pipelining. In go-back-n, the ‘N” determines the size of the sender window. The value of N defines the number of frames that can be sent while the sender is waiting for the acknowledgement. The value of N is always greater than 1 else it would behave in a stop-and-wait manner.

The frames at the sender side are numbered sequentially. In go-back-n, the sender can buffer N frames whereas the size of the receiver window is 1 which means the receiver can buffer only one frame at a time. However, there can be multiple data frames and acknowledgement in the channel at the same time and the sliding sender window can also slide by one or more frames at once.

If the sender does not receive an acknowledgement before the corresponding timer expires the sender retransmit all the frames in the current sender window. While if the receiver receives a corrupted frame it silently discards that frame without taking any action this results in the expiration of the corresponding timer at the sender side which lead to retransmission of frames in the current sender window. That’s why it is referred to as an automatic repeat request.

Working and Example of Go-Back-N

Let us understand the working of go-back-n with the help of an example. Consider that the sender has 16 frames to transmit. The first thing is to provide a sequence number to the frame so that each frame has an independent identity.

Sequencing

The frames to be transmitted are numbered using modulo 2^m. Where m is the number of bits allowed by the frame header to represent the sequence number of a frame. Now if the sender has 16 frames to be transmitted which if number serially would lie from 0, 1, 2 …, 15.

Consider that the header allows only 3 bits to represent the sequence number of the frame i.e. m= 3. The sequence number would range from 0 to 2³-1 i.e. from 0 to 7. So the 16 frames at the sender side are numbered as 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7 and so on.

Sender Sliding Window

For the proper working of the protocol, the maximum size of the sliding window in go-back-n must be 2^m – 1. As in the explanation above we have m=3 the maximum size of the window would be 2² – 1= 7.

Now, the entire sender’s window can be classified into four regions. The very first region of the sender window has the sequence numbers of frames that are acknowledged and the sender can purge these frames. The sequence number of frames in the second region are those frames that are sent but not yet acknowledged by the receiver. These are also called outstanding packets. The third region is the sequence of frame numbers that can be sent once the frames with the sequence number in the second region are acknowledged. The fourth region has sequence numbers that can be used when the window slides.

Depending on the number of acknowledgements arrived the sliding window can slide one or more slots toward the right. Consider that the sender has received acknowledgement for frame with sequence number 4 then it will slide only one slot towards the right.

If the sender receives two acknowledgements for the frame with sequence numbers 4 and 5 then it will slide two slots towards the right.

Receiver Sliding Window

In go-back-n, the size of the receiver side sliding window is 1 which limits the receiver to look for the arrival of a specific packet. The receiver in go-back-n accepts the packets sequentially. If it receives any packet out of order then it discards those packets which are later retransmitted by the sender.

The receiver window can be categorized into three regions. The first region to the left has the sequence number of the frames that are received and even acknowledged. The second region has a sequence number of only one frame that the receiver is expecting to arrive. The third region has a sequence of frames that cannot be accepted.

Now let us understand the working of go-back-n step by step with the help of the figure below.

The sender sends frames 0, 1, 2, 3 while waiting for the acknowledgement of the first outstanding packet i.e. 0. However, the sender sliding window covers the sequence number of the frames from 0 to 6 as the sliding window size here is 7.

The frames with sequence numbers 0, 1, 2, and 3 are the outstanding packet means these frames are sent and the sender is waiting for the acknowledgement whereas the data for frames 4, 5, and 6 is yet to come from the sender’s application layer.

Meanwhile, the sender receives an acknowledgement for frame 0, the senders sliding window slides by 1 slot to right covering sequence number 7. Even the data for frames with sequences 4 and 5 is received from the sender’s application layer. And the sender sends a frame with sequence numbers 4 and 5.

After sending packet 5 the sender receives the acknowledgement for packets 1 and 2 which makes the sender sliding window shift by two slots covering sequence numbers 0 and 1.

However, in the meantime, the timer for acknowledgement of packet 3 expires. The reason may be that packet 3 may have arrived at the receiver but with an error or the packet may have lost or may its acknowledgement may have lost.

When the timer for acknowledgement of packet 3 expires the sender has to go back and resend all the outstanding packets i.e. packets 3, 4, and 5.

So this is how the go-back-n protocol controls error and flow of the data packets from sender to receiver. Though the go-back-n protocol is still inefficient as for one loosed packet the sender has to retransmit all the outstanding packets wasting the bandwidth of the channel.