Foundations of Computer Networks

TL;DR

You'll learn how routers decide paths (link-state's Dijkstra vs distance-vector's Bellman-Ford), how bits get checked for errors (parity, checksums, CRC), and how LANs actually move frames (CSMA/CD, ARP, Ethernet, switches). Together these cover Chapter 5's control plane and Chapter 6's link layer — the two layers that make "the network" actually work, not just carry bits.

1. The Mental Model

Routing is planning the whole trip; forwarding is glancing at the exit sign at each interchange. The link layer is the "last mile" logic: how two directly connected devices actually agree on who talks when, and how they catch a bit flipped by noise. Control plane answers "which way?"; link layer answers "how do we not collide, and did the message arrive intact?"

2. The Core Material

2.1 Routing Algorithms: Link-State vs Distance-Vector (pp 378–394)

Photo by Google DeepMind on Pexels

A routing algorithm's job: compute good paths and fill every router's forwarding table. Two families solve this very differently.

Link-State (LS), uses Dijkstra's algorithm. Every router floods a Link-State Packet (LSP) to all other routers, announcing its direct neighbors and link costs. After flooding, every router has the entire network map. Each router then runs Dijkstra's shortest-path algorithm locally on that map to compute its own shortest paths to everyone. Because every router sees the same global picture, LS converges fast and predictably — but a single router lying about its costs can poison the whole network's view.

Distance-Vector (DV), uses the Bellman-Ford equation. Each router knows only its direct neighbors' costs. It keeps a vector of its best-known distance to every destination, and periodically exchanges that vector with its direct neighbors only (no flooding). The update rule is:

$$d_x(y) = \min_{v \in N(x)} \{ c(x,v) + d_v(y) \}$$

Read this as: "my best distance to y is the smallest sum of (cost to a neighbor v) + (that neighbor's best distance to y), over all my neighbors." Each router recomputes this whenever a neighbor's vector changes, and iterates until nothing changes — that's convergence. DV is cheap to run (no full map needed) but slow to propagate bad news: if a link dies, routers can bounce distance estimates back and forth, slowly creeping toward infinity — the classic count-to-infinity problem.

graph LR
    A((A)) -- 1 --> B((B))
    A -- 4 --> C((C))
    B -- 2 --> C
    B -- 6 --> D((D))
    C -- 3 --> D

This 4-node graph is the one used in the Worked Example below, for both algorithms.

2.2 Link-Layer Error Detection (pp 454–460)

Photo by Miguel Á. Padriñán on Pexels

Bits get flipped by electrical noise, so every frame carries extra bits purely to catch errors.

Parity check. Add one bit so the total number of 1s is even (even parity). A single-bit flip is always caught because it changes the count's parity. Weakness: two flips cancel out and slip through undetected. Two-dimensional parity arranges data in a grid, computes a parity bit per row and per column — this not only detects but can correct a single-bit error, since the intersection of the failed row and column pinpoints the bad bit."

Checksum (Internet checksum). Treat the data as a sequence of 16-bit integers, add them with wraparound (end-around carry), then send the one's complement of the sum. The receiver adds everything including the checksum; if the result is all 1s, the frame is accepted. Cheap to compute, but weak — it can miss errors that reorder bytes or cancel out in the sum.

CRC (Cyclic Redundancy Check). Treat the data bits as a polynomial. Both sender and receiver agree on a generator polynomial G of r+1 bits. The sender appends r zero bits to the data D, divides by G using modulo-2 (XOR) division, and the remainder R becomes the frame check sequence sent with D. The receiver divides the received bits (D and R together) by G; a zero remainder means no detected error. CRC catches far more error patterns than checksums and is what real Ethernet hardware uses.

2.3 Multiple Access & Switched LANs (pp 461–508)

Photo by Brett Sayles on Pexels

When many devices share one link (a "multiple access channel"), something must decide who transmits when.

CSMA/CD (Carrier Sense Multiple Access with Collision Detection) — classic Ethernet's rule: listen before transmitting (carrier sense); if two stations transmit together, detect the collision, stop immediately, and each waits a random backoff time before retrying (binary exponential backoff doubles the range after each collision). This only works on shared broadcast media like old coax/hub Ethernet.

Link-layer addressing & ARP. Every network interface has a fixed 48-bit MAC address, burned into hardware, globally unique (in principle), flat (no hierarchy like IP). To send a frame on a LAN you need the destination's MAC address, but you usually only know its IP address — that's what ARP (Address Resolution Protocol) solves. The sender broadcasts an ARP query ("who has IP X?") to everyone on the LAN; the host owning that IP replies directly with its MAC address. Results get cached in an ARP table to avoid repeating the broadcast every time.

Ethernet. The dominant wired LAN technology. A frame has: preamble (sync bits), destination MAC, source MAC, type field, payload (data), and a CRC trailer. It's connectionless (no handshake) and unreliable (no ACK) — any reliability is pushed up to transport layer protocols like TCP.

Switches. A link-layer switch is smarter than a hub: it's plug-and-play, self-learning. It builds a switch table by watching incoming frames' source MAC addresses and which port they arrived on. To forward a frame, it looks up the destination MAC: if known, send out only that one port; if unknown, flood out all ports except the one it came from. This gives each pair of hosts a private, collision-free link — switches eliminate the need for CSMA/CD entirely in modern full-duplex LANs.

flowchart TD
    Frame["Frame arrives on Port 3"] --> Learn["Learn: Source MAC -> Port 3"]
    Learn --> Lookup{"Destination MAC in table?"}
    Lookup -- Yes --> Forward["Forward out matched port only"]
    Lookup -- No --> Flood["Flood out all ports except Port 3"]

3. Worked Example

Using the graph in Section 2.1 (A-B=1, A-C=4, B-C=2, B-D=6, C-D=3):