Selective repeat protocol is a sliding window protocol that uses the concept of pipelining where multiple packets can be sent while the sender is waiting for the acknowledgement for the first sent packet. The selective repeat protocol manages error and flows control between the sender and receiver.
In this section, we will discuss the need for selective repeat ARQ (Automatic Repeat Request) and how it overcomes the shortcomings of the go-back-n protocol. We will also discuss the working of selective repeat with the help of an example.
Why Selective Repeat ARQ?
The go-back-n protocol that we have studied in our previous content is efficient if the error rate and loss of packets is less. If the connection is poor, there will be frequent loss of packets and the sender would have to retransmit all the outstanding packets. This wastes the bandwidth of the channel.
In go-back-n, the size of the receiver window is 1 so it buffers only one packet in order that it has to acknowledge next and if this expected packet is lost or corrupted all the received out of order packets are discarded. And the sender has to retransmit all the outstanding packets though some of these may have arrived at the receiver safely but out of order.
This retransmission of packets increases the traffic on the network creating a cumulative increase in congestion. The alternative approach for this is selective repeat protocol. In the section ahead we will discuss the working of this selective repeat protocol.
Working of Selective Repeat Protocol
Like go-back-n, selective repeat protocol is also a sliding window protocol. Unlike the go-back-n protocol, the selective repeat protocol resends only a selective packet that is either lost or corrupted. Let us first discuss the windows in selective repeat.
In selective repeat, both sender and receiver have a sliding window. On the sender side, the window covers the sequence of packets that are either sent or can be sent. At the receiver, the sliding window covers the sequence number of the packets that are either received or are expected to be received. In selective repeat, the size of the sender and receiver window is the same. Let us study the sender window and receiver window in brief.
1. Sender Window
The sender window in selective repeat is much smaller as compared to the go-back-n protocol. The size of the sender window here is 2m-1. Here m is the number of bits used by the packet header to express the sequence number of the corresponding packet.
The sender window covers the packets that are sent but not yet acknowledged, one that is acknowledged out of order and the one that can be sent once the data for the corresponding are received by the sender’s application layer.
2. Receiver Window
The maximum size of the receiver window is 2m-1 which is the same as the sender window. The receiver window covers the sequence number of the packets that are received out of order and are waiting for the packets that were sent earlier but are not yet received.
The receiver transport layer does not deliver packets out of order to the application layer. It waits until a set of consecutive packets are received so that they can be delivered to the application layer.
In selective repeat, at the sender side, a timer is attached to each sent packet and if the acknowledgement is not received before the timer expire the corresponding packet is resent.
Let understand selective repeat protocol with the help of an example. Consider that the header of a packet has allotted 3 bits to resemble the sequence number of the corresponding packet so m=3 here. Now as m is 3 the packets are sequenced using modulo 2m. So the sequence number of packets lie from 0, 1, 2, 3, …, 7.
The size of the receiver and sender window will be 2m-1 i.e. 23-1 = 4. So the size of the receiver and sender window is 4.
Operation at Sender Side
As you can see in the figure above the sender window covers the sequence number of the packets from 0 to 7 as the window size is 8. The sender has sent packets 0, 1, 2, and 3 and is waiting to receive the data of packets 4, 5, 6, and 7 for its application layer.
Before the application layer provides data for packets 4 and 5, the sender receives an acknowledgement for frame 0 and the sender window slides by one slot. After receiving data for packets 4 and 5 the sender sends packets 4 and 5.
Later the sender receives out of order acknowledgement for packets 2 and 3. The sender window does not slide as it has not yet received acknowledgement for packet 1. Meanwhile, the timer for packet 1 get expired and the sender has to resend packet 1.
Operation at Receiver Side
The size of the receiver window is 8 so the receiver window covers the sequence number from 0 to 7. If first receives packet 0 and immediately send an acknowledgement for it. Later it receives out of order packets 2 and 3 and sends an acknowledgement for these received packets. Late it again receives an out of order packet 5 and 1.
The receiver stores the packets in the receiver window until there is a set of consecutive packets to be delivered to the application layer. In selective repeat, there should be a complex logic to reinsert the retransmitted packet in proper order. However, the sender must also have complex logic to identify and resend the packet out of order.
In this way, the selective repeat avoids traffic on the network by retransmitting the corrupted the lost packet only. And this is possible as it allows the sending and receiving packets out of order.