Comparison of LS and DV algorithms

Message complexity

• LS: with n nodes, E links, O(nE) msgs sent each

• DV: exchange between neighbors only

  • convergence time varies

Speed of Convergence

• LS: O(n**2) algorithm requires O(nE) msgs

  • may have oscillations

• DV: convergence time varies

  • may be routing loops
  • count-to-infinity problem

Robustness: what happens if router malfunctions?

LS:

• node can advertise incorrect link cost
• each node computes only its own table

DV:

• DV node can advertise incorrect path cost
• each node’s table used by others
  • error propagate thru network

Previous slide

Next slide

Back to first slide

View graphic version