The link layer, LANs and Ethernet

The network layer gets a datagram from one host to another across many links; the link layer moves it across each individual link, from one node to the next. Nodes are hosts and routers, and links are the copper, fibre and radio channels between neighbours. The link layer is where networking meets hardware: it is implemented largely in network interface cards and their drivers. This lesson covers the services the link layer offers, error detection with parity and cyclic redundancy checks, how many nodes share a single broadcast medium with multiple access protocols, the MAC addresses and ARP that connect the link layer to IP, and Ethernet, switches and VLANs, which together build the local area networks in homes, offices and data centres. DCE-210 and DCE-320 cover data centre networking and cabling; here the focus is on the protocols.

Link-layer services

Every link-layer protocol does framing: it wraps each network-layer datagram in a frame with a header and often a trailer. Beyond that, services vary with the kind of link. Link access rules, the medium access control (MAC) protocol, decide when a node may transmit on a shared medium. Many link layers detect bit errors, and some correct them. Some provide reliable delivery between neighbours: Wi-Fi acknowledges and retransmits frames because radio links lose many, while wired Ethernet does not, because its error rate is so low that end-to-end recovery by TCP is enough. Some provide flow control between adjacent nodes.

There are two broad kinds of link. A point-to-point link connects exactly two nodes, such as a fibre between two routers or the link from a computer to a switch port. A broadcast link connects many nodes to one shared medium, such as early coaxial Ethernet, Wi-Fi and cable access networks; every frame sent is heard by every node, which raises the multiple access problem discussed below.

Error detection and correction

Bits get corrupted on links by electrical noise, interference and signal fading. The simplest check is a single parity bit, chosen so that the total number of 1s is even; it detects any odd number of flipped bits but misses even numbers, and errors often come in bursts. Two-dimensional parity arranges data in rows and columns with a parity bit for each; a single flipped bit then shows up in exactly one row and one column, so the receiver can not only detect but correct it, an example of forward error correction.

# Two-dimensional parity can locate and correct a single-bit error
rows = ["1010", "1111", "0110"]
bits = [[int(b) for b in r] for r in rows]
row_par = [sum(r) % 2 for r in bits]
col_par = [sum(c) % 2 for c in zip(*bits)]
print("row parity", row_par, "column parity", col_par)
bits[1][2] ^= 1                                   # flip one bit in transit
bad_row = [i for i, r in enumerate(bits) if sum(r) % 2 != row_par[i]]
bad_col = [j for j, c in enumerate(zip(*bits)) if sum(c) % 2 != col_par[j]]
print("error detected at row", bad_row, "column", bad_col)
bits[bad_row[0]][bad_col[0]] ^= 1                 # correct it
print("corrected:", ["".join(map(str, r)) for r in bits] == rows)

row parity [0, 0, 0] column parity [0, 0, 1, 1]
error detected at row [1] column [2]
corrected: True

Link layers in practice use cyclic redundancy checks (CRCs). Sender and receiver agree on an \(r+1\)-bit generator \(G\). For \(d\) data bits \(D\), the sender appends \(r\) bits \(R\) chosen so that the \(d + r\) bits, viewed as a polynomial with coefficients in modulo-2 arithmetic, are exactly divisible by \(G\). In modulo-2 arithmetic, addition and subtraction are both exclusive-or with no carries, so the division is a sequence of shifts and XORs that hardware performs at line rate. The receiver divides what it receives by \(G\); a nonzero remainder means an error. A CRC with an \(r\)-bit check detects every burst error of \(r\) or fewer bits and almost all longer ones.

import zlib
def crc_remainder(data_bits: str, gen: str) -> str:
    """Mod-2 long division: remainder of data * 2^r divided by the generator."""
    r = len(gen) - 1
    bits = list(data_bits + "0" * r)
    for i in range(len(data_bits)):
        if bits[i] == "1":
            for j, g in enumerate(gen):
                bits[i + j] = str(int(bits[i + j]) ^ int(g))
    return "".join(bits[-r:])
D, G = "101110", "1001"                     # textbook-sized example: r = 3
R = crc_remainder(D, G)
print("data", D, "generator", G, "-> CRC bits", R, "-> send", D + R)
print("receiver remainder:", crc_remainder(D + R, G))           # all zeros: accept
print("after a burst error:", crc_remainder("101011" + R, G))   # nonzero: reject

