4005-741 -- Advanced Computer Networks

Alan Kaminsky

•

Department of Computer Science

•

Rochester Institute of Technology

•

4486 + 2220 = 6706

Home Page

Advanced Computer Networks

•

4005-741-01

•

Fall Quarter 2009

Course Page

4005-741-01 Advanced Computer Networks
Module 1C. Theory -- Error Control
Lecture Notes

Prof. Alan Kaminsky -- Fall Quarter 2009
Rochester Institute of Technology -- Department of Computer Science

Three Approaches

Error detection and retransmission
Erasure coding
Forward error correction

Error Detection and Retransmission

Also known as Automatic Repeat reQuest (ARQ)
Operation
- Receiver detects whether an error exists in a received packet
- If so, receiver discards the packet and requests transmitter to re-send packet
Error detection techniques
- Parity
- Cyclic redundancy check (CRC)
- Checksum
Parity
- Transmitter: Add one check bit = modulo-2 sum of the data bits
- Receiver: Verify that modulo-2 sum of the data and check bits = 0
- Can detect a single-bit error
Cyclic redundancy check
- With a generating polynomial of degree n:
  - There are n check bits
  - Can detect an error burst of up to n bits with probability 1
  - Otherwise, probability of undetected error is approximately 2⁻ⁿ
- Some generating polynomials:
  - CRC-16-ANSI = x¹⁶ + x¹⁵ + x² + 1
  - CRC-16-CCITT = x¹⁶ + x¹² + x⁵ + 1
  - CRC-32-IEEE 802.3 = x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1
- Transmitter:
  - Append n 0 bits to data bits
  - Treat the result as coefficients of a polynomial (mod 2)
  - Divide this polynomial by the CRC generator polynomial (mod 2)
  - Remainder polynomial = check bits
  - Send data bits plus check bits
- Receiver:
  - Treat the data bits plus check bits as coefficients of a polynomial (mod 2)
  - Divide this polynomial by the CRC generator polynomial (mod 2)
  - Verify that remainder = 0
- Can be done very easily in hardware with a shift register, no division circuits needed

CRC example

Generator polynomial = CRC-4-ITU = x⁴ + x + 1; represented as 10011

Transmitter:

Data = 10010110; represents x⁷ + x⁴ + x² + x
Data plus check bits = 100101100000; represents x¹¹ + x⁸ + x⁶ + x⁵

Divide data-plus-check polynomial by generator polynomial (only the mod 2 coefficients are shown):

            10001111
      +-------------
10011 | 100101100000
       -10011
        -----
         00011
        -00000
         -----
          00111
         -00000
          -----
           01110
          -00000
           -----
            11100
	   -10011
	    -----
	     11110
	    -10011
	     -----
	      11010
	     -10011
	      -----
	       10010
	      -10011
	       -----
	        0001

Remainder = check bits = 0001
Send 100101100001

Receiver:

Divide data-plus-check polynomial by generator polynomial:

            10001111
      +-------------
10011 | 100101100001
       -10011
        -----
         00011
        -00000
         -----
          00111
         -00000
          -----
           01110
          -00000
           -----
            11100
           -10011
            -----
             11110
            -10011
             -----
              11010
             -10011
              -----
               10011
              -10011
               -----
                0000

Remainder = 0, so no error detected

Receiver, with errors:

An error burst garbles the first four bits, 111101100001 received

Divide data-plus-check polynomial by generator polynomial:

            11100100
      +-------------
10011 | 111101100001
       -10011
        -----
         11011
        -10011
         -----
          10001
         -10011
          -----
           00100
          -00000
           -----
            01000
           -00000
            -----
             10000
            -10011
             -----
              00110
             -00000
              -----
               01101
              -00000
               -----
                1101

Remainder ≠ 0, so error detected

Checksum
- Internet Checksum: RFC 1071, RFC 1141, RFC 1624
- Transmitter:
  - Group pairs of bytes into words, first byte = most significant, second byte = least significant
  - Checksum = − sum of the words (mod 65535)
  - Append checksum to packet
