ARQ Lab

Data Communication, Lecture 12. Send frames over a link that loses some of them. Compare Stop-and-Wait, Go-Back-N and Selective Repeat, work out how busy the link really is, see why the window size has a limit, and build HDLC and PPP fields. Works offline.

SenderReceiver
frameACKNAK✕ losttime runs downwards

Windows at time

Sender: acknowledged sent, waiting may send now outside window

Receiver: delivered stored, waiting for a gap window: accepts these

What happened

    Lose a frame, watch the recovery

    Frames transmittedOf which resentFinished atLink efficiency

    One cycle of Stop-and-Wait vs a full window

    Working

    
  
    
  
    
    
    How busy is the link?
    
    
    
    
    
    
    
    
    
    Stop-and-WaitWindow WW for 100%m (Go-Back-N)m (Sel. Repeat)
    
    
    a = propagation ÷ transmission time. Utilisation = W ÷ (1 + 2a), at most 100%.
    
  
    

    


    
  
    
    
    The scenario
    
      
    Sequence numbers in time order (the label is the number written in the frame):
    
      
    sender: sent, all ACKs lost resent after time-out
    
      
    receiver: already delivered its window now: it accepts these numbers
    
      
    
  
    
  
    
    
    Why the window has a limit
    
    
    
    
    
    Largest safe window
    
    
    Go-Back-N: window ≤ 2m − 1. Selective Repeat: window ≤ 2m−1. Push the slider one past the limit and the receiver mistakes an old frame for a new one.
    
  
    

    


    
  
    
    
    HDLC control field (bit 1 on the left, as sent)
    
      
    Whole frame: Flag 01111110 Address Control Information FCS Flag
    
    
    PPP byte stuffing (flag 7E, escape 7D)
    
      
    Frame: 7E · FF (address) · 03 (control) · protocol · payload · FCS · 7E. Payload bytes in, stuffed bytes out:
    
      
    Forouzan's simplified rule (insert 7D before 7E or 7D):
    
      
    Real PPP, RFC 1662 (insert 7D, then XOR the byte with 20):
    
      
    
  
    
  
    
    
    Build a frame's fields