frame = b"Saturday shift: 3 volunteers needed"
fcs = zlib.crc32(frame)                     # the same CRC-32 polynomial Ethernet uses
print(f"CRC-32 of the frame: 0x{fcs:08x}")
damaged = bytearray(frame); damaged[5] ^= 0b0010_0000
print("CRC-32 detects the change:", zlib.crc32(bytes(damaged)) != fcs)

data 101110 generator 1001 -> CRC bits 011 -> send 101110011
receiver remainder: 000
after a burst error: 101
CRC-32 of the frame: 0xce2e43a4
CRC-32 detects the change: True

Ethernet's frame check sequence is CRC-32, the same polynomial used by zlib and PNG files. Links that are especially noisy, such as cellular and Wi-Fi radio, add forward error correction codes that let the receiver repair many errors without retransmission, at the cost of extra bits. Recall from lesson 6 that the internet checksum used above the link layer is much weaker than a CRC; the combination of a strong link-layer CRC with an end-to-end checksum gives defence in depth.

Multiple access protocols

When many nodes share one broadcast channel, two simultaneous transmissions collide and both are garbled. A multiple access protocol coordinates transmissions. Ideally, with a channel of rate \(R\), a single active node should send at \(R\), \(M\) active nodes should each average \(R/M\), the protocol should be decentralized so no master node can fail, and it should be simple. Protocols fall into three classes.

Slotted ALOHA, developed for the University of Hawaii's ALOHAnet radio network in 1970, is the simplest random access protocol to analyse. Time is divided into slots the length of one frame. A node with a frame transmits at the start of the next slot; if a collision occurs, it retransmits in each later slot with probability \(p\) until it succeeds. With \(N\) busy nodes, a slot is successful when exactly one node transmits, which happens with probability \(Np(1-p)^{N-1}\). Choosing \(p = 1/N\) maximizes this, and as \(N\) grows the maximum efficiency approaches \(1/e \approx 0.37\): at best 37% of slots carry a successful frame. Pure, unslotted ALOHA is half as efficient, because a frame can collide with frames that started up to one frame time before or after it.

import math, random
# Efficiency of slotted ALOHA with N nodes each transmitting in a slot with probability p
def slotted(N, p):
    return N * p * (1 - p) ** (N - 1)
for N in (2, 10, 50, 1000):
    p = 1 / N                                   # the best choice of p
    print(f"N = {N:4d}: best efficiency {slotted(N, p):.4f}")
print(f"limit 1/e = {1/math.e:.4f}; pure ALOHA limit 1/(2e) = {1/(2*math.e):.4f}")

# Simulate slotted ALOHA to check the formula
random.seed(10)
N, p, slots = 20, 1 / 20, 100_000
success = sum(1 for _ in range(slots) if sum(random.random() < p for _ in range(N)) == 1)
print(f"simulated efficiency with N = 20: {success / slots:.4f}  (formula {slotted(20, 1/20):.4f})")

N =    2: best efficiency 0.5000
N =   10: best efficiency 0.3874
N =   50: best efficiency 0.3716
N = 1000: best efficiency 0.3681
limit 1/e = 0.3679; pure ALOHA limit 1/(2e) = 0.1839
simulated efficiency with N = 20: 0.3760  (formula 0.3774)

Carrier sense multiple access (CSMA) improves on ALOHA by listening before transmitting: a node does not start sending while it hears someone else. Collisions can still happen because of propagation delay: two nodes may both hear silence and start at almost the same moment. CSMA with collision detection (CSMA/CD), used by classic shared Ethernet, adds a second rule: a node keeps listening while it transmits and aborts as soon as it detects a collision, sending a short jam signal. It then waits a random time chosen by binary exponential backoff: after the \(n\)th collision in a row, it picks \(K\) at random from \(\{0, 1, \dots, 2^n - 1\}\), with \(n\) capped at 10, and waits \(K\) times 512 bit times. The more collisions, the wider the range, which adapts automatically to the number of competing nodes.

For collision detection to work, a node must still be transmitting when news of a collision arrives from the far end of the network, which takes up to twice the one-way propagation delay. This is why Ethernet has a minimum frame size of 64 bytes and why shared Ethernet segments had a maximum diameter.

