Sliding Window Algorithm Types in Data Link Layer (DLL)

In the previous post , we have seen two important flow control protocols i.e the Stop – Wait protocol and the Sliding Window protocol . Now in this post, we gonna see some further varieties of the sliding window algorithm in detail.

A One Bit Sliding Window Protocol (Stop and Walt ARQ) in Data Link Layer 

This protocol is called one bit protocol because the maximum window size here i.e. ‘n’ is equal to 1. It uses the slop and wait technique which we have discussed earlier. The sender sends one frame and waits to get its acknowledgement.

The sender transmits its next frame only after receiving the acknowledgement for the earlier frame. So one bit sliding window protocol is also called a stop and wait protocol.

Operation of the protocol

The operation in this protocol is based on the ARQ (automatic repeat request) principle. So the sliding window protocols are also called as ARQ protocols.

If it receives a positive acknowledgement (ACK) it transmits the next frame. If it receives a negative acknowledgement (NAK) it retransmits the same frame.

The retransmission of the frame is essential under the following events:

• If the received frame is damaged
• If the transmitted frame is lost
• If the acknowledgement from the receiver is lost

Demerit of Stop and wait protocol

The sender will have to wait at least one round trip time before sending next. At any moment, only one frame is in transition.

A Protocol using GO Back N 

To improve the efficiency of transmission (filling the pipe), multiple frames must be in the transition while waiting for an acknowledgment. In other words, we need to allow more than one frame to be outstanding to keep the channel busy while the sender is waiting for acknowledgment.

In this stop and wait protocol, it was assumed that the transmission time required for a frame to arrive at the receiver plus the transmission time for the acknowledgment to come back is negligible.

It is a method used to overcome the inefficiency of the flow control protocols ARQ by allowing the transmitter to continue sending enough frames so that the channel is kept busy while the transmitter waits for acknowledgements.

Sequence numbers : Frames from a sending station (sending host) are numbered sequentially. However, since we need to include the sequence number of each frame in the header, we need to set a limit. If the header of the frame allows ‘m’ bits for the sequence number, the sequence numbers range from ‘0’ to 2 raised to ‘m’ – 1.

The major difference between this and the previous system is that the sender does not wait for ACK signal for the transmission of the next frame. It transmits the frames continuously as long as it does not receive the “NAK” signal . NAK is the negative acknowledgement signal sent by the receiver to the transmitter.

The errors can get introduced, if the transmitted frames are damaged or lost or if the acknowledgement is lost.In Go-Back-N ARQ , the size of the send window must be less than 2 raised to ‘m’ , the size of the receiver window is always 1.

The disadvantage of Go-back-n ARQ protocol is that in noisy channels it has poor efficiency because cf the need to. retransmit the frame in error and all the subsequent frames.

Selective Repeat ARQ in Data Link Layer

Go-Back-N ARQ basically simplifies the process at the receiver site. The receiver basically keeps track of only one variable, and there is no need to buffer out-of-order frames, they are then simply discarded. However, this protocol is very inefficient for any noisy link (mostly the ideal case).

In the noisy link, a frame has a higher probability of damage, which simply means the resending of multiple frames. For noisy links, there is yet another mechanism that does not resend N frames when just one frame is damaged, only the damaged frame is resent. This mechanism is called Selective Repeat ARQ .

In this method, only the specified damaged or lost frame is retransmitted. A selective repeat system differs from the go-back-n method in the following ways :

• The receiver can do sorting of data frames and is also able to store frames received after it has sent the NAK until the damaged frame has been replaced.
• The transmitter has a searching mechanism that allows it to choose only those frame which is requested for retransmission.
• The window size in this method is less than or equal to (n + 1)/2, whereas in the case of go-back-n it is n – 1 . In Selective Repeat ARQ, the size of the sender and receiver window must be atmost one-half  of 2 raised to ‘m’.

In this system as well, the transmitter does not wait for the ACK signal for the transmission of the next frame. It transmits the frames continuously until it receives the “NAK” signal from the receiver.

The receiver sends the “NAK” signal back to the transmitter as soon as it detects an error in the received frame. For example, the receiver detects an error in the third frame.

On reception of “NAK” signal, the transmitter will retransmit only the frame 3 and then continues with the sequence 8, 9 .

The frames 4, 5, 6 and 7 received by the receiver which do not contain any error are not discarded by the receiver. The receiver receives the retransmitted frames in between the regular frames. Therefore the receiver will have to maintain the frames sequentially.

The Selective Repeat Protocol also uses two windows i.e a send window and a receive window. However, there are differences between the windows in this specific protocol and the ones in Go-Back-N. First, the size of the send window will be much smaller.

The smaller window size simply means less efficiency in filling the pipe, but the fact that there will be fewer duplicate frames can compensate for this.

The selective ARQ protocol is the most complex of all the ARQ protocols. Thus in selective repeat ARQ only the frame which is damaged or lost is retransmitted by the transmitter. The lost ACK or NAK frames are treated in the same manner as the go-back-n method.

One main difference is the number of timers. Here, each frame sent or resent needs a timer, which means that the timers need to be numbered.The timer for frame 1 starts at the second request, restarts when a NAK arrives, and finally stops when the last ACK arrives. The other two timers start when the corresponding frames are sent and stop at the last arrival event.

The disadvantage of this method is that because of the complexity of sorting and storage required by the receiver and the extra logic needed by the transmitter to select frames for retransmission, the system becomes more expensive.

In the next post we will discuss about the HDLC protocol in the data link layer . Stay tuned…