Sliding Window Protocol

In this tutorial, you will learn the basics of the Sliding Window Protocols. After reading this tutorial, you will understand the working, advantages, disadvantages, and flow control mechanism of Sliding Window protocols.

Contents:

  1. Elementary Data Link Protocols Vs Sliding Window Protocols
  2. Sending Window and Receiving Window
  3. Types of Acknowledgements
  4. Sliding Window Protocols
  5. Stop-and-Wait ARQ Protocol
  6. Go-Back-N ARQ Protocol
  7. Selective Repeat ARQ Protocol
  8. Comparison of Sliding Window Protocols

Elementary Data Link Protocols Vs Sliding Window Protocols

In the Elementary data link protocol, data frames were transmitted in only one direction. But in practice, the communication between the sender and the receiver should take place in both directions. We can achieve full-duplex mode communication in the sliding window protocol by creating two instances of one of the Elementary data link protocols.

  • In two of the Elementary data link protocols, the half-duplex mode was in use. In the sliding window protocol, the sender and receiver use the same link to send frames and acknowledgements for data in both directions.
  • In the sliding window protocol, each frame sent by the sender has a sequence number. Sequence numbers can range from 0 to 2n-1 when there are n-bit field.
  • In the sliding window protocol, the sender maintains a set of sequence numbers corresponding to the frames that are allowed to be sent.

Sending Window and Receiving Window

The sliding window protocol has the concept of a window. The sender has a sending window, and the receiver has a receiving window.

  • The frames on the sender’s machine come within the sending window. Similarly, the receiver has a receiving window to store the received frame.
  • The size of the sending and receiving window may vary as per the requirement. Some protocols have a fixed sending and receiving window size. But in other protocols, the size of the sending and receiving windows increase and decrease according to the size of the sending and receiving frames.
  • The sender looks at the sequence number of frames in the sending window to check which frames have been sent and can be sent.
  • There is a possibility of frames being lost during transmission, so the sender keeps all these frames in a buffer for retransmission. If the sending window size is n, the sender needs n buffers to hold the un-acknowledged frames.

advertisement
advertisement

Types of Acknowledgement

When a frame reaches the receiver, the receiver sends an acknowledgement to the sender, informing about the received frame information. There are total 6 types of an acknowledgement as follows:

  1. Positive Acknowledgement
  2. Negative Acknowledgement
  3. Lost Acknowledgement
  4. Independent Acknowledgement
  5. Cumulative Acknowledgement
  6. Delayed Acknowledgement
  • Positive Acknowledgement: The Acknowledgement sent by the receiver on receiving a frame successfully is known as positive acknowledgement.
  • Negative Acknowledgement: When the frame is lost during transmission and the receiver sends an acknowledgement for the retransmission of the lost frame is known as negative acknowledgement.
  • Lost Acknowledgement: The frame is successfully received by the receiver, but the acknowledgement sent by the receiver to the sender is lost during transmission, known as lost acknowledgement.
  • Independent Acknowledgement: The sender sends frames one by one, and the receiver is sending an acknowledgement of each received frame, this is known as Independent Acknowledgement.
  • Cumulative Acknowledgement: The sender sends a set of frames to the receiver, and the receiver sends an acknowledgement for the next set of frames is known as Cumulative Acknowledgement.
  • Delayed Acknowledgement: When the acknowledgement sent by the receiver reaches the sender after exceeding the time limit is known as delayed acknowledgement.

The figure below shows the types of Acknowledgement.

Types of Acknowledgment

As shown in the figure, Positive Acknowledgement, Negative Acknowledgement, Lost Acknowledgement, Independent Acknowledgement, Cumulative Acknowledgement, and Delayed Acknowledgement are the types of Acknowledgement.

Sliding Window Protocols

Typically, the sliding window protocol is used for flow control purposes. In a noisy channel, the data flow increases when the sender sends multiple frames at once before receiving acknowledgement of the frame received from the receiver.

  • The sliding window protocols also send multiple frames from sender to receiver to improve channel efficiency. For that, they use flow control mechanisms, which provide reliable communication.
  • Here, the term sliding window refers to the buffers or memory that consists of frames.

