Spanning Tree Algorithm

Wed Nov 26, 2008 11:04 pm

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 .

: Example Spanning Tree

: Example Spanning Tree cont

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!

: Example Spanning Tree cont2

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)