Thursday, 3 March 2011

Spanning Tree protocol - How to build a tree in any graph

Spanning tree protocol is used in Local Area Network (LAN) to build a tree which ensure that the distance between root and any node has minimum cost.

The final result is a logic network built over the physic network which has the tree structure, avoiding any loop.

The basic steps of the algorithm are
1. Find the root
By the agreement, the root is the node which has lower ID. Where
ID = Priority (configurable) + direction MAC

2. Find the root port of each of the bridges
Normally it is what has the less cost to the root

3. Find the bridge assigned in each LAN
For each LAN, there should be one port that has less cost to the root. Once the bridge is assigned, all the communication will pass thought it.

4. Block all the rest of ports

More information:
http://en.wikipedia.org/wiki/Spanning_Tree_Protocol

No comments:

Post a Comment