Spanning Tree Protocol (STP)
The spanning tree protocol was introduced to get rid of cycles in networks that used bridges and hubs. It does this by forming a spanning tree in the network so that the layer 2 devices use to send messages through.
This is a distributed algorithm and is computed locally on each device in the network for their neighbours. Each device will have a unique ID and the tree will be formed by picking the root of the tree to be the device with the lowest ID. Then each device working out its nearest neighbour to the root of the tree.
This is done iteratively by each device telling its neighbours 4 bits of information:
- The ID of itself,
- The node it believes is the root,
- The shortest distance between itself and that node, and
- If this host thinks that node is the next node in the shortest path to the root. These messages are Bridge Protocol Data Units (BPDUs).
Once it receives a configuration message, it then recalculates what it thinks is the new root and its shortest distance to that root. It then tells all its neighbours about its new status.
To calculate the spanning tree it keeps track of which node is its next nearest neighbour to the root. It splits ties of equal distance paths by taking the path that ends in the root with the lowest ID.
To calculate the set of active connections a node keeps track of which node is the next node in the shortest path to the root and the nodes that think it is the next node in the shortest path to the root. These nodes are the nodes that are considered active links.
When broadcasting and flooding all switches still send messages to all links but a switch only forwards or floods a message it receives on an active connection.
When switches are working out the topology they do not forward regular messages.