The Spanning Tree Protocol (STP) is a network protocol that ensures a loop-free topology for any bridged Ethernet local area network. The basic function of STP is to prevent bridge loops and the broadcast radiation that results from them. Spanning tree also allows a network design to include spare (redundant) links to provide automatic backup paths if an active link fails, without the danger of bridge loops, or the need for manual enabling/disabling of these backup links.
Spanning Tree Protocol (STP) was originally standardized as IEEE 802.1D, in 802.1d-1998, but much of the functionality (spanning tree, rapid spanning tree, multiple spanning tree) previously specified in 802.1D, 801.1s, 802.1w has been incorporated into IEEE 802.1Q-2014 which includes shortest path bridging, the IEEE sanctioned replacement for these spanning tree functions.
As the name suggests, it creates a spanning tree within a network of connected layer-2 bridges (typically Ethernet switches), and disables those links that are not part of the spanning tree, leaving a single active path between any two network nodes. STP is based on an algorithm that was invented by Radia Perlman while she was working for Digital Equipment Corporation.
Protocol Operation
A local area network (LAN) can be depicted as a graph whose nodes are bridges and LAN segments (or cables), and whose edges are the interfaces connecting the bridges to the segments. To break loops in the LAN while maintaining access to all LAN segments, the bridges collectively compute a spanning tree. The spanning tree is not necessarily a minimum cost spanning tree. A network administrator can reduce the cost of a spanning tree, if necessary, by altering some of the configuration parameters in such a way as to affect the choice of the root of the spanning tree.
Select a root bridge. The root bridge of the spanning tree is the bridge with the smallest (lowest) bridge ID. Each bridge has a configurable priority number and a MAC Address; the bridge ID contains both numbers combined together - bridge priority + MAC (32768.0200.0000.1111). The bridge priority default is 32768 and can only be configured in multiples of 4096 (Spanning tree incorporated 802.1t, and per 802.1t, uses the 4 most-significant bits of the 802.1d two-octet priority field as priority, and the least-significant 12 bits of that field as the extended system ID). When comparing two bridge IDs, the priority portions are compared first and the MAC addresses are compared only if the priorities are equal. The switch with the lowest priority of all the switches will be the root; if there is a tie, then the switch with the lowest priority and lowest MAC address will be the root. For example, if switches A (MAC=0200.0000.1111) and B (MAC=0200.0000.2222) both have a priority of 32768 then switch A will be selected as the root bridge. The original 802.1d envisioned the possibility of the root bridge having more than one port on the same LAN segment, and in that case, the port with the lowest port ID would become the designated port for that LAN segment, and put into forwarding mode, while its other ports on that same LAN segment became non-designated ports put into blocking mode. Not all bridge manufacturers follow that rule, some making all ports designated ports and putting them all into forwarding mode. If the network administrators would like switch B to become the root bridge, they must set its priority to be less than 32768 or configure the spanning tree a root primary/secondary. When configuring the root primary and root secondary the switch will automatically change the priority accordingly, 24576 and 28672 respectively with the default configuration.
Determine the least cost paths to the root bridge. The computed spanning tree has the property that messages from any connected device to the root bridge traverse a least cost path, i.e., a path from the device to the root that has minimum cost among all paths from the device to the root. The cost of traversing a path is the sum of the costs of the segments on the path. Different technologies have different default costs for network segments. An administrator can configure the cost of traversing a particular network segment. The property that messages always traverse least-cost paths to the root is guaranteed by the following two rules.
Least cost path from each bridge. After the root bridge has been chosen, each bridge determines the cost of each possible path from itself to the root. From these, it picks one with the smallest cost (a least-cost path). The port connecting to that path becomes the root port (RP) of the bridge.
Least cost path from each network segment. The bridges on a network segment collectively determine which bridge has the least-cost path from the network segment to the root. The port connecting this bridge to the network segment is then thedesignated port (DP) for the segment.
Disable all other root paths. Any active port that is not a root port or a designated port is a blocked port (BP).
Modifications in case of ties. The above rules over-simplify the situation slightly, because it is possible that there are ties, for example, the root bridge may have two or more ports on the same LAN segment, two or more ports on a single bridge are attached to least-cost paths to the root or two or more bridges on the same network segment have equal least-cost paths to the root. To break such ties:
Breaking ties for root ports. When multiple paths from a bridge are least-cost paths, the chosen path uses the neighbor bridge with the lower bridge ID. The root port is thus the one connecting to the bridge with the lowest bridge ID. For example, in figure 3, if switch 4 was connected to network segment d instead of segment f, there would be two paths of length 2 to the root, one path going through bridge 24 and the other through bridge 92. Because there are two least cost paths, the lower bridge ID (24) would be used as the tie-breaker in choosing which path to use.
Breaking ties for designated ports. When the root bridge has more than one port on a single LAN segment, the bridge ID is effectively tied, as are all root path costs (all equal zero). The designated port then becomes the port on that LAN segment with the lowest port ID. It's put into Forwarding mode while all other ports on the root bridge on that same LAN segment become non-designated ports and are put into blocking mode.[4] Not all bridge/switch manufacturers follow this rule, instead making all root bridge ports designated ports, and putting them all in forwarding mode. A final tie-breaker is required as noted in the section "The final tie-breaker."
When more than one bridge on a segment leads to a least-cost path to the root, the bridge with the lower bridge ID is used to forward messages to the root. The port attaching that bridge to the network segment is the designated port for the segment. In figure 4, there are two least cost paths from network segment d to the root, one going through bridge 24 and the other through bridge 92. The lower bridge ID is 24, so the tie breaker dictates that the designated port is the port through which network segment d is connected to bridge 24. If bridge IDs were equal, then the bridge with the lowest MAC address would have the designated port. In either case, the loser sets the port as being blocked.
The final tie-breaker. In some cases, there may still be a tie, as when the root bridge has multiple active ports on the same LAN segment (see above, "Breaking ties for designated ports") with equally low root path costs and bridge IDs, or, in other cases, multiple bridges are connected by multiple cables and multiple ports. In each case, a single bridge may have multiple candidates for its root port. In these cases, candidates for the root port have already received BPDUs offering equally-low (i.e. the "best") root path costs and equally-low (i.e. the "best") bridge IDs, and the final tie breaker goes to the port that received the lowest (i.e. the "best") port priority ID, or port ID.
In summary, the sequence of events to determine the best received BPDU (which is the best path to the root) is
- Lowest root bridge ID - Determines the root bridge
- Lowest cost to the root bridge - Favors the upstream switch with the least cost to root
- Lowest sender bridge ID - Serves as a tie breaker if multiple upstream switches have equal cost to root
- Lowest sender port ID - Serves as a tie breaker if a switch has multiple (non-Etherchannel) links to a single upstream switch, where:
- Bridge ID = priority (4 bits) + locally assigned system ID extension (12 bits) + ID [MAC address] (48 bits); the default bridge priority is 32768, and
- Port ID = priority (4 bits) + ID (Interface number) (12 bits); the default port priority is 128.
Data rate and STP path cost
The access speeds of the links determine the path cost that STP/RSTP assumes. The STP path cost default was originally calculated by the formula 1 Gigabit / secondbandwidth. When faster speeds became available the default values were adjusted as otherwise speeds above 1 Gbit/s would have been indistinguishable by STP. Its successor RSTP uses a similar formula with a larger numerator: 20 Terabit / secondbandwidth. These formulas lead to the sample values in the table below:[6]:154
| Data rate | STP cost (802.1D-1998) | RSTP cost (802.1W-2004, default value)[6]:154 |
|---|---|---|
| 4 Mbit/s | 250 | 5,000,000 |
| 10 Mbit/s | 100 | 2,000,000 |
| 16 Mbit/s | 62 | 1,250,000 |
| 100 Mbit/s | 19 | 200,000 |
| 1 Gbit/s | 4 | 20,000 |
| 2 Gbit/s | 3 | 10,000 |
| 10 Gbit/s | 2 | 2,000 |
Bridge Protocol Data Units
The above rules describe one way of determining what spanning tree will be computed by the algorithm, but the rules as written require knowledge of the entire network. The bridges have to determine the root bridge and compute the port roles (root, designated, or blocked) with only the information that they have. To ensure that each bridge has enough information, the bridges use special data frames called Bridge Protocol Data Units (BPDUs) to exchange information about bridge IDs and root path costs.
A bridge sends a BPDU frame using the unique MAC address of the port itself as a source address, and a destination address of the STP multicast address 01:80:C2:00:00:00.
There are two types of BPDUs in the original STP specification[6]:63 (the Rapid Spanning Tree (RSTP) extension uses a specific RSTP BPDU):
- Configuration BPDU (CBPDU), used for Spanning Tree computation
- Topology Change Notification (TCN) BPDU, used to announce changes in the network topology
BPDUs are exchanged regularly (every 2 seconds by default) and enable switches to keep track of network changes and to start and stop forwarding at 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 the forwarding state, albeit after a delay of about 30 seconds while it goes through the listening and learning states (see below). The time spent in the listening and learning states is determined by a value known as the forward delay (default 15 seconds and set by the root bridge). 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 receipt 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 states:
- Blocking - A port that would cause a switching loop if it were active. No user data is sent or received over a blocking port, but it may go into forwarding mode if the other links in use fail and the spanning tree algorithm determines the port may transition to the forwarding state. BPDU data is still received in blocking state. Prevents the use of looped paths.
- Listening - The switch processes BPDUs and awaits possible new information that would cause it to return to the blocking state. It does not populate the MAC address table and it does not forward frames.
- Learning - While the port does not yet forward frames it does learn source addresses from frames received and adds them to the filtering database (switching database). It populates the MAC Address table, but does not forward frames.
- Forwarding - A port receiving and sending data, normal operation. STP still monitors incoming BPDUs that would indicate it should return to the blocking state to prevent a loop.
- Disabled - Not strictly part of STP, a network administrator can manually disable a port
To prevent the delay when connecting hosts to a switch and during some topology changes, Rapid STP was developed, which allows a switch port to rapidly transition into the forwarding state during these situations.
Bridge Protocol Data Unit fields
IEEE 802.1D and IEEE 802.1aq BPDUs have the following format:
1. Protocol ID: 2 bytes (0x0000 IEEE 802.1D)
2. Version ID: 1 byte (0x00 Config & TCN / 0x02 RST / 0x03 MSTP / 0x04 SPT BPDU)
3. BPDU Type: 1 byte (0x00 Config BPDU, 0x80 TCN BPDU, 0x02 RST BPDU)
4. Flags: 1 byte
bits : usage
1 : 0 or 1 for Topology Change
2 : 0 (unused) or 1 for Proposal in RST/MST/SPT BPDU
3-4 : 00 (unused) or
01 for Port Role Alternate/Backup in RST/MST/SPT BPDU
10 for Port Role Root in RST/MST/SPT BPDU
11 for Port Role Designated in RST/MST/SPT BPDU
5 : 0 (unused) or 1 for Learning in RST/MST/SPT BPDU
6 : 0 (unused) or 1 for Forwarding in RST/MST/SPT BPDU
7 : 0 (unused) or 1 for Agreement in RST/MST/SPT BPDU
8 : 0 or 1 for Topology Change Acknowledgement
5. Root ID 8 bytes (CIST Root ID in MST/SPT BPDU)
bits : usage
1-4 : Root Bridge Priority
5-16 : Root Bridge System ID Extension
17-64 : Root Bridge MAC Address
6. Root Path Cost: 4 bytes (CIST External Path Cost in MST/SPT BPDU)
7. bridge id: 8 bytes (CIST Regional Root ID in MST/SPT BPDU)
bits : usage
1-4 : Bridge Priority
5-16 : Bridge System ID Extension
17-64 : Bridge MAC Address
8. Port ID 2 bytes
9. Message Age: 2 bytes in 1/256 secs
10. Max Age: 2 bytes in 1/256 secs
11. Hello Time: 2 bytes in 1/256 secs
12. Forward Delay: 2 bytes in 1/256 secs
13. version 1 Length: 1 byte (0x00 no ver 1 protocol info present. RST, MST, SPT BPDU only)
14. version 3 Length: 2 bytes (MST, SPT BPDU only)
The TCN BPDU includes fields 1-3 only.
No comments:
Post a Comment