Multiple Spanning Tree (MST) is an IEEE standard inspired from the Cisco proprietary Multiple Instances Spanning Tree Protocol (MISTP) implementation. This document assumes that the reader is familiar with Rapid STP (RSTP) (802.1w), as MST heavily relies on this other IEEE standard. 

Where to Use MST

This diagram shows a common design that features access Switch A with 1000 VLANs redundantly connected to two distribution Switches, D1 and D2. In this setup, users connect to Switch A, and the network administrator typically seeks to achieve load balancing on the access switch Uplinks based on even or odd VLANs, or any other scheme deemed appropriate.

These sections are example cases where different types of STP are used on this setup:

PVST+ Case

In a Cisco Per-VLAN Spanning Tree (PVST+) environment, the spanning tree parameters are tuned so that half of the VLANs forward on each Uplink trunk. In order to easily achieved this, elect Bridge D1 to be the root for VLANs 501 through 1000, and Bridge D2 to be the root for VLANs 1 through 500. These statements are true for this configuration:

• In this case, optimum load balancing results.

• One spanning tree instance for each VLAN is maintained, which means 1000 instances for only two different final logical topologies. This considerably wastes CPU cycles for all of the switches in the network (in addition to the bandwidth used for each instance to send its own Bridge Protocol Data Units (BPDUs)).

Standard 802.1q Case

The original IEEE 802.1q standard defines much more than simply trunking. This standard defines a Common Spanning Tree (CST) that only assumes one spanning tree instance for the entire bridged network, regardless of the number of VLANs. If the CST is applied to the topology of this diagram, the result resembles the diagram shown here:

In a network running the CST, these statements are true:

• No load balancing is possible; one Uplink needs to block for all VLANs.

• The CPU is spared; only one instance needs to be computed.

Note: The Cisco implementation enhances the 802.1q in order to support one PVST. This feature behaves exactly as the PVST in this example. The Cisco per-VLAN BPDUs are tunneled by pure 802.1q bridges.

MST Case

MSTs (IEEE 802.1s) combine the best aspects from both the PVST+ and the 802.1q. The idea is that several VLANs can be mapped to a reduced number of spanning tree instances because most networks do not need more than a few logical topologies. In the topology described in the first diagram, there are only two different final logical topologies, so only two spanning tree instances are really necessary. There is no need to run 1000 instances. If you map half of the 1000 VLANs to a different spanning tree instance, as shown in this diagram, these statements are true:

• The desired load balancing scheme can still be achieved, because half of the VLANs follow one separate instance.

• The CPU is spared because only two instances are computed.

From a technical standpoint, MST is the best solution. From an end-user's perspective, the main drawbacks associated with a migration to MST are:

• The protocol is more complex than the usual spanning tree and requires additional training of the staff.

• Interaction with legacy bridges can be a challenge. For more information refer, to the Interaction Between MST Regions and the Outside World section of this document.

MST Region

As previously mentioned, the main enhancement introduced by MST is that several VLANs can be mapped to a single spanning tree instance. This raises the problem of how to determine which VLAN is to be associated with which instance. More precisely, how to tag BPDUs so that the receiving devices can identify the instances and the VLANs to which each device applies.

The issue is irrelevant in the case of the 802.1q standard, where all instances are mapped to a unique instance. In the PVST+ implementation, the association is as follows:

• Different VLANs carry the BPDUs for their respective instance (one BPDU per VLAN).

The Cisco MISTP sent a BPDU for each instance, including a list of VLANs that the BPDU was responsible for, in order to solve this problem. If by error, two switches were misconfigured and had a different range of VLANs associated to the same instance, it was difficult for the protocol to recover properly from this situation.

The IEEE 802.1s committee adopted a much easier and simpler approach that introduced MST regions. Think of a region as the equivalent of Border Gateway Protocol (BGP) Autonomous Systems, which is a group of switches placed under a common administration.

MST Configuration and MST Region

Each switch running MST in the network has a single MST configuration that consists of these three attributes:

1. An alphanumeric configuration name (32 bytes)

2. A configuration revision number (two bytes)

3. A 4096-element table that associates each of the potential 4096 VLANs supported on the chassis to a given instance

In order to be part of a common MST region, a group of switches must share the same configuration attributes. It is up to the network administrator to properly propagate the configuration throughout the region. Currently, this step is only possible by the means of the command line interface (CLI) or through Simple Network Management Protocol (SNMP). Other methods can be envisioned, as the IEEE specification does not explicitly mention how to accomplish that step.

Note: If for any reason two switches differ on one or more configuration attribute, the switches are part of different regions. For more information refer to the Region Boundary section of this document.

Region Boundary

In order to ensure consistent VLAN-to-instance mapping, it is necessary for the protocol to be able to exactly identify the boundaries of the regions. For that purpose, the characteristics of the region are included in the BPDUs. The exact VLANs-to-instance mapping is not propagated in the BPDU, because the switches only need to know whether they are in the same region as a neighbor. Therefore, only a digest of the VLANs-to-instance mapping table is sent, along with the revision number and the name. Once a switch receives a BPDU, the switch extracts the digest (a numerical value derived from the VLAN-to-instance mapping table through a mathematical function) and compares this digest with its own computed digest. If the digests differ, the port on which the BPDU was received is at the boundary of a region.

In generic terms, a port is at the boundary of a region if the designated bridge on its segment is in a different region or if it receives legacy 802.1d BPDUs. In this diagram, the port on B1 is at the boundary of region A, whereas the ports on B2 and B3 are internal to region B:

MST Instances

According to the IEEE 802.1s specification, an MST bridge must be able to handle at least these two instances:

• One Internal Spanning Tree (IST)

• One or more Multiple Spanning Tree Instance(s) (MSTIs)

The terminology continues to evolve, as 802.1s is actually in a pre-standard phase. It is likely these names will change in the final release of 802.1s. The Cisco implementation supports 16 instances: one IST (instance 0) and 15 MSTIs.