<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:






Loops in physical connections create problems for switched networks








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:





Trees are undirected graphs that are connected and have no cycles
















These graphs are not trees



This is not a connected graph.





This graph has cycles.






Useful properties of graphs that are trees







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





Find minimum spanning trees for the following graphs