Spanning tree (networks)

From Free net 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.

Spanning Tree Protocol operation

STP is used in switched networks to prevent loops, and has been standardised by IEEE 802.1D. Its structure corresponds to that of the spanning tree in graph theory. Networks must have only one path to any destination active at any one point in time, this is called a loop free topology. If more than one open path were to exist then data frames could loop endlessly (known as a broadcast storm) crippling the network. However, a good network design should include spare (redundant) links to provide an alternate path if one fails. The minimum spanning tree algorithm ensures that only one path to a destination is available at any one time by detecting loops and blocking switch ports as required.

Electing a root bridge

A loop free topology looks like a tree and at the base of every tree is its root. In a switched network a "root bridge" (switch) is automatically selected by the spanning tree algorithm. 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 lowest MAC address wins, and because no two MAC addresses are the same one switch will always be successfully elected as the root bridge. Other switches in the network will then calculate the shortest distance to the root bridge using bandwidth as a measurement and so produce a loop free tree topology. 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) 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 another switch is connected the port may remain in blocking mode if it is determined that it would cause a loop in the network.

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
• Forwarding - A port receiving and sending data, normal operation
• 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 sent and received in blocking mode.
• 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.

Evolutions and extensions

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).

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":
(It should be noted that 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.

References

{{cite book

| last = Perlman
| first = Radia
| authorlink = 
| coauthors = 
| year = 2000
| title = Interconnections, Second Edition
| publisher = Addison-Wesley
| location = USA
| id = ISBN 0201634481

}}

External links

• Radia Perlman at Sun Labs
• ANSI/IEEE 802.1D-2004 standard
• Cisco's version of 'Understanding STP'
• RFCs
  • RFC 2674-1999, proposed standard, Definitions of Managed Objects for Bridges with Traffic Classes, Multicast Filtering and Virtual LAN Extensions
  • RFC 1525-1993, - SBRIDGEMIB, proposed standard, Definitions of Managed Objects for Source Routing Bridges
  • RFC 1493-1993 - BRIDGEMIB, draft standard, Definitions of Managed Objects for Bridgesde:Spanning Tree Protocol

it:Spanning Tree Protocol pl:Protokół drzewa opinającego pt:Spanning Tree Protocol ru:STP