Routing Algorithms: The Graph Abstraction

A computer network graph is a pair $G = (N, E)$ where $N$ is the set of nodes (routers, and sometimes end-hosts or autonomous systems, depending on the level of abstraction) and $E$ is the set of edges representing direct communication links between pairs of nodes. Each edge $(x, y) \in E$ carries a cost $c(x, y)$, a nonnegative real number quantifying how expensive it is to send traffic across that link. This single number can stand in for a wide variety of physical or policy realities: propagation delay, queueing delay, the reciprocal of available bandwidth, a monetary charge from an ISP, or an administratively assigned weight reflecting preference. The algorithm that computes routes never needs to know what the cost represents — only that costs along a path can be summed and compared. A path in this graph is a sequence of nodes $(x_1, x_2, \ldots, x_p)$ such that consecutive nodes are joined by an edge in $E$. The cost of a path is the sum of the costs of its constituent edges: ``` cost(path) = c(x1, x2) + c(x2, x3) + ... + c(x_{p-1}, x_p) ``` A least-cost path between source $x$ and destination $y$ is any path whose cost is minimal among all paths connecting $x$ to $y$. Note the phrase "any path" — least-cost paths need not be unique, though for the purposes of building a forwarding table, a router only needs to identify one such path (or, more precisely, the correct next hop along one). This is precisely the shortest-path problem from graph theory, and network engineers use "least-cost path" and "shortest path" interchangeably even when the cost metric has nothing to do with physical distance. The crucial insight that makes internet-scale routing tractable is this: once the topology and costs are expressed as a graph, decades of shortest-path algorithms — Dijkstra's algorithm, Bellman-Ford, and their distributed variants — become directly applicable. The engineering problem of "how do routers decide where to send packets" reduces to the mathematical problem of "how do you compute shortest paths in a weighted graph," and, crucially, to a second question unique to networking: who computes it, and with what information? This second question is where the centralized versus decentralized distinction arises. In a centralized (or "global") approach, some entity — conceptually a single powerful algorithm, though in practice this is distributed as link-state routing — gathers complete knowledge of the graph (every node, every edge, every cost) before computing paths. In a decentralized (or "distributed") approach, no single node ever sees the whole graph; each node knows only its own directly connected edges and iteratively exchanges partial information with neighbors, with the correct global solution emerging as a consequence of repeated local updates converging to a stable state. Both approaches solve the same mathematical problem — least-cost paths in a weighted graph — but they differ radically in information requirements, communication overhead, computational placement, and failure behavior.

Step 1: Build the graph abstraction

Before any algorithm runs, the physical network must be translated into the graph model. ``` FUNCTION build_graph(physical_topology): N := set of all routers (and relevant interfaces) in the topology E := empty set of edges FOR each physical or logical link L in physical_topology: (x, y) := the two endpoints of L c := cost_function(L) # e.g., 1/bandwidth, measured delay, admin weight add edge (x, y) with cost c(x, y) to E RETURN graph G = (N, E) ``` The cost function is a policy decision, not an algorithmic one. A common simple choice sets `c(x,y) = 1` for every link, which reduces least-cost routing to minimizing hop count. A more refined choice sets `c(x,y)` inversely proportional to link bandwidth, so that a 1 Gbps link is "cheaper" than a 10 Mbps link even if the latter has fewer hops. The graph model is agnostic to this choice: it only requires that costs be well-defined, nonnegative numbers assigned consistently to every edge.

Step 2: Decide what "least-cost path" computation requires

Given the graph $G$, the routing problem is: for every node $x$, and for (in general) every possible destination $y$, determine the least-cost path from $x$ to $y$ — or, since forwarding tables only need the first hop, determine which neighbor of $x$ lies on some least-cost path to $y$. This is where the fundamental architectural fork occurs.

Centralized (global) computation. A global algorithm requires complete knowledge: the identities of all nodes and the costs of all edges, gathered into one place before computation begins. Once assembled, a single run of an algorithm such as Dijkstra's produces least-cost paths from one source to all destinations simultaneously. In real networks this is realized by having every router broadcast its local link information to every other router (link-state advertisement, or flooding), so that each router ends up with an identical, complete copy of the graph and can compute shortest paths independently. This paradigm is developed in full in Link-State Routing and Dijkstra's Algorithm.

