Framing and Error Detection in Network Protocols

Posted on Sep 8, 2024 in Computers

Framing and Error Detection

Framing: Breaking Down Data Streams

Framing involves dividing a stream of bits into smaller, digestible chunks called frames. This process offers several benefits:

  • Allows physical media to be shared.
  • Provides a manageable unit for error handling.

Frame Structure

A frame typically includes the payload (data) wrapped with additional information:

  • Header: Contains information like the source and destination addresses.
  • Trailer: Might include a checksum for error detection.

The frame serves as the basic unit of reception. It’s either delivered entirely or not at all (up to the maximum transmission unit, MTU). Some link layers require the absence of frames or minimum gaps between them.

Identifying Frames

Receivers need to identify the start and end of frames to interpret the data stream correctly. Different framing methods exist:

Fixed-Length Frames

Easy to manage but can be inefficient for variable-length payloads.

Explicitly Delimited Frames

  • Length-Based Framing: A length field indicates the frame size. Decoding errors can occur if the beginning of the frame is not identified correctly.
  • Sentinel-Based Framing: Special markers (bit, byte, or signal patterns) denote the start and end of frames. The marker cannot appear in the data, requiring techniques like stuffing.
    • Common pattern: 01111110 (0x7e)
    • Byte stuffing: Inserting a zero after five consecutive 1s in the data.
    • Character-level stuffing: Using STX and ETX flags.

Fixed-Duration Frames

Frames have a fixed duration (in seconds). This method requires tight clock synchronization between the sender and receiver.

Example: Synchronous Optical Network (SONET)

  • All frames have the same duration.
  • Each frame starts with signal bits, eliminating the need for stuffing.
  • Synchronization within frames is maintained using transitions.

Handling Framing Errors

Corrupted length fields, sentinels, or clock drift can lead to framing errors. Error detection mechanisms are necessary to identify corrupted data within frames.

Error Handling Techniques

Various methods ensure reliable data delivery:

  • Redundancy
  • Hamming Distance
  • Parity
  • Voting
  • 2D-Parity
  • Checksum
  • Cyclic Redundancy Check (CRC)

Reliable Data Delivery

Automatic Repeat Request (ARQ)

The receiver sends acknowledgments (ACKs) to confirm successful frame reception. The sender retransmits if an ACK is not received within a timeout period.

  • ACKs can also be lost, potentially leading to data duplication.
  • Sequence numbers help the receiver discard duplicate data while still sending ACKs.

Stop-and-Wait ARQ

  • Only one outstanding frame is allowed at a time.
  • Packets can be delayed, and sequence numbers can become very large.
  • Performance suffers if the transmission time of one packet is significantly less than the propagation delay.

Pipelined Transmission

  • Multiple packets are “in flight” simultaneously.
  • The receiver acknowledges the highest consecutive frame received.

Go-Back-N ARQ

  • Retransmits all packets from the point of loss.
  • Packets sent after the loss are ignored and resent.

Sliding Window Protocol

  • A single mechanism supports multiple outstanding packets, reliable delivery, in-order delivery, and flow control.
  • The sender and receiver maintain “window” abstractions to track outstanding packets.
  • The sender’s window bounds unacknowledged data. On timeout, it can implement either Go-Back-N or Selective Repeat (retransmitting only the lost packets).
  • The receiver buffers out-of-order data, acknowledges cumulatively, selectively, or negatively.

Retransmission Timing

The sender uses timers to decide when to retransmit. The timer should be based on the round-trip time (RTT).

  • Negative acknowledgments (asking for only the missing packet) can shorten timeouts.
  • Fast retransmit: The receiver acknowledges the last in-order packet. When the sender receives duplicate acknowledgments, it resends the missing packet.

Media Access Control

Channel Partitioning

Sharing media among multiple nodes requires channel partitioning techniques:

Frequency Division Multiple Access (FDMA)

Divides the bandwidth into separate frequency channels. Guard bands prevent interference between channels.

Time Division Multiple Access (TDMA)

Divides the channel into time slots, allowing multiple hosts to transmit in turns.

Code Division Multiple Access (CDMA)

All stations transmit simultaneously in the same frequency band using spread spectrum techniques. Each sender modulates their signal with a unique code, and the receiver uses a code filter to extract the desired signal.

