Tutorial 2: Routing Algorithms and Graph-Theoretic Foundations Expanded

Learning Objectives

• Model a network as a graph with nodes (routers) and edges (links) with associated costs.
• Define the least-cost path problem and compute shortest paths using graph algorithms.
• Analyse common routing metrics (hop count, bandwidth, delay, administrative cost) and their impact on path selection.
• Distinguish between static and dynamic routing, and evaluate appropriate use cases for each.
• Understand the principles of routing optimization, including trade-offs between optimality and stability.
• Explain the scalability challenges of routing in large networks and the need for hierarchical routing.
• Compare centralised and distributed computation of shortest paths.
• Preview the key algorithms (Dijkstra, Bellman-Ford) and their properties.

Overview

Routing algorithms form the core of the control plane. At a fundamental level, a network can be abstracted as a graph where vertices represent routers (or networks) and edges represent links, each assigned a cost (weight). The routing problem reduces to finding the least-cost path between any source-destination pair. This tutorial provides a rigorous foundation in graph theory as applied to networking, including the formal definition of the least-cost path, the choice of routing metrics, and the classification of routing approaches (static vs dynamic). We explore the trade-offs involved in routing optimization, including the multi-constraint path problem, and discuss the scalability challenges that motivate hierarchical routing. Finally, we introduce the two classic algorithms—Dijkstra and Bellman-Ford—that underpin link-state and distance-vector protocols, setting the stage for detailed study in later tutorials.

Detailed Technical and Theoretical Content

1. Graph Model of a Network

A network is mathematically represented as a weighted graph G = (V, E, w), where:

• V = set of vertices (routers, switches, or hosts).
• E ⊆ V × V = set of edges (links) connecting vertices.
• w: E → ℝ⁺ assigns a non-negative cost (metric) to each edge.

In many networks, links are undirected (symmetric costs), but some may be directed (e.g., asymmetric routing policies or wireless links with different transmission powers). The graph may also be dynamic, with edges appearing or disappearing over time.

The cost w(u,v) reflects a quantitative measure such as delay, bandwidth (inverse), monetary cost, or a composite metric. The goal of routing is to find a path P = (v₀, v₁, ..., vₖ) between a source s and a destination t that minimises the total cost: ∑_{i=0}^{k-1} w(v_i, v_{i+1}).

2. The Least-Cost Path Problem

Given a graph with positive edge weights, the single-source shortest path (SSSP) problem is to find the least-cost paths from a source node to all other nodes. This is the core computation performed by routing algorithms. The complexity of SSSP depends on the graph size and the chosen algorithm.

For routing, we typically need the all-pairs shortest paths in small networks, but in practice, each router only computes paths to all destinations (distributed). The Bellman-Ford and Dijkstra algorithms are the two primary approaches, each with different assumptions and performance characteristics.

3. Routing Metrics and Cost Functions

Metrics can be simple or complex:

• Hop count: Number of routers along the path (RIP). Simple but ignores link capacity.
• Bandwidth: Higher bandwidth → lower cost. Typically defined as cost = 10^8 / bandwidth (OSPF default).
• Delay: Measured propagation + transmission + queuing delay. Can be dynamic.
• Load: Based on current traffic utilisation (e.g., in some dynamic routing protocols).
• Administrative cost: Manually assigned by network administrators to enforce policies.

A key issue is that a single metric cannot capture all objectives (e.g., minimizing delay and maximizing bandwidth simultaneously). This leads to multi-constraint routing, which is NP-hard in general, prompting heuristics (e.g., using additive metrics and QoS routing).

4. Static versus Dynamic Routing

• Static routing: Routes are manually configured; they do not change unless an administrator intervenes. Suitable for small, stable networks with predictable traffic. Advantages: no overhead, secure (no route updates). Disadvantages: no adaptation to failures, labour-intensive.
• Dynamic routing: Routers automatically discover and share information about topology changes. Advantages: resilience, scalability, reduced administrative burden. Disadvantages: overhead, complexity, potential convergence issues.

Most modern networks use dynamic routing protocols (OSPF, BGP) but may incorporate static routes for specific purposes (e.g., default route).

5. Routing Optimization and Multi-Constraint Paths

In many scenarios, a path must satisfy multiple constraints (e.g., delay ≤ 50 ms, bandwidth ≥ 10 Mbps). This is the multi-constrained path (MCP) problem, which is known to be NP-hard when there are more than two additive constraints (or one additive and one multiplicative). Heuristics like the k-shortest paths or constrained shortest path first (CSPF) are often used. In practice, routing protocols usually optimize a single additive metric, while policies handle constraints.

6. Scalability Challenges and Hierarchical Approaches

As networks grow, maintaining a global shortest path tree becomes infeasible due to:

• Computation: O(|V| log |V|) per update.
• Storage: O(|V|) entries per router.
• Convergence: Flooding updates to all routers may cause high overhead.

To address this, networks are organized hierarchically into Autonomous Systems (ASes). Within an AS, an IGP (e.g., OSPF) handles internal routing; between ASes, an EGP (e.g., BGP) manages reachability with policy. This reduces the size of the routing table and limits the scope of updates.

7. Advanced: Distributed vs Centralised Computation

In a distributed system, each router computes its own shortest paths using only information exchanged with neighbours. This leads to asynchronous algorithms like Bellman-Ford (distance-vector) and OSPF (link-state). In centralised computation, a single node (controller) collects all topology information and computes paths for all routers, installing forwarding rules (SDN). Centralised can achieve global optimality and easier policy enforcement, but at the cost of a single point of failure and potential bottleneck.

8. Algorithms in Practice: Dijkstra and Bellman-Ford Preview

