COMPSCI 311 – Computer Network Architecture
Error Detection
Errors will happen
• Hardware
• Interference, link cuts, card failures, device failures, power outages
• Software
• Forwarding errors, routing errors
How to handle errors
• Error detection
• Need to at least detect that something went wrong
• If probability of failure is low, then retransmission should be enough
• Error correction
• Recover from errors when they occur
• Only useful against transmission errors, no help against permanent failures
How to handle errors
• Error detection
• Need to at least detect that something went wrong
• If probability of failure is low, then retransmission should be enough
• Error correction
• Recover from errors when they occur
• Only useful against transmission errors, no help against permanent failures
• Need additional information in packets to detect errors
• Overhead
• Need even more information to correct errors
Parity bits
• Add a redundant bit to ensure parity Data P Σ
• If no parity, then error has occurred 1 0 0 1 1 1 0 0 0 4
1 0 0 1 1 1 0 0 0 4
0 1 1 0 1 0 0 0 1 4
1 1 1 1 0 0 0 1 1 6
1 1 0 0 0 1 1 0 1 5
Parity bits
• Add a redundant bit to ensure parity Data P Σ
• If no parity, then error has occurred 1 0 0 1 1 1 0 0 0 4
1 0 0 1 1 1 0 0 0 4
0 1 1 0 1 0 0 0 1 4
• Fast 1 1 1 1 0 0 0 1 1 6
• Used in server RAM 1 1 0 0 0 1 1 0 1 5
• Misses many errors
• Any even number of bit flips is missed
• High overhead
• 11% in server memory
Checksum
• A checksum is any error-detection code based on addition
• Addition is easy in software, can be computed on CPUs
Checksum
• A checksum is any error-detection code based on addition
• Addition is easy in software, can be computed on CPUs
• Internet checksum
• Add up all 2-byte “words” in a message and transmit the result
• Receiver can recompute the sum and check for errors
Checksum
• A checksum is any error-detection code based on addition
• Addition is easy in software, can be computed on CPUs
• Internet checksum
• Add up all 2-byte “words” in a message and transmit the result
• Receiver can recompute the sum and check for errors
• Misses many errors
• For example, two errors may change two words by inverse amounts
• +x to one word and –x to another word = sum remains unchanged
• Not used in hardware
CRC (Cyclic Redundancy Check)
• A specific type of error detection code
• Convenient to implement in hardware using a shift register
CRC (Cyclic Redundancy Check)
• A specific type of error detection code
• Convenient to implement in hardware using a shift register
• CRC computation
• Sequence of bits considered a polynomial
• Divide the message by a generator polynomial
• Remainer is the CRC (subtracting it from the message ensures divisibility)
No need to learn how to compute a CRC by hand in this course.
CRC (Cyclic Redundancy Check)
• A specific type of error detection code
• Convenient to implement in hardware using a shift register
• CRC computation
• Sequence of bits considered a polynomial
• Divide the message by a generator polynomial
• Remainer is the CRC (subtracting it from the message ensures divisibility)
• “Good” generator polynomial ensures many classes of errors are caught
• All single-bit errors
• Double bit errors
• Odd number of errors
• Any burst of errors shorter than k bits
CRC is the choice in many link layer protocols
• BISYNC
• DDCMP
• HDLC
• Ethernet
• WiFi
