7 min read
On this page

Data Link Layer

The data link layer provides reliable communication over a physical link — framing bits into frames, detecting/correcting errors, and controlling access to the shared medium.

Framing

Byte Count

First byte of each frame indicates the frame length. Simple but one error in the count desynchronizes everything.

Byte Stuffing

Delimit frames with a special flag byte (e.g., 0x7E). If the flag appears in the data, escape it by preceding with an escape byte.

Used in PPP (Point-to-Point Protocol).

Bit Stuffing

Delimit with a flag pattern (e.g., 01111110). After every 5 consecutive 1s in data, insert a 0. Receiver removes the stuffed bit.

Used in HDLC.

Error Detection

Parity

Even parity: Add a bit so the total number of 1s is even. Detects any single-bit error.

2D parity: Arrange data in a matrix. Compute parity for each row AND column. Can detect and correct single-bit errors. Detects most double-bit errors.

Limitation: Parity detects errors but provides weak correction.

Checksums

Sum all data words. Store the checksum. Receiver recomputes and compares.

Internet checksum (TCP/IP): 16-bit one's complement sum of all 16-bit words. Simple and fast but weak — doesn't detect reordering.

CRC (Cyclic Redundancy Check)

Treat the bit string as a polynomial. Divide by a generator polynomial. Append the remainder as the CRC.

Data:      D = 1010001101  (polynomial: x⁹ + x⁷ + x³ + x² + 1)
Generator: G = 10011       (polynomial: x⁴ + x + 1)
CRC: remainder of D × x⁴ / G = 1110
Transmitted: 10100011011110

Receiver: Divide received data by G. If remainder is 0 → no error.

Detection capability: CRC-n detects all burst errors of length ≤ n, all odd numbers of errors (if G has x+1 as factor), most longer burst errors.

| CRC | Polynomial | Used In | |---|---|---| | CRC-8 | x⁸ + x² + x + 1 | ATM headers, Dallas 1-Wire | | CRC-16 | x¹⁶ + x¹⁵ + x² + 1 | USB, Modbus | | CRC-32 | x³² + x²⁶ + ... + 1 | Ethernet, ZIP, PNG, MPEG-2 | | CRC-32C | (different polynomial) | iSCSI, Btrfs, ext4, SCTP |

CRC-32: Detects all errors of ≤ 32 bits and virtually all longer errors. Hardware acceleration available (x86 crc32 instruction).

Error Correction

Hamming Codes

Add check bits at positions that are powers of 2 (1, 2, 4, 8, ...). Each check bit covers specific data bit positions.

For (7,4) Hamming code: 4 data bits + 3 check bits. Can correct any single-bit error and detect any 2-bit error (SECDED — with an extra overall parity bit).

Reed-Solomon Codes

Block codes over GF(2⁸). Can correct t symbol errors using 2t redundancy symbols.

Used in: CDs/DVDs, QR codes, deep-space communication, RAID, NAND flash.

Forward Error Correction (FEC)

Add redundancy so the receiver can correct errors without retransmission. Essential for high-latency or unreliable channels (satellite, deep space, wireless).

Modern FEC: LDPC codes, turbo codes, polar codes (approach Shannon limit).

Flow Control

Prevent a fast sender from overwhelming a slow receiver.

Stop-and-Wait

Send one frame, wait for ACK before sending the next.

Utilization: U = 1 / (1 + 2a) where a = propagation delay / transmission delay. Very low for high-latency links (U ≈ 1% for satellite).

Sliding Window

Allow multiple frames in flight simultaneously.

Window size W: Maximum number of unacknowledged frames.

Go-Back-N: On error, retransmit frame N and all subsequent frames. Receiver only accepts in-order frames. Simpler receiver but wastes bandwidth on errors.

Selective Repeat: On error, retransmit only the errored frame. Receiver buffers out-of-order frames. Better utilization but more complex.

Optimal window: W ≥ 1 + 2 × BDP / frame_size (to keep the pipe full).

Medium Access Control (MAC)

When multiple devices share a channel, MAC protocols determine who transmits when.

ALOHA

Pure ALOHA: Transmit whenever you have data. If collision (detected by missing ACK), wait a random time and retransmit. Maximum throughput: 18%.

Slotted ALOHA: Time divided into slots. Transmit only at slot boundaries. Maximum throughput: 37%.

CSMA (Carrier Sense Multiple Access)

"Listen before talk." Sense the channel before transmitting.

1-persistent: If channel idle → transmit immediately. If busy → wait, then transmit immediately when free. Collisions can still occur (two stations find the channel idle simultaneously).

Non-persistent: If busy → wait a random time, then re-sense. Fewer collisions but higher delay.

p-persistent: If idle → transmit with probability p, wait with probability 1-p. Compromise.

CSMA/CD (Collision Detection)

Used in Ethernet (wired). Listen while transmitting. If collision detected → abort, send jam signal, wait random backoff.

Binary exponential backoff: After k-th collision, wait a random time from [0, 2ᵏ-1] × slot_time. Maximum k = 10. After 16 collisions → give up.

