Multiple Spanning Tree Protocol


The Multiple Spanning Tree Protocol and algorithm, provides both simple and full connectivity assigned to any given virtual LAN throughout a bridged local area network. MSTP uses bridge protocol data unit to exchange information between spanning-tree compatible devices, to prevent loops in each [|Multiple Spanning Tree instance] and in the [|common and internal spanning tree], by selecting active and blocked paths. This is done as well as in Spanning Tree Protocol without the need of manually enabling backup links and getting rid of switching loop danger.
Moreover, MSTP allows frames/packets assigned to different VLANs to follow separate paths, each based on an independent MSTI, within MST regions composed of local area networks and MST bridges. These regions and the other bridges and LANs are connected into a single common spanning tree.

History and motivation

It was originally defined in IEEE 802.1s as an amendment to 802.1Q, 1998 edition and later merged into IEEE 802.1Q-2005 Standard, clearly defines an extension or an evolution of Radia Perlman's Spanning Tree Protocol and the Rapid Spanning Tree Protocol. It has some similarities with Cisco Systems' Multiple Instances Spanning Tree Protocol, but there are some differences.
The original STP and RSTP work on the physical link level, preventing bridge loops when redundant paths are present. However, when a LAN is virtualized using VLAN trunking, each physical link represents multiple logical connections. Blocking a physical link blocks all its logical links and forces all traffic through the remaining physical links within the spanning tree. Redundant links cannot be utilized at all. Moreover, without careful network design, seemingly redundant links on the physical level may be used to connect different VLANs and blocking any of them may disconnect one or more VLANs, causing bad paths.
Instead, MSTP provides a potentially better utilization of alternate paths by enabling the use of alternate spanning trees for different VLANs or groups of VLANs.

Main Entities

Multiple Spanning Tree Instances (MSTI)

As MSTP enables grouping and mapping VLANs into different spanning tree instances, there's an urge of determining a group or set of VLANs, which are all using the same spanning tree, this is what we come to know as a MSTI.

Each instance defines a single forwarding topology for an exclusive set of VLANs, by contrast, STP or RSTP networks contains only a single spanning tree instance for the entire network, which contains all the VLANs. A region can include:
  • Internal Spanning-Tree Instance : Default spanning tree instance in any MST region. All VLANs in this IST instance conform a single spanning tree topology, allowing only one forwarding path between any two nodes. It also provides the root switch for any VLAN configured switches which are not specifically assigned to a MSTI.
  • Multiple Spanning Tree Instance : Unlike IST, this kind of instance comprises all static VLANs specifically assigned to it and at least, must include one VLAN.
While each MSTI can have multiple VLANs, each VLAN can be associated with only one MSTI.

MSTP Regions

A set of interconnected switches that must have configured the same VLANs and MSTIs, also have the same following parameters:
  • MST Configuration Name
  • Revision Level
  • Configuration Digest: Mapping of which VLAN are mapped to which MST instances.
An MSTI is unable to span across MST regions because of its inherent locality to a single MST region. This is done by an identifying number for each MSTI. For achieving the task of assigning each bridge to a region, each switch/bridge must compare their MST Configuration Identifiers , either of them represents VLAN to MSTIs mapping for each bridge.

Common and Internal Spanning Tree (CST/CIST)

We can differentiate two kinds of conformated Spanning Trees into the different networks created by MSTP, these are:
  • Common Spanning Tree : Administers the connectivity among MST regions, STP LANs and RSTP LANs in a bridged network.
  • Common Internal Spanning Tree : Identifies regions in a network and administers the CIST root bridge for the network, for each region and for each spanning tree instance in each region. It's also the default spanning tree instance of MSTP so that any VLAN which isn't a member of a particular MSTI, will be a member of the CIST. Furthermore, works as well as the spanning tree that runs between regions and between MST regions and Single Spanning Tree entities.
The role of the Common Spanning Tree in a network, and the Common and Internal Spanning Tree configured on each device, is to prevent loops within a wider network that may span more than one MSTP Region and parts of the network running in legacy STP or RSTP mode.

