Data Link Frames and Error Handling — Week 5

Data Link Frame

• Data link frames serve as envelopes for data transmission in a layered TCP/IP stack. A frame encapsulates several parts:
  • Payload: the actual data to be transmitted
  • Headers for each TCP/IP layer (addresses, error detection/control information)
  • Data link layer header: source and destination addresses for the frame on the local network
  • Data link layer trailer: optional
  • Synchronization bits added to aid alignment and timing
• Frames are defined by the data link connections and carry all the information needed to deliver the payload across a single hop or local network segment.

Frame Components

• The TCP/IP layers involved in framing:
  • Transport layer: contains the port number identifying the destination application on the receiving device
  • Network layer: contains the IP address that uniquely identifies the destination computer across networks
  • Data link layer: contains the MAC (Media Access Control) address that uniquely identifies each device’s network port on the local network
• The frame structure typically appears as:
  • Synchronization bits (at the data link layer)
  • Data link layer header(s)
  • Network layer header(s)
  • Transport layer header(s)
  • Original data (payload)
  • Data link layer trailer

Errors and Noise

• Noise is always present in communication channels.
• If a line experiences excessive noise, the signal can be lost or corrupted.
• Systems should check for transmission errors and take action when errors are detected.
• Some systems discard data with errors without attempting recovery; others implement varying error control strategies.

Noise and Errors (visual concepts described)

• Noise can cause slower or faster effective data rates depending on error incidence and recovery strategies.
• High noise levels may cause multiple bits to be lost or corrupted.

Error Prevention, Detection, and Control

• Three broad categories of techniques:
  • Error Prevention: reduce the likelihood of errors occurring
  • Error Detection: identify when errors have occurred
  • Error Control: respond to detected errors (retry, correct, or tolerate)

Gaussian Noise

• Also known as thermal or white noise.

• Relatively constant and can be reduced using regenerators and filters.

• If white noise becomes too strong, it can completely disrupt the signal.

• Representation:

  • Illustration examples show increasing noise levels leading to more distortion: no noise, little noise, much noise.

Impulse Noise

• One of the most disruptive forms of noise.
• Random spikes of power that can destroy one or more bits of information.
• Difficult to remove from an analog signal because a spike may be hard to distinguish from the original signal.
• Can damage more bits if transmitted at a faster rate (bits closer together).

Crosstalk

• Unwanted coupling between two signal paths.
• Example: hearing another conversation on a landline.
• Relatively constant and can be reduced with proper shielding and layout.

Echo

• Reflective feedback of a transmitted signal as it travels through a medium.
• If echo is strong, it could interfere with the original signal.
• Relatively constant and can be significantly reduced with proper termination and impedance matching.

Jitter

• Timing irregularities during transmission of digital signals.

• Occurs when a digital signal is repeated or delayed irregularly.

• If severe, jitter forces systems to slow down transmission.

• Steps to reduce jitter include improved circuitry and timing control.

• Visualization: a clean digital waveform vs. a jittered one.

Attenuation

• The continuous loss of a signal’s strength as it travels through a medium.
• Remedied by amplifiers (analog systems) or repeaters (digital systems).

Error Prevention (Techniques by Error Type)

• Gaussian noise: install special analog filters; use digital regeneration for digital signals.
• Impulse noise: install analog filters; use digital signal processing for digital signals.
• Crosstalk: proper shielding on cables.
• Echo: proper termination on cables.
• Jitter: better-quality circuitry; fewer repeaters; slower transmission where possible.
• Attenuation: devices to amplify analog signals; digital regeneration for digital signals.
• Note: Attenuation is not an error type by itself, but it indirectly affects error rates.

Error Detection

• Even with prevention, errors may still occur.
• To detect errors, an extra error detection code is appended to the data.
• Three basic techniques: parity checking, arithmetic checksum, cyclic redundancy checksum.

Parity Checks

• Simple parity:
  • Even parity: add a parity bit so that the total number of 1s remains even.
  • Odd parity: add a parity bit so that the total number of 1s remains odd.
• Example: send 1001010 using odd parity (3 ones → parity bit 0), and 1001011 using even parity (4 ones → parity bit 1).
• Parity limitations:
  • Simple parity detects odd numbers of bit errors but may miss certain errors (e.g., flipping two bits).
  • Example: if 10010101 is sent and the first two 0s flip to 1s, the received character is 11110101, which may not show a parity error under simple parity.

Longitudinal Parity

• Adds parity bits to each row of a block of characters and then adds a row of parity bits for the columns (parity across the block).
• This 2D parity adds redundancy and improves error detection across a block.
• Example: rows and columns of parity bits are computed; two bits flipping can be detected with this scheme.

Parity Checks: Limitations

• Neither simple parity nor longitudinal parity catches all errors.
• Simple parity catches only odd-numbered bit errors; longitudinal parity improves detection but increases the number of check bits.
• A more powerful detection method is needed.

Arithmetic Checksum

• Used in TCP and IP on the Internet.

