Selective Repeat Protocol

Selective Repeat Protocol is a sliding window protocol used in the data link layer for efficient data transmission in computer networks. It is used to transmit data over noisy channels.

Unlike it’s counterparts, Stop and Wait ARQ and Go-Back-N ARQ, Selective Repeat ARQ Protocol allows:

Sender to send multiple frames at the same time.

Receiver to selectively acknowledge and buffer out-of-order frames.

Basically, if a frame is lost or damaged, the receiver sends a negative acknowledgment (NACK) to the sender. However, if the frame is correctly received, it sends back an acknowledgment (ACK). The sender would only resend the selected lost or damaged frames. This reduces unnecessary retransmissions and improves overall network efficiency. It is one of the most efficient flow control protocols available.

Window Size and Sequence Numbers

In Selective Repeat ARQ, both the sender window size and the receiver window size is 2^m-1 , where m is the number of bits that can be used to represent the frame numbers.

$Sender \hspace{0.1cm} Window \hspace{0.1cm} Size = Receiver \hspace{0.1cm} Window \hspace{0.1cm} Size = 2^{m-1}$

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

Now, as m=3, the window size would be 4

(1) $\begin{flalign*} Window \hspace{0.1cm} Size(Sender \hspace{0.1cm} and \hspace{0.1cm} Receiver) & =2^{m-1}&\\ & =2^{3-1}&\\ & =2^2&\\ & = 4 \end{flalign*}$

So in this case, m is 3, the frames are numbered from 0-7 and the window size of both the sender and receiver is 4. This means 4 frames can be send at a time by the sender.

The Sender and Receiver Window

Let us now look at how the sender and receiver window. Let’s take another example. In this, m =2.

If m=2, then the sequence numbers range from 0-3 and the window size is 2.

Working of Selective Repeat Protocol

Let’s look at our example above, fig(1). The current window of the sender is at frame 2 and 3. So it sends frame 2 and 3. It also sends a timer for each.

Now, suppose frame 2 gets lost in transmission and the receiver receives only frame 3. The receiver would then send a NACK(negative acknowledgement) for frame 2. It would accept and buffer frame 3.

If, the sender receives the NACK for frame 2, it would resend only Frame 2 again (unlike in Go-Back-N, it won’t send all the frames in the current window).

If, however the NACK for frame 2 is lost, the sender would wait till the timer (or the timeout period expires) and resend frame 2 again.

From this we can conclude:

The sender maintains a sending window that contains a range of sequence numbers corresponding to the frames it can transmit.

The sender sends multiple frames within the window, one after another, without waiting for individual acknowledgments.

The sender starts a timer upon sending a frame in the window.

If the sender receives an acknowledgment within the timeout period, it slides the sending window forward, discarding the acknowledged frames.

If the sender does not receive an acknowledgment within the timeout period, it assumes that some frames are lost or corrupted. It retransmits only the frames that have not been acknowledged.

The receiver has a window size which is the same as the sender window size.

If the receiver receives an out-of-order frame within its receiving window, it buffers the frame and acknowledges the highest consecutive sequence number received.

If the receiver receives a duplicate frame, it discards the duplicate but acknowledges the frame to prevent unnecessary retransmissions.

Characterstics of Selective Repeat

Selective Repeat is a sliding window protocol used to transmit data over noisy channels.

Selective Repeat optimizes network efficiency by allowing the sender to retransmit only the frames that are lost or damaged. This eliminates unnecessary retransmissions of frames that have already been successfully received like in the case of Go-Back-N ARQ Protocol.

In Selective Repeat Protocol, the sender window size and the receiver window size depend upon the number of bits that can be used to represent the frame numbers, m. Also, dender window size and receiver window size is equal.

$Sender \hspace{0.1cm} Window \hspace{0.1cm} Size = Receiver \hspace{0.1cm} Window \hspace{0.1cm} Size = 2^{m-1}$

where ‘m’ is the number of bits that can be used to represent the frame numbers, m.

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.

Retransmissions

As only the packet that is lost or damaged is retransmitted by the sender, we can say that:

$Retransmission = 1$

This is significantly lesser than the retransmission rate of go-back-n protocol and is a major beneifit of selective repeat.

Advantages of Selective Repeat Protocol

Efficient Retransmission

Unlike Go-Back-N protocol, which retransmits the entire window when any packet is lost or corrupted, Selective Repeat protocol only retransmits the specific lost or corrupted packets. This targeted retransmission reduces unnecessary retransmissions and improves efficiency.

Increased Utilization of Bandwidth

Selective Repeat protocol allows for continuous transmission of packets. The sender need not wait for the acknowledgment of the entire window. This increases the utilization of the available bandwidth and improves overall throughput.

Improved Error Recovery

The Selective Repeat protocol provides better error recovery as packets are individually acknowledged.

Selective Discarding

In Selective Repeat protocol, the receiver can selectively discard duplicate packets received. This prevents unnecessary processing of duplicate packets and in turn, improves the efficiency of the network.

Limitations of Selective Repeat Protocol

Increased Complexity

Selective Repeat protocol is more complex to implement compared to simpler protocols like Go-Back-N. It requires additional mechanisms at both the sender and receiver sides to manage and track individual packets. This results in increased processing overhead.

Larger Overhead

Selective Repeat protocol requires maintaining a larger buffer at the receiver to store out-of-order packets until they can be delivered in sequence. This increases the memory requirements and introduces additional overhead compared to simpler protocols.

Increased Latency

Selective Repeat protocol may introduce higher latency compared to protocols with immediate acknowledgment. This is because the receiver needs to wait for out-of-order packets. This may delay the delivery of in-order packets until all missing packets are received.

Increased Network Congestion

Selective Repeat protocol may increase network congestion due to the retransmission of individual lost packets. This congestion can impact the overall network performance, particularly in scenarios with high error rates or limited network resources.

In summary, the Selective Repeat protocol is an important protocol used by the data link layer of the TCP/IP suite. It offers improved efficiency by allowing the sender to transmit multiple frames before waiting for acknowledgments. It also reduces unnecessary retransmissions by selectively acknowledging out-of-order frames. This, however, incurs additional complexity and overhead.

Selective Repeat Protocol