Spanning Tree Protocol (STP) is a protocol to ensure there is no loop in layer 2 network. This protocol was invented by Radia Perlman in 1985 and published as a standard originally as IEEE 802.1D-1990.
In essence, STP works by sending a probe to every layer 2 switches and decides which link should be block if there is a loop.
Initially STP was used with one instance. This is when there was no understanding of VLAN which was introduced later in IEEE 802.1Q. Mono Spanning Tree runs a single Spanning Tree for all VLANs. Since it uses one Spanning Tree instance for all VLANs, it lacks the ability to engineer one path over another. All VLANs will have to share the same path and fate.
Cisco then introduced Per-VLAN Spanning Tree (PVST) that allows each VLAN to have its own Spanning Tree instance in ISL encapsulation. Then came PVST+ that allow the use of this protocol on 802.1Q encapsulation which is more common in the industry.
Rapid Spanning Tree Protocol (RSTP) originally introduced as IEEE 802.1W standard (and many still refer to this specific 802.1W for RSTP)
but it is now incorporated to the newer IEEE 802.1D-2004. RST provides faster layer 2 convergence compared to the initial STP IEEE 802.1D.
Cisco adopted this IEEE 802.1W in addition of more features and called it Rapid Per-VLAN Spanning Tree Plus (RPVST+).
While running one STP for all VLANs gives lack of flexibility and running one STP for each VLANs may be superfluous, Cisco introduces the use of grouping a set of VLANs to run one STP instance and initially called this as Multiple Instances Spanning Tree Protocol (MISTP). IEEE uses this as a standard in IEEE 802.1S – Multiple Spanning Trees. At this time of writing, IEEE 802.1Q-2014 supersedes the original 802.1S and also 802.1Q-1998, 802.1Q-2005, and 802.1Q-2011.
Both Cisco MISTP and IEEE 802.1S inherit the rapid-convergence feature from RSTP.
Reduced Spanning Tree Instances
Both Spanning Tree and Rapid Spanning Tree create one spanning tree instance in each VLAN and use different BPDU in each VLAN. The more VLANs created, the more spanning tree instances will be created, and more BPDU packets will be sent on the network. With the ability to group several VLANs into one instance, Cisco MISTP was able to reduce the number of BPDU sent down to one BPDU per instance. Later, Cisco Multiple Spanning Tree (MST) only uses one BPDU message and stores the multiple MST instances information in one BPDU.
Both Spanning Tree and Rapid Spanning Tree may configure the logical links in such a way that all of the links are being used between VLANs. The same practice can also be done in MST. One MST instance can be configured to use a different path than the other MST instance thus can achieve the same result as what Spanning Tree and Rapid Spanning Tree configured.
As shown below, VLANs 10-19 are mapped into MST Instance (MSTI) 1, VLANs 20-29 are mapped into MSTI 2, and VLANs 30-39 are mapped into MSTI 3. The layer two logical path can be engineered in such order that no link will be left idle.
Although it is correct that 802.1S (MST) can engineer the traffic the same way like 802.1D (STP) or 802.1W (Rapid STP), MST also offers:
- Better protocol communication. Less BPDU being sent means less chatty network. In this example, 30 BPDUs for 30 VLANs in SPT and RSTP compared to 1 BPDU for 30 VLANs in MST.
- Reducing the number of SPT instances. In this example, 30 STP instances compared to 3 STP instances.
Intra-Region vs. Inter-Region.
MST introduces the use of region. Multiple switches are considered within same region (Intra-Region) if the following are matched:
- Configuration name (MST Config name)
- Configuration Revision number (MST Config revision)
- Hash value of VLANs to instance number mapping (MST Config digest)
Figure below shows the MST packet capture where these information resides in the STP Extended System ID.
Switches that do not have the same MST details as above will be considered belong to the outside region (Inter-Region). Having the MST Config digest is the more efficient way to check for configuration consistency across the switches.
VTPv3 for VLAN to Instance Mapping Distribution.
VTP version 3 comes with many added features such as support for extended VLAN ID, Private VLAN, and Remote SPAN. It can also be used to distribute the VLAN to instance mapping.
The MST configuration still need to be manually configured on each of the MST switches and VTPv3 does not distribute the MST configuration. This is similar for the use of PVST+ or RPVST+. As many already know, VTPv3 does not configure the PVST+ or RPVST+ but only assisting in the VLAN database distribution.
The limitation is that you cannot configure VLAN to instance mapping for different region. VTPv3 will only distribute VLAN to instance mapping with the same region, revision number, and instances.
Spanning Tree Destination Hardware Address
MST grows from the Rapid Spanning Tree Protocol (RSTP) and in fact it still uses the same fundamental spanning tree algorithm to select the Root Bridge and Port Roles. It sends out Spanning Tree BPDU with destination address (eth.dst) of 01:80:c2:00:00:00. This is IEEE Spanning Tree Bridge Group Address. Cisco PVST previously used 01:80:0C:CC:CC:CD and later (PVST+) uses the IEEE Spanning Tree address.
MST uses port roles the same as those in RSTP such as Root, Designated, Alternate or Backup, or Disabled Port with an additional port role Master Port. The BPDU Flags bit 3-4 (stp.flags.port_role) recognizes the following port roles:
- 00 for Master Port. MST introduces Master port role. It is the port that points to the CIST Root Bridge from the CIST regional Bridge point of view when MST instance is created. MST instances map to CIST and follow a single path to the CIST Root which is Master port.
- 01 for Alternate/Backup. This has the same meaning as in STP. Alternate port is the backup and non-active port that points to the Root Bridge. It will become active when the main Root port failed.
- 10 for Root. This has the same meaning as in STP. Root port is the active port that points to the Root Bridge.
- 11 for Designated. This has the same meaning as in STP. Designated port is the port that is pointing away from the Root Bridge.
Number of Active MST Instances
Using the same 12-bit Extended System ID value, MST uses this for its instance number range from 0-4094. However, there can be only 64 active MST instances (MSTIs) plus one MST instance 0 (CIST).
Port costs in MST remains the same using 32-bit RSTP path cost value as per 802.1D-2004 Section 17.14.
- 10 Mbps – 2,000,000
- 100 Mbps – 200,000
- 1 Gigabit Ethernet – 20,000
- 10 Gigabit Ethernet – 2,000
M-Records holds the information about every MSTI (but not CIST) available in the region. This M-Records is encapsulated inside BPDU and do not send out of boundary ports.
With no MSTI configured, debug shows Num_mrec = 0
Switch>ena Switch#conf t Enter configuration commands, one per line. End with CNTL/Z. Switch(config)#spannin Switch(config)#spanning-tree mst con Switch(config-mst)#name TEST Switch(config-mst)#exit Switch(config)#spann Switch(config)#spanning-tree mode mst Switch(config)#exit Switch#debug spanning-tree mst bpdu transmit MSTP BPDUs TRANSMITted dump debugging is on Switch# *Jan 13 17:50:28.184: MST:-TX> Gi0/0 BPDU Prot:0 Vers:3 Type:2 *Jan 13 17:50:28.184: MST: Role :Desg Flags[APTc] Age:0 RemHops:20 *Jan 13 17:50:28.185: MST: CIST_root:32768.fa16.3e32.69dc Cost :0 *Jan 13 17:50:28.185: MST: Reg_root :32768.fa16.3e32.69dc Cost :0 *Jan 13 17:50:28.186: MST: Bridge_ID:32768.fa16.3e32.69dc Port_ID:32769 *Jan 13 17:50:28.186: MST: max_age:20 hello:2 fwdelay:15 *Jan 13 17:50:28.186: MST: V3_len:64 region:TEST rev:0 Num_mrec: 0
IST Root Bridge will not only send BPDU with cost of 0. It sends BPDU with Remaining Hop value of 20 and decrement every time it is received on a downstream switch. Once the value of Remaining Hop is 0, the BPDU will be ignored.
When a root bridge sends a superior BPDU and received BPDU with designated bit set from downstream, the root bridge will block the downstream and mark it as STP dispute link.
When Running STP or RSTP and a VLAN is pruned on one side, MST on the other side will not have the knowledge about it. This is due to the idea that STP/RSTP has STP instance for every VLAN but MST uses group of VLANs. Because there inconsistency on the VLAN pruning or blocking decision, the traffic for the VLAN will be blocked.
A lot of part of this note are adapted from this article Understanding MSTP by Petr Lapukhov. I really recommend to read the article for the complete context.
Thanks to Peter Palúch for the confirmation of the maximum number of MSTI. Read his CCIE Routing and Switching v5.0 Official Cert Guide Library, 5th Edition explaining more about this (and also others).
Also, you should use 802.1Q-2014 as the final reference for clarification and source of truth.