[SOLVED] CS6250 Assignment 7-Distance Vector

PROJECT GOAL

In the lectures, you learned about Distance Vector (DV) routing protocols, one of the two classes of routing protocols. DV protocols, such as RIP, use a fully distributed algorithm to find 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 similar to the Spanning Tree project, 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. Some distance vector routing protocols, that operate at higher levels (like BGP), must make routing decisions based on business valuations. These protocols are sometimes referred to as Path Vector protocols. 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.

Part 0: Getting Started

You should review some materials on Bellman-Ford. Some resources include:

• Wikipedia (https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm)
• “Computer Networking: A Top-Down Approach” by Kurose and Ross o 7^th edition discusses the algorithm on pages 384-385 in Chapter 5 (“The Network Layer: Control Plane”)

Download and unzip the Project Files for Distance Vector from Canvas in the Assignments section. This project can be completed in the class VM or on your local machine using Python

3.10.x. You must be sure that your submission runs properly in Gradescope.

Part 1: Files Layout

The DistanceVector directory contains the following files:

• 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.
• py – Represents a network node, i.e., a router.
• py – Represents a network topology. It is a container class for a collection of DistanceVector Nodes and the network links between them.
• 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.
• *Topo.txt – These are valid topology files that you will pass as input to the run.sh script (see below). Topologies should end with “.txt”.
• 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.
• 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.
• sh – A helper script that runs some basic system checks, the topology, and the validator, a wrapper for run_topo.py and output_validator.py .

Part 2: TODOs

There are a few TODOs in DistanceVector.py:

1. Review the methods already implemented in Node.py.
   1. Because DistanceVector is a subclass of Node, consider how you might use the existing methods to complete the TODOs in this list.
   2. Do NOT modify Node.py.
2. Decide on how each node will represent its distance vector.
   1. Consider what might be the simplest data structure to keep track of path weights (i.e., the distance vector).
   2. The distance vector variable should be local to the Node, i.e., defined in the init function as a variable accessible via the `self` object (i.e. self.mylist). C. Implement the Bellman-Ford algorithm.
   3. Each Node will:
      1. send out an initial message to its neighbors
      2. process messages received from other nodes

• send updates to other nodes as needed

1. Initially, a node only knows of:
2. itself and that it is reachable at cost 0,
3. its neighbors and the weights on its links to its neighbors

1. NOTE: a node’s links are unidirectional.
2. NOTE: The Bellman-Ford algorithm implementation should terminate naturally without external intervention.
3. Write a logging function that is specific to your distance vector structure.

1. You should use the add_entry function to help with logging.
2. You should assume that the logging function only knows itself.
3. Do NOT access the topology for logging; logging should happen at the Node level.

Part 3: Testing and Debugging

To run your algorithm on a specific topology, execute the run.sh bash script:

./run.sh *Topo

Substitute the correct, desired filename for *Topo. Don’t use the .txt suffix on the command line. This will execute your implementation of the algorithm in DistanceVector.py on the topology defined in *Topo.txt and log the results (per your logging function) to *Topo.log .

NOTE: You should not include the full filename of the topology when executing the run.sh script. For example, to run the algorithm on topo1.txt you should only specify topo1 as the argument to run.sh.

For this project, you may create as many topologies as you wish and share them on Ed Discussion. We encourage sharing new topologies with log outputs. Topologies with format errors will get an error back when you try to run them.

We’ve included four good topologies for you to use in testing and one bad topology to demonstrate invalid topology. The provided topologies do not cover all the edge cases; your code will be graded against more complex topologies.

Part 4: Assumptions and Clarifications

1. Node behavior:
   1. The direction of a link indicates how traffic will flow; two nodes connected with a link may pass messages regardless of traffic direction.
      1. Example: Node B has an incoming link from Node A, but has no outgoing link to Node A, Node B will send its distance vector to node A to

“advertise”     other     nodes     it     can     reach     (Nodes    C     and     D).

1. A Node’s distance vector is comprised of the nodes it can reach via its outgoing links (including to itself at distance = 0).
   1. A Node will never advertise a negative distance to itself. (Important for negative cycles.)
2. A Node advertises its distance vector to its upstream
3. Nodes do not implement poison-reverse.

1. Edge and Path weights:
   1. Edge weight values may be between -50 and 50, inclusive.
   2. The edge weight value type is an integer.
   3. There is no upper limit for path weights.
   4. The lower limit for path weights is “-99”, which is equivalent to “negative infinity” for this project. Negative cycles:
   5. A Node can forward traffic through a negative cycle.
   6. Negative cycles are a series of directed links that originate and terminate at a single node, where the sum of the link weights is less than 0.
      1. This can lead to a negative “count-to-infinity” problem. Therefore, your implementation must be able to detect negative cycles to terminate on its own.
      2. Any node that can reach a destination node and infinitely traverse a negative cycle enroute will set the distance to that node to -99.
         1. Your implementation only needs to detect and record these traversals appropriately; it does not need to mitigate them.
         2. Extra resource: Professor Vigoda explains Negative Weight Cycles and how to detect them, which is Lecture 4, Parts 2-7 of GATech’s “Introduction to Graduate Algorithms” course on Udacity.^[1] (Parts

6 & 7 are Bellman-Ford specific.)

• A Node can advertise a negative distance for other nodes (but not for itself).

