- Forward


Automatic Repeat Request (ARQ)
An Introduction


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Motivation
Back SMYC Forward
  • Unreliable Protocols:
    • A protocol that doesn't detect and correct lost and/or damaged messages is said to be unreliable
  • Automatic Repeat Request (ARQ) is Often Used to add Reliability:
    • Detect errors (e.g., using sequence numbers, parity checks, CRC)
    • Retransmit messages in the event of an error (i.e., be tenacious)
Common ARQ Schemes
Back SMYC Forward
  • Stop-and-Wait ARQ
  • Go-Back-N ARQ
  • Selective-Repeat ARQ
Stop-and-Wait ARQ
Back SMYC Forward
  • Based On:
    • Stop-and-Wait flow control
  • The Basics:
    • Frames have a 1-bit sequence number
    • ACKs include sequence numbers
    • Receiver sends an ACK 1-N if Frame N is receiveed
    • Transmitter waits for an ACK N before sending the Frame N
    • Transmitter retransmits Frame N if it does not receive ACK 1-N before the timeout-timer counts down
Stop-and-Wait ARQ (cont.)
Back SMYC Forward

An Example

stop-and-wait-ARQ
Go-Back-N ARQ
Back SMYC Forward
  • Based On:
    • Sliding window flow control
  • Changes:
    • If the transmitter sends all of the frames in its window and does not receive an ACK before the timeout-time counts down it will retransmit all of the frames in the window
  • Additions:
    • Receiver sends a NAK N if Frame N has an error (and then discards subsequent incoming frames until it receives Frame N)
    • If the transmitter receives a NAK N it retransmits Frame N and all subsequent frames that haven't been acknowledged
Go-Back-N ARQ (cont.)
Back SMYC Forward

Example of a Lost/Corrupted Frame

go-back-n-ARQ
An Analysis of Go-Back-N ARQ
Back SMYC Forward
  • Suppose:
    • The windows size is large
    • The product of delay and bandwidth is large
  • Implications?
    • A large number of packets are in the pipeline
    • An error in a packet causes a large number of packets to be retransmited, many of which needen't be
Selective-Repeat ARQ
Back SMYC Forward
  • Based On:
    • Go-Back-N ARQ
  • Changes:
    • Each frame must be acknowledged individually
    • The transmitter only retransmits frames for which a NAK is received
There's Always More to Learn
Back -