Description

In the lectures, you learned about Spanning Trees, which can be used to prevent forwarding loops on a layer 2 network. In this project, you will develop a simplified distributed version of the Spanning Tree Protocol that can be run on an arbitrary layer 2 topology (a topology of arbitrary nodes and links consisting of connected, uniquely-numbered switches with nonredundant links – see “Key assumptions and clarifications” below). This project is different from the previous project in that we’re not running the simulation using the Mininet environment (Don’t worry, Mininet will be back in later projects!). Rather, we will be simulating the communications between switches until they converge on a single solution, and then output the final spanning tree to a file. For this project, please use the class VM that you set up and used for Project 1.
• Project 2 Posted @81
• Project 2 Questions about Project Code @80
• Project 2 Test Topologies, Spanning Tree Outputs/Log Files, and Test Suites
@79
• Project 2 Infinite Loops/Message Processing/Queues @78
• Project 2 What is pathThrough? @77
• Project 2 Assumptions and Clarifications in the Project Description @76
• Project 2 Log File Formatting @75
Project Layout
In the Project2 directory, you can see quite a few files. You only need to (and should only) modify one of them, Switch.py. It represents a layer 2 switch that implements our simple Spanning Tree Protocol. You will have to implement the functionality described in the lectures and at the links above in the code sections marked with TODO comments to generate a Spanning Tree for each Switch.
The other files that form the project skeleton are:
• Topology.py – Represents a network topology of layer 2 switches. This class reads in the specified topology and arranges it into a data structure that your switch code can access.
• StpSwitch.py – A superclass of the class you will edit in Switch.py. It abstracts certain implementation details to simplify your tasks.
• Message.py – This class represents a simple message format you will use to communicate between switches. The format is similar to what was described in the course lectures. Specifically, you will create and send messages in Switch.py by declaring a message as msg
= Message(claimedRoot, distanceToRoot, originID, destinationID, pathThrough) and assigning the correct data to each input. See the comments in Message.py for more information on the data in these variables.
• run_spanning_tree.py – A simple “main” file that loads a topology file (see XXXTopo.py below), uses that data to create a Topology object containing Switches, and starts the simulation.
• XXXTopo.py, etc – These are topology files that you will pass as input to the
run_spanning_tree.py file.

• sample_output.txt – Example of a valid output file for Sample.py as described in the comments in Switch.py.
Here is an outline of the few sections of code that you will have to complete in Switch.py with suggestions for implementing the code, but you are free to implement your distributed spanning tree algorithm in other ways as long as it adheres to the spirit of the project and completes the labeled TODO sections in the project code per the comments in the code:
2. Implement the Spanning Tree Protocol by writing code that sends the initial messages to neighbors of the switch, and processes a message from an immediate neighbor. The comments describe how to send messages to immediate neighbors using the provided superclass. The messages are processed as a FIFO queue. As each switch processes messages, it compares the received message data to the data in its data structure to build the spanning tree. The switches do not need to push or pop on the FIFO queue since Topology.py does this for the switch as each switch calls send_msg.
The switch will update the root stored in the data structure if the switch receives a message with a root of a lower ID. The switch will update the distance stored in the data structure if the switch updates the root or if there is a tiebreaker situation that indicates a shorter path to the root. The switch will change the activeLinks stored in the data structure in two situations: First, if the switch finds a new path to the root, meaning the switch goes through a new neighbor to get to the root, so the switch will ensure the new neighbor is in its activeLinks. Second, if the switch receives a message with pathThrough = True but the switch did not have that originID in its activeLinks list, so the switch must add originID to the activeLinks list or if the switch receives a message with paththrough = False but the switch has that originID in its activeLinks so it needs to remove originID from the activeLinks list.
3. Write a logging function that is specific to your particular data structure. The format is simple, and should output only the links active in spanning tree.
To run your code on a specific topology (SimpleLoopTopo in this case) and output the results
to a text file (out.txt in this case), execute the following command:
python run_spanning_tree.py SimpleLoopTopo out.txt

For this project, you will be able to create as many topologies as you wish and share them on Piazza. We encourage you to share new topologies, and your output files to confirm correctness of your algorithm. We have included several topologies for you to test your code against.

