Assignment 3: Routing Algorithm

Due: Friday, March 27, 2020, 10:00 PM. In groups of up to 2 students

Overview

In this assignment, you will implement a distributed, asynchronous, distance-vector routing algorithm based on the Bellman-Ford algorithm that we learned in the lecture.

The network is modelled as an undirected graph with a certain number of nodes. Each link in the graph is associated with a positive integer cost. Below is a simple example of a graph with 3 nodes and 3 links. The nodes in the graph would, in a distributed and asynchronous manner, send each other messages containing information about their distance vectors, and, when receiving a message from another node, update their distance vectors accordingly. The expected outcome of the routing algorithm is that each node keeps a distance vector that stores its shortest-path distances (lowest costs) to other nodes in the graph, and knows how to find the shortest path to every other node.

Understanding the Starter Code

Download the starter code which includes two files: dvsim.py and dvnode.py. Below is an overview of these two files.

dvsim.py is the main simulator code which implements a simulated environment of the distributed, asynchronous route computing process. It initializes the topology (the nodes and the links with costs) of the input graph and provided class definitions such as Packet, Event and EventList. The implementation in this file is given to you and you won't need to change it much (and you won't submit it to MarkUs); however, you need read it carefully and understand thoroughly what it does and how it is related to the Node class defined in dvnode.py. You only need to modify this file when you try to create different test cases for your algorithm. Below are the things that you may need to modify.

dvnode.py is the file that you will work on completing. This file defines the Node class for each node in the network. You will implement the following methods:

Testing and Report

The command to run the simulator is the following:

python3 dvsim.py HasLinkChange Seed

where HasLinkChange (1 or 0) specifies whether or not to add link-change events to the simulation, and Seed (an integer) is the seed of the pseudo-random number generator.

You should create various test cases to verify that your implementation is correct, and to observe the behaviour of the algorithm in different scenarios. In particular, you're required to write up a report.pdf as part of your assignment submission. The report should include the following parts:

  1. Your name and student number, and a quick summary of what's completed and not completed in your submission.
  2. With HasLinkChange set to 0 (i.e., no link-change events), use a test case on a graph with 5 nodes to convince the reader that your algorithm is working correctly. Add printouts for the intermediate steps to show that the algorithm is behaving as expected.
  3. With HasLinkChange set to 1, use a test case on a graph with 4 nodes to demonstrate the "good news travels fast" behaviour of the routing algorithm.
  4. With HasLinkChange set to 1, use a test case on a graph with 4 nodes to demonstrate the "bad news travels slowly" behaviour of the routing algorithm.
  5. Study/analyze/discuss, on a reasonably detailed level, the complexity of the routing algorithm in terms of the number of messages needed to be sent in the network. Note that the requirement on this part is intentionally vague and open-ended so that you need to think about what approach is the best for studying this issue.
  6. Page limit: The total length of your report should NOT exceed 8 pages.

Requirements

Below are some specific requirements just so that you know what to do and that your code can be properly marked by the TA.

  1. Read the starter code thoroughly. The comments in the starter code contain detailed information regarding how the simulator works and how your code should be written. Please make sure to read it thoroughly and understand how exactly it works.
  2. Use Python 3 and make sure your code works correct on the lab computers.
  3. Make sure your dvnode.py works correctly with the original dvsim.py since your will NOT submit your own dvsim.py
  4. Follow the instructions in the comments in the starter code. Do NOT modify the parts that are marked as "DO NOT MODIFY".
  5. Your node should only send messages when it is necessary, i.e., the number of messages sent must be the minimum possible.
  6. Keep in mind that you're implementing a distributed algorithm, i.e., every node is only supposed to operate on the information stored locally and each node can only communicate with its immediate neighbours. Any violation of this principle, e.g., accessing information or invoking a method at other nodes, would result in significant deduction in marks.
  7. You may assume that every node has the knowledge that the distance value from a node to itself is always 0, regardless of whether the node is a neighbour or not.

Submissions

You will submit the following two files using the web submission interface of MarkUs.

  1. dvnode.py
  2. report.pdf with the content specified in the above "Testing and Report" section. Presentation matters: your report must be presented in a clean and concise manner that is easy-to-understand for others.

You can submit the same filename multiple times and only the latest version will be marked, so it is a good practice to submit your first version well before the deadline and then submit a newer version to overwrite when you make some more progress. Again, make sure your code runs as expected on a lab computer.

Late homework submissions are penalized by 1% for every hour of lateness, rounded up, to a maximum of 24 hours. Submissions will no longer be accepted 24-hours past the deadline, except for documented unusual circumstances.

Marking

Below is the tentative overall marking scheme of this assignment:

Coding style matters. Your code must be written in a proper style and must be well commented so that anyone else can read your code and easily understand how everything works in your code.

Academic Integrity

Please be reminded that ALL assignment submissions will be checked for plagiarism at the end of the term. Make sure to maintain your academic integrity carefully, and protect your own work. It is much better to take the hit on a lower assignment mark (just submit something functional, even if incomplete), than risking much worse consequences by committing an academic offence.