Sliding Window Protocol

What is Sliding Window Protocol?

Before learning about the sliding window protocol, let us first learn about computer networks, the OSI model, and the data link layer (as the Sliding Window Protocol is related to the data link layer).

A computer network is a set of devices (computers) connected to exchange information and resources such as files etc.

The OSI model stands for Open Systems Interconnection model. It is a conceptual reference model that describes the entire flow of information from one computer to the other computer. The OSI model is a 7-layered model so it is also known as a 7-layered architecture model. The data link layer is one of the seven layers of the OSI model.

Now, let us discuss the data link layer briefly so that we can get a better understanding of the Selective Repeat ARQ protocol as it is one of the most widely used protocols of the data link layer to control errors.

The data link is the second layer of the OSI model which is used for the transmission of the error-free frames from one node to the other node. If the two computer nodes are on the same networks then the data link layer provides a connection between the two nodes. The main work of the data link layer is to convert the data into the form of frames (refer to the sub-section below for details about framing).

The functions provided by the data link layer are as follows:

• It provides reliable and efficient communication between two or more devices.
• Framing: Framing is the technique in which the data is divided into streams of bits (called frames) received from the network layer. Along with the conversion of data into frames, the data link layer adds a header and trailer to the frames. The header (present at the starting of the frame) contains the hardware's physical address of source and destination. The trailer (present at the end of the frame) contains the error detection and correction bits.
• The data link layer also maintains the flow control of data during transmission. Suppose that the rate of data transmission and data absorption varies then there is data loss, so the data link layer maintains the flow control.
• As we have seen above, the data link layer adds the error detection and correction bits at the end of the frames in the form of trailers. These bits are used to detect the errors and then retransmit the damaged or lost data to prevent any kind of duplication.
• It also maintains access control. In situations where two or more devices are connected to the same communication medium then the data link layer protocols determine the device that can transmit the data.

The flow control protocols involved in the data link layers are as follows:

Refer to the image below to see the basic transmission of data and working of the data link layer.

The various protocols used in this layer are:

• PPP (Point-to-Point Protocol),
• Frame Relay,
• ATM (The asynchronous transfer mode protocol), etc.

The various devices used in this layer are:

• Bridges,
• Switches,
• NIC cards (Network Interface Cards), etc.

Now, let us get back to the topic of Sliding Window Protocol. The sliding window protocol is a data link layer protocol that is useful in the sequential and reliable delivery of data frames. Using the sliding window protocol, the sender can send multiple frames at a time. When the receiver receives the frame, it sends back an ACK (acknowledgment) to the sender. The ACK lets the sender know that a particular frame is received by the receiver correctly.

The sliding window protocol uses a mechanism of sequence numbers. The sender associates a sequence number to the data frames so that the receiver can use this sequence number to arrange the frames in order if any frame was re-transmitted. The sequence number also helps the receiver identify the lost or damaged packets.

In the sliding window protocol, we use an imaginary box called a window to hold the frames at the sender's end and the receiver's end. The window on the sender's side covers the sequence of data packets that are sent (or to be sent). On the other hand, the window on the receiver's side covers the sequence of data packets that are received (or to be received). The sender's window size is represented using Ws and the receiver's window size is represented using Wr.

Types of Sliding Window Protocols

There are two types of sliding window protocols. Let us discuss them one by one.

1. Go-Back-N ARQ

The Go-Back-N ARQ is one of the Sliding Window Protocol strategies that is used where reliable in-order delivery of the data packets is required. In the Go-Back-N ARQ, we use the concept of a timer. When the receiver receives the correct frame, it sends back an acknowledgment or ACK. Once the sender gets an ACK for a data frame, it shifts its window forward and sends the next frame. If the ACK is not received within the specified period then all the data frames starting from the lost frame are retransmitted.

In the Go-Back-N ARQ, the sender's window size is taken as N but the receiver's window size is always 1. Hence, the sender can send N data frames at a time but the receiver can receive only 1 frame at a time. The Go-Back-N ARQ is used for noisy channels or links and it manages the flow and error control between the sender and the receiver.