Minimum frame size: Must be long enough that a collision is detected before transmission ends. Ethernet: 64 bytes (for 2500m cable + 4 repeaters at 10 Mbps).

Not used in modern Ethernet: Full-duplex switched Ethernet has no collisions (each link is point-to-point).

CSMA/CA (Collision Avoidance)

Used in Wi-Fi (wireless). Can't detect collisions during transmission (wireless = half-duplex, own signal drowns out others).

RTS/CTS: Sender sends Request To Send. Receiver replies Clear To Send. Other stations hear CTS and stay quiet. Solves the hidden terminal problem.

DIFS/SIFS: Different interframe spacings prioritize ACKs (short) over data (long).

Virtual carrier sensing: NAV (Network Allocation Vector) — stations hearing an RTS/CTS set a timer and stay quiet.

Ethernet (IEEE 802.3)

Ethernet Frame

[Preamble (7B)] [SFD (1B)] [Dest MAC (6B)] [Src MAC (6B)] [Type/Len (2B)] [Payload (46-1500B)] [CRC (4B)]

Preamble: 7 bytes of 10101010 for clock synchronization. SFD: 10101011 (Start Frame Delimiter). MAC addresses: 48-bit (6 bytes), globally unique. Written as XX:XX:XX:XX:XX:XX (hex).

Ethernet Evolution

| Standard | Speed | Medium | Year | |---|---|---|---| | 10BASE-T | 10 Mbps | Cat 3 twisted pair | 1990 | | 100BASE-TX | 100 Mbps | Cat 5 twisted pair | 1995 | | 1000BASE-T | 1 Gbps | Cat 5e/6 | 1999 | | 10GBASE-T | 10 Gbps | Cat 6a | 2006 | | 25GBASE-T | 25 Gbps | Cat 8 | 2016 | | 100GBASE-SR4 | 100 Gbps | Multi-mode fiber | 2010 | | 400GBASE-SR8 | 400 Gbps | Multi-mode fiber | 2017 |

MAC Addressing

MAC address: 48-bit hardware address burned into the NIC. Format: OUI (24 bits, manufacturer) + device ID (24 bits).

Special addresses: FF:FF:FF:FF:FF:FF = broadcast (all stations receive).

ARP (Address Resolution Protocol)

Maps IP addresses to MAC addresses on a local network.

1. A wants to send to 192.168.1.5 but only knows the IP.
2. A broadcasts ARP request: "Who has 192.168.1.5?"
3. The device with 192.168.1.5 replies: "I'm at MAC AA:BB:CC:DD:EE:FF"
4. A caches the mapping and sends the Ethernet frame.

ARP cache: Stores recent mappings (timeout: ~20 minutes). arp -a to view.

ARP spoofing: Attacker sends fake ARP replies → redirects traffic (man-in-the-middle). Mitigated by Dynamic ARP Inspection (DAI) on switches.

Switches

Learning Bridge Algorithm

  1. When frame arrives on port P from MAC A → record "A is on port P."
  2. When forwarding a frame to MAC B:
    • If B's port is known → forward only to that port.
    • If unknown → flood to all ports except source port.

MAC address table ages entries (typically 300 seconds). If no frame from A in 300 seconds → remove entry.

Spanning Tree Protocol (STP)

Prevents loops in switched networks (loops cause broadcast storms — frames circulate forever).

Algorithm (IEEE 802.1D):

  1. Elect a root bridge (lowest Bridge ID).
  2. Each switch finds the shortest path to root.
  3. For each LAN segment, elect a designated bridge (closest to root).
  4. Disable all other ports (blocking).

Result: A loop-free tree spanning all switches.

RSTP (Rapid STP, 802.1w): Faster convergence (~1-2 seconds vs ~30-50 seconds for STP).

VLANs (IEEE 802.1Q)

Virtual LANs: Logically segment a physical network. Devices in the same VLAN can communicate as if on the same physical LAN, even if on different switches.

802.1Q tag: 4-byte tag inserted in the Ethernet frame (after source MAC):

[TPID (0x8100)] [Priority (3 bits)] [DEI (1 bit)] [VLAN ID (12 bits)]

12-bit VLAN ID → up to 4094 VLANs (0 and 4095 reserved).

Trunk ports: Carry frames from multiple VLANs (tagged). Access ports: Connect to end devices (untagged — tag is added/removed by the switch).

Benefits: Security (isolate departments), performance (limit broadcast domain), flexibility (move users without rewiring).

Applications in CS

  • Data center design: Switches, VLANs, STP form the foundation. Leaf-spine topology replaces traditional tree.
  • Network debugging: Understanding frames, MAC addresses, and ARP is essential for troubleshooting.
  • Security: MAC filtering, 802.1X port-based access control, DAI, DHCP snooping.
  • IoT: Constrained devices use lightweight data link protocols (BLE, Zigbee, Thread).
  • Software-defined networking: OpenFlow operates at the data link and network layers.