Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Routing: shortest path, flooding, distance vector and link state

Routing algorithms choose paths between network nodes; this note explains shortest-path (Dijkstra), flooding, distance-vector (Bellman–Ford style) and link-state methods, their equations, costs, and worked traces.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Routing decides how packets move from a source host to a destination across a network of routers. Engineers use routing algorithms to design, configure and troubleshoot routers and protocols (RIP, OSPF) so that traffic follows correct, efficient and stable paths.

Key ideas

Start with definitions (each term defined before use):

  • Routing: the process by which a network device selects a path over one or more links to send packets from a source to a destination. (Used to build routing tables that drive forwarding.)
  • Graph model: a network is modeled as a graph G = (V, E) with nodes V (routers) and edges E (links). Each edge (u, v) has a cost or weight c(u, v) ≥ 0 representing metric such as delay, bandwidth cost, hop count.
  • Path: a sequence of edges connecting two nodes. The path cost is the sum of edge costs along the path. A shortest path between node s and t is a path with minimum path cost.
  • Routing table: a table at each router with destination entries and next-hop information; built by the routing algorithm.
  • Forwarding: using the routing table to move an individual packet to the next hop.
  • Flooding: a packet distribution method where every incoming packet is forwarded on all outgoing links except the one it arrived on (repeat), with duplicate/loop control: e.g., include a per-source packet ID/sequence number and forward each packet ID at most once; a TTL/hop-limit only bounds lifetime and does not by itself prevent duplicates.
  • Distance-vector routing: a distributed routing method where each node maintains a distance vector — the current best-known cost to every destination — and periodically exchanges this vector with its neighbours. It uses the Bellman–Ford relaxation equation (below) to update costs.
  • Link-state routing: each node discovers the state (cost) of its directly attached links, floods this link-state information to all nodes, builds a complete map (graph) and runs a shortest-path algorithm (usually Dijkstra) locally to compute routes.
  • Convergence: the process and time taken for all routers' routing tables to stabilize after a topology or cost change.
  • Count-to-infinity: a failure mode of naive distance-vector protocols where incorrect increasing costs propagate slowly; solutions include split horizon, poison reverse and maximum cost (in RIP, 16 = infinity).

Exact statements and key derivations universities ask for:

  1. Bellman equation (used in distance-vector / Bellman–Ford): For node x, the estimated cost to destination y is D_x(y) = min_{v in N(x)} { c(x,v) + D_v(y) }, where N(x) is the set of neighbours of x and D_v(y) is v’s current estimate. Assumption: costs c(x,v) are non-negative and nodes exchange distance vectors periodically. In general, Bellman–Ford handles negative edge weights provided there are no negative cycles. Derivation idea: any shortest path from x to y must go via some neighbour v; pick the neighbour that minimizes the sum of the link cost to v and v's best cost to y.

  2. Dijkstra's algorithm correctness (statement): Given a graph with non-negative edge weights, Dijkstra's algorithm finds the shortest path distances from source s to all nodes. Key idea: the algorithm repeatedly selects the node with minimum tentative distance and finalizes it; once a node is finalized its distance is the true shortest distance. Assumption: all edge weights ≥ 0. Proof sketch often used in exams: by contradiction using the minimality of the selected tentative node and path decomposition.

  3. Flooding properties:

    • Guaranteed delivery to all nodes in the connected component if every node forwards each packet on all outgoing links (except incoming) exactly once (implemented by tracking per-packet IDs to avoid re-forwarding).
    • Potential for exponential message duplication unless duplicate suppression is used (e.g., per-packet IDs/sequence numbers and a seen cache); TTL/hop-limit only bounds the blow-up and does not prevent duplicates.
  4. Link-state steps (what to draw in a diagram):

    • For each router: (1) discover neighbours and link costs (draw small router boxes and labelled link costs), (2) create link-state packet (LSP) containing its incident links, (3) flood LSPs through the network (draw arrows showing LSP distribution), (4) each router builds the full graph and runs Dijkstra (draw final computed shortest-path tree rooted at the router).
  5. Complexity claims often needed:

    • Dijkstra with a binary heap: O((E + V) log V) (often written O(E log V)); with a Fibonacci heap: O(E + V log V). With simple array: O(V^2). Bellman–Ford (distance-vector full relaxations): O(V·E) per full calculation. Flooding: message cost O(E) per original packet if loop suppression works ideally; without suppression messages blow up.

Formulas

path_cost(P) = sum_{(u,v) in P} c(u,v) — path cost is sum of link costs; c(u,v) is cost on edge (u,v). Units: same as chosen metric (e.g., seconds). Applies always.

D_x(y) = min_{v in N(x)} ( c(x,v) + D_v(y) ) — Bellman equation. Symbols: D_x(y) = cost estimate at x to destination y (same units as c), N(x) = neighbours of x, c(x,v) = cost of link (x,v). Applies in distance-vector update.

Complexity: Dijkstra (binary heap) = O((E + V) log V) — V = number of nodes, E = number of edges. Applies when using a priority queue (binary heap). With a Fibonacci heap, O(E + V log V).

Complexity: Bellman–Ford (full relax) = O(V·E) — for the centralized algorithm performing V−1 full relaxations; distributed distance-vector convergence can be slower or unbounded in worst cases (count-to-infinity).

Flooding message cost (ideal) = O(E) — number of messages proportional to edges if each edge carries the packet at most once in each direction and duplicate suppression (per-packet IDs) is used.