Key assumptions and clarifications
To avoid confusion, there are some assumptions we will make about behaviors of switches in this project:
1. You should assume that all switch IDs are positive integers, and distinct. These integers do not have to be consecutive and they will not always start at 1.
2. Tie breakers: All ties will be broken by lowest switch ID, meaning that if a switch has multiple paths to the root at the same length, it will select the path through the lowest id neighbor. For example, assume switch 5 has two paths to the root, through switch 3 and switch 2. Assume further each path is 2 hops in length, then switch 5 will select switch 2 as the path to the root and disable forwarding on the link to switch 3.
3. Combining points one and two above, there is a single distinct solution spanning tree for each topology.
4. You can assume all switches in the network will be connected to at least one other switch, and all switches are able to reach every other switch.
5. You can assume that there will be no redundant links and there will be only 1 link between each pair of connected switches.
6. You can assume that the topology given at the start will be the final topology and there won’t be any changes as your algorithm runs (i.e adding a new switch).
7. Note that when a switch deactivates/blocks a port, this port is not completely discarded. While the switch treats it as inactive, it will still be communicated with during the simulation.

What to turn in

You only need to turn in the file you modify, Switch.py to Canvas, but you need to zip the file with your GTID you use to log into Canvas and the project number, such as mmckinzie5_p2.zip.
Be sure Switch.py is at the top directory in the zip file such that when it is unzipped.
There are some very important guidelines for this file you must follow:

1. Your submission must terminate! If your submission runs indefinitely (i.e. contains an infinite loop, or logic errors prevent solution convergence) it will not receive full credit. Termination here is defined as self-termination by the process. Manually killing your submission via console commands or interrupts is not an acceptable means of termination. The simulation stops when there are no messages left to send, at which time the logging function is called for each switch.
2. Pay close attention to the logging format! Our autograder expects your logs to be in a very specific format, specified in the comments. We provide you an example of a valid output log as well. Also pay close attention to how the links in the spanning tree should be ordered, separated in your log file, and what information belongs on its own line. Don’t log anything other than what we ask you to! We provide example logs in the Logs directory.
3. Remove any print statements from your code before turning it in! Print statements left in the simulation, particularly for inefficient but logically sound implementations, have drastic effects on run-time. Your submission should take well less than 10 seconds to process a topology. If your leave print statements in your code and they adversely affect the grading process, your work will not receive full credit. Feel free to use print statements during the project for debugging, but please remove them before you submit to Canvas.

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 switch level. Each switch only knows its internal state, and the information passed to it via messages from its direct neighbors – the algorithm must be based on these messages.
The skeleton code we provide you runs a simulation of the larger network topology, and for the sake of simplicity, the StpSwitch class defines a link to the overall topology. This means it is possible using the provided code for one Switch to access another’s internal state. This goes against the spirit of the project, and is not permitted. Additional detail is available in the comments of the skeleton code.
Additionally, you are not permitted to change the message passing format. We will not accept modified versions of Message.py, nor are you permitted to subclass the Message class.
When we grade your code, we will use a special version of the skeleton code that will have a

What you can (and cannot) share

Grading

10 pts Correct
Submission for turning in all the correct files with the correct names, and significant effort has been made in each file towards completing the project.
60 pts Provided
Topologies for correct Spanning Tree results (log file) on the provided topologies.
80 pts Unannounced
GRADING NOTE: Partial credit is not available for individual topology spanning tree output files. The output spanning tree must be correct to receive credit for that input topology. Thus, missing a single link will result in losing credit for that topology. Additionally, we will be using many topologies to test your project, including but not limited to the topologies we provide.

Additional Tips and Resources
Creating the Data Structure:

It is important to create a data structure in the correct place in Python (and most object oriented programming languages). If you create it inside a method, every time method is called it will be created as new. You should create a class object in the class constructor so that the data stored in the object exists for the life of the class instance that is created by Topology.py. For example self.mylist = [ ] in the constructor should create an empty list data structure and act as instance variable. But if mylist were instantiated in, say, process_messages, then it will be created every time the method is called. This could be useful in how you track which links are active to certain neighbors for any given switch.

Logging the Output

The output must be sorted. For example, your output should be:

1 – 2, 1 – 3
2 – 1, 2 – 4
3 – 1
4 – 2
However, this is not sorted:

1 – 3, 1 – 2,
2 – 4, 2 – 1,
4 – 2
3 – 1

Use of pathThrough

Questions to ask yourself
1. How does an infinite loop happen? When does each switch know it has a complete view of the tree or it should stop processing? How do the queues empty?
2. What is that pathThrough variable in the project code? Why is it required? Why did the project creators force that structure on the project?
3. Why did we have to give those assumptions? What would be unclear if they were not included?
4. How should the log files be formatted? Commas, semicolons, line endings? What is meant by
sorted?