Quick Notes: Spanning Tree Protocol (CCIE Official Cert Guide - Chapter 3)

From: CCIE Routing and Switching v5.0 Official Cert Guide, Volume 1, 5th Edition

802.1D Spanning Tree Protocol and Improvements 
  • The first IEEE standardized STP, often called the "legacy" STP, was originally described in 802.1D.
  • Its improvements were subsequently published in so-called amendments: Rapid Spanning Tree Protocol (RSTP) in 802.1w and Multiple Spanning Tree Protocol in 802.1s.
  • Since then, the amendments have been integrated into existing standards. The 802.1D-2004 covers RSTP (originally 802.1w), and the legacy STP is no longer included.
  • MSTP (802.1s) is integrated into 802.1Q-2005 and later revisions.
  • In short, RSTP is overed in 802.1D, MSTP is covered in 802.1Q, and legacy STP has been dropped.

STP Operation 
  • STP uses messaging between switches to stabilize the network into a logical loop-free topology. STP protocol messages are called Bridge Protocol Data Units (BPDU).
  • There are two types of STP BPDUs: Configuration BPDUs ("normal" BPDUs) and Topology Change Notification BPDUs (TCN BPDUs)
  • STP operation is based on the ability to compare any two arbitrary Configuration BPDUs and determine which one of them is better, or superior . The other BPDU is called inferior. 
  • To determine which BPDU out of a pair of BPDUs is superior, they are compared in the following sequence of values, looking for the first occurrence of a lower value:
    • Root Bridge ID (RBID)
    • Root Path Cost (RPC)
    • Sender Bridge ID (SBID)
    • Sender Port ID (SPID)
    • Receiver Port ID (RPID; not included in the BPDU, evaluated locally - uncommon)
  • The capability of selecting a single superior BPDU out of a set of BPDUs is at the core of STP’s capability to choose exactly one root bridge per a switched environment, exactly one Root Port on a non-root bridge, and exactly one Designated Port for each connected network segment.
  • Only Configuration BPDUs (Hello BPDUs) are compared.
  • Each time a Hello is received, the receiving switch can be thought to reevaluate its choice of a Root Port and updates the choice if necessary.
  • Neither Root Ports nor ports in the Blocking state send BPDUs.
  • An important fact to remember is that each port in STP stores (that is, remembers) the superior BPDU it has either sent or received.
  • Should a port store a received BPDU, it must be received again within a time interval of MaxAge-MessageAge seconds; otherwise it will expire after this period. This expiry is always driven by the timers in the BPDU, that is, according to timers of the root switch. 
  • The 802.1D STP process has three major steps:
    1. Elect the root switch. (The switch with the lowest BID.)
    2. Determine each switch's Root Port. (The most superior BPDU received on all its ports.) 
    3. Determine the Designated Port for each segment. (The most superior BPDU on the segment.)
  • Many people think of STP costs as being associated with a segment; however, the cost is actually associated with interfaces. Good design practices dictate using the same STP cost on each end of a point-to-point Ethernet segment, but the values can be different.
  • On recent Catalyst switches, the default costs correspond to the 802.1D-1998 version of the standard if PVST or Rapid PVST is used, and to the 802.1D- 2004 version if MSTP is used. With PVST and Rapid PVST, the 802.1D-2004 costs can be activated using the spanning-tree pathcost method long global configuration command. By default, spanning-tree pathcost method short is configured, causing the switch to use the older revision of the costs.

To sum up the rules:
  • The root switch is the switch that has the lowest Bridge ID in the topology.
  • On each non-root switch, a Root Port is the port receiving the best (that is, superior) resulting BPDUs from all received BPDUs on all ports. The adjective “resulting” refers to the addition of the port’s cost to the BPDU’s RPC value before comparing the received BPDUs.
  • On each connected segment, a Designated Port is the port sending the best (that is, superior) BPDUs on the segment. No modifications to the BPDUs are performed; BPDUs are compared immediately.
  • All ports that are neither Root Ports nor Designated Ports are superfluous in an active topology and will be put into the Blocking state.
  • Configuration BPDUs are sent out only from Designated Ports. Root and Non-Designated ports do not emit Configuration BPDUs because they would be inferiorto BPDUs of a Designated Port on this segment and hence ignored. Each port stores the best (that is, superior) BPDU it has received or sent itself. Designated Ports store the BPDU they send; Root and Blocking ports store the best BPDU they receive. The stored BPDU determines the role of the port and is used for comparisons.
  • Received superior stored BPDUs will expire in MaxAge-MessageAge seconds if not received within this time period.

Converging to a New STP Topology 
  • STP never stops working. With each received BPDU, a switch reevaluates its own choice of the Root Bridge, Root Port, and Designated/Non-Designated Ports, effectively performing all three steps all over again.
  • In precise terms, for STP, a topology change is an event that occurs when:
    • a Topology Change Notification BPDU is received by a Designated Port of a switch.
    • a port moves to the Forwarding state and the switch has at least one Designated Port (meaning that it is not a standalone switch with just a Root Port connected to an upstream switch and no other connected ports).
    • a port moves from Learning or Forwarding to Blocking.
    • a switch becomes the root switch.
  • When a change to the topology occurs, the elementary reaction of switches that detect the topology change is to start originating BPDUs with appropriately updated contents, propagating the information to their neighbors.
  • STP is not a protocol that tries to find shortest paths toward individual MAC addresses, so it cannot be expected to fill the CAM tables with new correct entries. All STP can do is to instruct switches to age out unused entries prematurely, assuming that the unused entries are exactly those that need updating. Even if good entries are flushed from CAM tables, this does not impair basic connectivity—switches will flood frames to unknown destinations rather than dropping them.
  • To update the CAMs, two things need to occur:
    • All switches need to be notified to time out their apparently unused CAM entries.
    • Each switch needs to use a short timer, equivalent to the Forward Delay timer (default 15 seconds), to time out the CAM entries.
  • A switch detecting a topology change notifies the root switch using a Topology Change Notification (TCN) BPDU. The TCN goes up the tree to the root. After that, the root notifies all the rest of the switches.