- Receiver:
  - Group pairs of bytes into words, first byte = most significant, second byte = least significant
  - Verify sum of the words (mod 65535) = 0
- Probability of undetected error is approximately 2⁻¹⁶
Internet Checksum example
- Transmitter:
  - Packet bytes (decimal) = (58, 110, 67, 83, 69, 234)
  - Words (decimal) = (58⋅256+110, 67⋅256+83, 69⋅256+234) = (14958, 17235, 17898)
  - Checksum = −(14958 + 17235 + 17898) (mod 65535) = 15444 = 60⋅256+84
  - Send (58, 110, 67, 83, 69, 234, 60, 84)
- Receiver:
  - Packet bytes = (58, 110, 67, 83, 69, 234, 60, 84)
  - Words = (14958, 17235, 17898, 15444)
  - (14958 + 17235 + 17898 + 15444) (mod 65535) = 0; no error detected
- Receiver, with errors:
  - The second byte gets garbled
  - Packet bytes = (58, 254, 67, 83, 69, 234, 60, 84)
  - Words = (15102, 17235, 17898, 15444)
  - (15102 + 17235 + 17898 + 15444) (mod 65535) = 144 ≠ 0; error detected

Erasure Coding

Scenario
- For each packet the transmitter sends . . .
- Either the receiver receives the packet with no errors . . .
- Or the receiver does not receive the packet at all; the packet is "dropped" or "erased"
- Also, the receiver knows which packets are missing
Reasons for erasure
- Router congestion
- Error detected in received packet
Erasure coding
- The transmitter generates additional, redundant packets . . .
- That let the receiver calculate what was in the missing packets . . .
- Without having to request retransmissions
Erasure coding techniques
- Longitudinal parity
- Longitudinal parity with interleaving
- Two-dimensional parity
- Reed-Solomon codes
Longitudinal parity
- Transmitter:
  - For every n data packets, generate one redundant packet
  - Each byte of redundant packet = XOR of corresponding bytes of data packets
- Receiver:
  - If one of the n+1 packets is erased . . .
  - Each byte of erased packet = XOR of corresponding bytes of remaining packets
- Can tolerate erasure of one packet out of n

Longitudinal parity example

16 data packets, n = 16, each packet = 3 bytes (hexadecimal)

+----------+
| c8 d4 58 |  ^
+----------+  |
| 27 a1 10 |  |
+----------+  |
| 7e ba e6 |  |
+----------+  |
| ae 0f 7c |  |
+----------+  |
| 64 95 46 |  |
+----------+  |
| 19 4e 20 |  |
+----------+  |
| 15 6b 5c |  |
+----------+  |
| cf 07 87 |  |
+----------+ Data packets
| a8 a3 be |  |
+----------+  |
| 0e 92 b9 |  |
+----------+  |
| 37 09 ef |  |
+----------+  |
| d5 28 5e |  |
+----------+  |
| fa 28 2d |  |
+----------+  |
| c8 92 d4 |  |
+----------+  |
| 51 f1 3a |  |
+----------+  |
| 56 3f b8 |  v
+----------+
| e9 13 a2 | Redundant packet
+----------+

Longitudinal parity with interleaving
- Transmitter:
  - For every n×k data packets, generate k redundant packets
  - Arrange data packets into an n×k matrix
  - k redundant packets = longitudinal parity of the columns
- Receiver:
  - If one of the n+1 packets in a column is erased . . .
  - Each byte of erased packet = XOR of corresponding bytes of remaining packets
- Can tolerate erasure of one packet in each column
- Can tolerate erasure of k consecutive packets (assuming packets are transmitted by rows)

Longitudinal parity with interleaving example

16 data packets, n = 8, k = 2, each packet = 3 bytes (hexadecimal)

