Distributed Bellman-Ford

DBF

The Distributed Bellman-Ford protocol is a proactive table-driven protocol on basis of the Bellman-Ford Algorithm. That means that every node maintains a routing table. There are three different steps for catching every needed entry.

Start Conditions:
Each router starts with a vector of distances to all directly attached networks. Each node maintains a routing table of <destination, distance, successor>.

Send step:
Every node sends path vector tuples (destination, distance) to all immediate neighbors (no broadcast). These updates are send periodically every second or minute. This depends on the size and the dynamic of the network. Triggered or immediate updates are send out whenever destination vectors, entries in the routing table change.

Receiving step:
For every network Y, router finds shortest distance to X considering current distance to X and it takes into account the distance to X from its neighbors. Router updates its cost to X. After doing this for all X destination routers (nodes), the router goes to send step.

Example

Illustration 1 shows the adjacent matrix from our thought network after the start procedure has done. The numbers appearing on the links between two routers are called link costs. The costs of links can signify the hop count, bandwidth or even the really cost if there are two different operators connected on one link.



Illustration 2 shows the network matrix after the first update from router D to neighbor E.



Illustration 3 shows the network matrix after the update from router B to neighbor A. E knows router C since the update from router D. But as we can see router A don’t takes the shortest path to C because he still doesn’t know the router D, so the path over E, D to C with lower costs.



Illustration 4 shows the network matrix after all updates have done. All red marked costs mean now all costs show the shortest way to every other destination in the network.



Illustration 5 shows the case where a broken link happened (link between router E and D). In this case a triggered update has to be sent out, and after the whole network is updated we can see red marked link costs have changed because of the broken link (E, D).
Router A is now no more able to reach router C by taking the shortest path over router E, D. Now A must actualize his routing table for the vector to C by using the longer but available path over router B.



Illustration 6 shows the routing table existing in Router E. Vertically on the left we can see all available destinations of the network and with a given next hop the cost to each other node. On the other hand the red marked costs are the shortest paths to other nodes.
For example is it possible to reach router A taking router B as next hop, naturally the costs are much more higher ( 7+8=15) then taking the path directly to router A (1).



Problems that appear are called count-to-infinity and looping

References

[Kravets2004] Pictures
[Bertsekas1987a] Original Paper

"Distributed Bellman-Ford" is mentioned on: Ad-Hoc Protocols (Classification) | Ad-Hoc Protocols (History) | Ad-Hoc Workshop Winter 04/05 (Termine) | Highly Dynamic Destination-Sequenced Distance-Vector Routing