# CSMA/CD: minimum frame size and binary exponential backoff
R = 10e6                       # classic 10 Mbit/s Ethernet
d, s = 2500, 2e8               # maximum span (m) and propagation speed (m/s), ignoring repeaters
tau = d / s
min_bits = 2 * tau * R
print(f"one-way propagation {tau*1e6:.1f} us; frame must last 2*tau -> at least {min_bits:.0f} bits")
print("Ethernet's 64-byte (512-bit) minimum covers this plus repeater delays")
import random
random.seed(3)
slot = 512 / R
for n in range(1, 11):
    K = random.randrange(2 ** min(n, 10))     # after the nth collision choose K in 0..2^n - 1
    print(f"collision {n:2d}: choose K from 0..{2**min(n,10)-1:4d}, picked {K:4d}, wait {K*slot*1e6:8.1f} us")

one-way propagation 12.5 us; frame must last 2*tau -> at least 250 bits
Ethernet's 64-byte (512-bit) minimum covers this plus repeater delays
collision  1: choose K from 0..   1, picked    0, wait      0.0 us
collision  2: choose K from 0..   3, picked    1, wait     51.2 us
collision  3: choose K from 0..   7, picked    5, wait    256.0 us
collision  4: choose K from 0..  15, picked   15, wait    768.0 us
collision  5: choose K from 0..  31, picked    4, wait    204.8 us
collision  6: choose K from 0..  63, picked    1, wait     51.2 us
collision  7: choose K from 0.. 127, picked  120, wait   6144.0 us
collision  8: choose K from 0.. 255, picked  132, wait   6758.4 us
collision  9: choose K from 0.. 511, picked  239, wait  12236.8 us
collision 10: choose K from 0..1023, picked  392, wait  20070.4 us

MAC addresses and ARP

Network interfaces have link-layer addresses, called MAC addresses, which are 48 bits long and written as six hexadecimal bytes such as a4:b1:c2:d3:e4:f5. Manufacturers buy blocks of addresses from the IEEE, so each interface traditionally has a unique, permanent address. (Phones and laptops now often use randomized MAC addresses for each Wi-Fi network to make tracking harder.) MAC addresses are flat, like a social insurance or social security number, while IP addresses are hierarchical, like a postal address: a MAC address does not change when a device moves, but its IP address does.

A host that wants to send a datagram to an IP address on its own subnet needs the corresponding MAC address. The Address Resolution Protocol (ARP, RFC 826) finds it: the host broadcasts an ARP request to the address ff:ff:ff:ff:ff:ff asking who has that IP address, and the owner replies directly with its MAC address. The host caches the answer for a few minutes. To send to a host on another subnet, the sender uses ARP to find its default gateway router's MAC address and sends the frame there; the router then repeats the process on the next link. IPv6 replaces ARP with the Neighbor Discovery Protocol, which uses ICMPv6 multicast instead of broadcast. Because ARP replies are not authenticated, an attacker on the same LAN can send forged replies to intercept traffic, ARP spoofing, which CISSP-113 lesson 3 discusses.

Ethernet

Ethernet, invented by Bob Metcalfe and colleagues at Xerox PARC in 1973 and standardized as IEEE 802.3, dominates wired LANs. Its success comes from being first, simple and cheap, and from evolving: speeds have grown from 10 Mbit/s to 400 Gbit/s and 800 Gbit/s while the frame format stayed the same. A frame has a preamble for clock synchronization, destination and source MAC addresses, a two-byte EtherType naming the payload protocol, 46 to 1,500 bytes of data (more with jumbo frames), and a four-byte CRC-32. Ethernet is connectionless and unreliable: a frame that fails its CRC is simply discarded. Early Ethernet used a shared coaxial bus and CSMA/CD; modern Ethernet uses a star of twisted-pair or fibre links to a switch, each link full-duplex, so there are no collisions at all and CSMA/CD is unused.

Link-layer switches

A switch forwards frames between its ports based on destination MAC addresses. It is self-learning: when a frame arrives, the switch records the source address and the port it came in on. To forward a frame, it looks up the destination address; if the address is known, the frame goes out only on that port, and if it is unknown or is the broadcast address, the frame is flooded out of every port except the one it arrived on. Entries expire after a few minutes, so the table tracks hosts that move. No configuration is needed: switches are plug and play.