Important Points regarding the Go-Back-N ARQ:

• In the Go-Back-N ARQ, we retransmit all the data frames starting from the lost or damaged frames.
• The ACK has the sequence number of the frame that helps the sender to identify the lost frame.
• The sender sets a timer for each frame so whenever the timer is over and the sender has not received any acknowledgment, then the sender knows that the particular frame is either lost or damaged.
• The ACK has the sequence number of the frame that helps the sender to identify the lost frame.
• The sender's window size is N.
• The receiver's window size is 1.
• The sender waits for the period specified by the timer before sending the frame again. Hence, the Go-Back-N ARQ is a slower protocol than the Selective Repeat ARQ.
• In Go-Back-N ARQ protocol, the efficiency is N/(1+2xa) where a is ratio of propagation delay vs the transmission delay and N is number of packets sent.
• GoBackN is quite easy to implement but here lot of bandwidth is used in case of high error rate for the retransimmion of the entire window every time.

2. Selective Repeat ARQ

The selective repeat ARQ is one of the Sliding Window Protocol strategies that is used where reliable in-order delivery of the data packets is required. The selective repeat ARQ is used for noisy channels or links and it manages the flow and error control between the sender and the receiver.

In the selective repeat ARQ, we only retransmit the data frames that are damaged or lost. If any frame is lost or damaged then the receiver sends a negative acknowledgment (NACK) to the sender and if the frame is correctly received, it sends back an acknowledgment (ACK). As we only resend the selected damaged frames so we name this technique the Selective Repeat ARQ technique. The ACK and the NACK have the sequence number of the frame that helps the sender to identify the lost frame.

Important Points regarding the Selective Repeat ARQ:

• In the selective repeat ARQ, we only resend the data frames that are damaged or lost.
• If any frame is lost or damaged then the receiver sends a negative acknowledgment (NACK) to the sender and if the frame is correctly received, it sends back an acknowledgment (ACK).
• The sender sets a timer for each frame so whenever the timer is over and the sender has not received any acknowledgment, then the sender knows that the particular frame is either lost or damaged.
• As the sender needs to wait for the timer to expire before retransmission. So, we use negative acknowledgment or NACK.
• The ACK and the NACK have the sequence number of the frame that helps the sender to identify the lost frame.
• The receiver has the capability of sorting the frames present in the memory buffer using the sequence numbers.
• The sender must be capable enough to search for the lost frame for which the NACK has been received.
• The size of the sender's window is $2^{(m-1)}$, where m is the number of bits used in the header of the packet to express the packet's sequence number.
• The window size of the receiver is the same as that of the sender i.e. $2^{(m-1)}$.
• In Selective Repeat protocol, the efficiency is N/(1+2xa) where a is ratio of propagation delay vs the transmission delay and N is number of packets sent.
• It is efficient as only the lost or broken packets need retransmission.

Let us briefly discuss ARQ. ARQ stands for Automatic Repeat Request. ARQ is an error-control strategy that ensures that a sequence of information is delivered in order and without any errors or duplications despite transmission errors and losses.

Working of Sliding Window Protocols

The sender sends the data frames according to the specified window size of the sender and the receiver receives the data frames according to its specified window size. The range of the sequence number depends on the size of the data frame i.e. N. So, the range of the sequence numbers can be $0$ to $2^ N-1$.

Let us take a simple example to understand the working of the Sliding Window Protocol.

Let us suppose that the sender's window size is taken as 4. So, the sequence number of the data frame will be in the range of $0$ to $(2 ^ N-1)$ i.e. 0, 1, 2, 3, 0, 1, 2, 3, and so on.

The steps of data transmission can be:

1. The sender sends multiple frames.
2. The receiver receives the frames and sends back an ACK.
3. Again the sender sends the next frame.
4. If the receiver does not send back an ACK in the specified time then the sender sends back the frame as the frame is either lost or damaged in the last transmission.
5. This process is continued till all the frames have been received by the receiver.