Distributed Bellman Ford Link costs may change over time Changes in traffic conditions Link failures Mobility Each node maintains its own routing table Need to update table regularly to reflect changes in network Let di be the shortest distance from node i to the destination Di=min 0[Dj+ di: update equation Each node regularly updates the values of Di using the update equation Each node maintains the values of dif to its neighbors, as well as values of Dj received from its neighbors Uses those to compute Di and send new value of Di to its neighbors If no changes occur in the network, algorithm will converge to shortest paths in no more than n stepsEytan Modiano Slide 8 Distributed Bellman Ford • Link costs may change over time – Changes in traffic conditions – Link failures – Mobility • Each node maintains its own routing table – Need to update table regularly to reflect changes in network • Let Di be the shortest distance from node i to the destination – Di = min {j} [Dj + dij] : update equation • Each node (i) regularly updates the values of Di using the update equation – Each node maintains the values of dij to its neighbors, as well as values of Dj received from its neighbors – Uses those to compute Di and send new value of Di to its neighbors – If no changes occur in the network, algorithm will converge to shortest paths in no more than N steps