Selective Reject Protocol / Selective Repeat Protocol

The go-back-n protocol works well if errors are less, but if the line is poor it wastes a lot of bandwidth on retransmitted frames. An alternative strategy, the selective repeat protocol, is to allow the receiver to accept and buffer the frames following a damaged or lost one.

In this technique, only those frames are retransmitted for which negative acknowledgement (NAK) has been received.

It uses two windows of equal size: a sending window that stores the frames to be sent and a receiving window that stores the frames receive by the receiver. The size is half the maximum sequence number of the frame. For example, if the sequence number is from 0 – 15, the window size will be 8.

Selective Repeat protocol provides for sending multiple frames depending upon the availability of frames in the sending window, even if it does not receive acknowledgement for any frame in the interim. The maximum number of frames that can be sent depends upon the size of the sending window.

The receiver records the sequence number of the earliest incorrect or un-received frame. It then fills the receiving window with the subsequent frames that it has received. It sends the sequence number of the missing frame along with every acknowledgement frame.

The sender continues to send frames that are in its sending window. Once, it has sent all the frames in the window, it retransmits the frame whose sequence number is given by the acknowledgements. It then continues sending the other frames.

Go-Back-N ARQ

Go-Back-N ARQ (Go-Back-N automatic repeat request) is a flow control protocol where the sender continues to send several frames specified by a window size even without receiving feedback from the receiver node.

It is a special case of the general sliding window protocol where the transmitter or sender window size is N and the receiver's window size is 1, which means that it can transmit N frames to the receiving node before waiting for a feedback.

It uses the principle of protocol pipelining in which the multiple frames can be sent before receiving the acknowledgment of the first frame. If we have five frames and the concept is Go-Back-3, which means that the three frames can be sent, i.e., frame no 1, frame no 2, frame no 3 can be sent before expecting the acknowledgment of frame no 1.

In Go-Back-N ARQ, the frames are numbered sequentially as Go-Back-N ARQ sends the multiple frames at a time that requires the numbering approach to distinguish the frame from another frame, and these numbers are known as the sequential numbers.

If the acknowledgment of a frame is not received within an agreed-upon time period, then all the frames available in the current window will be retransmitted. 

Working of Go-Back-N ARQ

Suppose there are a sender and a receiver, and let's assume that there are 11 frames to be sent. These frames are represented as 0,1,2,3,4,5,6,7,8,9,10, and these are the sequence numbers of the frames.

Consider the window size as 4, which mean that the four frames can be sent at a time before expecting the acknowledgment of the first frame.

First, the sender will send the first four frames to the receiver, i.e., 0,1,2,3, and now the sender is expected to receive the acknowledgment of the 0^th frame.

Assume that the receiver has sent the acknowledgment for the 0 frame, and the receiver has successfully received it. The sender will then send the next frame, i.e., 4, and the window slides containing four frames (1,2,3,4).

The receiver will then send the acknowledgment for the frame no 1. After receiving the acknowledgment, the sender will send the next frame, i.e., frame no 5, and the window will slide having four frames (2,3,4,5).

Assume that the receiver is not acknowledging the frame no 2, either the frame is lost, or the acknowledgment is lost.

Instead of sending the frame no 6, the sender Go-Back to 2, which is the first frame of the current window, retransmits all the frames in the current window, i.e., 2,3,4,5.

Points to remember:

• In Go-Back-N, N determines the sender's window size, and the size of the receiver's window is always 1.
• It does not consider the corrupted frames and simply discards them.
• It does not accept the frames which are out of order and discards them.
• If the sender does not receive the acknowledgment, it leads to the retransmission of all the current window frames.

Stop & Wait ARQ (Automatic Repeat Request)

Stop & Wait ARQ is a sliding window protocol for flow control and it overcomes the limitations of Stop & Wait.

Stop & Wait ARQ assumes that the communication channel is noisy (Stop & Wait assumed that the communication channel is not noisy). Stop & Wait ARQ also assumes that errors may occur in the data while transmission.

Stop & Wait ARQ is a 1-bit sliding window protocol where the size of the sender window as well as the receiver window is 1. Thus, in Stop & Wait ARQ technique, the minimum number of sequence numbers required is equal to the sum of sender window size & receiver window size.

minimum number of sequence numbers required = sender window size + receiver window size.

Thus, the minimum number of sequence numbers required in Stop & Wait ARQ is 2, which are 0 and 1.

Stop & Wait ARQ overcomes the problem of a lost data packet. For solving this problem, time out timer is used, after transmitting the data packet to the receiver through the communication channel; the sender starts the time out timer. Now if the data packet's ACK is received by the sender before the timer expires, then the sender stops the timer and transmits the next data packet.

And if the time out timer expires and the ACK is not received by the sender then, the sender retransmits the data packet. This prevents the occurrence of deadlock in the network.

The problem of delayed/lost ACK (which used to happen in Stop & Wait protocol) is solved by putting sequence numbers on data packets.

If the ACK given by the receiver is lost, then the sender resends the same data packet after its timer expires. This prevents the occurrence of deadlock. The sequence number on the data packets helps the receiver to identify the duplicate data packet; the receiver discards the duplicate data packet & resends the same ACK.

