Skip to main content

IEEE 802.1s MSTP: one spanning tree per group of VLANs

· 5 min read
PhD candidate, LyRIDS (ECE) × CEDRIC (Cnam)

RSTP builds one tree for the whole network, so every redundant link stays idle. Once a network carries several VLANs, there is an obvious improvement: give different VLANs different trees, so that each link carries some traffic. That is what the Multiple Spanning Tree Protocol (MSTP) does.

The IEEE 802.1Q bridge: architecture and data-plane actionsIEEE 802.1Q bridge ↗Control planeSRP (Qat), TSN configuration (Qcc), path control (Qca)frame inframe outIngressPSFP (Qci)FRER (CB)Relayforwardingexplicit treesQueuingCBS (Qav)ATS (Qcr)Tx selectiongates (Qbv)CQF (Qch)MAC / PHYpreemption(Qbu, 802.3br)Common time: gPTP (802.1AS)
Figure 1. Where MSTP acts: in the control plane, like RSTP. It computes several active topologies; the data plane uses the one assigned to each frame's VLAN.Source: own drawing, after the bridge architecture, data-plane actions and QoS function chain in J. Farkas, TSN Basic Concepts, DetNet–TSN workshop, 11 November 2018, slides 7, 8 and 10.
Abbreviations used in this post (14)
AbbreviationStands forMeaning
BPDUBridge Protocol Data UnitThe message bridges exchange to run STP, RSTP and MSTP.
CNCCentralized Network ConfigurationThe 802.1Qcc entity that computes paths, schedules and reservations for the whole network and configures the bridges.
CSTCommon Spanning TreeThe tree that connects MSTP regions and single bridges; compatible with STP and RSTP.
IEEEInstitute of Electrical and Electronics EngineersThe professional association whose Standards Association publishes the IEEE 802 LAN/MAN standards.
IS-ISIntermediate System to Intermediate SystemA link-state routing protocol (ISO/IEC 10589, RFC 1195); the control plane of SPB and PCR.
ISTInternal Spanning TreeThe part of the common spanning tree inside one MSTP region.
MSTMultiple Spanning TreeA spanning tree to which one or more VLANs are mapped under MSTP.
MSTIMST InstanceOne spanning tree inside an MSTP region, together with the VLANs mapped to it.
MSTPMultiple Spanning Tree ProtocolIEEE 802.1s, now in 802.1Q: several spanning trees, each used by a group of VLANs.
RSTPRapid Spanning Tree ProtocolIEEE 802.1w, now in 802.1Q: a faster-converging spanning tree with alternate and backup port roles.
SPBShortest Path BridgingIEEE 802.1aq: bridges compute shortest path trees with IS-IS, so all links can be used.
STPSpanning Tree ProtocolThe original 802.1D protocol that blocks redundant links to leave a loop-free tree; now replaced by RSTP.
TSNTime-Sensitive NetworkingThe set of IEEE 802.1 standards that give Ethernet bounded latency, time synchronisation and high reliability.
VLANVirtual LANA logical LAN within a bridged network, identified by a 12-bit VLAN ID in the 802.1Q tag.

1. Definition​

The Multiple Spanning Tree Protocol was defined in IEEE 802.1s-2002 and merged into IEEE 802.1Q-2005. It is an extension of RSTP that makes VLANs more useful [1]. Under MSTP, a spanning tree can be defined for individual VLANs or for groups of VLANs [1]. In the words of the IEEE 802.1 tutorial, different VLANs may share different spanning trees [3].

Five bridges controlled by RSTP (one shared tree), MSTP (one tree per group of VLANs) and SPB (one shortest path tree per bridge)
Figure 2. RSTP, MSTP and SPB compared: under MSTP (centre) different VLANs may share different spanning trees, so the redundant links of the RSTP tree (left) can carry traffic.Source: P. Thaler, N. Finn, D. Fedyk, J. Farkas, G. Parsons, E. Gray, “IEEE 802.1Q: Media Access Control Bridges and Virtual Bridged Local Area Networks,” IEEE 802.1 tutorial, IETF 86, 10 March 2013, slide 26; cropped, with neighbouring slide text, logos or navigation icons blanked.

2. Regions and instances​

MSTP organises bridges and VLANs in two steps [1]:

  1. bridges are assigned to an MST region;
  2. VLANs are mapped to MST instances (MSTIs), each of which is a spanning tree.

Inside a region, frames of a VLAN follow the tree of the instance their VLAN is mapped to. The terms in the standard are as follows [1]:

TermMeaning
Multiple spanning tree (MST)A spanning tree to which one or more VLANs are mapped
MST instance (MSTI)A group of VLANs and the spanning tree they use inside a region
Common spanning tree (CST)The tree that connects regions and single bridges; backward compatible with STP and RSTP
Internal spanning tree (IST)The instance of the common tree inside a region
Boundary portA port at the edge of a region, towards an RSTP or STP bridge or an end station

3. One BPDU for all instances​

Proprietary per-VLAN spanning trees send one set of BPDUs per VLAN. MSTP instead puts all of its information into one BPDU format [1]:

  • the BPDU starts with a standard RSTP BPDU;
  • an additional region section follows, with one message per MSTI (from 0 to 64 instances, although many bridges support fewer);
  • instead of the full table of VLAN-to-instance mappings, the BPDU carries an MD5 digest of it. Two neighbours with the same digest and the same configured region values belong to the same region.

This keeps the number of BPDUs low. Because an RSTP bridge can read an MSTP BPDU as an RSTP BPDU, it also keeps compatibility with RSTP and with STP [1].

4. A region seen from outside​

To RSTP bridges outside, a whole MST region looks like one RSTP bridge, however many bridges it contains. MSTP uses a remaining-hops counter inside the region instead of the message age timer of RSTP. The message age is incremented only once when spanning-tree information enters a region, so RSTP bridges see the region as a single hop [1]. As in RSTP, boundary ports facing end stations can be edge ports and start forwarding at once [1].

5. MSTP among the control options​

Control plane overview: VLANs assigned to control modes, and the control options for each topology layer
Figure 3. Control options per VLAN: spanning-tree VLANs controlled by MSTP, shortest-path VLANs by IS-IS (SPB), and software-defined VLANs by an external agent, all in one network.Source: J. Farkas, “Introduction to IEEE 802.1: Focus on the Time-Sensitive Networking Task Group,” IEEE 802.1, 15 May 2017, slide 49; cropped, otherwise unchanged.

802.1Q assigns a control mode per VLAN. Spanning-tree VLANs are controlled by MSTP, shortest-path VLANs by IS-IS, and software-defined VLANs by an external agent, and the modes can coexist in one network [2]. A TSN network can therefore keep MSTP for its ordinary VLANs while a controller installs explicit paths for streams, with path control or a CNC.

For determinism, MSTP shares the properties of RSTP. Each VLAN has one active path between two bridges, and that path changes when the tree of its instance reconverges.

References​

  1. Wikipedia, "Spanning Tree Protocol," section on the Multiple Spanning Tree Protocol. Article
  2. J. Farkas, "Introduction to IEEE 802.1: Focus on the Time-Sensitive Networking Task Group," 15 May 2017, slide 49. Slides
  3. P. Thaler, N. Finn, D. Fedyk, J. Farkas, G. Parsons, E. Gray, "IEEE 802.1Q: Media Access Control Bridges and Virtual Bridged Local Area Networks," IEEE 802.1 tutorial, IETF 86, 10 March 2013, slides 25–26. Slides