<http://lib.cnfolio.com/ENG653SpanningTreeAlgorithm>
WAN and VLAN Solutions

## Spanning tree algorithm

### Physical network connections aim to maximize redundancy

Multiple connections are made between switches and network segments in case of problems with some connections. Networks improve fault tolerance by increasing redundancy:
• Reduce or eliminate single points of failure
• Design multiple paths between devices and segments

### Loops in physical connections create problems for switched networks

• Broadcast storms occur when frames are continually flooded out of all ports of switches connected in a loop.
• Instability of MAC addresses tables occur when switches learn the wrong ports for MAC addresses because duplicate frames are transmitted by switches connected in a loop.

Routers do not have problems with loops because Layer 3 frame headers have a Time to Live (TTL) field, which is decremented each time the frame is forwarded and eventually discarded when the TTL reaches zero.

### The solution is to have a logical topology without loops

Spanning tree protocol was invented in 1985 by Radia Perlman to establish a logical topology which is a subset of the physical network connections.

### Spanning tree protocol (STP)

STP was published as the 802.1D standard by the IEEE in 1990 based on the algorithm developed by Radia Perlman. The key steps of the protocol are:
1. Select the switch in the network with the lowest ID as called it the root bridge. The ID is based on a combination of the MAC address of the switch and a configurable priority value.
2. Identify the lowest cost paths to the root bridge by identifying these ports:
• Identify the root port for each switch (other than the root bridge) which is the port that has the least cost path to the root bridge.
• Select a designated port for each network segment, which is the root port of the switch that has the least cost path to the root bridge.
• Bridge Protocol Data Units (BPDU) are special frames used by switches to update each other about the physical network connections and the current logical network topology.
3. Set the state for all switch ports as follows:
• Forwarding ports operates normally to forward data frames, receive data frames, populate MAC address tables from incoming data frames and listen for incoming BPDUs in case there is need to transition to a different state.
• Blocking ports do not forward or receive data frames and do not populate MAC address tables. They listen for incoming BPDUs in case there is need to transition to a different state.
• Learning ports do not forward data frames, but they do receive data frames and update MAC address tables. They listen for incoming BPDUs in case there is need to transition to a different state.
• Listening ports do not forward or receive data frames and do not populate MAC address tables. They listen for incoming BPDUs in case there is need to transition to a different state. Ports in listening state are preparing to move to forwarding state.
• Disabled ports are manually configured by a network adminstrator.

There are a number of competing protocols aiming to replace STP, including:
• MLAG from Extreme Networks
• QFabric from Juniper
• FabricPath from Cisco
• TRILL from IETF
• Shortest Path Bridging from IEEE

### Trees are undirected graphs that are connected and have no cycles

• A connected graph has at least one path between each pair of vertices.
• A cycle is a sequence of connected vertices that start and end at the same vertex.

### These graphs are not trees

This is not a connected graph.

This graph has cycles.

### Useful properties of graphs that are trees

• A tree with n vertices has n-1 edges.
• There is always exactly one path from each vertex to any other vertex in a tree.
• A spanning tree for a graph is a tree that includes every vertex of the original graph.
• Any node of a tree can be considered as the root node.
• If each edge has an associated weight, a spanning tree that has minimum total weight is called a minimum-weight spanning tree, which is shortened to just minimum spanning tree.

### Prim's algorithm to find a minimum spanning tree

START
Randomly select one vertex of the graph to be the first vertex
of the spanning tree
WHILE there is a vertex missing from the spanning tree
Find the smallest edge which connects a vertex in the spanning tree
to a vertex not yet in the spanning tree
Add that edge and vertex to the spanning tree
END WHILE
END

Notes about the operation of Prim's algorithm
• When there are multiple edges of equal weight, you may select any edge (the reason is that there may be multiple different minimum spanning trees)
• Do not select a vertex if that edge would create a cycle (if so, that would no longer be a tree)
• The weight of the minimum spanning tree is the sum of the weights of all the edges