• Data are converted to numeric form, then summed; the sum is sent with the message (appended in some form).

• Simple example: a message’s numbers are added to produce a checksum value appended to the end of the message.

• Receiver performs the same summation and compares the computed sum with the transmitted sum.

• TCP/IP checksum logic is slightly more complex, but the core idea is the same.

• Simple illustration: sum of 7-bit numbers for a payload results in a checksum value (e.g., 1167 in the example) appended to the message.

• Limitation: arithmetic checksum can miss some error patterns; hence stronger methods like CRC are used.

Cyclic Redundancy Checksum (CRC)

• CRC treats the payload as a large polynomial and uses polynomial division with a generator polynomial.

• Transmitter: form message polynomial, divide by generator, append the remainder (the check bits) to the end of the message.

• Remainder size options: 8, 16, or 32 check bits.

• Key representation:

  • Transmitter: message(x) ÷ G(x) → remainder R(x); transmitted as message(x) || R(x)
  • Receiver: divide received message by G(x); if remainder is zero, no error is detected; otherwise, there was an error.

• Common generator polynomials (examples):

  • CRC-8: G_8(x) = x^8 + x^7 + x^6 + x^4 + x^2 + 1; common representation: 0x ext{D5}
  • CRC-12: G_{12}(x) = x^{12} + x^{11} + x^3 + x^2 + x + 1; representation: 0x80F
  • CRC-16 (CRC-16-IBM / CRC-CCITT variant context): G_{16}(x) = x^{16} + x^{15} + x^2 + 1; representation: 0x8005
  • CRC-CCITT (CRC-16-CCITT): G_{CCITT}(x) = x^{16} + x^{12} + x^5 + 1; representation: 0x1021
  • CRC-16 (Bluetooth common variant) and others: often listed under typical USB/Bluetooth contexts
  • CRC-32 (Ethernet standard): G_{32}(x) = x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1; representation: 0x04C11DB7

• CRC performance characteristics (typical):

  • Single-bit errors: 100% detection
  • Double-bit errors: 100% detection if generator polynomial has at least three 1s
  • Odd number of bits in error: 100% detection if generator contains a factor x + 1
  • Burst errors: certain lengths have near-100% detection depending on r (where r is the degree of the generator)

• Summary of CRCs and why they’re powerful:

  • CRCs are excellent at detecting common error patterns (bit flips, bursts)
  • They provide strong, probabilistic guarantees about error detection with minimal overhead
  • Different polynomials are chosen for different applications (e.g., Ethernet, USB, Bluetooth, digital satellite TV)

Error Control (What to do when an error is detected)

• After an error is detected, a receiver must decide how to respond. Options:
  • Do nothing (toss the frame/packet) – rely on higher-layer protocols to handle retransmission
  • Return an error message to the transmitter – request retransmission or error handling
  • Fix the error without involving the transmitter – forward error correction (FEC)

Do Nothing (Toss the Frame/Packet)

• A common scenario: an Ethernet switch discards a frame after CRC detects an error.
• The frame is discarded without a response; transport-layer or higher-layer protocols are responsible for retransmission or error handling.

Return A Message

• Error detected leads to a control message back to the transmitter.
• Two basic forms:
  • Stop-and-Wait Error Control
  • Sliding Window Error Control

Stop-and-Wait Error Control

• The simplest error control protocol.

• Operation:

  • Transmitter sends one frame, then stops and waits for an acknowledgment (ACK).
  • If ACK is received, the next frame is sent.
  • If a negative acknowledgment (NAK) is received or a timeout occurs, the same frame is transmitted again.

• Sequence numbers: transmitter uses 0,1,0,1,… while receiver acknowledges 1,0,1,0,…

• Diagrammatic intuition: a single frame in flight at a time; the sender halts until an ACK indicates success.

Sliding Window Error Control

• More efficient than Stop-and-Wait by allowing multiple frames (or bytes) to be in transit before waiting for ACKs.

• Key ideas:

  • The transmitter can send a window of frames up to a chosen window size before needing ACKs.
  • The receiver’s ACK acknowledges the next expected frame (or the last received in-order frame), allowing the sender to advance its window.

• Example concepts:

  • ACKs can carry the number of the next frame expected by the receiver (cumulative acknowledgement).
  • Window sizes and timing determine throughput and efficiency.

• Practical details (as in TCP/IP):

  • Rule 1: If a receiver has data to send, piggyback an ACK with its data.
  • Rule 2: If no data to send and last ACK was sent, wait 500 ms for another packet; if another packet arrives during the wait, send the ACK immediately.
  • Rule 3: If no data to send and last ACK was sent, wait 500 ms; if no packet arrives, send an ACK when needed.

• Visual scenarios described:

  • Multiple frames in flight with a given window (e.g., bytes 201-350 and 351-700 in buffers) and corresponding ACKs.
  • Out-of-order delivery and buffering behavior when packets arrive out of sequence.
  • Handling of lost packets and lost ACKs via timeouts and retransmissions.

