Link Level Flow Control

Flow control is a technique that a transmitting entity does not conquer a receiving entity with data. Two fundamental mechanisms are acknowledgement and timeouts.

Ø  After getting each frame the receiver will send ACK to sender.

Ø  If the sender does not receive ACK up to reasonable amount of time then it retransmit the original frame waiting for reasonable amount of time is called timeout.

The two flow control mechanisms are

Ø  Stop and wait Flow Control

Ø  Sliding Window Flow Control

Stop and Wait Algorithm

Ø  After transmitting one frame, the sender waits for an                  acknowledgment before transmitting the next frame.

Ø  If the acknowledgment does not arrive after a certain period of time, the sender times out and retransmit the original frame.

            a) The ACK is received before

                  the timer expires    

                                    

      

 b) The original frame is lost

                        c) The ACK  is lost

d)The timeout fires too soon

Fig: illustrates four different scenarios that result from this basic algorithm. The sending side is represented on the left, the receiving side is depicted on the right, and time flows from top to bottom.

Ø  In Fig (a) ACK is received before the timer expires, (b) and (c) show the situation in which the original frame and the ACK, respectively, are lost, and (d) shows the situation in which the timeout fires too soon..

Ø  Suppose the sender sends a frame and the receiver acknowledges it, but the acknowledgment is either lost or delayed in arriving. This situation is in (c) and (d). In both cases, the sender times out and retransmit the original frame, but the receiver will think that it is the next frame, since it correctly received and acknowledged the first frame.

Ø  This makes the receiver to receive the duplicate copies. To avoid this two sequence numbers (0 and 1) must be used alternatively.

Ø  The main drawback of the stop-and-wait algorithm is that it allows the sender have only one outstanding frame on the link at a time.

Sliding Window Algorithm

Ø  The sender can transmit several frames before needing an acknowledgement.

Ø  Frames can be sent one right after another meaning that the link can carry several frames at once and it s capacity can be used efficiently.

Ø  The receiver acknowledges only some of the frames, using a single ACK to confirm the receipt of multiple data frames

Ø  Sliding Window refers to imaginary boxes at both the sender and the receiver.

Ø  Window can hold frames at either end and provides the upper limit on the number of frames that can be transmitted before requiring an acknowledgement.

Ø  Frames are numbered modulo-n which means they are numbered from o to n-1

Ø  For eg. If n=8 the frames are numbered 0,1,2,3,4,5,6,7. i.e the size of the window is n -1.

Ø  When the receiver sends ACK it includes the number of the next frame it expects to receive.

Ø  When the sender sees an ACK with the number 5, it knows that all frames up through number 4 have been received.

There are two methods to retransmit the lost frames

Ø  GO-Back N

Ø  Selective Repeat

Go – Back N Method

Sender Window

Ø  At the beginning of transmission, the sender window contains n-1 frames. As frames are sent out, the left boundary of the window moves inward, shrinking the size of the window

Ø  If size of window is W if three frames have been transmitted since the last acknowledgement then the number of frames left in the window is w -3.

Ø  Once an ACK arrives, the window expands to allow in a number of new frames equal to the number of frames acknowledged by that ACK.

Receiver Window

Ø  The receive window is an abstract concept defining an imaginary box of size 1 with one single variable Rn.

Ø   The window slides when a correct frame has arrived, sliding occurs one slot at a time.

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

Selective Repeat

 Sender Window

Receiver window

Ø  The Selective Repeat Protocol allows as many frames as the size of the receive window to arrive out of order and be kept until there is a set of in-order frames to be delivered to the network layer.

Ø  Because the sizes of the send window and receive window are the same, all the frames in the send frame can arrive out of order and be stored until they can be delivered.

Ø  If any frame lost, sender has to retransmit only that lost frames.