Routing Algorithms

Jr Codex Computer Networks Notes

Level: Intermediate–Advanced Prerequisites: Chapter 3: Routing Fundamentals; DSA Notes, Module 9 Time to complete: ~25 minutes

The Network as a Graph
Distance Vector
The Count-to-Infinity Problem
Link State
Comparing Them
Interior vs Exterior — and BGP
Summary & Next Steps

1. The Network as a Graph

The Mapping
─────────────────────────────────────────
  ROUTERS   ──►  vertices
  LINKS     ──►  edges
  COST      ──►  edge weights

  Routing is then SHORTEST PATH — exactly the
  problem from the DSA Notes, Module 9, with one
  crucial difference:

  NO SINGLE ROUTER SEES THE WHOLE GRAPH.

  Each knows only its own links. The algorithm must
  build a global answer from local knowledge, by
  exchanging information.

  That constraint is what makes routing protocols
  interesting rather than a textbook Dijkstra call.
─────────────────────────────────────────

What "Cost" Means
─────────────────────────────────────────
  hop count      simple; ignores that links differ
  bandwidth      OSPF's default — faster links cost
                 less
  delay          better for latency-sensitive
                 traffic
  administrative a number you assign to express
                 policy or price

  The metric encodes what you consider "best", and
  different protocols make different choices.
─────────────────────────────────────────

2. Distance Vector

The Principle
─────────────────────────────────────────
  "Tell your NEIGHBOURS everything you know."

  Each router keeps a vector of (destination, cost,
  next hop) and periodically sends it to its
  directly connected neighbours.

  On receiving a neighbour's vector:
    for each destination in it:
      my_cost = neighbour's cost + cost to reach
                that neighbour
      if my_cost < what I have, adopt it, with that
      neighbour as the next hop

  This is the BELLMAN-FORD equation, run
  distributedly and forever.
─────────────────────────────────────────

def distance_vector_update(my_table, neighbour_table, neighbour, link_cost):
    """One exchange. Returns True if anything changed."""
    changed = False
    for dest, (n_cost, _) in neighbour_table.items():
        new_cost = n_cost + link_cost
        current  = my_table.get(dest, (float('inf'), None))[0]
        if new_cost < current:
            my_table[dest] = (new_cost, neighbour)         # adopt via this neighbour
            changed = True
    return changed
 
A = {"A": (0, None), "B": (1, "B")}
B = {"B": (0, None), "C": (1, "C"), "A": (1, "A")}
distance_vector_update(A, B, "B", 1)
print(A)     # A now knows C at cost 2, via B — WITHOUT ever seeing C

Its Defining Property
─────────────────────────────────────────
  A router NEVER LEARNS THE TOPOLOGY. It only ever
  knows "destination X is reachable at cost N, send
  it to neighbour Y".

  It trusts its neighbours completely and cannot
  verify what they say — which is exactly the flaw
  Section 3 exposes.

  Protocols: RIP, EIGRP (an advanced hybrid).
─────────────────────────────────────────

3. The Count-to-Infinity Problem

The Failure
─────────────────────────────────────────
  A ── B ── C        C is reachable

  A: "C is cost 2, via B"
  B: "C is cost 1, direct"

  The B-C link FAILS.

  B: "C is now unreachable... but A says it can
      reach C at cost 2. So C is cost 3, via A."
  A: "B now says cost 3, so my route via B is
      cost 4."
  B: "A says 4, so mine is 5."
  ...

  They count upward together, forever, and packets
  for C bounce between A and B until the TTL
  expires.
─────────────────────────────────────────

Why It Happens
─────────────────────────────────────────
  A's route to C GOES THROUGH B. But A's
  advertisement does not say so.

  B hears "A can reach C" and believes it, unaware
  that A's path depends on B itself.

  A router cannot tell a genuine alternative path
  from an echo of its own information.
─────────────────────────────────────────

The Mitigations
─────────────────────────────────────────
  SPLIT HORIZON
    Do not advertise a route back to the neighbour
    you learned it from. A stops telling B about C.

  POISON REVERSE
    Stronger: advertise it back with INFINITE cost.
    "C is unreachable via me" — explicit rather
    than silent.

  HOLD-DOWN TIMERS
    After a route fails, ignore any new
    advertisement for it for a period, so stale
    information does not resurrect it.

  DEFINE INFINITY LOW
    RIP treats 16 as infinity, so counting stops
    quickly — and caps any RIP network at 15 hops.

  These help and do not fully solve it in complex
  topologies, which is why link state exists.
─────────────────────────────────────────

4. Link State

The Principle
─────────────────────────────────────────
  "Tell EVERYONE about your NEIGHBOURS."

  The inverse of distance vector.

  1. Each router discovers its directly connected
     neighbours and link costs
  2. It builds a LINK STATE ADVERTISEMENT listing
     only that
  3. It FLOODS the LSA to every router in the area
  4. Every router assembles all LSAs into an
     IDENTICAL map of the whole topology
  5. Each independently runs DIJKSTRA on that map
     to find its own shortest paths
─────────────────────────────────────────

import heapq
 
def dijkstra(graph, source):
    """Every router runs this on its OWN copy of the same complete map."""
    dist = {source: 0}
    prev = {}
    pq = [(0, source)]
    seen = set()
 
    while pq:
        d, node = heapq.heappop(pq)
        if node in seen:
            continue
        seen.add(node)
        for neighbour, cost in graph[node].items():
            nd = d + cost
            if nd < dist.get(neighbour, float('inf')):
                dist[neighbour], prev[neighbour] = nd, node
                heapq.heappush(pq, (nd, neighbour))
    return dist, prev
 