Decentralized (distributed) computation. A distributed algorithm never assembles a global picture anywhere. Each node begins knowing only the costs to its immediate neighbors, and periodically exchanges distance estimates (not full topology) with those neighbors. Each node updates its own estimate of the least cost to each destination using only what its neighbors report, and the process repeats until no node's estimate changes further — a state called convergence. This paradigm, and the recurrence relation that powers it, is developed in Distance-Vector Routing and Bellman-Ford. Below is the shared skeleton that both paradigms ultimately specialize. It expresses the definition of a least-cost path — independent of algorithm — via the recursive structure that any correct shortest-path algorithm must respect. ```

# Generic specification of least-cost path cost from source s to node v.

# Both centralized and decentralized algorithms must satisfy this recurrence;

# they differ only in HOW it is evaluated and WHERE the data lives. D(s, s) = 0 D(s, v) = min over each neighbor w of v of [ D(s, w) + c(w, v) ] for v != s ``` This recurrence is the mathematical heart of every routing algorithm discussed elsewhere in this scope: Dijkstra's algorithm evaluates it greedily with full information; the distributed Bellman-Ford equation evaluates it iteratively with only local information, converging to the same fixed point.

Step 3: Translate least-cost paths into a forwarding table

Once least-cost paths (or, more precisely, least costs $D(s,v)$ for all $v$, together with the neighbor that achieves the minimum) are known at node $s$, building the forwarding table is a direct lookup: ``` FUNCTION build_forwarding_table(s, D, predecessor_neighbor): table := empty map FOR each destination v in N, v != s: next_hop := predecessor_neighbor[v] # neighbor achieving the min in D(s,v) table[v] := next_hop RETURN table ``` This table is exactly what the Network Layer Services and the Forwarding vs. Routing Distinction describes as the output of the routing process, consumed by the (fast-path, per-packet) forwarding process.

Why the recurrence is well-defined. The recurrence $D(s,v) = \min_w [D(s,w) + c(w,v)]$ rests on a structural fact known as the optimal substructure (or subpath optimality) property of shortest paths: > If $P = (s, \ldots, w, v)$ is a least-cost path from $s$ to $v$, then the prefix of $P$ ending at $w$ is itself a least-cost path from $s$ to $w$. Proof sketch. Suppose not — suppose there were a cheaper path $P'$ from $s$ to $w$ than the prefix of $P$. Then splicing $P'$ together with the final edge $(w, v)$ would create a path from $s$ to $v$ cheaper than $P$, contradicting the assumption that $P$ is least-cost. Because costs are simply summed along a path and $c(w,v) \ge 0$ is fixed, replacing a suboptimal prefix strictly decreases total cost, giving the contradiction. $\blacksquare$ This property is what licenses solving the problem by combining optimal solutions to smaller subproblems — the definition of a problem amenable to dynamic-programming-style recurrences, and it is exactly the property both Dijkstra's algorithm and Bellman-Ford exploit, in different orders of evaluation.