• Practical implications:

  • Sliding window increases throughput over unreliable or high-latency links.
  • Proper window sizing balances throughput against buffering and potential reordering.

Time-out and Retransmission Scenarios

• If a packet is lost:
  • The next packet may arrive out of sequence and be buffered until the missing packet is retransmitted.
• If an ACK is lost:
  • The sender waits for a timeout and then retransmits the last packet.
  • Time-out triggers retransmission to recover from the missing ACK.

Forward Error Correction (FEC)

• FEC aims to correct errors without requiring retransmission from the transmitter.

• This requires adding redundancy to the transmitted data so the receiver can detect and correct errors.

• Common approach: Hamming codes (and other more powerful codes) with additional check bits.

• Hamming codes overview:

  • Add extra check bits to data to allow detection and correction of bit errors.
  • Hamming distance concept: the smallest number of bit differences between any two valid code words.
  • To create a self-correcting code, design the code with an appropriate Hamming distance.

• Example Hamming code (8 data bits, 4 check bits):

  • Data bits: b12, b11, b10, b9, b7, b6, b5, b3
  • Check bits: c8, c4, c2, c1
  • Ordering of bits in the transmitted block: b12, b11, b10, b9, c8, b7, b6, b5, c4, b3, c2, c1
  • Check bit roles:
  • c8 checks bits b12, b11, b10, b9
  • c4 checks bits b12, b7, b6, b5
  • c2 checks bits b11, b10, b7, b6, b3
  • c1 checks bits b11, b9, b7, b5, b3

• Example scenario (bit flip detection):

  • If bit b9 flips, the check bits appear as:
  • c8: 01000
  • c4: 00101
  • c2: 100111
  • c1: 100011
  • Written in parity-error sequence as 1001, which corresponds to the 9th bit position. This identifies the exact location of the error for correction.

• Extensions and usage:

  • Forward error correction is used in real-time signal transmission (e.g., digital television) and long-distance data transmission.
  • Reed-Solomon codes are a common FEC family used in broadcasting and storage.

• Note on forward error correction in practice:

  • FEC trades extra redundancy for reduced need for retransmission, which is advantageous in real-time or latency-constrained environments.

Real-World Relevance and Connections

• Data link frames and error handling are foundational for reliable communication across local networks and the Internet.
• Error detection and correction mechanisms are designed to cope with typical channel impairments such as Gaussian noise, impulse noise, crosstalk, echo, jitter, and attenuation.
• The choice of error detection (parity, checksum, CRC) and error control (Stop-and-Wait, Sliding Window, FEC) reflects trade-offs among overhead, latency, complexity, and tolerance to different error patterns.
• CRCs and FEC codes are widely used in networking and storage systems to ensure data integrity with minimal performance penalties.

Summary of Key Points (quick reference)

• Data link frame components: payload, layer headers, synchronization bits, trailer.
• Frame components per TCP/IP layers: Transport (port), Network (IP), Data link (MAC).
• Types of noise and their impact on data integrity: Gaussian, impulse, crosstalk, echo, jitter, attenuation.
• Error prevention techniques: shielding, up-to-date equipment, proper use of repeaters/amplifiers, and respect for medium capacities.
• Error detection techniques:
  • Parity checks (simple parity, longitudinal parity) – limitations include incomplete detection.
  • Arithmetic checksum – sums numeric representations; vulnerable to some patterns.
  • Cyclic Redundancy Check (CRC) – robust, uses generator polynomials, supports various bit-lengths (8, 12, 16, 32, etc.).
• CRC generator examples and polynomials:
  • CRC-8: G_8(x) = x^8 + x^7 + x^6 + x^4 + x^2 + 1, representation: 0xD5
  • CRC-12: G_{12}(x) = x^{12} + x^{11} + x^3 + x^2 + x + 1, representation: 0x80F
  • CRC-16: G_{16}(x) = x^{16} + x^{15} + x^2 + 1, representation: 0x8005
  • CRC-CCITT: G_{CCITT}(x) = x^{16} + x^{12} + x^5 + 1, representation: 0x1021
  • CRC-32: G_{32}(x) = x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1, representation: 0x04C11DB7
• Error control strategies:
  • Do nothing (toss the frame) when an error is detected.
  • Return an error message to trigger retransmission (Stop-and-Wait or Sliding Window).
  • Forward error correction to correct errors without retransmission (e.g., Hamming codes, Reed-Solomon).
• Stop-and-Wait basics: one frame in flight; ACK/NAK governs retransmission.
• Sliding Window basics: multiple frames in flight; piggybacking of ACKs; receiver’s ACKs indicate next expected frame.
• Practical TCP/IP ACK rules (conceptually): piggyback ACKs with data, use 500 ms waiting policy when no data to send, and immediate ACKs if additional packets arrive.
• Forward error correction example demonstrates locating a single-bit error using parity checks across data and check bits; the 4 parity bits yield a binary index for error location.