There are 3 types of sliding window protocols used for flow control.

  1. Stop-and-Wait ARQ Protocol
  2. Go-Back-N ARQ Protocol
  3. Selective Repeat ARQ Protocol

Stop-and-Wait ARQ Protocol

In the Stop-and-Wait ARQ protocol, the size of the sending window and receiving window is 1. Since the sender and receiver window size is ‘1’, the sender transmits one frame and waits for an acknowledgement from the receiver before sending the next one. It is also known as a one-bit sliding window protocol because only one bit is transmitted on a channel.

The diagram below explains the Stop-and-Wait ARQ protocol.

advertisement
Stop-and-Wait ARQ Protocol
  • As shown in the above figure, Sn is at the 0th position. So the sender will send frame-0 to the receiver. As soon as the receiver receives frame-0, it will check the Rn and send ACK-1 to the sender, as it wants frame-1 from the sender.
  • Now, the sender receives ACK-1 and sends frame-1 to the receiver. But frame-1 is lost during transmission. Therefore, the sender will wait for the acknowledgement from the receiver until the timeout.
  • After the timeout, the sender will again send frame-1 to the receiver. Now, the receiver Rn is on the 0th frame because it wants the next frame, which is frame-0.
  • So, the receiver will send ACK-0 to the sender, and the sender will send the second frame-0 to the receiver. The receiver sends ACK-1, but it is lost during transmission.
  • So the sender will resend the frame-0 to the receiver, but the receiver will discard it as it is duplicated, and ACK-1 is sent to the sender. Similarly, this process continues until all the frames have been sent to the receiver.

Go-Back-N ARQ Protocol

In the Go-Back-N ARQ protocol, the sending and receiving window sizes are N-bit and One-bit, respectively. It uses cumulative and independent acknowledgement for communication.

  • The Go-Back-N ARQ protocol does not accept corrupted frames during transmission. Furthermore, it does not accept out-of-order frames and silently discards them.
  • AIf the receiver does not accept a frame, the go-back-n protocol leads to the re-transmission of the entire window.
  • When a frame is lost during transmission, the go-back-n protocol resends the frame after the timeout.

The diagram below explains the Go-Back-N ARQ protocol.

Go-Back-N ARQ protocol
  • As shown in the diagram above, the sending and receiving windows have window sizes of 6 and 1, respectively. Both Sf and Sn are located in the first position.
  • Here, Sf specifies the frame of the window that has been sent but has not received acknowledgement from the receiver, and Sn specifies which frame to send. Since Sn is at the beginning, the sender will send frame-0 to the receiver.
  • On the receiver side, Rn describes which frame the receiver expects to receive. As the receiver accepts frame-0, it slides the Rn onto frame-1, indicating that it now wants frame-1. So, the receiver will send ACK-1 to the sender.
  • When the sender receives ACK-1, it sends frame-1 to the receiver. But frame-1 is lost during transmission, and the sender is waiting for an acknowledgement.
  • As soon as the timeout is over, the sender will resend frame-1 to the receiver. This time, the receiver receives frame-1 and sends ACK-2 to the sender. Now, Sn on the sender side will increase by one.
  • When the sender receives ACK-2, it sends frame-2 to the receiver. The receiver receives frame-2 and sends ACK-3, but ACK-3 is lost during transmission.
  • Before receiving ACK-3, the sender sends frame-3 and frame-4 to the receiver. When the receiver sends ACK-5, the sender will understand that the previous frames were received by the receiver successfully.
  • The sender sends frame-5 and frame-6 to the receiver, but frame-5 is lost during transmission, and frame-6 reaches the receiver. But this is an out-of-delivery frame, and the receiver will not accept frame-6. The sender will retransmit frame-5 and frame-6 after the timeout.

Selective Repeat ARQ Protocol

