reliable transmission is accomplished using a combination of two fundamental mechanisms:
- acknowledgments - small control frame sent back from receiver to sender saying it has received the frame
- timeouts - the action of sender waiting a reasonable amount of time to receive acknowledgement, otherwise retransmit the frame
ARQ (Automatic Repeat Request)
- types of ARQ algorithms
- stop-and-wait
- sliding window
- go back n
- selective acknowledgements
- concurrent logical channels
Stop-and-Wait
- after transmitting one frame, the sender waits for acknowledgement before sending the next frame
- if acknowledgement does not arrive after a certain period of time, the sender timeout and retransmit the original frame
- problem: suppose sender sends frame and receiver acknowledges it, but the acknowledgment lost. The sender times out and retransmits the original frame, but the receiver will think that it is the next frame, since it correctly received and acknowledged the first frame
- solution: include a 1-bit sequence number that takes on the values 0 or 1
Sliding Window
- sliding window protocol can be used to serve 3 roles
- reliably deliver frames across an unreliable link
- preserve order of frames transmitted and received
- support flow control - a feedback by receiver to sender
- Go Back N - How It Works
- the sender assigns a sequence number to each frame
- sender maintains 3 variables
- SWS (send window size) - upper bound on number of unacknowledged frames that the sender can transmit
- LAR - sequence number of the last acknowledged frame
- LFS - sequence number of the last frame sent
- sender maintains the invariant
- LFS - LAR <= SWS
- receiver maintains 3 variables
- RWS (receiver window size) - upper bound on number of out-of-order frames that the receiver is willing to accept
- LAF - sequence number of the largest acceptable frame
- LFR - sequence number of the last frame received
- receiver maintains the invariant
- LAF - LFR <= RWS
- to avoid problems: SWS < MaxSeqNum
- MaxSeqNum is the number of available sequence numbers
- Selective Acknowledgements
- a variant of sliding window where the receiver acknowledges the frames received rather than just the highest numbered frame received in order
- SWS = is selected according to how many frames we want to have outstanding on the link at a given time
- RWS = from 1 to SWS
- to avoid problems: SWS < (MaxSeqNum + 1)/2 when SWS = RWS
Concurrent Logical Channels (ARPANET protocol)
- idea: multiplex several logical channels onto a single point-to-point link and to run the stop-and-wait algorithm on each of these logical channels
- consequence of this approach:
- frames sent are not kept in order
- implies nothing about flow control