Internet Routing Protocols and Algorithms

🧭

On this page — click any heading below to jump straight to it. ⬅️ Back to P-II.II. Computer Communications & Networks

---

OSI Layer: Network Layer (L3)

Definition

Routing protocols determine how routers automatically exchange topology/reachability information and select the optimal path to forward packets across a network of networks. Without them, every routing table would need to be configured and updated by hand (static routing), which does not scale to the Internet.

Static vs Dynamic Routing

• Static routing — routes manually configured by an administrator; simple and predictable, but does not adapt to link failures or topology changes, and does not scale to large networks.
• Dynamic routing — routers run a routing protocol to automatically discover and adapt routes as the topology changes; scales well but adds protocol overhead and complexity.

Classification by Algorithm Type

1. Distance Vector Routing

• Each router maintains a table of "distance" (typically hop count) to every known destination and periodically shares its entire table with its directly connected neighbours only.
• Based on the Bellman-Ford algorithm: a router updates its own table if a neighbour advertises a shorter path to some destination — "routing by rumour," since a router trusts what neighbours report without seeing the full topology.
• Weakness — Count-to-Infinity: when a link fails, incorrect information can loop between neighbouring routers, each incrementally increasing a bad hop count, converging very slowly. Mitigations: split horizon (don't advertise a route back to the neighbour it was learned from), poison reverse, hold-down timers.
• Example protocol: RIP (Routing Information Protocol) — hop count metric, maximum 15 hops (16 = unreachable), slow convergence, simple to configure — suited only to small networks.

2. Link State Routing

• Each router builds a complete, identical topology map of the entire network by flooding "link state advertisements" (LSAs) describing its direct links to every other router.
• Each router independently runs Dijkstra's shortest-path algorithm on this full map to compute optimal routes to every destination.
• Converges much faster and more reliably than distance vector, at the cost of higher memory/CPU use and more complex implementation.
• Example protocol: OSPF (Open Shortest Path First) — supports areas (hierarchical scaling), fast convergence, cost-based metric (can reflect bandwidth) — the standard IGP for medium-to-large enterprise networks.

3. Path Vector Routing

• Used specifically between autonomous systems (organisations/ISPs, each with its own independently-administered network), where trusting a simple metric like hop count is unsafe across administrative boundaries.
• Each route advertisement carries the entire path (sequence of AS numbers) it has traversed, allowing a receiving AS to detect and reject loops (if its own AS number already appears in the path) and apply policy-based decisions (commercial agreements, not just shortest path).
• Example protocol: BGP (Border Gateway Protocol) — the single protocol that holds the global Internet together, exchanging reachability information between all the world's Autonomous Systems.

Classification by Scope

• Interior Gateway Protocols (IGP) — operate within a single autonomous system (e.g., one ISP's or one university's network): RIP, OSPF, EIGRP, IS-IS.
• Exterior Gateway Protocols (EGP) — operate between different autonomous systems: BGP is effectively the only EGP in real-world use today.

Comparison Table

Numericals

Q1 — Count-to-infinity illustration

Routers A–B–C in a line, metric = hop count, C's link to a destination D fails.

• Without split horizon: B still believes A has a route via itself (loop); B and A increment the hop count back and forth (2, 3, 4, … up to the maximum, e.g. 16 in RIP) before both mark D unreachable — illustrating why RIP's slow convergence is a real practical weakness.

Q2 — Dijkstra shortest path (conceptual)

Given link costs A–B = 2, B–C = 3, A–C = 8: the link-state algorithm at every router computes A→C via B (cost 5) as cheaper than the direct A→C link (cost 8), so it is chosen — demonstrating link-state routing's global-view advantage over distance vector's neighbour-only view.

CSS Exam Angle

• Contrast Distance Vector vs Link State clearly across information shared, algorithm, and convergence speed — a classic comparison-table question.
• Discuss path-vector BGP when the question asks for routing categories or inter-domain routing. For a question explicitly limited to link state and distance vector, keep the answer focused on those two.
• Explicitly state the IGP vs EGP scope distinction; examiners often ask which protocol is used within vs between autonomous systems.
• The count-to-infinity problem with its mitigations (split horizon, poison reverse) is a strong "depth" addition to a distance-vector answer.

Example

BGP is what allows Pakistani ISPs (e.g., PTCL, Transworld) to exchange routing information with global Internet backbones and each other, determining how the country's international internet traffic is actually routed and peered — a live, examinable national-relevance example.

Likely Questions

1. Differentiate between distance vector and link state routing algorithms, citing relevant protocols.
2. What is the count-to-infinity problem in distance vector routing, and how is it mitigated?
3. Explain the role of BGP as a path vector protocol between autonomous systems.
4. Distinguish Interior Gateway Protocols from Exterior Gateway Protocols with examples.

📜 Past-Paper Questions & Structured Answers

Questions are paraphrased; answer focus is suggested guidance, not an official marking scheme.

2019 · Paper-II · Q3(b) · 6 marks

Question (paraphrased): Compare link-state and distance-vector routing with examples.

Answer focus: Explain both algorithms and demonstrate the same route choice.

Example: link costs A–B=2, B–C=1, A–C=5. With distance vector, B advertises cost 1 to C; A calculates 2+1=3 and chooses B rather than its direct cost-5 link. With link state, A knows all three links and computes the same cost-3 path using Dijkstra.

Trade-off: link state generally converges rapidly but needs topology memory and flooding. Distance-vector behaviour is simpler but convergence can be slow after failures; mechanisms such as split horizon reduce some problems. Neither family guarantees zero transient disruption during every change.

2022 · Paper-II · Q5(a) · 8 marks

Question (paraphrased): Explain one algorithm for selecting among competing routes.

Answer focus: Algorithm steps, worked graph/table, route selection and limitations.

Choice: link-state routing using Dijkstra, as used in OSPF. Model routers as vertices and link costs as non-negative edge weights.

Before calculation: discover neighbours, obtain link costs, flood link-state information and construct the topology database. Initialise the source distance to zero, all others to infinity. Repeatedly select the unvisited node with the smallest tentative distance, mark it settled, and relax its neighbours: new distance = min(old distance, selected distance + link cost).

Worked example: A–B=2, A–C=5, B–C=1, B–D=4, C–D=1.

Final decision: route A→B→C→D costs 4, beating A→B→D (6) and A→C→D (6). A installs B as next hop to D. Equal-cost paths can be used through ECMP when supported.

Evaluation: a consistent topology yields a shortest-path tree; updates allow recalculation after failures. A binary-heap implementation takes O((V+E) log V). Flooding, memory and computation cost more than a very simple distance-vector design, and temporary inconsistencies can occur during convergence.

2024 · Paper-II · Q1 item 5 · 1 mark

Question: Which offered statement best characterises shortest-path computation?

Reasoned answer: A — Dijkstra, under the usual networking interpretation. With a binary heap it has polynomial complexity O((V+E) log V), provided edge weights are non-negative. The paper’s terms “fairly low” and “very efficient” are imprecise; A* performance depends on its heuristic, and randomisation is not automatically superior. This is a reasoned selection, not a verified official answer key. Paper