1. A Node that receives an advertisement with a distance of -99 from a downstream neighbor should also assume that it can reach the same destination at infinitely low cost (-99).
2. Example: Traffic from Node F to Node D can route through A->B->C->A indefinitely to         reach   an        extremely        low      (very    negative)

1. A Node will not forward traffic destined to itself.
2. Example: The below topology will not result in a count-to-infinity problem, as there are no possible pairs of source and destination nodes

where traffic could indefinitely traverse a negative cycle. Node A will not forward traffic for Node A, and similarly for Nodes B and C.

1. Topologies used in grading:

1. We will be using many topologies to test your project. This includes but is not limited to:
   • topologies with and without cycles (loops), including odd length cycles o topologies of varying sizes, including topologies with more than 26 nodes  o topologies with nodes with names longer than one character o topologies with multiple paths to different nodes
   • topologies that include any combination of positive weights, zero weight, and negative weight
   • topologies with negative cycles, meaning a node may reach another at infinitely low cost
   • topologies with Nodes that do not have incoming or outgoing links ▪ All nodes will be connected but:
     • some may have both incoming and outgoing links
     • some may only have incoming links some may only have outgoing links

1. We will NOT test your submission against the following topologies (which means your algorithm does not need to account for them):
   • topologies with more than one link from the same origin to the same destination (multi-graphs)
   • topologies with portions of the network disconnected from each other

(partitioned networks) o topologies that do not require intermediate steps (such as a topology with a single node)

• topologies with a valid path between two indirectly linked nodes with no cycle with an actual total cost of ≤ -99 (topologies will respect that -99 is “negative infinity” for this project)

Part 5: Correct Logs for Provided Topologies

Below are the correct final logs for the provided topologies. We are providing them to help you identify correct behavior with respect to negative cycles and the assumptions in the instructions. We are only providing the final round; each topology should produce at least 2 rounds of output.

SimpleTopo:

A:A0,C3,B1,D3 B:A1,C2,B0,D2 C:A3,C0,B2,D0 D:A3,C0,B2,D0 E:A2,C-1,B1,E0,D-1

SingleLoopTopo:

A:A0,C16,B6,E6,D5 B:A2,C10,B0,E0,D7 C:C0 D:A3,C11,B1,E1,D0 E:A2,C10,B0,E0,D7

SimpleNegativeCycle:

AA:AA0,CC-99,AB0,AE-1,AD-2 AB:AA-1,CC-99,AB0,AE-2,AD-3 AD:AA1,CC-99,AB2,AE1,AD0 AE:AA0,CC-99,AB1,AE0,AD-2 CC:CC0,AA-1,AB0,AE-2,AD-3

ComplexTopo:

ATT:TWC-99,GSAT-8,UGA-99,ATT0,VZ-3,CMCT-99,VONA-11 CMCT:TWC-99,GSAT-7,UGA-99,ATT1,VZ-2,CMCT0,VONA-10 DRPA:TWC-99,GT-1,GSAT5,UGA-99,PTGN1,OSU1,ATT13,VONA2,EGLN1,VZ10,DRPA0,CMCT-99,UC-1 EGLN:TWC-99,GT-2,GSAT5,UGA-99,PTGN0,OSU2,ATT13,VONA3,EGLN0,VZ11,DRPA1,CMCT-99,UC-2 GSAT:TWC-99,GSAT0,UGA-99,ATT7,VZ5,CMCT-99,VONA-3 GT:TWC-99,GT0,GSAT7,UGA99,PTGN2,OSU0,ATT15,VONA5,EGLN2,VZ13,DRPA3,CMCT-99,UC0 OSU:TWC-99,GT0,GSAT7,UGA99,PTGN2,OSU0,ATT15,VONA5,EGLN2,VZ13,DRPA3,CMCT-99,UC0 PTGN:TWC-99,GT-1,GSAT5,UGA-99,PTGN0,OSU1,ATT13,VONA3,EGLN1,VZ11,DRPA2,CMCT-99,UC-1 TWC:TWC0,GSAT-7,UGA-99,ATT1,VZ-2,CMCT-99,VONA-10 UC:TWC-99,GT0,GSAT7,UGA99,PTGN2,OSU0,ATT15,VONA5,EGLN2,VZ13,DRPA3,CMCT-99,UC0 UGA:TWC-99,GSAT42,UGA0,ATT50,VZ47,CMCT-99,VONA39 VONA:TWC-99,GSAT2,UGA-99,ATT10,VZ8,CMCT-99,VONA0 VZ:TWC-99,GSAT-6,UGA-99,ATT2,VZ0,CMCT-99,VONA-9

Part 6: Spirit of the Project

The goal of this project is to implement a simplified version of a network protocol using a distributed algorithm. This means that your algorithm should be implemented at the network node level. Each network node only knows its internal state, and the information passed to it by its direct neighbors. Declaring global variables will be a violation of the spirit of the project.

The skeleton code we provide you runs a simulation of the larger network topology. For simplicity, the Node class defines a link to the overall topology. This means it is possible using the provided code for one Node to access another Node’s internal state. This goes against the spirit of the project and is not permitted. If you have questions about whether your code is accessing data it should not, please ask on Ed Discussion or during office hours!

You should not use any global variables for managing any data relating to the Nodes. However, you may use a global variable as a setting. I.E.: NEGATIVE_INFINITY = -99