Computer Networking — Chapter 6: The Link Layer and LANs

Introduction to the Link Layer

The link layer is responsible for transferring a datagram from one node to an adjacent node over a single communication link.

Services Provided:

• Framing — encapsulating datagram into a frame (header + trailer)
• Error detection — detecting bit errors (caused by signal attenuation, noise)
• Reliable delivery — retransmission of lost/corrupted frames (rarely used on low-BER links)
• Multiple access — coordinating access to a shared broadcast channel

Where is the link layer implemented? On the network interface card (NIC) (e.g., Ethernet NIC, WiFi adapter). The NIC implements both link and physical layers.

Error-Detection and -Correction Techniques

Parity Checks

• Single parity bit: even/odd parity — detects odd number of bit errors
• Two-dimensional parity: detects and corrects single bit errors

Checksumming Methods

• Internet checksum (used in IP, TCP, UDP): one’s complement sum of 16-bit words
• Relatively weak error detection (can miss some multi-bit errors)

Cyclic Redundancy Check (CRC)

CRC: Given data D of d bits, generator G of r+1 bits, sender computes remainder R of r bits such that <D, R> is exactly divisible by G (mod 2 arithmetic). Receiver divides <D, R> by G; if remainder is non-zero, error detected.

Key properties:

• Detects all single-bit errors
• Detects all odd-bit errors (if G is a factor of x+1)
• Detects all burst errors of length <= r
• Very strong detection for longer bursts (probability = 1 - (1/2)^r)

Multiple Access Links and Protocols

Two types of links:

• Point-to-point: single sender, single receiver (e.g., PPP, DSL)
• Broadcast: shared medium (e.g., WiFi, Ethernet in legacy hub mode)

Channel Partitioning Protocols

Random Access Protocols

Slotted ALOHA:

• Nodes transmit only at slot boundaries
• If collision, retransmit with probability p
• Max efficiency: 1/e ≈ 0.37

Pure ALOHA:

• Nodes transmit immediately
• Max efficiency: 1/(2e) ≈ 0.18

CSMA (Carrier Sense Multiple Access):

• Listen before transmitting (carrier sensing)
• If channel busy, defer transmission
• Collisions still occur due to propagation delay

CSMA/CD (CSMA with Collision Detection): Used in Ethernet. Algorithm:

1. Sense channel; if idle, transmit; if busy, wait
2. If collision detected during transmission:
   • Abort transmission immediately
   • Send jam signal to ensure all nodes detect collision
   • Wait random time (exponential backoff), then retry

Ethernet exponential backoff: After m collisions, choose K randomly from {0, 1, …, 2^m-1}. Wait K * 512 bit times. m = min(n, 10). After 16 attempts, give up.

Efficiency of CSMA/CD: 1 / (1 + 5 * t_prop / t_trans)

Taking-Turns Protocols

• Polling: master node polls each slave; higher overhead, single point of failure
• Token passing: token circulates; only token holder transmits; token recovery overhead

DOCSIS (Data Over Cable Service Interface Specification):

• Cable Internet access protocol
• CMTS (headend) allocates time slots; cable modems request and use slots
• Combination of FDM (channels) + TDM/TDMA (time slots)

Switched Local Area Networks

Link-Layer Addressing and ARP

MAC Addresses:

• 48-bit globally unique address (burned into NIC ROM)
• Flat structure (not hierarchical), used by ARP and switches
• Format: 1A-2B-3C-4D-5E-6F (hex)

ARP (Address Resolution Protocol):

• Maps IP addresses to MAC addresses on a LAN
• ARP table: (IP, MAC, TTL) stored at each node
• ARP query: broadcast “who has IP X?”; ARP response: unicast “I am at MAC Y”
• Plug-and-play — table entries are created automatically

ARP operation example:

Ethernet

Ethernet Frame Structure:

Ethernet is connectionless and unreliable:

• No handshake between sender and receiver
• No ACK/NAK — data delivery is not guaranteed
• Recovery via higher-layer protocols (TCP)

Link-Layer Switches

Switch Forwarding/Filtering:

• Maintains a switch table: (MAC address, interface, TTL)
• Self-learning: when frame arrives, record sender’s MAC + incoming port
• Filter: if dest MAC is on same segment as source, drop (no need to forward)
• Forward: if dest MAC is known, forward to that port only; otherwise flood

Switches vs Routers:

Virtual Local Area Networks (VLANs)

• A switch can be logically partitioned into multiple isolated LANs
• Port-based VLAN: each port assigned to a VLAN
• Trunk ports carry traffic for multiple VLANs (802.1Q tagging)
• VLAN tag (12-bit VLAN ID) inserted between source MAC and Type field

Link Virtualization: MPLS

MPLS (Multiprotocol Label Switching):

• Adds a label (20 bits) between link and network layer headers
• MPLS-capable routers forward based on label, not IP address
• Enables traffic engineering, VPNs, faster forwarding (fixed-length label lookup)

Data Center Networking

• Top-of-Rack (ToR) switch: connects servers in a rack
• Spine-leaf topology: load balancing across multiple parallel paths
• Load balancing: ECMP (Equal-Cost Multi-Path) across multiple spine switches
• Full bisection bandwidth important for east-west traffic (server-to-server)

Retrospective: A Day in the Life of a Web Page Request

Sequence for requesting www.example.com:

1. DHCP: Computer boots, broadcasts DHCP discover; DHCP server offers IP, DNS, gateway
2. DNS: Computer sends DNS query to DNS server (via gateway router, intra-domain routing) to resolve www.example.com
3. ARP: Computer needs gateway’s MAC address; broadcasts ARP query
4. Intra-domain routing: DNS query forwarded through the AS to DNS server
5. TCP: TCP three-way handshake to www.example.com server
6. HTTP: HTTP GET request sent; server responds with the page