[Computer Networking] 13. Routing Algorithms: Link-State and Distance-Vector

Network Graph Example
======================

        2
  (u) -------> (v)
  |  \          |
 1|   \5        |3
  |    \        |
  v     v       v
 (x)---(w)---->(y)---->(z)
    3      1        2

c(u,v) = 2, c(u,x) = 1, c(u,w) = 5
c(v,y) = 3, c(x,w) = 3, c(w,y) = 1
c(y,z) = 2

Routing Algorithm Classification
==================================

1. By information scope:
   - Global: Knows all node information, then computes --> Link-State
   - Decentralized: Iterative computation using only neighbor info --> Distance-Vector

2. By operation mode:
   - Static: Routes rarely change
   - Dynamic: Periodically recalculated as network changes

3. By load sensitivity:
   - Load-Sensitive: Reflects link congestion in cost
   - Load-Insensitive: Current Internet routing approach

Dijkstra's Algorithm
======================

Initialization:
  N' = source node u
  D(v) = c(u,v) (cost of directly connected neighbors)
         infinity (nodes not directly connected)

Loop:
  1. Select node w not in N' with minimum D(w)
  2. Add w to N'
  3. For each neighbor v of w:
     D(v) = min(D(v), D(w) + c(w,v))
  4. Repeat until all nodes are in N'

Dijkstra Execution (Source: u)
================================

Step | N'        | D(v) | D(w) | D(x) | D(y) | D(z)
-----+-----------+------+------+------+------+------
  0  | u         |  2   |  5   |  1   |  inf |  inf
  1  | u,x       |  2   |  4   |  1   |  inf |  inf
  2  | u,x,v     |  2   |  4   |  1   |  5   |  inf
  3  | u,x,v,w   |  2   |  4   |  1   |  5   |  inf
  4  | u,x,v,w,y |  2   |  4   |  1   |  5   |  7
  5  | all nodes  |  2   |  4   |  1   |  5   |  7

Shortest path tree:
  u -> v: cost 2 (direct)
  u -> x: cost 1 (direct)
  u -> w: cost 4 (u -> x -> w)
  u -> y: cost 5 (u -> v -> y or u -> x -> w -> y)
  u -> z: cost 7 (u -> ... -> y -> z)

LS Oscillation Problem Example
================================

Time 1: Most traffic flows via A -> B path
  --> A -> B link cost increases

Time 2: All nodes switch to A -> C -> D -> B path
  --> A -> C link cost increases

Time 3: Switch back to A -> B path (oscillation repeats)

Solution: Randomize routing update timing

Bellman-Ford Equation
======================

d(x, y) = min { c(x, v) + d(v, y) }
           v

where v ranges over all neighbors of x

Meaning: The minimum cost from x to y is
  = cost from x to neighbor v + minimum cost from v to y
  Travel via the neighbor v that minimizes this value

DV Algorithm Operation
========================

Each node x maintains:
  - c(x,v): link cost to neighbor v
  - Dx: distance vector of x (estimated cost to all destinations)
  - Dv: distance vector of each neighbor v

Operation:
  1. Initialize: link cost for directly connected neighbors, infinity for the rest
  2. When receiving a distance vector from a neighbor:
     Dx(y) = min { c(x,v) + Dv(y) } (for all neighbors v)
  3. If own distance vector changed, send to all neighbors
  4. Repeat until no changes

DV Algorithm Execution (3-node example)
=========================================

Topology:
  x ---7--- y
  |       / |
  1     /   1
  |   2     |
  z --------+

Initial distance vectors:
  Dx = [0, 7, 1]  (x->x, x->y, x->z)
  Dy = [7, 0, 1]  (y->x, y->y, y->z)
  Dz = [1, 1, 0]  (z->x, z->y, z->z)

Step 1: Each node receives neighbors' DV and updates

  Node x update:
    Dx(y) = min(c(x,y)+Dy(y), c(x,z)+Dz(y))
          = min(7+0, 1+1) = 2
    Dx(z) = min(c(x,y)+Dy(z), c(x,z)+Dz(z))
          = min(7+1, 1+0) = 1

  Updated Dx = [0, 2, 1]  (x->y changed from 7 to 2)

Step 2: Propagate changed DV to neighbors, terminate when no more changes

Count-to-Infinity Example
===========================

Topology: x ---4--- y ---1--- z

Initial distance vectors:
  Dy(x) = 4, Dz(x) = 5 (z -> y -> x)

Link change: c(x,y) = 4 --> 60

y update: Dy(x) = min(60, 1+Dz(x)) = min(60, 1+5) = 6
  (thinks going via z costs 6, but z also goes via y!)

z update: Dz(x) = min(1+Dy(x)) = 1+6 = 7

y update: Dy(x) = min(60, 1+7) = 8

z update: Dz(x) = 1+8 = 9

... keeps incrementing by 1, converges only after 44 iterations!

Poisoned Reverse Operation
============================

z reaches x via y (z -> y -> x)

Information z tells y:
  Dz(x) = infinity  (actually 5, but reports infinity to y)

Reason: Since z goes via y, prevent loop where y goes via z

When link change c(x,y) = 60 occurs:
  y update: Dy(x) = min(60, 1+infinity) = 60
  y sends Dy(x)=60 to z
  z update: Dz(x) = min(1+60) = 61

  --> Converges to correct value immediately!

Link-State vs Distance-Vector
================================

Item               | Link-State (LS)       | Distance-Vector (DV)
-------------------+-----------------------+------------------------
Information Scope  | Full network topology | Only neighbor DVs
Message Complexity | O(N x E) messages     | Variable until convergence
Convergence Speed  | O(N^2) fast           | Slow (loops possible)
Robustness         | Independent computation| Errors can propagate
                   | (limited error impact) | (wrong DV propagation)
Memory Requirement | Store full topology   | Store only neighbor DVs
Practical Use      | OSPF, IS-IS           | RIP, BGP (path vector)

Protocols and Algorithms in Practice
======================================

Routing Protocol  | Algorithm      | Scope
------------------+----------------+------------------
RIP               | DV             | Small AS interior
OSPF              | LS             | Large AS interior
IS-IS             | LS             | ISP networks
BGP               | Path Vector    | Inter-AS (entire Internet)
EIGRP             | Enhanced DV    | Cisco networks