This blog contains a full description of my first Computer Networks project, a Distance Vector protocol implementation that uses Bellman-ford to determine the shortest routing paths in a distributed network.
Initial Network set-up
I just intended to use one machine for this project. As a result, I ran Routers as separate Processes on distinct and valid port numbers ranging from 1024 to 65535. During execution, each of these routers will run synchronously and exchange messages over UDP sockets.
Port numbers 0 to 1024 are reserved for privileged services and are designated as well-known ports.
Brief Intro to Bellman-Ford algorithm
Bellman ford is a Dynamic-Programming approach to find the shortest path in a graph. Each router maintains a Distance Vector that stores the shortest distance between itself and all of the possible destination nodes.
Distance Vector Information
Basic Implementation Steps for Bellman-Ford
- Distance Vector is individually set up for all the nodes in a network with distance to itself equal to 0 and distance to all other nodes equal to MAX_VALUE(infinity).
- Receive the DVs from your neighbors, update your DV using the Bellman-Ford Formula, and synchronously send your DV back to your neighbors — This operation is repeated synchronously by the entire network until the shortest distances are identified.
This is exactly how the shortest distance is calculated and DVs are updated.
Use of Multi-Processing
As previously said, I use numerous processes to run multiple routers on different port numbers at the same time. Basically, the datafiles repo has 6 .dat files that hold information about each node’s neighbors; hence, during initialization, the user must specify 6 different port numbers for the processes to execute on.
Use of Multi-Threading
The project uses two threads for each router:
- First thread, to read the Distance Vectors of neighbors and update the global distance matrix
- The second thread calculates the shortest distance using the algorithm and updates the information to the neighbors.
After each writing, the thread waits 5 seconds before receiving any information from the neighbors, then performs the calculations and waits another 10 seconds before repeating the entire process.
Personal evaluation
As this was my first computer networking project, it took me almost a week to understand and implement the entire thing. I think understanding Bellman-Ford was probably the easiest part, but multi-threading and socket programming were a little challenging. Anyway, making this was a lot of fun, and I’ll definitely be implementing some more graph algorithms into computer networks in the near future!