Worked examples

  1. Dijkstra example (numerical, exam style) Graph: nodes A,B,C,D,E. Edges with costs (unit: ms): A–B: 4 ms, A–C: 2 ms, B–C: 1 ms, B–D: 5 ms, C–D: 8 ms, C–E: 10 ms, D–E: 2 ms. Find shortest paths from source A. Step 0: Initialize distances: dist(A)=0, dist(B)=∞, dist(C)=∞, dist(D)=∞, dist(E)=∞. Unvisited = {A,B,C,D,E}. Step 1: Select A (dist 0). Relax edges from A: formula used: new = dist(A) + c(A,x)
  • dist(B) = min(∞, 0 + 4) = 4 ms
  • dist(C) = min(∞, 0 + 2) = 2 ms Mark A visited. Step 2: Select unvisited node with smallest dist = C (2 ms). Relax C's edges:
  • to B: new = 2 + 1 = 3 ms → dist(B) = min(4, 3) = 3 ms
  • to D: new = 2 + 8 = 10 ms → dist(D) = 10 ms
  • to E: new = 2 + 10 = 12 ms → dist(E) = 12 ms Mark C visited. Step 3: Select B (3 ms). Relax B's edges:
  • to D: new = 3 + 5 = 8 ms → dist(D) = min(10, 8) = 8 ms Mark B visited. Step 4: Select D (8 ms). Relax D's edges:
  • to E: new = 8 + 2 = 10 ms → dist(E) = min(12, 10) = 10 ms Mark D visited. Step 5: Select E (10 ms). No better relaxations. Final distances:
  • dist(A)=0 ms
  • dist(B)=3 ms via A→C→B (path A–C–B)
  • dist(C)=2 ms via A→C
  • dist(D)=8 ms via A→C→B→D
  • dist(E)=10 ms via A→C→B→D→E Final answer (bold): shortest costs from A: B=3 ms, C=2 ms, D=8 ms, E=10 ms.
  1. Distance-vector trace (small exchange example) Network: nodes X, Y, Z, W with link costs (unitless hops): X–Y:1, Y–Z:2, Z–W:1, X–W:7. Initially each node knows direct neighbour costs; show one round of exchanges and convergence. Initial distance vectors (only entries for destinations X,Y,Z,W):
  • X: to X=0, Y=1, Z=∞, W=7
  • Y: X=1, Y=0, Z=2, W=∞
  • Z: X=∞, Y=2, Z=0, W=1
  • W: X=7, Y=∞, Z=1, W=0 Round 1: nodes exchange vectors with neighbours and apply Bellman equation. At X, consider neighbour Y: new to Z via Y = c(X,Y)+D_Y(Z) = 1+2=3 → update D_X(Z)=3 (was ∞). new to W via Y = 1+∞ = ∞ (no update). From neighbour W: new to Z via W = 7+1=8, no improve. After one round X has {X:0,Y:1,Z:3,W:7}. Similarly Y learns W via Z: c(Y,Z)+D_Z(W)=2+1=3 → D_Y(W)=3 and X already 1. Z learns X via Y: c(Z,Y)+D_Y(X)=2+1=3 → D_Z(X)=3. W learns Y via Z: 1+2=3 → D_W(Y)=3. After convergence (a few rounds) final shortest costs are: X–W via X–Y–Z–W cost 1+2+1=4, but X had direct 7, so final D_X(W)=4 (via Y and Z). The algorithm converges to the shortest paths. Note: this example demonstrates how distributed relaxations propagate distance information step by step.
  1. Flooding example (short): Graph: A connected to B and C; B connected to D; C connected to D. A sends a flooded packet. Forwarding if no suppression: A forwards to B and C; B forwards to D and (back to A but drop because arrived from A) ; C forwards to D and back to A (drop) ; D receives two copies (from B and C). To prevent duplicates: include a unique packet ID/sequence number and have each node forward a given ID at most once; a TTL/hop-limit can be added to bound lifetime but does not by itself prevent duplicates.

Common mistakes

  • Forgetting to carry units in numerical examples (e.g., ms) and not showing intermediate steps in Dijkstra relaxation.
  • In distance-vector updates, applying Bellman equation incorrectly by using stale values from same iteration instead of the neighbor's last advertised vector.
  • Believing flooding always produces one copy per node — it produces multiple duplicates unless duplicate suppression (e.g., per-packet IDs/sequence numbers and a seen cache) is used; TTL/hop-limit only bounds lifetime and does not prevent duplicates.

For your exam

Kinds of questions:

  • Definitions and short notes: define distance-vector, link-state, flooding, convergence, count-to-infinity. Include examples and trade-offs (message overhead, memory, convergence time).
  • Derivations/proofs: prove Dijkstra correctness sketch; derive Bellman equation and show a relaxation step.
  • Numericals/traces: run Dijkstra on a small weighted graph; trace distance-vector updates for a few rounds; show flooding with sequence number suppression.
  • Diagrams: draw a small graph (label nodes A..E and edge costs), show Dijkstra frontier or link-state LSP propagation arrows and resulting shortest-path tree. When a diagram is required, draw: nodes as circles with labels, edges as straight lines with cost numbers beside them; for Dijkstra mark finalized nodes with a shading and record their final dist next to node. A full-marks answer includes definitions, assumptions (e.g., non-negative weights), step-by-step algorithm trace (show tentative distances and chosen node each step), and final routes with next-hops.

Quick check

  1. What condition on edge weights is required for Dijkstra's algorithm to be correct?
  2. Write the Bellman equation used in distance-vector updates.
  3. Name two methods to prevent duplicate deliveries in flooding. Answers: 1) All edge weights must be non-negative. 2) D_x(y) = min_{v in N(x)} ( c(x,v) + D_v(y) ). 3) Use per-packet IDs/sequence numbers with a seen-cache (forward each ID once) or constrain flooding to a spanning tree/reverse-path forwarding; TTL/hop-limit only bounds lifetime and does not prevent duplicates. Also note split horizon/poison reverse address loops in distance-vector, not flooding.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?