+----------+----------+
| c8 d4 58 | 27 a1 10 |  ^
+----------+----------+  |
| 7e ba e6 | ae 0f 7c |  |
+----------+----------+  |
| 64 95 46 | 19 4e 20 |  |
+----------+----------+  |
| 15 6b 5c | cf 07 87 |  |
+----------+----------+ Data packets
| a8 a3 be | 0e 92 b9 |  |
+----------+----------+  |
| 37 09 ef | d5 28 5e |  |
+----------+----------+  |
| fa 28 2d | c8 92 d4 |  |
+----------+----------+  |
| 51 f1 3a | 56 3f b8 |  v
+----------+----------+
| f3 e3 e2 | 1a f0 40 | Redundant packets
+----------+----------+

Two-dimensional parity
- Transmitter:
  - For every n×n data packets, generate 2n redundant packets
  - Arrange data packets into an n×n matrix
  - n redundant packets = longitudinal parity of the rows
  - n redundant packets = longitudinal parity of the columns
- Receiver:
  - If one of the n+1 packets in a row or column is erased . . .
  - Each byte of erased packet = XOR of corresponding bytes of remaining packets in the same row or column
- Can tolerate erasure of one packet in each row and one packet in each column
- Can tolerate erasure of k consecutive packets (assuming packets are transmitted by rows)

Two-dimensional parity example

16 data packets, n = 4, each packet = 3 bytes (hexadecimal)

                                                                Redundant
                   <--------------Data packets--------------->   packets
                  +----------+----------+----------+----------+----------+
               ^  | c8 d4 58 | 27 a1 10 | 7e ba e6 | ae 0f 7c | 3f c0 d2 |
               |  +----------+----------+----------+----------+----------+
               |  | 64 95 46 | 19 4e 20 | 15 6b 5c | cf 07 87 | a7 b7 bd |
     Data packets +----------+----------+----------+----------+----------+
               |  | a8 a3 be | 0e 92 b9 | 37 09 ef | d5 28 5e | 44 10 b6 |
               |  +----------+----------+----------+----------+----------+
               v  | fa 28 2d | c8 92 d4 | 51 f1 3a | 56 3f b8 | 35 74 7b |
                  +----------+----------+----------+----------+----------+
Redundant packets | fe ca 8d | f8 ef 5d | 0d 29 6f | e2 1f 1d |
                  +----------+----------+----------+----------+

Reed-Solomon coding
- For every n packets, generate k redundant packets
- Details: See "A tutorial on Reed-Solomon coding for fault-tolerance in RAID-like systems"
- Can tolerate erasure of any k packets
Probability of erasures
- p = probability of erasing a packet
- Assume erasures are independent
- Pr[n,k] = probability of erasing exactly k packets in a group of n packets = C(n,k) p^k (1 − p)^n−k
- C(n,k) = n! / k! / (n − k)!
- Probability of erasing anywhere from 0 to k packets in a group of n packets = Sum from i = 0 to k of Pr[n,i]

Forward Error Correction

Scenario
- Done at the bit level rather than the packet level
- Transmitter appends check bits to each data word
- Receiver uses check bits to detect and correct errors
Notation: "[n,k,d] code"
- Each codeword is n bits
- Each codeword contains k data bits (and n − k check bits)
- The minimum Hamming distance between any two codewords is d
To correct m errors, we need d ≥ 2m + 1
Hamming code
- A [2ⁱ − 1, 2ⁱ − 1 &minus i, 3] code for some i
- Can correct a one-bit error
- Details: See "The Hamming Code"
Golay code
- A [24, 12, 8] code
- Can correct up to three bit errors
- Used by the Voyager I and Voyager II spacecraft (1979−1981) to send pictures of Jupiter and Saturn
Reed-Solomon code
- Can also be used to correct errors, not just recover from erasures
- Used on compact discs to deal with scratches on the disc's surface
- Used on recent space missions like Mars Pathfinder

Usage

ARQ: Used universally in TCP
Erasure coding: ACK-less error control
- Best when packet loss probability is small
- Proactive erasure coding
- Reactive erasure coding; NACK-based protocols
- Reliable multicast protocols
FEC: Eliminates errors altogether (with high probability)
- Best when bit error rate is not too high, but packet loss rate is high
- Good for data links with large latency, where feedback from receiver to transmitter is undoable