MSTP BPDUs

The main function of bridge protocol data units is enabling MSTP to select its root bridges for the proper CIST and each MSTI. MSTP includes all its spanning tree information in a single BPDU format. Not only does reduce the number of BPDUs required on a LANs to communicate spanning tree information for each VLAN, but it also ensures backward compatibility with RSTP.
BPDUs' general format comprises a common generic portion, octets 1 to 36, that are based on those defined in IEEE Standard 802.1D, 2004, followed by components that are specific to CIST, octets 37 to 102. Components specific to each MSTI are added to this BPDUs data block.

MSTP Configuration Identification

In case there is an allocation of VIDs into a MST Region which differs within the different bridges that compound it, frames for some VIDs might be duplicated or even not delivered to some LANs at all. To avoid this, MST Bridges check that they are allocating VIDs to the same spanning trees as their neighboring MST Bridges in the same Region by transmitting and receiving MST Configuration Identifiers along with the spanning tree information. These MST Configuration Identifiers, while compact, are designed so that two matching identifiers have a very high probability of denoting the same configuration even in the absence of any supporting management practice for identifier allocation. Either one of this "objects" contains the following:
  • Configuration Identifier Format Selector: Indicates the use which is going to be given to the following components.
  • Configuration Name
  • Revision Level and the Configuration Digest: A 16B signature HMAC-MD5 Algorithms created from the MST Configuration Table.

This object is specific and unique of MSTP, neither STP or RSTP use it.

Protocol Operation

MSTP configures for every VLAN a single spanning tree active topology in a manner that there's at least one data route between any two end stations, eliminating data loops. It specifies various "objects" allowing the algorithm to operate in a proper way. The different bridges in the various VLANs start advertising their own configuration to other bridges using the MST Configuration Identifier in order to allocate frames with given VIDs to any of the different MSTI. A priority vector is utilized to construct the CIST, it connects all the bridges and LANs in a Bridged LAN and ensures that paths within each region are always preferred to paths outside the Region. Besides, there is a MSTI priority vector, this one compromises the necessary information to build up a deterministic and independently manageable active topology for any given MSTI within each region.
Additionally, comparisons and calculations done by each bridge select a CIST priority vector for each Port. This leads to one bridge been selected as the CIST Root of the Bridged LAN; then, a minimum cost path to the root is shifted out for each Bridge and LANs. Subsequently, in each region, the bridge whose minimum cost path to the root doesn't pass through another bridge with the same MST Conf.ID will be identified as its Region's CIST Regional Root. Conversely, each Bridge whose minimum cost path to the Root is through a Bridge using the same MST Configuration Identifier is identified as being in the same MST Region as that Bridge.
In summary, MSTP encodes some additional information in its BPDU regarding region information and configuration, each of these messages conveys the spanning tree information for each instance. Each instance can be assigned several configured VLANs, frames assigned to these VLANs operate in this spanning tree instance whenever they are inside the MST region. To avoid conveying their entire VLAN to spanning tree mapping in each BPDU, bridges encode an MD5 digest of their VLAN to instance table in the MSTP BPDU. This digest is then used by other MSTP bridges, along with other administratively configured values, to determine if the neighboring bridge is in the same MST region as itself.

Port Roles

Common Internal Spanning Tree Ports

  • Root: Provides the minimum cost path from the Bridge to the CIST Root through the Regional Root.
  • Designated: Provides the least cost path from the attached LAN through the Bridge to the CIST Root.
  • Alternate or Backup: Provides connectivity if other Bridges, Bridges Ports or LANs fail or are erased.

    Multiple Spanning Tree Instance Ports

  • Root: Provides the minimum cost path from the Bridge to the MSTI Regional Root.
  • Designated: Provides the least cost path from the attached LANs through the Bridge to the Regional Root.
  • Master: Provides connectivity from the Region to a CIST Root that lies outside the Region. The Bridge Port that is the CIST Root port for the CIST Regional Root is the Master port for all MSTI.
  • Alternate or Backup: Provides connectivity if other Bridges, Bridges ports or LANs fail or are erased.