Multiple Spanning Tree Protocol

Different Spanning trees created by different MSTIs on the same physical layout.

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:[1]

• Internal Spanning-Tree Instance (IST): 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 (MSTI): 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.

MSTIs in different 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 (Format Selector, Region Name, Revision Level and Configuration Digest), either of them represents VLAN to MSTIs mapping for each bridge.

CIST operates links between regions and to SST devices.

We can differentiate two kinds of conformated Spanning Trees into the different networks created by MSTP, these are:

• Common Spanning Tree (CST): Administers the connectivity among MST regions, STP LANs and RSTP LANs in a bridged network.
• Common Internal Spanning Tree (CIST): 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 (SST) entities.

The role of the Common Spanning Tree (CST) in a network, and the Common and Internal Spanning Tree (CIST) 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.

Its main function 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 (and in effect, classic STP too).

BPDUs' general format comprises a common generic portion -octets 1 to 36- that are based on those defined in IEEE Standard 802.1D,2004,[2] followed by components that are specific to CIST -octets 37 to 102. Components specific to each MSTI are added to this BPDUs data block.

BPDU table info and STP BPDUs show a deeper resume of the MSTP BPDU format and, besides, some additional information about how was this object structured in older or different versions of this protocol as STP and RSTP, maintaining its compatibility.

In case there is an allocation of VIDs (VLAN IDs) 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[3][4][5]
• Revision Level and the Configuration Digest:[6][7] 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.

• 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.

• 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.

Be sure of having configured VLANs and having associated them with switch ports, afterwards determine: MSTP Regions, revision level and instances; which VLANs and switch ports will belong to which MSTIs and, finally, which devices do you want to be root bridges for each MSTI.

Simple network topology for MSTP trials.

1. Switches must have the same MST configuration identification elements (region name, revision level and VLAN to MSTI mapping) to be in the same MST region. When configuring multiple MST regions for MSTP, MSTIs are locally significant within an MST region. MSTIs will not span from one region to another region.
2. Common and Internal Spanning Tree (CIST) is the default spanning tree instance for MSTP. This means that all VLANs that are not explicitly configured into another MSTI are members of the CIST.
3. The software supports a single instance of the MSTP Algorithm consisting of the CIST and up to 15 MSTIs.

A VLAN can only be mapped to one MSTI or to the CIST. One VLAN mapped to multiple spanning trees is not allowed. All the VLANs are mapped to the CIST by default. Once a VLAN is mapped to a specified MSTI, it is removed from the CIST.To avoid unnecessary STP processing, a port that is attached to a LAN with no other bridges/switches attached, can be configured as an edge port.

An example of how to configure a simple, three switch MSTP topology wherein a layer-two access switch carries four VLANs and has two uplinks to two distribution switches, can be found here: MSTP Configuration Guide
A good configuration view, from the above-mentioned example shall be:

S3# show spanning-tree mst

##### MST0    vlans mapped:   1-19,21-39,41-4094
Bridge        address 000e.8316.f500  priority      32768 (32768 sysid 0)
Root          address 0013.c412.0f00  priority      0     (0 sysid 0)
             port    Fa0/13          path cost     0
Regional Root address 0013.c412.0f00  priority      0     (0 sysid 0)
                                     internal cost 200000    rem hops 19
Operational   hello time 2, forward delay 15, max age 20, txholdcount 6 
Configured    hello time 2, forward delay 15, max age 20, max hops    20
Interface        Role Sts Cost      Prio.Nbr Type
---------------- ---- --- --------- -------- --------------------------------
Fa0/13           Root FWD 200000    128.13   P2p 
Fa0/16           Altn BLK 200000    128.16   P2p
##### MST1    vlans mapped:   20,40
Bridge        address 000e.8316.f500  priority      32769 (32768 sysid 1)
Root          address 000f.345f.1680  priority      1     (0 sysid 1)
             port    Fa0/16          cost          200000    rem hops 19
Interface        Role Sts Cost      Prio.Nbr Type
---------------- ---- --- --------- -------- --------------------------------
Fa0/13           Altn BLK 200000    128.13   P2p 
Fa0/16           Root FWD 200000    128.16   P2p

