The goal of a routing protocol is to determine “good” paths/routes from sending hosts to a receiving host through a network of routers.

• Path - sequence of routers that packets traverse from a given initial source host to final destination host
• A “good” path is one that has the least cost/is the fastest/is least congested
• Routing is a “top-10” networking challenge

We can abstract routers/links as a graph:

• $c_{a, b}$ - cost of direct link connecting
  • No direct link between nodes ⇒ infinite cost
    • $c_{w, z} = 5, c_{u, z} = \infty$
  • Cost is defined by network operator
    • Could always be 1
    • Could be inversely related to bandwidth/congestion
• Graph $G = (N, E)$
  • $N$ - set of routers (in this case, $\{u, v, w, x, y, z\}$
  • $E$ - set of links, $\{(u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z)\}$

Routing algorithms can be broadly classified:

Link State Algorithms

In a link state algorithm, all routers have complete topology info (i.e. link cost info).

We consider Dijkstra’s link state routing algorithm:

• Centralized algorithm
  • Network topology and link costs are known to all nodes
  • “Global information” is achieved via “link state broadcast” - all nodes have the same info
• Computes least cost paths from one node (”source”) to all other nodes
  • i.e. get forwarding table for that node
• Iterative algorithm ⇒ after $k$ iterations, the least cost path to $k$ destinations is known
• Notation:
  • $c_{x, y}$ - direct link cost from node $x$ to $y$
    • Infinite cost if not direct neighbors
  • $D(v)$ - current estimate of cost of least-cost path from source to destination $v$
  • $p(v)$ - predecessor node along path from source to $v$
  • $N'$ - set of nodes whose least-cost-path definitively known

Dijkstra’s algorithm is ran on each particular node.

Examples of running Dijkstra’s algorithm