Sliding Window and Stop – Wait protocol for Flow Control in data link layer

Flow control is one of the most important aspects of the Data Link Layer (DLL). It basically determines the rate at which the sender must send the data packets before receiving an acknowledgment.  Flow control refers to a set of procedures used to restrict the amount of data that the sender can send before waiting for an acknowledgement (ACK).

It may possible that the sender’s rate of sending data is different from that of the receiver’s rate of receiving data . In that case , the flow of data must not be allowed to increase from that of the sender (to avoid further traffic and congestion).

Any receiving device has a limited speed at which it can process incoming data and a limited amount of memory in which it has to store incoming data.

Thus flow control mainly helps in maintaining the data transfer rate between the sender and receiver. Each receiving device has a block of memory called  buffer, reserved for storing incoming data until they are processed. It is a set of procedures that inform a sender how much data it can transmit before it must wait for an acknowledgment from the receiver(otherwise there will be an overflow of data).

From the above , we can say that there should be some feedback mechanism in order to avoid the data overflow.So let us now see some of the methods  implemented for the flow control in DLL :

Stop-and-Wait Protocol in flow control of DLL

If data frames (rate of arrival) arrive at the receiver site faster than they can be processed, the frames must be stored until their use. Normally, the receiver does not have enough storage space, particularly if it is receiving data from many sources at a time.

This eventually results in either discarding of frames or denial of service. To prevent the receiver from becoming overwhelmed with frames, we somehow need to inform the sender to slow down. Here comes the feedback mechanism.

This protocol is called the Stop and Wait protocol ,  it is so since the sender sends one frame, stops, and waits until it receives confirmation from the receiver (fine to go further), and then sends the next frame . The implementation of this scheme depends upon the noise level of the channel.

Let us assume that the communication channel is noisy and can introduce errors in the data traveling over it. The channel noise can either damage the frames or they may get lost completely. Let us understand this in simple steps:

• The sender first transmits one frame ,it then stops transmission and waits for an acknowledgment from the receiver.
• If positive acknowledgment (which means that the receiver is ready to receive the next frame ) received, then go to step 1 above.
• If negative acknowledgment  (NACK) received (the receiver is not ready to receive the next frame), then wait for a positive acknowledgment (ACK) from the receiver.

In this protocol, the sender waits for a positive acknowledgment before advancing to the next data item. There is a timer set at the sender when a frame is sent. If the sender times out it will resend the same frame again .

So it is called as PAR (Positive acknowledgment with retransmission) or Automatic Repeat Request (ARQ) type protocol. If a frame is badly damaged or lost then the sender would retransmit it.

Since an ACK (acknowledgment) frame can also be corrupted and lost, it too needs redundancy bits and a sequence number. The ACK frame for this protocol generally has a sequence number field. In this protocol, the sender simply discards any corrupted ACK frame or ignores an out-of-order one.

The receiver can check the sequence number of each arriving frame to check for the possible duplicate frame. If a frame is duplicated then the receiver will discard it.

Piggybacking in flow control of DLL 

In a full-duplex transmission, there will be two-way communication of frames between the sender and receiver. A separate channel (forward and reverse) can be used to transmit frames both ways, with both channels having the same capacity.

When a data frame arrives, the receiver waits does not send the control frame (acknowledgment) back immediately. The receiver then waits until its network layer passes in the next data packet.

The acknowledgment is then attached to this outgoing data frame. Thus the acknowledgment travels along with the next data frame. This technique in which the outgoing acknowledgment is delayed temporarily is called as piggybacking.

Sliding Window Protocols (continuous flow control)  in DLL

Sliding windows are basically the imaginary boxes at the transmitter and receiver.  This window holds the frames at the transmitting as well as receiving ends and provides the upper limit on the number of frames that can be transmitted before an acknowledgement is obtained.

The range which is the concern of the sender is called the send sliding window, the range that is the concern of the receiver is called the receive sliding window.

One of the important features of all the sliding window protocols is that each outbound frame contains a sequence number, ranging from 0 to some maximum value. The maximum value is generally equal to (2 raised to ‘n’  – 1). Where ‘n’ is an arbitrary number.

These frames which are being permitted to sent are said to be residing inside the sending window. The receiver also maintains a receiver window. It corresponds to the set of frames that the receiver is permitted to accept. The sender and receiver windows can be of different sizes.

The positive or negative acknowledgment (ACK or NAK) should be used after every frame. That means the sender sends frame, waits for the acknowledgment, and sends the next frame or retransmits the original one (depending upon positive or negative ACK) . 

A send window can slide one or more slots to the right when an acknowledgment arrives from the other end and the receive window makes sure that the correct data frames are then received and the correct acknowledgments are sent. The size of the receive window is always 1. 

The received window is an abstract concept of defining an imaginary box of size 1 with one single variable Rn . The window then slides when a correct frame has arrived, sliding occurs one slot at a time.

Resending of Frame

When the timer expires, the sender then resends all outstanding frames. For example, suppose the sender has already sent frame 6, but the timer for frame 4 expires. This means that frame 4 has not been acknowledged; the sender goes back and sends frames  4, 5, and 6 again. That is why the protocol is called the  Go-Back-N ARQ . 

The sender as well as the receiver maintain their own sliding windows. The sender sends the number of frames allowed by the size of its own sliding window and then waits for an acknowledgment from the receiver. The receiver sends an acknowledgment which includes the number of the next frame that the sender should send.

Finally, we have reached the end of this post . Stay tuned for more exciting stuff in this series.