802.1d (Standard Spanning-tree)
So the entire goal of spanning-tree is to create a loop free layer 2 domain. There is no TTL in a layer 2 frame so if you don’t have spanning-tree, a frame can loop forever. So the original 802.1d standard set out to fix this. There are a few main pieces to the 802.1d process. They are…
1. Elect a root bridge.
This bridge is the ‘root’ of the spanning-tree. In order to elect a root bridge, all of the switches send out BPDU (Bridge Protocol Data Units). The BPDU has a bridge priority in it which the switches use to determine which switch should be the root. The lowest ID wins. The original standard specified a bridge ID as…
As time progressed there became a need to create multiple spanning-trees for multiple VLANs (we’ll get to that later). So, the bridge ID format had to be changed. What they came up with was..
So, now you know why you need to have a bridge priority that’s in multiples of 4096 (if you don’t.. A total of 4 bits gives you a total of 16 values, 16 * 4096 gives you 65,536 which is the old bridge priority max value – 1).
So at this point, we have a mess of switches swarming around with BPDUs. If a switch receives a BPDU with a lower bridge priority it knows that it isn’t the root. At that point, it stops sending out it’s own bridge ID and starts sending out BPDUs with the better (lower) priority that it heard of. In the end, all of the switches will be forwarding BPDUs with the lowest bridge ID. At that point, the switch originating the best(lowest) bridge ID knows that it is the root bridge.
2. Each switch selects a root portSo now that we know which switch is the root, every non-root switch needs to select it’s root port. That is, the port with the lowest cost to the root switch. To determine this, the root port sends ‘Hellos’ out of all of it’s port every 2 seconds. When a non-root switch receives the hello, it does a couple of things. First, it reads the ‘cost’ from the hello message and updates it by adding the port cost. So if a hello came in a fast Ethernet port with a cost of 4, the switch would add 19 to it giving you a new cost of 23. After all of the hellos are sent, the switch picks it’s root port by selecting the port which had the lowest calculated cost. Now, a bit about port costs. See the table below…
|Original IEEE Port Cost||New IEEE port Cost|
So as you can see, with the increase in speed came a upgrade to the port costs. Now that we have 40 gig interfaces I’m wondering if they will redo that again. At any rate, if there is a tie, say two ports that have a calculated cost of 23. The switch breaks the tie in the following fashion..
1. Pick the lowest bridge ID of switch that sent the hellos
2. Pick the lowest port priority of the switch that sent the hellos
3. Use the lowest port number of the switch that sent the hellos
(We’ll talk about port priorities in a bit) Now that we have a root port we can move onto step 3.
3. Pick a designated portThis part is pretty easy. Basically, each segment can only have one designated port. The switch that forwards the lowest cost hello onto a particular segment becomes the designated switch and the port that it uses to do that is the designated port. So, that would mean that each port on the root bridge would be a designated port. Then, ports that are neither root ports or designated ports (non-designated ports) go into blocking state. If a tie occurs, the same tiebreaker process occurs as in step 2.
At this point, we have a fully converged spanning-tree!
Normal OperationUnder normal operation the root sends hellos out of all it’s active ports. Each connected switch receives the hellos on their root ports, updates it, and forwards it out of it’s designated port (if it has one). Blocked ports receive the hellos, but never forward them.
When a switch notices a topology change, it’s responsible for telling all other connected switches about the change. The most effective way to do this, is to tell the root switch so that it can tell all of the other switches. When a switch notices a topology change, it sends a TCN (topology change notification) out it’s root port. The switch will send the TCN every hello time until the upstream switch acknowledges it. The upstream switch acknowledges by sending a hello with a TCA (topology change acknowledgement). This process continues until the root becomes notified. The root will then set the TC flag on it’s hellos. When switches in the tree see the TC set in the hello from the root, they know that there has been a topology change and that they need to age out their CAM tables. Switches aging out their CAM tables is an important part of a topology change and reconvergence.
802.1D Port States
Blocking – The port is blocking all traffic with the exception of receiving STP BPDUs. The port will not forward any frames in this state.
Listening – Same as blocking but will now begin to send BPDUs.
Learning – The switch will begin to learn MAC information in this state.
Forwarding – Normal full up and up port state. Forwarding normal traffic.
TimingThere are a couple of main timers in the STP protocol. These are..
Forward Delay Timer – Default of 15 seconds
Hello – Default of 2 seconds
MaxAge – Default of 20 seconds
Spanning-Tree enhancements (Cisco Proprietary)
PortFast – Immediately puts a port into forwarding mode. Essentially disables the STP process. Should only be used for connecting to end hosts.
UplinkFast – Should be used on access layer switches connecting to distribution. Used to fail over the root port in the case of the primary root port failing. CAM entries are timed out by the access layer generating multicast frames with attached devices MACs as the source for the frames. This is different than the normal TCN process as described earlier. UplinkFast also causes the switch to increase the root priority to 49152 and set all of the ports costs to 3000.
BackboneFast – Used to detect indirect STP failures. This way the switch doesn’t have to wait MaxAge to reconverge. The feature needs to be configured on all switches in order for it to work. The switch queries it’s upstream switches when it sops receiving hellos with a RLQ (Root Link Query). If the upstream switch had a failure it can reply to the local switch so that it can converge to another port without waiting for the MaxAge to expire.
802.1w (Rapid Spanning-Tree)
Rapid spanning-tree takes 802.1d and makes it faster. In addition, they take some of the Cisco proprietary features and standardize them. Here are some of the notable changes that 802.1w makes.
-Switches only wait to miss 3 hellos on their root port prior to reconverging. This number in 802.1d was 10 (MaxAge, or 10 times hello).
-Fewer port states. 802.1w takes the number of port states from 5 (Im counting disabled) down to 3.
The new states are discarding, learning, and forwarding.
-Concept of a backup DP when a switch has multiple ports connected to the same segment.
-Standardization of the Cisco proprietary PortFast, UplinkFast, and BackboneFast.
802.1w Link TypesPoint to Point – Connects a switch to another switch in full duplex mode.
Shared – Connects a switch to a hub using half duplex
Edge – A user access port
802.1w Port roles
Root Port – The same as in 802.1d
Designated Port – The same as in 802.1d
Alternate Port – Same as the uplink fast feature, backup RP connection
Backup Port – Alternate DP port, can take over if the existing DP fails
802.1s (Multiple Spanning-Tree)
Multiple spanning-tree (MST) lets you map VLANs into a particular spanning tree. These VLANs are then considered to be part of the same MST region. MST uses the same features as RSTP for convergence, so if you are running MST, you are by default also running RSTP. Much like any other ‘group’ technology, there are several parameters that must be met before switches/vlans can become part of the same region.
-MST must be globally enabled
-The MST region name must be configured (and the same on each switch)
-Define the MST revision number (and make it the same on each switch)
-Map the same VLANs into each region (or instance)
MST can con-exist with other switches that don’t talk MST. In this case, the entire MST region appears to be a single switch to the other ‘external’ spanning-tree. The spanning-tree that connects the region to the ‘outside’ is considered to be the IST, or Internal Spanning Tree.
There are several ‘protection’ mechanisms available that can be implemented in conjunction with spanning-tree to protect the spanning-tree from failure or loops.
BPDU Guard – Should be enabled on all ports that will never connect to anything but an end user port. The configuration will err-disable a port if a BPDU is received on that port. To recover from this condition the port must be shut/no shut.
Root Guard – Protects the switch from choosing the wrong RP. If a superior BPDU is heard on this port the port is placed into root-inconsistent state until the BPDUs are no longer heard.
UDLD – Unidirectional link detection is used to detect when one side (transmit or receive) is lost. States like this can cause loops and loss of connectivity. UDLD functions in two modes, aggressive and normal. Normal mode uses layer 2 messaging to determine if a switches transmission capabilities have failed. If this is detected, the switch with the failed transmit side goes into err-disable. In aggressive mode the switch tries to reconnect with the other side 8 times. If this fails, both sides go into err-disable.
Loop Guard – When a port configured with loop guard stops hearing BPDUs it goes into loop-inconsistent state rather than transitioning into forwarding.