topology = {
    "A": {"B": 1, "C": 4},
    "B": {"A": 1, "C": 2, "D": 5},
    "C": {"A": 4, "B": 2, "D": 1},
    "D": {"B": 5, "C": 1},
}
print(dijkstra(topology, "A")[0])      # {'A': 0, 'B': 1, 'C': 3, 'D': 4}

Why It Has No Count-to-Infinity
─────────────────────────────────────────
  Every router has the COMPLETE MAP.

  When a link fails, the LSA describing it is
  flooded, every router updates its map, and each
  recomputes from first principles.

  There is no rumour to believe and no possibility
  of circular reasoning, because nobody is relying
  on a neighbour's conclusion — only on its
  observation of its own links.
─────────────────────────────────────────

OSPF in Practice
─────────────────────────────────────────
  The dominant interior link-state protocol.

  AREAS: a large network is divided into areas, all
  connected to a backbone (area 0). LSAs are
  flooded within an area, and only summaries cross
  between areas.

  WHY: Dijkstra on a 5,000-router graph is
  expensive, and every link change would trigger a
  recomputation everywhere. Areas bound both the
  flooding and the computation.

  It is the same hierarchy argument as route
  aggregation (Chapter 3) — divide, summarise,
  scale.
─────────────────────────────────────────

5. Comparing Them

	Distance Vector	Link State
Knowledge	Distances via neighbours	Complete topology
Shares with	Neighbours only	Everyone (flooded)
Shares what	Its whole table	Only its own links
Algorithm	Bellman-Ford, distributed	Dijkstra, local
Convergence	Slow	Fast
Loops	Count-to-infinity	None
CPU / memory	Low	Higher
Scales via	Poorly	Areas
Examples	RIP, EIGRP	OSPF, IS-IS

The Trade in One Line
─────────────────────────────────────────
  Distance vector is CHEAP and BADLY BEHAVED under
  failure.
  Link state is EXPENSIVE and CORRECT.

  Modern networks almost always choose link state,
  because router CPU is no longer scarce and
  convergence time is.
─────────────────────────────────────────

6. Interior vs Exterior — and BGP

The Distinction
─────────────────────────────────────────
  IGP — Interior Gateway Protocol
    Routing WITHIN one autonomous system
    (Module 1, Chapter 4).
    Goal: find the technically BEST path.
    OSPF, IS-IS, EIGRP, RIP.

  EGP — Exterior Gateway Protocol
    Routing BETWEEN autonomous systems.
    Goal: enforce POLICY.
    BGP — and only BGP.
─────────────────────────────────────────

Why BGP Is Different in Kind
─────────────────────────────────────────
  Between organisations, "shortest" is the wrong
  objective.

  An ISP does not want the shortest path. It wants
  the path it is PAID to use, or the one that costs
  it nothing (Module 1, Chapter 4's peering and
  transit).

  So BGP is a PATH VECTOR protocol: it advertises
  the full AS PATH to a destination, and selects on
  policy — local preference first, AS path length
  only later.

  A packet's route is therefore a commercial
  decision as much as a technical one.
─────────────────────────────────────────

The AS Path
─────────────────────────────────────────
  Advertisement: "203.0.113.0/24, AS path:
                  65001 65002 65003"

  Two purposes:

  LOOP PREVENTION — a router seeing its OWN AS
  number in the path rejects the route. This is how
  BGP avoids count-to-infinity: the full path is
  visible, not just a distance.

  POLICY INPUT — shorter paths are preferred, all
  else equal, and operators lengthen paths
  deliberately (AS path prepending) to make a route
  less attractive.
─────────────────────────────────────────

BGP's Structural Weakness
─────────────────────────────────────────
  BGP has essentially NO AUTHENTICATION. A router
  announcing "I am the best path to 8.8.8.8" is
  generally believed.

  ROUTE HIJACKING — accidental or deliberate — has
  taken major services offline and redirected
  traffic through unintended countries, repeatedly.

  MITIGATIONS in progress: RPKI, which
  cryptographically signs which AS may originate
  which prefix, and route filtering between peers.
  Adoption is partial.

  It is the same class of problem as ARP spoofing
  (Module 2, Chapter 4) — a protocol designed among
  trusted parties, later exposed to everyone.
─────────────────────────────────────────

7. Summary & Next Steps

Key Takeaways

Routing is shortest path with one crucial constraint: no router sees the whole graph, so a global answer must be built from local knowledge.
Distance vector shares its whole table with neighbours and suffers count-to-infinity, because a router cannot distinguish a genuine alternative path from an echo of its own information.
Link state floods only each router's own links, so every router builds an identical map and runs Dijkstra locally — which makes loops structurally impossible.
BGP optimises for policy rather than distance, uses the full AS path for loop prevention, and lacks authentication, which is why route hijacking remains possible.

Concept Check

Why can a distance vector router not detect that a neighbour's advertised route depends on itself?
What exactly does a link state router flood, and why does that prevent count-to-infinity?
Why does BGP not simply choose the shortest path?

Next Chapter

→ Chapter 5: NAT, DHCP and ICMP

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index | Back to Computer Networks Index

Jr Codex Computer Networks Notes

Table of Contents

1. The Network as a Graph

2. Distance Vector

3. The Count-to-Infinity Problem

4. Link State

5. Comparing Them

6. Interior vs Exterior — and BGP

7. Summary & Next Steps

Key Takeaways

Concept Check

Next Chapter