Gyaan

Routing Algorithms (Distance Vector, Link State)

intermediate routing ospf rip bgp distance-vector link-state

Routers don’t manually know every network on the internet — they learn routes from each other using routing protocols. There are two main families: distance vector and link state, plus BGP for the global internet.

In simple language: routers gossip about which networks they can reach and how far away those networks are. From that gossip, each router computes its forwarding table.

The Two Families

  • Distance Vector — “I tell my neighbors what I can reach and how far it is.” Bellman-Ford under the hood. Example: RIP.
  • Link State — “Everyone broadcasts a complete map of their links. Each router computes shortest paths locally with Dijkstra.” Example: OSPF.

Plus a third for the internet:

  • Path Vector (BGP) — like distance vector but with the full AS-path attached, used between Autonomous Systems.

Interior vs Exterior

  • Interior Gateway Protocols (IGP) — within a single organization / AS. RIP, OSPF, IS-IS, EIGRP.
  • Exterior Gateway Protocols (EGP) — between ASes. BGP is the only one that matters today.

Distance Vector: RIP

RIP (Routing Information Protocol) is the simplest IGP.

  • Each router knows its directly-connected networks.
  • Periodically (every 30s), it tells its neighbors: “Here’s my list of networks and the hop count to each.”
  • Neighbors update their own tables: “I can reach X via you, hop count = your_count + 1.”

This is the Bellman-Ford algorithm in distributed form.

RIP messages from router A:
  192.168.1.0/24  hop=0  (directly connected)
  10.0.0.0/8      hop=1  (learned from neighbor B)
  172.16.0.0/12   hop=2

Router B receives -> if "via A" gives a shorter path than current, update.

RIP’s Problems

  • Slow convergence. It can take minutes for a topology change to propagate.
  • Count to infinity. A loop can cause hop counts to climb forever. RIP caps at 15 (“infinity”) to limit the damage.
  • Doesn’t scale beyond small networks.

Modern networks rarely use RIP. It’s a teaching example.

OSPF (Open Shortest Path First) is the modern IGP. It uses Dijkstra’s algorithm.

  1. Each router discovers its directly-connected neighbors (Hello packets).
  2. Each router floods a Link-State Advertisement (LSA) describing its links and costs.
  3. Every router builds an identical map of the entire area (the Link-State Database).
  4. Each router runs Dijkstra locally to compute shortest paths to every destination.

Result: fast convergence, loop-free, scales to thousands of routers (with areas).

OSPF Concepts

  • Cost — typically based on link bandwidth (cost = ref_bw / link_bw).
  • Areas — break a big OSPF domain into sub-domains. Area 0 is the backbone.
  • Hello timers — neighbors exchange Hellos every few seconds; 4 missed Hellos = neighbor down.

IS-IS

IS-IS is OSPF’s older cousin — link-state, similar idea, common in large ISPs because it’s protocol-agnostic (carries IPv4 and IPv6 routes equally well).

                  Distance Vector (RIP)        Link State (OSPF)
Algorithm         Bellman-Ford                 Dijkstra
Knowledge         Only what neighbors say      Full topology of area
Convergence       Slow                         Fast
CPU/memory        Low                          Higher
Loops             Possible (count to infinity) Avoided by design
Scale             Small networks               Large enterprises

BGP — Routing the Internet

BGP (Border Gateway Protocol) connects the Autonomous Systems (ASes) that make up the internet. An AS is a network operated by a single organization (your ISP, AWS, Google, Cloudflare).

  • BGP is path vector — it advertises full AS paths, not just costs.
  • Decisions are policy-based, not just shortest-path: “prefer routes through cheaper/contracted peers.”
  • It’s TCP-based (port 179), unlike OSPF which has its own protocol number.
AS 64500 advertises 198.51.100.0/24 as path: [64500]
AS 64501 receives, prepends itself: [64501, 64500]
AS 64502 receives, prepends: [64502, 64501, 64500]

The AS_PATH lets BGP detect loops: if a router sees its own AS in the path, drop it.

Why BGP Matters

When BGP misconfigurations happen, large parts of the internet go dark. Famous outages:

  • Pakistan / YouTube (2008) — accidental hijack via misadvertised prefix.
  • Cloudflare / Verizon (2019) — leaked routes from a small ISP redirected major traffic.
  • Facebook (2021) — withdrew its own routes, took itself off the internet.

Quick Algorithm Refresher

  • Bellman-Ford: relaxes edges, handles negative weights, runs in O(V·E). Distance vector basis.
  • Dijkstra: greedy, non-negative weights, O(E log V) with a heap. Link state basis.

Common Gotcha

People conflate routing protocols with routed protocols. IP is the routed protocol — what gets carried. OSPF/BGP/RIP are routing protocols — they decide where IP packets go. Different layer, different job.

Interview Tip

Three crisp answers for routing protocols:

  • RIP = distance vector = Bellman-Ford = slow, small networks
  • OSPF = link state = Dijkstra = enterprise IGP
  • BGP = path vector = the internet’s glue

References