We give a brief overview of the two classic algorithms:

• Dijkstra's algorithm: Assumes non-negative weights; operates greedily, computing shortest paths from a source in O(|E| log |V|) with a priority queue. Used in link-state routing (OSPF).
• Bellman-Ford algorithm: Handles negative weights (but no negative cycles); works iteratively, relaxing edges |V|-1 times. O(|V|·|E|). Used in distance-vector routing (RIP).

We will cover these in detail in later tutorials.

    (A)---2---(B)
     |         |
     4         1
     |         |
    (C)---3---(D)
    

Quiz

Answer each question; check your understanding by revealing the answer.

Question 1: In a network graph, what do vertices and edges represent?

Question 2: What is the least-cost path problem?

Question 3: Name three common routing metrics.

Question 4: What is the primary disadvantage of static routing?

Question 5: What is the time complexity of Dijkstra's algorithm with a binary heap?

Question 6: Which algorithm can handle negative edge weights, assuming no negative cycles?

Question 7: Explain the concept of route aggregation and how it helps scalability.

Question 8: What is a multi-constrained path?

Question 9: Why is the multi-constrained path problem NP-hard?

Question 10: What is the difference between distributed and centralised routing?

Question 11: What is an Autonomous System (AS)?

Question 12: What is the typical cost function used in OSPF?

Question 13: Can hop count be considered a good metric for large networks? Why or why not?

Question 14: What is the purpose of link-state advertisements (LSAs) in OSPF?

Question 15: How does hierarchical routing reduce the size of routing tables?

Question 16: What is the main advantage of dynamic routing over static routing?

Question 17: What is the Bellman-Ford equation for distance-vector routing?

Question 18: Is Dijkstra's algorithm guaranteed to find the shortest path if some weights are negative? Explain.

Question 19: What is the difference between a directed and undirected graph in networking?

Question 20: Why is it beneficial to model a network as a graph?

Question 21: What is the impact of using a very large metric for a link?

Question 22: Explain the trade-off between optimality and stability in routing.

Exercises

Work through these problems to apply the concepts. Sample solutions are hidden.

Exercise 1: Given the graph below, compute the least-cost path from A to all other nodes using Dijkstra's algorithm (show steps).

    (A)---1---(B)
     |         |
     4         2
     |         |
    (C)---3---(D)

Exercise 2: Explain why hop count can lead to suboptimal routing in networks with heterogeneous link speeds.

Exercise 3: Convert the OSPF cost formula (cost = 10^8 / bandwidth) into a metric where bandwidth is in Mbps. Calculate the cost for links of 10 Mbps, 100 Mbps, and 1 Gbps.

Exercise 4: A router receives three routing updates for the same destination prefix: via OSPF (cost 5), via RIP (hop count 3), and via a static route. The administrative distances are: OSPF=110, RIP=120, static=1. Which route is installed in the FIB? Why?

Exercise 5: Describe a scenario where static routing might be preferred over dynamic routing.

Exercise 6: Explain the concept of "equal-cost multipath" (ECMP) and how it can improve network performance.

Exercise 7: Given a network with 5 nodes and link costs, use the Bellman-Ford algorithm to compute distances from a source. Provide the initial and final distance vectors for each node.

Exercise 8: What is the impact of increasing the update interval in a distance-vector protocol like RIP?

Exercise 9: Discuss the trade-offs between using a single additive metric versus multiple metrics for routing decisions.

Exercise 10: Compare the scalability of Dijkstra's algorithm (link-state) with Bellman-Ford (distance-vector) in terms of communication overhead and computation.

Homework Assignments

These require deeper thinking and research. Write comprehensive answers.

Homework 1: Prove that Dijkstra's algorithm correctly computes shortest paths in a graph with non-negative edge weights. (You may use induction.)

Homework 2: Discuss the challenges of using dynamic metrics (e.g., based on congestion) in routing protocols. How can oscillations be avoided?

Homework 3: Design a small network (6 nodes) and assign costs. Then, compare the shortest paths computed by Dijkstra and Bellman-Ford assuming no negative cycles. Show that they produce the same result.

Homework 4: Research the concept of "route poisoning" and how it helps prevent routing loops in distance-vector protocols.

Homework 5: Explain the relationship between routing metrics and Quality of Service (QoS). How can routing support QoS guarantees?

Homework 6: Compare the use of OSPF areas and BGP route reflectors for scalability. What are the similarities and differences?

Homework 7: Explore the NP-hardness of the multi-constrained path problem. Give a reduction from a known NP-hard problem (e.g., knapsack).

Homework 8: A network operator wants to minimize latency but also avoid congested links. Propose a composite metric and discuss its advantages and limitations.

Homework 9: Analyse the effect of link failures on the convergence time of a distance-vector protocol. What parameters influence the time to reach a consistent state?

Homework 10: Research and compare the shortest path algorithms used in OSPF (Dijkstra) and IS-IS (also Dijkstra). Are there any differences in their implementations?

Homework 11: Explain the concept of "route summarisation" and provide an example of how it reduces routing table size.

Homework 12: Discuss the implications of using negative edge weights in routing. Why are they generally avoided in practice?

Summary

This tutorial provided a rigorous introduction to the graph-theoretic foundation of routing. We defined the network as a weighted graph, formulated the least-cost path problem, and examined the role of routing metrics. We contrasted static and dynamic routing and discussed the challenges of scalability and multi-constraint optimization. The preview of Dijkstra and Bellman-Ford algorithms set the stage for detailed exploration in later tutorials. Understanding these fundamentals is essential for mastering the control-plane protocols that operate in real networks.

End of Tutorial 2 .