Whenever a data packet is damaged/corrupted, the receiver then sends negative acknowledgement (NAK) to the sender and then it resends the same data packet.

The Stop & Wait ARQ is very less efficient because the sender window size is 1, which allows the sender to keep only one frame without ACK. So, the sender sends a data packet and waits for the ACK, and it gets the feedback it sends another data packet.

The following comparison table states the differences between the two protocols-

Stop and Wait Protocol	Stop and Wait ARQ
It assumes that the communication channel is perfect and noise free.	It assumes that the communication channel is imperfect and noisy.
Data packet sent by the sender can never get corrupt.	Data packet sent by the sender may get corrupt.
There is no concept of negative acknowledgements.	A negative acknowledgement is sent by the receiver if the data packet is found to be corrupt.
There is no concept of time out timer.	Sender starts the time out timer after sending the data packet.
There is no concept of sequence numbers.	Data packets and acknowledgements are numbered using sequence numbers.

Flow Control - Stop and Wait , Sliding Window Protocols

Data-link layer is responsible for implementation of point-to-point flow. When a data frame (Layer-2 data) is sent from one host to another over a single medium, it is required that the sender and receiver should work at the same speed. That is, sender sends at a speed on which the receiver can process and accept the data.

Flow control is actually set of procedures that explains sender about how much data or frames it can transfer or transmit before data overwhelms receiver. The receiving device may contain limited amount of speed and memory to store data. The receiving device should be able to tell or inform the sender about stopping the transmission or transferring of data on temporary basis before it reaches limit. It also needs buffer, large block of memory for just storing data or frames until they are processed.

Two methods have been developed to control the flow of data:

• Stop-and-wait
• Sliding window

Stop and Wait

This flow control mechanism forces the sender after transmitting a data frame to stop and wait until the acknowledgement of the data-frame sent is received.

When acknowledgment is received, then only sender will send or transfer the next frame. This process is continued until sender transmits EOT (End of Transmission) frame.

The Stop-and-wait method is simple as each frame is checked and acknowledged before the next frame is sent.

Stop-and-wait technique is inefficient to use as each frame must travel across all the way to the receiver and an acknowledgement travels all the way before the next frame is sent. Each frame sent and received uses the entire time needed to traverse the link.

Sliding Window

In this flow control mechanism, both sender and receiver agree on the number of data-frames after which the acknowledgement should be sent.  It is point to point protocol that assumes that none of the other entity tries to communicate until current data or frame transfer gets completed.

At the beginning of a transmission, the sender window contains n-1 frames, and when they are sent out, the left boundary moves inward shrinking the size of the window.

Once the ACK has arrived, then the sender window expands to the number which will be equal to the number of frames acknowledged by ACK.

Sliding Window on Sender Side

 At the beginning of a transmission, the sender’s window contains n-l frames.  As the frames are sent by source, the left boundary of the window moves inward, shrinking the size of window. This means if window size is w, if four frames are sent by source after the last acknowledgment, then the number of frames left in window is w-4.

When the receiver sends an ACK, the source’s window expand i.e. (right boundary moves outward) to allow in a number of new frames equal to the number of frames acknowledged by that ACK.

 For example, Let the window size is 7 (see diagram (a)), if frames 0 through 3 have been sent and no acknowledgment has been received, then the sender’s window contains three frames – 4,5,6.

Now, if an ACK numbered 3 is received by source, it means three frames (0, 1, 2) have been received by receiver and are undamaged. The sender’s window will now expand to include the next three frames in its buffer. At this point the sender’s window will contain six frames (4, 5, 6, 7, 0, 1). (See diagram (b)).

Sliding Window on Receiver Side

At the beginning of transmission, the receiver’s window contains n-1 spaces for frame but not the frames. As the new frames come in, the size of window shrinks. Therefore the receiver window represents not the number of frames received but the number of frames that may still be received without an acknowledgment (ACK) to be sent.

Given a window of size w, if three frames are received without an ACK being returned, the number of spaces in a window is w-3.

As soon as acknowledgment is sent, window expands to include the number of frames equal to the number of frames acknowledged.

For example, let the size of receiver’s window is 7 as shown in diagram. It means window contains spaces for 7 frames. With the arrival of the first frame, the receiving window shrinks, moving the boundary from space 0 to 1. Now, window has shrunk by one, so the receiver may accept six more frame before it is required to send an ACK.

If frames 0 through 3 have arrived but have not been acknowledged, the window will contain three frame spaces.

As receiver sends an ACK, the window of the receiver expands to include as many new placeholders as newly acknowledged frames. The window expands to include a number of new frame spaces equal to the number of the most recently acknowledged frame minus the number of previously acknowledged frame. For e.g., If window size is 7 and if prior ACK was for frame 2 & the current ACK is for frame 5 the window expands by three (5-2).

Therefore, the sliding window of sender shrinks from left when frames of data are sending. The sliding window of the sender expands to right when acknowledgments are received.

The sliding window of the receiver shrinks from left when frames of data are received. The sliding window of the receiver expands to the right when acknowledgement is sent.