CS2302 Computer Networks Unit - I (Link-level flow control)

UNIT I

Network architecture – layers – Physical links – Channel Access on links– Hybrid multiple access techniques – Issues in the data link layer –Framing – Error correction and detection – Link-level flow control


Link-level flow control
 

Reliable Transmission  

• RCC is used to detect errors.
• Some error codes are strong enough to correct errors.
• The overhead is typically too high.
• Corrupt frames must be discarded.
• A link-level protocol that wants to deliver frames reliably must recover from these discarded frames.

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. 

  

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.  

                                    Timeline for stop-and-wait with 1-bit sequence number

•      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. 
•   The sender has only one outstanding frame on the link at a time. 

                     –This may be far below the link’s capacity

•  Consider a 1.5 Mbps link with a 45 ms RTT
• The link has a delay    bandwidth product of 67.5 Kb or approximately 8 KB

• Since the sender can send only one frame per RTT and
• assuming a frame size of 1 KB 
• Maximum Sending rate 
• Bits per frame    Time per frame = 1024    8    0.045 = 182
• Kbps Or about one-eighth of the link’s capacity 
•  To use the link fully, then sender should transmit up to eight frames before having to wait for an acknowledgement 

 

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.
• Sender assigns a sequence number denoted as SeqNum to each frame. 
• Assume it can grow infinitely large.
• Sender maintains three variables.
• Sending Window Size (SWS)
• Upper bound on the number of outstanding (unacknowledged) frames that the sender can transmit.
• Last Acknowledgement Received (LAR)
• Sequence number of the last acknowledgement received
• Last Frame Sent (LFS)
• Sequence number of the last frame sent.
  
                                    Timeline for Sliding Window Protocol

• Sender also maintains the following invariant 
• LFS – LAR ≤ SWS

 

                                                                Sliding Window on Sender

• When an acknowledgement arrives
• the sender moves LAR to right, thereby allowing the sender to transmit another frame
• Also the sender associates a timer with each frame it transmits
• It retransmits the frame if the timer expires before the ACK is received 
• Note that the sender has to be willing to buffer up to SWS frames 

 

• Receiver maintains three variables  
• Receiving Window Size (RWS) 
• Upper bound on the number of out-of-order frames that the receiver is willing to accept 
• Largest Acceptable Frame (LAF) 
• Sequence number of the largest acceptable frame 
• Last Frame Received (LFR) 
• Sequence number of the last frame received  
• Receiver also maintains the following invariant 
• LAF – LFR ≤ RWS  

 

 

                                                            Sliding Window on Receiver

 

• When a frame with sequence number SeqNum arrives, what does the receiver do? 
• If SeqNum ≤ LFR or SeqNum > LAF
• Discard it (the frame is outside the receiver window)   
• If LFR < SeqNum ≤ LAF
• Accept it 
• Now the receiver needs to decide whether or not to send an ACK