The first skel of this protocol was proposed in.[8] AMSTP is a simplified one tree instance rooted at each edge bridge in the core to forward frames.

To set up these trees, AMSTP relies in one basic tree which will be used to obtain instances (named Alternate Multiple Spanning Tree Instances – AMSTI), until one of them is built per switch for the network. The process applied to build up the main/basic tree is the same as in RSTP. In summary, firstly a bridge must be elected as the Root Bridge (this is done by the emission of BPDUs from each switch on the network periodically, every "Hello Time", and selecting the lowest Bridge ID). Then, every switch will compute and calculate its cost to the Root Bridge and, afterwards, the root ports must be elected by selecting the one which receives the best BPDU, this is, the one that announces minimum path cost to root bridge.

AMSTP BPDUs use the same local multicast protocol addresses than STP and have a structure that resembles MSTP BPDUs since both are comprised essentially of a basic BPDU and several AM-Records, allowing full-backwards compatibility with RSTP and STP standard protocols. Each of the AM-Records contains the data used to negotiate a specific tree instance (AMSTI). Every ABridge, except for the elected root bridge, creates an AM-Record for its own spanning tree instances. They are used by connected ports of neighboring switches to negotiate the transitions of each tree instance with a proposal/agreement mechanism.

This protocol, developed in[9] emphasizes in the terms of efficiency in network usage and path length. That's the main cause why it uses AMSTP, a simplified and self-configuring version of MSTP protocol.
Abridges can be described as a two-tiered hierarchy of layer-two switches in which network islands running independent rapid spanning tree protocols communicate through a core formed by island root bridges (ABridges). As it has been mentioned, it is focused in terms of efficiency, this is due to the ability of AMSTP to provide optimum paths in the core mesh and the usage of RSTP to aggregate efficiently the traffic at islands networks. Its convergence speed is as fast as RSTP and MSTP.

Two-layer network proposal for ABridges.

With the objective of enhancing the properties of Abridges protocol, a two-level hierarchical link layer infrastructure in which segmentation is performed at link layer is proposed. The core will be composed, primarily, by Abridges (Bridges using an implementation of AMSTP) and will oversee connecting the leaf access networks that are referred to as "access layer". Besides, each of this access networks, also called islands, will be a layer-two sub-network using STP connected to one or more Abridges.

Inside every island or access network a bridge is automatically elected to behave as the Root Bridge, this one bridge will behave as a gateway, allowing the forwarding of frames from the core to an island and conversely. Just one Abridge is going to perform these gateway functions, although many could be connected. Communication among 802.1D bridges and between standard 802.1D bridges and ABridges does not require point-to-point connections.

The ABridge receiving an ARP frame from an island host obtains the island in which the destination is located by asking an ARP server where the host was previously registered by its island ABridge. This server stores the IP to MAC mapping and the island ABridge ID. The ARP servers distribute its load based on equal result of short hashing of the IP addresses served. The core self-configures and the operation is transparent to all hosts and standard switches at islands.

ABridges is composed by three basic functional modules, which could be resumed in:

• STD Bridge: Performs standard bridging functions with the nodes of its island. The access functionality resides on the access ports of this module, which has an equivalent behavior to a standard bridge acting as a root bridge.
• AMSTP Routing: Routes frames between Abridges and the Gateway. It has core ports, either of them interconnect ABridges, which learn root bridge IDs from the AMSTP BPDUs received and store this information in a database, known as "Forwarding Database".
• GateWay: Interconnects the above-mentioned modules.

Abridges will configure each of their ports to be part either of the core or of an island, this port self-configuration is done with very simple stipulations: if a port is not connected to another Abridge using a point-to-point link, it will turn itself an access port; on the other hand, ports directly connected to another Abridge are configured as core ports. This auto-configuration mechanism is pretty like the one used in RSTP.

As any layer-two based protocol, ABridges uses ARP broadcasts to obtain the link layer address associated to an IP address at the same LAN or VLAN. That is the main cause why avoiding overflooding is a matter of paramount priority; to limit this broadcast traffic, is recommended the use of distributed load ARP servers, although its use is not compulsory.