A Link-State Routing Algorithm
net topology, link costs known to all nodes
- accomplished via “link state broadcast”
- all nodes have same info
computes least cost paths from one node (‘source”) to all other nodes
- gives routing table for that node
iterative: after k iterations, know least cost path to k dest.’s
c(i,j): link cost from node i to j. cost infinite if not direct neighbors
D(v): current value of cost of path from source to dest. V
p(v): predecessor node along path from source to v, that is next v
N: set of nodes whose least cost path definitively known