Lecture Notes: Error Detection and Correction in Networking

Introduction

• Revisiting a topic from section 3.3 on the UDP protocol, focusing on error detection and correction at the link layer.
• Internet checksum is used for error detection in datagrams by UDP.
• At the link layer, focus shifts to frames and two key points:
  1. Error correction without re-transmissions.
  2. Introduction to cyclic redundancy check (CRC) for error detection.

Error Detection and Correction Scenario

• Network layer passes datagrams to link layer for transmission, converting them into frames.
• Frames include error detection and correction bits (EDC).
• Transmission over link may introduce bit errors, checked at the receiver.
• If errors are detected, the frame may be dropped or retransmission initiated.

Parity Checking

Simple Parity Check

• Parity bit ensures total number of bits (original + parity) is even (even parity).
• Receiver checks for even number of one-valued bits.
  • Odd count indicates error.
  • Even count suggests no errors or even number of errors.

Two-Dimensional Parity Check

• Arranging bits in a grid; computing parity for each row and column.
• Detects and corrects single bit errors without re-transmission.
• Example:
  • Grid with parity error in specific rows/columns identifies flipped bit.

Forward Error Correction Techniques

• Used in DVDs, DSL, and deep space communication.
• Allows error correction upon receipt, avoiding delays from retransmission.

Internet Checksum

• Similar to parity, but sums bytes instead of bits.
• Used on the sender side to compute the checksum, sent with data.
• Receiver performs similar concept of error checking.
• Not used in link layer protocols due to lack of strength.

Cyclic Redundancy Check (CRC)

• More powerful than checksum for error detection.
• Involves a generator (g), a standardized pattern of bits.
• CRC-32 (IEEE standard) uses a 32-bit generator.
• Data plus CRC bits (d+r) are computed for divisibility by generator g.

Computation of CRC

• Sender computes CRC bits such that the frame is divisible by g.
• Receiver checks by dividing received bits by g; non-zero remainder indicates error.
• CRC detects all consecutive bit errors of less than r+1 bits.

Example Calculation

• Toy example of a 4-bit generator; division process illustrated.
• Remainder from division used as CRC bits to be sent.

Conclusion

• Overview of error detection/correction at the link layer.
• Emphasis on forward error correction and CRC's practical application.
• Importance of CRC codes in Ethernet and Wi-Fi for error detection.