Distance Vector Routing
In the lectures, you learned about Distance Vector (DV) routing protocols1 , one of the two classes of routing protocols. DV protocols, such as RIP, use a fully distributed algorithm that finds shortest paths by solving the Bellman-Ford equation at each node. In this project, you will develop a distributed Bellman-Ford algorithm and use it to calculate routing paths in a network. This project is like Project 2, except that we are solving a routing problem, not a switching problem.
In “pure” distance vector routing protocols, the hop count (the number of links to be traversed) determines the distance between nodes. However, some distance vector routing protocols that operate at higher levels (like BGP) must make routing decisions based on business relationships in addition to hop count. These protocols are sometimes referred to as Path Vector protocols2 . We will explore this by using weighted links (including negatively weighted links) in our network topologies.
We can think of Nodes in this simulation as individual Autonomous Systems (ASes), and the weights on the links as a reflection of the business relationships between ASes. Links are directed, originating at one Node and terminating at another.
The Project-3 directory contains the following files:
• DistanceVector.py - This is the only file you will modify. It is a specialization (subclass) of the Node class that represents a network node (i.e., router) running the Distance Vector algorithm, which you will implement.
• Node.py - Represents a network node, i.e., a router.
• Topology.py - Represents a network topology. It's a container class for a collection of DistanceVector Nodes and the network links between them.
• run_topo.py - A simple “driver” that loads a topology file (see *Topo.txt below), uses that data to create a Topology object containing the network Nodes, and starts the simulation.
• helpers.py - This contains logging functions that implement that majority of the logging code for you.
• *Topo.txt - These are valid topology files that you will pass as input to the run.sh script (see below).
• BadTopo.txt - This is an invalid topology file, provided as an example of what not to do, and so you can see what the program says if you pass it a bad topology.
• output_validator.py - This script can be run on the log output from the simulation to verify that the output file is formatted correctly. It does not verify that the contents are correct, only the format.
• run.sh - Helper script that launches the simulation on a specified topology and automatically runs the output
validator on the log output when the simulation finishes; basically a convenient wrapper for run_topo.py
and output_validator.py .