Routing algorithm goal: determine good paths from sending hosts to receiving host. So what is a good path? Here "good" means least cost, fastest and least congested. Cost is defined by network operator: related to bandwidth, related to congestion, etc.
For the characterisitics of network, We apply graph abstraction to solve this problem. Let routers be vertices, connections be edges and the "cost" of connection be weights of edges.
There is routing algorithm classification:
- global: all routers have complete topology, link cost info
- decentralized: iterative process of computation, exchange of info with neighbors
- dynamic: routes change more quickly
- static: routes change slowly over time
Link State
Link State Algorithm is iterative and centralized/global, which knows network topology, link costs needed. And it computes least cost paths from one node to all other nodes.
Notation: \(C_{a,b}\) is the cost from \(a\) to \(b\). \(D(a)\) is the cost of least-cost-path from source to destination \(a\). \(p(a)\) is the predecessor node along path from source to \(a\). And \(N'\) is set of nodes whose least-cost-path definitively known.
And it's mostly the same as Dijkstra's Algorithm or Prim Algorithm in Graph Theory. Omit details here.
Optimized algorithm complexity: \(O(nlogn)\)
Message Complexity: Each router must broadcast its link state information to other \(n\) routers, so complexity is \(O(n^2)\)
Distance Vector
Distance Vector is an application of Bellman Ford Algorithm, which is decentralized, iterative and asynchronous. In this algorithm, each node propagates its cost(distance vector) to its neighbors, so that they can update their own distance vectors.
The process for each node is: - wait for change in local link cost or msg from neighbor - recompute its own DV estimates with DV received from neighbor - if its own DV changed, send it to its neightbors
Such thing is like state information diffusion. As a compiler learner, I think it's the same as what MFP(Maximum FixedPoint) implements
However, there's difference where one of the costs increase. For example, with path x-4-y-1-z, when \(C_{x,y}\) updates to 60, \(y\) will update \(D_y(x)\) to 6 because \[D_y(x) = min(D_y(x), C_{y,z} + D_z(x))\], while \(D_z(x)\) is out-of-date. Such count-to-infinity problem is tricky to solve.
Message complexity: exchange between neighbors; convergence time varies.
Comparsion of LS and DV algorithms
robustness: - LS: - router can advertise incorrect link cost. - each router computes only its own table.
- DV:
- DV router can advertise incorrect path cost:black-holing.
- each router;s DV is used by others: error propagate through network.