Spanning Tree Algorithm

Spanning Tree Concepts :

1.Path Cost

• A cost associated with each port on each bridge ("weight" of the segment)
  default is 1
  
• The cost associated with transmission onto the LAN connected to the port
  
  • Can be manually or automatically assigned
    
  • Can be used to alter the path to the root bridge

2.Root Port

• Each non-root bridge has a Root port: The port on the path towards the root bridge .
  parent pointer
  
• The root port is part of the lowest cost path towards the root bridge If port costs are equal on a bridge, the port with the lowest ID becomes root port .

3.Designated Port

• Each LAN has a single designated port
  
• This is the port reporting minimum cost path to the root bridge for the LAN
  
• Only designated and root ports remain active!

Spanning Tree Requirements

• Each bridge has a unique identifier
  
• A broadcast address for bridges on a LAN
  
• A unique port identifier for all ports on all bridges

--> Bridge id + port number

Spanning Tree Algorithm:Implementation

Keep pumping a single message: (my root ID, my cost to root, my ID)
BPDU: Bridge Protocol Data Unit
Update var's when receiving:
My_root_ID: smallest seen so far
My_cost_to_root: smallest received to my_root + link cost
Break ties by ID
That's enough!

Select Designated Bridges

Bridges send BPDU frames to its attached LANs

• sender port ID
  
• bridge and port ID of the bridge the sending bridge considers root

root path cost for the sending bridge
3. Best bridge wins, and it knows it (and winning port)
(lowest ID/cost/priority)