Physical network connections aim to maximize 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.

The solution is to have a logical topology without loops

Spanning tree protocol (STP)

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.

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.

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

• 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