|
The spanning tree network protocol provides a loop free topology for any bridged LAN. The Spanning Tree Protocol, which is also referred to as STP, is defined in the IEEE Standard 802.1D. Spanning tree is based on an algorithm invented by Radia Perlman while working for Digital Equipment Corporation. STP is used in switched networks to prevent loops, and has been standardised by IEEE 802.1D. As the name suggests it finds a spanning tree within the mesh formed by the network installer and disables the links that are not part of that tree. If more than one open path were to be active at once then there would be several problems. First, there would be a broadcast storm caused by broadcast packets looping. Second, the traditional source-based location system used by switches to operate correctly. The result of this would be to cripple the network. However, a good network design should include spare (redundant) links to provide an alternate path if one fails. Hence the need for spanning tree protocol. Protocol operation Electing a root bridge Each switch has a MAC address and a configurable priority number; both of these numbers make up the bridge identification or BID. The BID is used to elect a root bridge based upon the lowest priority number; if this is a tie then the numerically lowest MAC address wins. Because it is next to impossible that two MAC addresses will be the same (they are uniquely assigned), one switch should always be successfully elected as the root bridge with the switch that has the next lowest priority/cost acting as a secondary (backup) root bridge. Other switches in the network will then apply this same algorithmic process to calculate the shortest path to the root bridge and so produce a loop free tree topology where multiple paths to the root bridge exist. The priority number is normally left at its default value but can be reconfigured to a lower number if the network administrator wishes a particular switch to be elected; otherwise the whole process is totally automated. Bridge Protocol Data Units (BPDUs) BIDs and other Spanning Tree Protocol information are carried in special data frames called bridge protocol data units (BPDUs). BPDUs are exchanged regularly (every 2 seconds by default) and enable switches to keep track of network changes and activate or disable ports as required. When a device is first attached to a switch port, it will not immediately start to forward data. It will instead go through a number of states while it processes BPDUs and determines the topology of the network. When a host is attached such as a computer, printer or server the port will always go into forwarding mode, albeit after a delay of about 50 seconds while it goes through the listening and learning states (see below). However, if instead another ''switch'' is connected, the port may remain in blocking mode if it is determined that it would cause a loop in the network. Topology Change Notification (TCN) BPDUs are used to inform other switches of port changes. TCNs are injected into the network by a non-root switch and propagated to the root. Upon receival of the TCN, the root switch will set a Topology Change flag in its normal BPDUs. This flag is propagated to all other switches to instruct them to rapidly age out their forwarding table entries. STP switch port modes: To prevent the delay when connecting hosts to a switch Rapid STP was developed and standardised by IEEE 802.1w which allows a switch port to go immediately into forwarding mode when an end device is attached. Per-VLAN Spanning Tree (PVST) In Ethernet switched environments where multiple Virtual LANs exist, spanning tree can be deployed per Virtual LAN. PVST can be used with ISL only due to its embedded Spanning tree ID. Due to high penetration of IEEE 802.1q trunking standard and PVST's incompability with 802.1q, Cisco redefined its PVST standard and called it PVST+. Both PVST and PVST+ protocols are Cisco proprietary protocol and they cannot be used on 3rd party switches. Cisco's name for this is per VLAN spanning tree (PVST and PVST+ which is the default protocol used by Cisco switches). Rapid Spanning Tree Protocol (RSTP) In 1998, the IEEE introduced an evolution of the Spanning Tree Protocol: Rapid Spanning Tree Protocol (RSTP) or 802.1w. In the 2004 edition of 802.1D, STP is superseded by the RSTP. Multiple Spanning Tree Protocol (MSTP) The 2003 revision of the standard also rolled in the Multiple Spanning Tree Protocol (MSTP) originally defined in IEEE 802.1s and later merged into IEEE 802.1Q-2003 Trivia Radia Perlman, the inventor of the algorithm summarized it in the form of a poem, titled "Algorhyme": (This poem was modified from the original entitled "Trees", by Joyce Kilmer). I think that I shall never see A graph more lovely than a tree. A tree whose crucial property Is loop-free connectivity. A tree which must be sure to span. So packets can reach every LAN. First the Root must be selected By ID it is elected. Least cost paths from Root are traced In the tree these paths are placed. A mesh is made by folks like me Then bridges find a spanning tree. See also | |||||||
|
| ||||||||
 |
|
| |