Spanning Tree
CS 6250
Spring 2025

PROJECT GOAL

Part 1: Setup

Part 2: Files Layout

There are many files in the SpanningTree directory, but you should only modify Switch.py.

The files in the project skeleton are described below. DO NOT modify these files. All of your work must be in Switch.py ONLY. You should study the other files to understand the project framework.

msg = Message(claimedRoot, distanceToRoot, originID,

destinationID, pathThrough, timeToLive)

• run.py - A "main" file that loads a topology file (see XXXTopo.py below), uses that to create a Topology object containing Switches, and runs the simulation.
• XXXTopo.py, etc. - These are topology files that you will pass as input to the run.py file.

Part 3: TODOs

This is an outline of the code you must implement in Switch.py with suggestions for implementation. Keep in mind that certain update rules will take precedence over others.

A. Decide on the data structure(s) that you will use to keep track of the spanning tree.

1. The collection of active links across all switches is the resulting spanning tree.
2. The data structures may be variable(s) needed to track each switch’s own view of the tree. A switch only has access to its member variables. A switch may not access its neighbor’s information – to learn information from a neighbor, the neighbor must send a message.
3. This is a distributed algorithm. The switch can only communicate with its direct neighbors. It does not have an overall view of the topology as a whole (do not access self.topology).
4. An example data structure should include, at a minimum:

a. a variable to store the switch ID that this switch sees as the root,

b. a variable to store the distance to the switch’s root,

c. a list or other datatype that stores the “active links” (only the links to neighbors that are in the spanning tree).

d. a variable to keep track of which neighbor it goes through to get to the root (a switch should only go through one neighbor, if any, to get to the root).

5. More variables may be used to track data as needed to build the spanning tree and will depend on your specific implementation.

B. Implement processing a message from an immediate neighbor.

I. The switch should update the root stored in its data structure if it receives a message with a lower claimedRoot. 4

II. The switch should update the distance stored in its data structure if a) the switch updates the root, or b) there is a shorter path to the same root.

I. The switch finds a new path to the root (through a different neighbor). In this case, the switch should add the new link to activeLinks and removes the old link from activeLinks

II. The switch receives a message with pathThrough = TRUE but does not have that originID in its activeLinks list. In this case, the switch should add originID to its activeLinks list.

III. The switch receives a message with pathThrough = FALSE but the switch has that originID in its activeLinks. In this case, the switch should remove originID from its activeLinks list

I. The message FIFO queue is maintained in Topology.py. The switch implementation does not interact with the FIFO queue directly, but uses the send_message function, and receives messages as arguments in the process_message function.

II. When sending messages, pathThrough should only be TRUE if the destinationID switch is the neighbor that the originID switch goes through to get to the  claimedRoot.Otherwise, pathThrough should be FALSE.

III. The switch should continue sending messages to its neighbors until the ttl (time to live) on the Message being processed is 0. You need to decrement the ttl every time you process a Message. Note: This is one place where this project deviates from the STP algorithm you learned in the lectures.

a. The switch that is dropped should never split the original topology. That means that the final Topology will remain connected.

b. The switch that is dropped could be the original root, your algorithm should adapt accordingly.

c. The Topology file will include the ttl_limit and drops. The ttl_limit is the starting ttl for each message in the Topology. The drops indicate which switch(es) will be dropped.

d. You do not need to access the ttl_limit. This will be given to each message at the start of the process. You need to decrement the ttl to 0 to trigger the

Topology’s drop process.

3. Sorted:         Not sorted:

Part 4: Testing and Debugging

To run your code on a specific topology (SimpleLoopTopo.py in this case) and output the results to a text file (out.txt in this case), execute the following command: 

python run.py SimpleLoopTopo

“SimpleLoopTopo” is not a typo in the example command – don’t include the .py extension.

We have included several topologies with correct solutions for you to test your code against. You can (and are encouraged to) create more topologies and test suites with output files and share them on Ed Discussion. There will be a designated post where students can share these files.6

You will only be submitting Switch.py – your implementation must be confined to modifications of that file. We recommend testing your submission against a clean copy of the rest of the project files prior to submission.

You may add print statements to facilitate debugging during your development process, but they should be removed or commented out prior to submission.

Part 5: Assumptions and Clarifications

What to Turn In

Submit ONLY your Switch.py file to Gradescope as a single file. Do not modify the name of Switch.py. You may make an unlimited number of submissions to Gradescope before the deadline. Your last submission will be your grade unless you activate a different submission.

Before submission:

a. Any Honor Code violations will result in a 0 and be referred to OSI.

b. Any attempt to bypass or distort the autograder will result in a 0 and will be referred to OSI.

What you can and cannot share

Honor Code/Academic Integrity: Do NOT share any code from Switch.py with your fellow students, on Ed Discussion, or publicly in any form, even after the course ends. You may share log files for any topology, and you may share any code you write that will not be turned in, such as new topologies or testing suites.

All work must be your own, and consulting Spanning Tree Protocol solutions, even in another programming language or just for reference, are considered violations of the honor code. Do not reference solutions on Github! Do not use IDE extensions (like Github Copilot or any AI) that write or recommend blocks of code to you (autocomplete for function names is fine). For more information see the Syllabus Definition of Plagiarism. We provide you with all the materials you need to complete this project without help from Google/Stack Overflow (Searching basic Python syntax is fine). Do not risk an honor code violation for a very doable project.

Start early, ask questions in Ed Discussion, and attend TA chat sessions if needed.

Rubric