ALOHA

A wireless communication protocol developed for the Hawaiian islands.

  • Stations transmit data whenever they have it.
  • Retransmission occurs after a random delay if no acknowledgment is received.
  • Prone to collisions.

Slotted ALOHA

Time is divided into equal-sized slots. Hosts transmit at the beginning of a slot, requiring time synchronization. The channel is useful for transmissions only 37% of the time at best.

Carrier Sense Multiple Access (CSMA)

Stations listen to the channel before transmitting to avoid collisions.

Non-Persistent CSMA

The station gives up or retransmits after a random delay if the channel is busy. This can lead to large delays when the channel is idle.

1-Persistent CSMA

The station transmits as soon as the channel becomes idle, potentially causing collisions if multiple stations are waiting.

P-Persistent CSMA

The station transmits with probability ‘p’ if the channel is idle and repeats the process if unsuccessful.

Collision Detection

Collisions can still occur in CSMA. The time it takes to detect a collision depends on the propagation delay of the medium.

Ethernet (IEEE 802.3)

Framing

Ethernet frames consist of a preamble, a 32-bit CRC, and variable-length data.

Performance

Ethernet performs better than ALOHA or CSMA in practice due to its larger frame sizes, which reduce the overhead of arbitration.

Factors Affecting Efficiency

  • Number of hosts
  • Packet size
  • Link length

Contention-Free Protocols

Polling

A master node invites slave nodes to transmit in turn. This method suffers from polling overhead, latency, and a single point of failure (the master).

Token Passing

A control token is passed sequentially between nodes, granting permission to transmit. This method can be fast for point-to-point links but has overhead, latency, and a single point of failure (the token).

Token Ring (802.5)

A token circulates a ring of nodes, granting permission to transmit. The sender injects the packet into the ring and removes it later. A maximum token holding time (THT) limits access time. This method provides round-robin service, acknowledgments, and priorities. Monitors track the ring’s health.

Fiber Distributed Data Interface (FDDI)

A high-speed token ring protocol offering fast, contention-free, fair, and prioritized access. Disadvantages include complexity, reliability, and scalability.

Why Ethernet Won

Failure Modes

  • Token rings: Network failure if the ring is broken.
  • Ethernet: Single node detachment does not affect the entire network.

Performance and Deployment

  • Good performance in common scenarios.
  • Completely distributed and easy to maintain.
  • Incremental deployment.
  • High volume leads to lower costs, further driving adoption.

Wireless Media Access

Wireless media access presents unique challenges:

  • Collision detection is not possible.
  • Transmitters have different coverage areas.
  • Hidden and exposed terminal problems.

CSMA with Collision Avoidance (CSMA/CA)

Stations choose a random backoff time (contention window) before transmitting. If a collision is inferred, the backoff time is increased exponentially. Acknowledgments indicate successful transmissions.

Request to Send/Clear to Send (RTS/CTS)

Used to avoid collisions by reserving the medium for a transmission.

802.11 a/b/g

  • Uses CSMA/CA for multiple access.
  • Optional RTS/CTS.
  • Supports both base station and ad-hoc modes.
  • Uses a physical layer header to indicate the data rate of the packet.
  • Network Allocation Vector (NAV) allows for long or multi-frame exchanges by reserving the channel for a specific duration.

Addressing Alternatives

Addressing Modes

  • Unicast: One destination.
  • Multicast: A group of nodes.
  • Broadcast: All nodes.

Dynamic Addressing

Addresses are chosen randomly. If an address is already in use, a different one is selected.

Static Addressing

Addresses are assigned permanently (e.g., Ethernet, 802.11, Token Ring).

IEEE Addressing

Structure

IEEE addresses are 6 bytes (48 bits) long.

Allocation

Each network adapter is given a globally unique address during manufacturing. The address space is allocated to manufacturers, with 24 bits identifying the manufacturer.

Reception

Frames are received by all adapters on the LAN but are dropped if the destination address does not match.

Special Addresses

  • Broadcast: ff:ff:ff:ff:ff:ff
  • Multicast: Adapters maintain a list of multicast groups they are interested in.

Non-Unique Addresses