Propagating information about a topology change:
  1. A topology change event occurs on a port of a switch.
  2. After detecting the event, the switch sends a TCN BPDU out its Root Port; it repeats this message every Hello time until it is acknowledged.
  3. The next designated switch receiving that TCN BPDU sends back an acknowledgment through its next forwarded Hello BPDU by marking the Topology Change Acknowledgment (TCA) bit in the Flags field of the Hello.
  4. The designated switch on the segment in the second step repeats the first two steps, sending a TCN BPDU out its Root Port, and awaits acknowledgment from the designated switch on that segment.
  5. After the TCN arrives at the root switch, it also acknowledges its arrival through sending a BPDU with the Topology Change Acknowledgment bit set through the port through which the TCN BPDU came in. At this point, the root switch has been informed about a topology change that occurred somewhere in the network.
  6. For the next MaxAge+ForwardDelay seconds, the root switch will originate BPDUs with the Topology Change (TC) bit set, instructing all switches to shorten the agingtime for CAM entries to ForwardDelay seconds.

PVST+ and STP over Trunks  
  • PVST+ creates an STP instance for each VLAN.
  • Each STP instance can use different root switch and can have different interfaces block.
  • As a result, the traffic load can be balanced across the available links.
  • Support for PVST+ implies the capability of trunk ports to be selectively blocked or forwarding for individual VLANs.
  • Non-Cisco switches that follow exclusively the IEEE standard support only a so-called Common Spanning Tree (CST).
  • CST is not aware of VLANs.
  • When building networks using a mix of Cisco and non-Cisco switches with 802.1Q trunking, you need to think about the interoperation between 802.1D STP and PVST+.
  • Cisco PVST+ uses a VLAN 1 STP instance to communicate with non-Cisco switch CST instance.
  • Inside CST regions, the active loop-free topology is binding for all VLANs; inside PVST+ regions, the active loop-free topology applies to VLAN 1 only.
  • Other VLANs inside the PVST+ regions have their own PVST+ instances.
  • PVST+ BPDUs are sent to the multicast address 0100.0CCC.CCCD (ordinary STP BPDUs are destined to 0180.C200.0000), and they are tagged with the corresponding VLAN (ordinary STP BPDUs are untagged), and use SNAP encapsulation (ordinary STP BPDUs use LLC encapsulation without SNAP).
  • Each PVST+ BPDU has a special TLV place at its end that carries the VLAN number in which the PVST+ BPDU originated (called Port VLAN ID TLV or PVID TLV).
  • This TLV is analyzed by PVST+ and compared to the VLAN in which the BPDU is received to detect native VLAN mismatches.
  • PVST+ BPDUs are tunneled across CST regions, with CST switches flooding them as ordinary multicasts without processing them.
  • To non-VLAN 1 PVST+ instances, the entire switched network appears as PVST+ regions interconnected by shared segments.
  • Both standard STP BPDUs and PVST+ BPDUs are sent for VLAN 1. The PVST+ BPDUs for VLAN 1 are used to detect native VLAN mismatches and are otherwise ignore upon arrival.
  • In summary, when sending BPDUs:
    • IEEE-formatted BPDUs for VLAN 1, always untagged.
    • PVST+ BPDUs untagged for the native VLAN and tagged for ohter VLANs. Each of them carries the PVID TLV. 
  • When processing received BPDUs, an access port must receive only IEEE BPDUs; otherwise, a Type Inconsistent state is declared. These BPDUs will be processed by the STP instance for the access VLAN of the port. 
  • On trunk ports, the processing is more complex.
  • IEEE-formatted BPDUs will be immediately processed by the VLAN 1 STP instance.
  • PVST+ BPDUs are processed in the following sequence:
    1. Assign the BPDU to the appropriate VLAN by looking at its 802.1Q tag. If the tag is present, assign the BPDU to that VLAN. If the tag is not present, assign the BPDU to the native VLAN.
    2. Check the PVID TLV in the BPDU. If the VLAN stored in the PVID TLV does not match the VLAN to which the BPDU was assigned, drop the BPDU and declare the PVID_Inconsistent state for the offending pair of VLANs. This is the native VLAN mismatch check.
    3. BPDUs whose PVID TLV VLAN matches the assigned VLAN will be processed by the STP instance of that VLAN - except BPDUs for VLAN 1. Because the information for VLAN 1 is duplicated in the IEEE BPDUs and PVST+ BPDUs, and the IEEE BPDUs always have to be processed, the PVST+ BPDU for VLAN 1 is only used to protect against native VLAN mismatch in VLAN 1 and can be dropped afterwards.