# ARP resolution and a self-learning switch
arp_cache = {}
hosts = {"10.0.0.11": "aa:aa:aa:00:00:11", "10.0.0.12": "aa:aa:aa:00:00:12", "10.0.0.1": "aa:aa:aa:00:00:01"}
def arp(ip):
    if ip in arp_cache:
        return arp_cache[ip], "cache hit"
    mac = hosts[ip]                      # broadcast "who has ip?"; the owner replies by unicast
    arp_cache[ip] = mac
    return mac, "broadcast request, unicast reply"
for ip in ("10.0.0.1", "10.0.0.12", "10.0.0.1"):
    print("ARP", ip, "->", *arp(ip))

table = {}                               # MAC address -> switch port
def switch(frame_src, frame_dst, in_port):
    table[frame_src] = in_port           # learn where the sender is
    out = table.get(frame_dst)
    if frame_dst == "ff:ff:ff:ff:ff:ff" or out is None:
        return "flood to all ports except " + str(in_port)
    return "drop (same port)" if out == in_port else f"forward to port {out}"
frames = [("aa:aa:aa:00:00:11", "aa:aa:aa:00:00:01", 1), ("aa:aa:aa:00:00:01", "aa:aa:aa:00:00:11", 3),
          ("aa:aa:aa:00:00:12", "ff:ff:ff:ff:ff:ff", 2), ("aa:aa:aa:00:00:11", "aa:aa:aa:00:00:01", 1)]
for src, dst, port in frames:
    print(f"from {src[-2:]} to {dst[-2:]:2s} on port {port}: {switch(src, dst, port)}")
print("switch table:", {k[-2:]: v for k, v in table.items()})

ARP 10.0.0.1 -> aa:aa:aa:00:00:01 broadcast request, unicast reply
ARP 10.0.0.12 -> aa:aa:aa:00:00:12 broadcast request, unicast reply
ARP 10.0.0.1 -> aa:aa:aa:00:00:01 cache hit
from 11 to 01 on port 1: flood to all ports except 1
from 01 to 11 on port 3: forward to port 1
from 12 to ff on port 2: flood to all ports except 2
from 11 to 01 on port 1: forward to port 3
switch table: {'11': 1, '01': 3, '12': 2}

Switches and routers are both store-and-forward packet switches, but they differ. Switches are plug and play, forward at very high rates and are invisible to hosts, but they offer no protection against broadcast storms, and a network of switches must form a tree: redundant links that create loops would let flooded frames circulate forever, since Ethernet frames have no TTL. The Spanning Tree Protocol disables redundant links to keep a loop-free tree, at the cost of leaving capacity unused; large data centres instead run routed fabrics or newer protocols that use all links. Routers keep broadcast traffic within a subnet, use the network's redundancy through routing, and isolate faults, but need address configuration. Networks of a few hundred hosts are often switched; larger networks combine switched subnets joined by routers.

VLANs

A university might want separate LANs for students, staff and building controls for security and to limit broadcast traffic, without buying separate switches for each. Virtual LANs (VLANs, IEEE 802.1Q) divide one physical switch network into several logical ones. Each switch port is assigned to a VLAN, and frames are forwarded only among ports of the same VLAN. Trunk links between switches carry frames for many VLANs, each frame marked with a four-byte tag holding a 12-bit VLAN identifier and a three-bit priority. Traffic between VLANs must pass through a router, where it can be filtered.

import struct
# An 802.1Q tag inserted between the source address and the EtherType
dst, src = bytes.fromhex("aaaaaa000001"), bytes.fromhex("aaaaaa000011")
vid, pcp = 30, 5                                    # VLAN 30, priority 5 (voice)
tag = struct.pack("!HH", 0x8100, (pcp << 13) | vid)
frame = dst + src + tag + struct.pack("!H", 0x0800) + b"..IPv4 datagram.."
tpid, tci = struct.unpack("!HH", frame[12:16])
print(f"TPID 0x{tpid:04x}, priority {tci >> 13}, VLAN ID {tci & 0x0FFF}, then EtherType 0x{struct.unpack('!H', frame[16:18])[0]:04x}")
print("tag adds", len(tag), "bytes; VLAN IDs available:", 2 ** 12 - 2)

TPID 0x8100, priority 5, VLAN ID 30, then EtherType 0x0800
tag adds 4 bytes; VLAN IDs available: 4094