As we have seen in the Go-Back-N ARQ protocol, the sender and receiver window sizes are N and 1, respectively. Also, it does not receive out-of-order delivery. But in Selective Repeat ARQ protocol, sending and receiving windows are of equal size, which is N. In addition, it also accepts out-of-order frames.

advertisement
  • Selective Repeat ARQ protocol uses independent acknowledgement for communication.
  • Similar to the Go-Back-N ARQ protocol, the Selective Repeat ARQ protocol also does not accept corrupted frames. But, the selective repeat ARQ protocol does not silently discard corrupted frames, like the Go-Back-N ARQ protocol.
  • To find the frame to be sent to the receiver, the sender performs the search operation. On the receiver side, since it accepts out-of-order frames, it needs a sorting operation to sort the frames according to the sequence number.
  • If a frame loss occurs during transmission, the Selective Repeat ARQ protocol resends the loss frame to the receiver.

The below diagram explains the Selective Repeat ARQ protocol.

Selective Repeat ARQ protocol
  • In the above figure, Sf specifies the frame of the window that has been sent but has not received acknowledgement from the receiver, Sn specifies which frame to send and Rn describes which frame the receiver expects to receive.
  • As shown in the figure, the sender and receiver windows are of size 4 bits. The sender sends frame-0 to the receiver, and the receiver sends ACK-1.
  • After receiving the ACK-1, the sender sends frame-1 to the receiver, and the receiver sends ACK-2 to the sender. Upon receiving ACK-2, the sender sends frame-2, and frame-2 is lost during transmission.
  • The sender also sends frame-3 and frame-4 before receiving the acknowledgement from the receiver.
  • When frame-3 arrives, the receiver will send a negative acknowledgement to the sender. So the sender will see the NAK-2 and resend the frame-2 to the receiver.
  • This process continues until all frames have been sent and received by the sender and receiver, respectively. Sf, Sn, and Rn will change as per the situation.

Comparison of Sliding Window Protocols

The table below explains the comparison of sliding window protocols.

Key Stop-and-Wait ARQ Go-Back-N ARQ Selective Repeat ARQ
Window Size Sending Window = 1
Receiving Window = 1
Sending Window = N
Receiving Window = 1
Sending Window = N
Receiving Window = N
Maximum Sequence Numbers 2 N+1 2N
Bandwidth Low High Moderate
Power Usage Low Moderate High
Implementation Easy Moderate Complex
Mode of Transmission Half-duplex Full-duplex Full-duplex
Acknowledgement Independent Acknowledgements Cumulative and Independent Acknowledgements Independent Acknowledgements

Key Points to Remember

Here is the list of key points we need to remember about “Sliding Window Protocols”.

  • In the sliding window protocol, the sender and receiver use the same link to send frames and acknowledgements for data in both directions.
  • The sender has a sending window, and the receiver has a receiving window. On the sender and receiver side, frames are stored in the sending and receiving windows, respectively.
  • There are total 6 types of acknowledgement as follows:
    1. Positive Acknowledgement
    2. Negative Acknowledgement
    3. Lost Acknowledgement
    4. Independent Acknowledgement
    5. Cumulative Acknowledgement
    6. Delayed Acknowledgement
  • There are 3 types of sliding window protocols used for flow control.
    1. Stop-and-Wait ARQ Protocol
    2. Go-Back-N ARQ Protocol
    3. Selective Repeat ARQ Protocol
  • In the Stop-and-Wait ARQ protocol, the sender transmits one frame and waits for an acknowledgement from the receiver before sending the next one.
  • The Go-Back-N ARQ protocol does not accept corrupted and out-of-order frames and silently discards them.
  • Similar to the Go-Back-N ARQ protocol, the Selective ARQ protocol also does not accept corrupted frames. But, the selective repeat ARQ protocol does not silently discard corrupted frames.
  • Sending and Receiving window sizes are 1, N and 1, and N in Stop-and-Wait ARQ Protocol, Go-Back-N ARQ Protocol, and Selective Repeat ARQ Protocol, respectively.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.