05 Link Layer
Table of Contents
Overview
The link layer (Data Link Layer) transfers frames between adjacent nodes over a link. It provides services to the network layer above and uses services from the physical layer below.
Link Layer Services
Framing
Encapsulate network layer datagram into frame
Link Access
Coordinate access to shared medium (MAC)
Reliable Delivery
Detect and correct errors (optional)
Error Detection
Detect bit errors in frames
Error Correction
Correct detected errors (FEC)
Flow Control
Pace sender/receiver
Link Layer Implementation
Where: Network adapter (NIC - Network Interface Card) or chip
Frame Structure
Error Detection
Detect errors in transmitted frames.
Parity Bit
Single-bit parity: Add 1 bit to make number of 1s even (or odd).
Limitation: Cannot detect even number of bit errors
Two-Dimensional Parity
Arrange bits in grid, compute parity for each row and column.
Checksum
Sum of data treated as integers, then complement.
Example (16-bit checksum):
Used in: IP, TCP, UDP
Weakness: Simple errors can cancel out
CRC (Cyclic Redundancy Check)
Most powerful error detection, widely used in link layer.
Key Idea: Treat bit string as polynomial, divide by generator polynomial.
Process:
Sender:
Data bits: D
Generator: G (r+1 bits)
Compute R = remainder of (D × 2^r) / G
Send: D concatenated with R
Receiver:
Receive: D' concatenated with R'
Compute: (D' × 2^r + R') / G
If remainder = 0 → no error detected
If remainder ≠ 0 → error detected
Example:
Standard Generators:
CRC-8: x^8 + x^2 + x + 1
CRC-16: x^16 + x^15 + x^2 + 1
CRC-32 (Ethernet): x^32 + x^26 + x^23 + ... + 1
Properties:
Detects all burst errors ≤ r bits
Detects all odd number of bit errors (if G has factor x+1)
High probability of detecting other errors
Multiple Access Protocols
Problem: How to coordinate access to shared broadcast channel?
Channel Partitioning
1. TDMA (Time Division Multiple Access)
Divide time into slots, each node gets fixed slot.
Pros: No collisions, fair Cons: Unused slots wasted, node must wait for its slot
2. FDMA (Frequency Division Multiple Access)
Divide spectrum into frequency bands, each node gets fixed band.
Pros: No collisions, simultaneous transmission Cons: Unused bandwidth wasted
3. CDMA (Code Division Multiple Access)
All nodes transmit simultaneously on same frequency, but with different codes.
Encode data with unique code
Receiver decodes with same code
Other signals appear as noise
Used in: Cellular networks (3G, 4G)
Random Access
Nodes transmit at full channel rate, collisions possible.
1. ALOHA
Simply transmit when you have data.
Pure ALOHA:
No coordination
If collision, wait random time and retransmit
Efficiency: ~18%
Slotted ALOHA:
Time divided into slots
Nodes transmit only at slot beginning
Efficiency: ~37%
2. CSMA (Carrier Sense Multiple Access)
Listen before transmit: If channel idle, transmit; if busy, defer.
Collision still possible: Due to propagation delay
3. CSMA/CD (with Collision Detection)
Used in Ethernet.
Detect collision while transmitting, abort immediately.
Binary Exponential Backoff:
Efficiency:
4. CSMA/CA (with Collision Avoidance)
Used in Wi-Fi (wireless can't detect collisions during transmission).
Algorithm:
Optional RTS/CTS (for hidden terminal problem):
Taking Turns
1. Polling
Master node invites slave nodes to transmit.
Pros: No collisions, efficient at high load Cons: Polling overhead, single point of failure (master)
2. Token Passing
Token circulates among nodes, node can transmit when it has token.
Pros: Decentralized, no collisions Cons: Token overhead, failure can disrupt entire ring
MAC Addresses
Media Access Control (MAC) address is a 48-bit identifier for network interface.
Format:
Structure:
Special Addresses:
Broadcast: FF:FF:FF:FF:FF:FF (all devices)
Multicast: First bit = 1
MAC vs IP:
Layer
Link (Layer 2)
Network (Layer 3)
Scope
Local link
Global (internetwork)
Portability
Stays with device
Changes with location
Assignment
Burned into NIC (usually)
Configured (DHCP, manual)
Format
48-bit, hex
32-bit (IPv4), dotted-decimal
ARP
Address Resolution Protocol maps IP addresses to MAC addresses.
ARP Operation
ARP Table
Each host maintains ARP cache.
Entries time out to handle changes (device replaced, IP reassigned).
ARP Across Subnets
If destination on different subnet, ARP for gateway router.
Ethernet
Dominant wired LAN technology.
Ethernet Standards
10BASE-T
10 Mbps
Cat 3 UTP
100m
100BASE-TX
100 Mbps
Cat 5 UTP
100m
1000BASE-T
1 Gbps
Cat 5e UTP
100m
10GBASE-T
10 Gbps
Cat 6a UTP
100m
100GBASE-SR4
100 Gbps
Multimode fiber
100m
Ethernet Frame Structure
Fields:
Preamble (7 bytes): 10101010... for synchronization
SFD (1 byte): Start Frame Delimiter, 10101011
Destination MAC (6 bytes)
Source MAC (6 bytes)
Type (2 bytes): Protocol type (0x0800 = IPv4, 0x86DD = IPv6)
Payload (46-1500 bytes): Data from network layer
FCS (4 bytes): Frame Check Sequence (CRC-32)
Minimum payload: 46 bytes (padded if necessary)
Ensures collision detection works correctly
Minimum frame 64 bytes ensures collision detected before transmission finishes
Ethernet Evolution
Half-Duplex (Legacy):
CSMA/CD
Shared medium (hub)
Collisions possible
Full-Duplex (Modern):
Point-to-point links (switch)
Simultaneous send/receive
No collisions, no CSMA/CD needed
Switches
Link-layer device: Operates at Layer 2, forwards frames based on MAC addresses.
Switch Functions
1. Forwarding: Use switch table to selectively forward frames
2. Learning: Build switch table by examining source MAC addresses
Switch Table
Switch Learning
Self-Learning Example
Switch vs Router
Layer
Link (Layer 2)
Network (Layer 3)
Addressing
MAC addresses
IP addresses
Forwarding
Learns via flooding
Computes via routing algorithms
Configuration
Plug-and-play
Requires configuration
Isolation
Same broadcast domain
Separate broadcast domains
Use
Within LAN
Between networks
VLANs
Virtual LANs partition switch into multiple virtual switches.
Wi-Fi
Wireless LAN based on IEEE 802.11 standards.
Wi-Fi Standards
802.11b
1999
2.4 GHz
11 Mbps
35m
802.11a
1999
5 GHz
54 Mbps
35m
802.11g
2003
2.4 GHz
54 Mbps
38m
802.11n (Wi-Fi 4)
2009
2.4/5 GHz
600 Mbps
70m
802.11ac (Wi-Fi 5)
2013
5 GHz
1.3 Gbps
35m
802.11ax (Wi-Fi 6)
2019
2.4/5 GHz
9.6 Gbps
30m
Wi-Fi Architecture
Infrastructure Mode:
Ad-Hoc Mode: Devices communicate directly (no AP)
CSMA/CA in Wi-Fi
Problem: Can't detect collisions during transmission (wireless)
Solution: Avoid collisions proactively
CSMA/CA Algorithm:
IFS (Inter-Frame Spacing):
SIFS (Short IFS): ~10μs, for ACKs, CTS
DIFS (DCF IFS): ~50μs, for data frames
Hidden Terminal Problem
Solution: RTS/CTS
Wi-Fi Frame
Wi-Fi Security
Evolution:
WEP (Wired Equivalent Privacy): Broken, insecure
WPA (Wi-Fi Protected Access): Better, but flawed
WPA2: Strong (AES encryption)
WPA3: Strongest (2018, mandatory since 2020)
WPA2 Authentication:
Pre-Shared Key (PSK): Password-based
Enterprise (802.1X): RADIUS server authentication
Summary
The link layer handles communication between adjacent nodes on a link:
Error Detection:
Parity: Simple, limited
Checksum: Medium strength
CRC: Strong, widely used in link layer
Multiple Access:
Channel partitioning: TDMA, FDMA (no collisions but waste capacity)
Random access: ALOHA, CSMA, CSMA/CD, CSMA/CA (efficient but collisions)
Taking turns: Polling, token passing (efficient, complex)
MAC Addresses:
48-bit physical address
Identifies network interface
ARP maps IP to MAC
Ethernet:
Dominant wired LAN
Frame: Preamble, addresses, type, payload, FCS
Modern: Full-duplex, switched, no collisions
Switches:
Layer 2 forwarding
Self-learning via flooding
Plug-and-play operation
Wi-Fi (802.11):
Wireless LAN
CSMA/CA (collision avoidance)
Hidden terminal problem → RTS/CTS
Security: WPA2/WPA3
References
Course Materials:
CSEE 4119: An Introduction to Computer Networks - Columbia University
Textbooks:
Kurose, James F., and Keith W. Ross. Computer Networking: A Top-Down Approach. 8th Edition, Pearson, 2021.
Standards:
IEEE 802.3: Ethernet
IEEE 802.11: Wi-Fi
IEEE 802.1Q: VLANs
Last updated