Spanning tree protocol

From Wikipedia, the free encyclopedia

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 standardized 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, broadcast storm caused by broadcast packets looping between switches would reduce available CPU overhead and bandwidth. Second, the traditional source-based location system used by switches would fail to operate correctly. However, a good network design should include spare (redundant) links to provide an alternate path if one fails. Hence the need for spanning tree in a switched network.

Contents

[edit] Protocol operation

  • Elect a root bridge.
  • Find least cost (measured as sum of all traversed port costs) paths to root bridge.
  • Disable links that are not part of those paths.

[edit] 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 that use spanning tree will use the 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 fully automated.

[edit] 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:

  • Listening - The switch processes BPDUs and determines the network topology
  • Learning - The switch builds a switching table that maps MAC addresses to port numbers
  • Blocking - A port that would cause a switching loop, no user data is sent or received but it may go into forwarding mode if the trunk link in use were to fail. BPDU data is still received in blocking mode
  • Forwarding - A port receiving and sending data, normal operation
  • Disabled - Not strictly part of STP, a network administrator can manually disable a port

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.

[edit] Evolutions and extensions

[edit] Per-VLAN Spanning Tree (PVST)

In Ethernet switched environments where multiple Virtual LANs exist, spanning tree can be deployed per Virtual LAN. Cisco's name for this is per VLAN spanning tree (PVST and PVST+ which is the default protocol used by Cisco switches). Both PVST and PVST+ protocols are Cisco proprietary protocols and they cannot be used on 3rd party switches, and only with ISL 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+.

[edit] 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.

[edit] 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

[edit] 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.

[edit] References

  • Perlman, Radia (2000). Interconnections, Second Edition. USA: Addison-Wesley. ISBN 0-201-63448-1.

[edit] See also

[edit] External links

Retrieved from "http://en.wikipedia.org../../../s/p/a/Spanning_tree_protocol.html"