Bellman-Ford algorithm in Distance Vector (DV) routing protocol
This post is a brief summary of the repo here https://github.com/jl4730/BellmanFordinDistanceVectorProtocol. The repo implemented the Bellman-Ford algorithm in the Distance Vector routing protocol. This project is very similar to the previous post about the Spanning Tree Algorithm, except that we are solving a routing problem here, not a switching problem. In this project, we will develop a distributed Bellman-Ford algorithm and use it to calculate routing paths in a network.
1. Intro to Bellman-Ford Algorithm
Here is the wiki link to the algorithm: [Bellman-Ford](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm) For our project, the algorithm will be used to calculate the shortest path from one node to another. The following graph shows the key logic behind the implementation:
2. Implement the Bellman-Ford algorithm
Each node will need to:
a) send out initial messages to its neighbors,
b) process messages received from other nodes, and
c) send updates as needed.
Initially, a node only knows of:
a) itself and that it is reachable at cost 0, and
b) its neighbors and the weights on its links to its neighbors
3. Assumptions
3.1 Node behavior
A Node’s distance vector is comprised of the nodes it can reach via its outgoing links (including to itself at distance = 0). A Node advertises its distance vector to its upstream neighbors. Messages are sent to incoming links/upstream neighbors only. This is because a node only cares about other nodes it can reach so it only wants messages from its outgoing nodes.
3.2 Edge and Path weights
The lower limit for path weights is “-99”, which is equivalent to “negative infinity” for this project.
3.3 Negative cycles
Negative cycles are a series of direct links that originate and terminate at a single node, where the sum of the link weights is less than 0. This can lead to a negative “count-to-infinity” problem. Therefore, the implementation must be able to detect negative cycles in order to be able to terminate on its own.
4. Example
Take the following topology as an example:
In the initialization stage, each node will only have information about itself at the distance of 0 (note this distance won’t change even when the neighbors told it differently). The messages here are what the node is going to process, which are received from the downstream nodes. For instance, AA received the message from AD which is the distance vector AD has. The same goes for all other nodes.
Then the nodes started to process the messages and also update upstream neighbors if there are any changes. If the new node shared by the neighbor is not included in its vector yet, then the distance should be calculated and the node should be added to the distance vector.
AA node received the message from AD and updated its vector to include AD. Then the updated vector should be sent to its upstream AB.
The negative cycle started to develop when AB evaluated message from AA. AB has a link to AA at -1 and sees it can reach CC at a cheaper cost by going through AA instead of directly to CC. AB has lost that it will be routing traffic back through AB to get to CC. No way to tell. Starting negative count to infinity. Node CC won’t ever actually receive traffic because of the infinite loop (AB will send to AA, go around the loop and again come to AB) There is a negative cycle because AA->AD->AE->AB->AA is a cost of -1 and it can be traversed an infinite number of times, always decreasing by 1. In assumptions, we may stop at -99 and mark it as a negative cycle. Keep doing the processing until you see that the cost to CC continually decreases for every node in this topology.
Finally, we will have the distance vector as follows:
5. Code
As mentioned in the beginning, the idea of this project is similar to the spanning-tree algorithm, which also leveraged the distributed system.
The data structure used in this project to keep track of the distance vector for each node is Dictionary. The messages sent out will have two parts: the origins and the vector the origin owned (which is a dictionary).
The key part is really how the nodes processing the information and update the neighbors. The details can be found in the following gist, which implemented the different scenarios mentioned in the previous example.
6. Personal reflection
This is the second project on distributed dynamic programming. I spent 2 weekends on the spanning tree project as I was struggling with both the Class structure and the logic to update vectors. I only spent 6 hours on this one as most of the ideas are the same as the previous one. Dynamic programming is interesting and I had lots of fun finishing the projects.
