Automatic Repeat Request (ARQ)

Automatic Repeat Request (ARQ)
An Introduction

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Motivation

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

Stop-and-Wait ARQ

Stop-and-Wait ARQ (cont.)

An Example

Go-Back-N ARQ

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.)

Example of a Lost/Corrupted Frame

An Analysis of Go-Back-N ARQ

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

Based On:
- Go-Back-N ARQ
Changes:
- Each frame must be acknowledged individually
- The transmitter only retransmits frames for which a NAK is received