Programming Challenge: Spanning Tree Protocol

Problem Statement

In this challenge, you will implement a simplified version of the spanning tree protocol. For this challenge, you should assume that a switch and a bridge are the same things. The only practical difference is that bridges have few ports, whereas switches have many many ports.

Spanning Tree Protocol

We saw a gist of this protocol in the last lesson. Let’s build upon that.

Configuration Bridge Protocol Data Units

The spanning tree is created by the exchange of messages between the bridges. These messages are called Configuration Bridge Protocol Data Units, or Configuration BPDUs. We’ll refer to them as BPDUs. The format of a BPDU for this challenge is a list of integers as follows: [Root ID, Cost, Transmitting Bridge ID, Transmitting Port ID]

The following table explains what each field of a BPDU means.

Field	Explanation of field
Root ID	ID of the bridge currently believed/known to be root
Transmitting Bridge ID	ID of the bridge transmitting this BPDU
Cost	Cost of the least cost path from the transmitting bridge to the currently known root
Transmitting Port ID	ID of the port out of which BPDU is transmitted

Comparing Bridge Protocol Data Units

Some BPDUs are better than others. Here’s how to determine which is better.

• A BPDU with a lower root bridge ID is better than a BPDU with a higher root bridge ID.
• If the root bridge ID of both BPDUs is the same, then a BPDU with a lower cost is better than a BPDU with a higher cost.
• If the cost and bridge ID of both BPDUs is the same, then a BPDU with a lower transmitting bridge ID is better than a BPDU with a higher transmitting bridge ID.
• If the cost, the bridge ID, transmitting bridge ID of both BPDUs is the same, then a BPDU with a lower transmitting port ID is better than a BPDU with a higher transmitting port ID.

How It Works

As described above, the protocol aims to build a tree in which one bridge is determined to be the root. Bridges can only forward data frames towards the root bridge or away from the root bridge. In this way, cycles are avoided.

Each bridge is assigned a unique bridge ID and the root bridge is the one with the smallest bridge ID.

1. When a bridge first boots up, it believes itself to be the root, and hence its BPDU looks like [its bridge ID, 0, its bridge ID, Port ID].
2. It multicasts this BPDU to all of its neighbors. The neighbors of this bridge are all the bridges on the LAN segment to which it is connected via any of its ports.
3. It also receives BPDUs from all of its neighbors.
4. It then processes these BPDUS to determine a couple of things:
   1. The root bridge. It declares a port to be root if the root bridge is accessible from this port.
   2. Which ports it should declare blocking. It declares a port blocking if it receives a better BPDU than the one it would have sent on that port. The ports are forwarding by default.
5. Finally, the bridge sends all of this newly learned information to all bridges accessible via its forwarding or root ports.