Why nonnegative costs matter. The recurrence assumes that adding an edge never decreases total path cost, i.e., $c(w,v) \ge 0$ for all edges. If negative costs were allowed, two problems appear: (1) a "least-cost path" might not exist at all, because a negative cycle (a cycle whose total cost is negative) could be traversed repeatedly to make cost approach $-\infty$; (2) even without negative cycles, some algorithms (Dijkstra's, specifically) become incorrect, because they rely on the greedy assumption that once a node's least cost is finalized, it can never be improved by a longer path through a later-finalized node — an assumption negative edges can violate. Real routing metrics (delay, inverse bandwidth, hop count, monetary cost) are naturally nonnegative, so this is rarely a practical restriction, but it is a genuine mathematical precondition, not an implementation detail.

Termination and complexity, at the level of this abstraction. The recurrence has $|N|$ unknowns, $D(s, v)$ for each $v \in N$, related to each other through the edges of the graph. Any correct algorithm must, at minimum:

• Examine every edge at least once (otherwise a change in an unexamined edge's cost could never affect the computed table) — an unavoidable $\Omega(|E|)$ lower bound on work per full computation.
• Produce, for each of the $|N|$ nodes, a next-hop decision — an unavoidable $\Omega(|N|)$ lower bound on output size.

The specific algorithms that meet these bounds efficiently — Dijkstra's algorithm achieving $O(|E| \log |N|)$ with a priority queue for the centralized case, and the distributed Bellman-Ford iteration converging in a number of rounds bounded by the network's diameter for the decentralized case — are treated in depth in their own articles. What belongs here, at the level of the abstraction itself, is the honest tradeoff between the two paradigms:

Neither paradigm is unconditionally superior — real large-scale networks (the internet's interior routing) predominantly use link-state protocols for intra-domain routing precisely because full-topology knowledge, though costly to disseminate, gives every router a consistent, fast-to-recompute view; while historically distance-vector approaches were valued for their much lower per-node information and computation requirements, at the cost of slower and sometimes fragile convergence.

Consider six routers forming the topology below, with costs assigned by an administrator to reflect (say) inverse link capacity, so cheaper numbers mean faster/cheaper links. Graph edges and costs (undirected, symmetric costs assumed for simplicity):

We want the least-cost path (and its cost) from source $u$ to every other node, applying the recurrence $D(s,v) = \min_w [D(s,w) + c(w,v)]$ by hand, tracking how the true least-cost distances satisfy it.

Step 1 — direct neighbors of u. $D(u,u) = 0$. $D(u,x)$ candidate via direct edge: $0 + 1 = 1$. $D(u,v)$ candidate via direct edge: $0 + 2 = 2$.

Step 2 — extend through x (currently the cheapest known non-source node). From $x$: to $w$, candidate $D(u,x) + c(x,w) = 1 + 1 = 2$. From $x$: to $v$, candidate $1 + 5 = 6$ — worse than the direct $u$–$v$ edge cost of 2, so $D(u,v)$ stays 2.

Step 3 — extend through v (cost 2) and w (cost 2), whichever is settled next. From $v$: to $w$, candidate $2 + 3 = 5$ — worse than the existing $D(u,w) = 2$ found via $x$, so no change. From $w$: to $y$, candidate $2 + 2 = 4$. From $w$: to $z$, candidate $2 + 1 = 3$.

Step 4 — extend through z (cost 3, cheaper than y's current 4). From $z$: to $y$, candidate $3 + 2 = 5$ — worse than the existing $D(u,y) = 4$ found via $w$ directly, so no change.

Final least-cost table from source u:

Notice something instructive: even though $v$ is a direct neighbor of $u$ with an attractive-looking edge cost of 2, the least-cost path to every other destination in the network routes through $x$, not $v$ — because $x$'s onward links are much cheaper. This is exactly why routing cannot be based on local edge cost alone; it requires solving the full recurrence over the graph, which is what both centralized and decentralized algorithms exist to do (differing only in how they gather the information needed to fill in this table). It also illustrates subpath optimality directly: the least-cost path to $z$, namely $u$–$x$–$w$–$z$, contains as a prefix the least-cost path to $w$ ($u$–$x$–$w$) and, within that, the least-cost path to $x$ ($u$–$x$) — exactly as the correctness proof predicted.

The graph-theoretic reduction underlying routing did not originate in networking — it was imported wholesale from decades of prior work in combinatorial optimization and operations research, then adapted by network engineers building the ARPANET and its successors.

Every intra-domain routing protocol in production networks is, underneath its configuration language and packet formats, an implementation of the graph abstraction described here. OSPF (Open Shortest Path First) and IS-IS are link-state protocols in which every router floods information about its local links to all other routers, each router assembles an identical copy of the network graph, and each router runs a shortest-path computation locally — the centralized-computation paradigm realized in a distributed system. Older and historically important protocols like RIP (Routing Information Protocol) instantiate the decentralized paradigm, with routers exchanging only distance estimates with immediate neighbors. Beyond the internet's core, the same abstraction underlies traffic engineering in data centers, where link costs might represent real-time congestion rather than static bandwidth, and software-defined networking controllers that compute routes centrally using exactly the classical graph algorithms, now made practical at scale by a controller with a synchronized topology database. Even outside networking, ride-sharing and mapping services, transportation planning, and VLSI circuit routing borrow this same weighted-graph, least-cost-path abstraction — a testament to how a clean mathematical model, once found, transfers far beyond its original domain.

Ask the tutor: How does the choice of edge-cost metric (hop count vs. inverse bandwidth vs. delay) change which paths get selected as "least-cost" in a real network?