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.