Multiple Spanning Tree Protocol

Last updated

The Multiple Spanning Tree Protocol (MSTP) and algorithm, provides both simple and full connectivity assigned to any given virtual LAN (VLAN) throughout a bridged local area network. MSTP uses bridge protocol data unit (BPDUs) to exchange information between spanning-tree compatible devices, to prevent loops in each Multiple Spanning Tree instance (MSTI) and in the common and internal spanning tree (CIST), by selecting active and blocked paths. This is done as well as in Spanning Tree Protocol (STP) without the need of manually enabling backup links and getting rid of switching loop danger.

Contents

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 (LANs) and MST bridges. These regions and the other bridges and LANs are connected into a single common spanning tree (CST).

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 (STP) and the Rapid Spanning Tree Protocol (RSTP). It has some similarities with Cisco Systems' Multiple Instances Spanning Tree Protocol (MISTP), 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)

Different Spanning trees created by different MSTIs on the same physical layout. MSTI.png
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]

While each MSTI can have multiple VLANs, each VLAN can be associated with only one MSTI.

MSTP Regions

MSTIs in different regions. MST Region.png
MSTIs in different regions.

A set of interconnected switches that must have configured the same VLANs and MSTIs, also have the same following parameters:

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.

Common and Internal Spanning Tree (CST/CIST)

CIST operates links between regions and to SST devices. CIST.png
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:

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.

MSTP Bridge Protocol Data Units (BPDU)

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.

MSTP Configuration Identification

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:

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 (VLAN ID) 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 (based on priority vectors, MST Configuration Identifiers and on an incremental Path Cost associated to each receiving 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 (thus preventing loops and ensuring full connectivity between VLANs). 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 (packets) 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

Multiple Spanning Tree Instance Ports

RSTP compatibility

MSTP is designed to be STP and RSTP compatible and interoperable without additional operational management practice, this is due to a set of measurements based on RSTP (Clause 17 of IEEE Std 802.1D, 2004 Edition) intending to provide the capability for frames assigned to different VLANs, to be transmitted along different paths within MST Regions.

Both protocols have in common various issues such as: the selection of the CIST Root Bridge (it uses the same fundamental algorithm, 17.3.1 of IEEE Std 802.1D, 2004 Edition, but with extended priority vector components within MST Regions), the selection of the MSTI Root Bridge and computation of port roles for each MSTI, the port roles used by the CIST are the same as those of STP and RSTP (with the exception of the Master Port), and the state variables associated with each port.

Into the bargain, they also share some problems as, for instance: MSTP can't protect against temporary loops caused by the inter-connection of two LANs segments by devices other than the Bridges that operate invisibly with respect to support of the Bridges' MAC Internal Sublayer Service.

For all the above, it can be concluded that MSTP is fully compatible with RSTP bridges, an MSTP BPDU can be interpreted by an RSTP bridge as an RSTP BPDU. This not only allows compatibility with RSTP bridges without configuration changes, but also causes any RSTP bridges outside of an MSTP Region to see the region as a single RSTP bridge, regardless of the number of MSTP bridges inside the region itself.

Protocol configuration

This section is mainly oriented to provide any user a proper manner of configuring a MSTP network over Cisco devices.

Before configuring MSTP

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.

Configuration guidelines for MSTP

Simple network topology for MSTP trials. MSTP config.png
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

Extensions

Alternative Multiple Spanning Tree Protocol (AMSTP)

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.

Protocol operation

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.

BPDUs

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.

ABRIDGES

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.

Architecture

Two-layer network proposal for ABridges. Architecture ABridges.png
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.

Protocol operation

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 functionality

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.

ARP and ABridge resolution

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.

See also

Related Research Articles

A network switch is networking hardware that connects devices on a computer network by using packet switching to receive and forward data to the destination device.

The Spanning Tree Protocol (STP) is a network protocol that builds a loop-free logical topology for Ethernet networks. The basic function of STP is to prevent bridge loops and the broadcast radiation that results from them. Spanning tree also allows a network design to include backup links providing fault tolerance if an active link fails.

A virtual local area network (VLAN) is any broadcast domain that is partitioned and isolated in a computer network at the data link layer. In this context, virtual, refers to a physical object recreated and altered by additional logic, within the local area network. VLANs work by applying tags to network frames and handling these tags in networking systems – creating the appearance and functionality of net

IEEE 802.1Q, often referred to as Dot1q, is the networking standard that supports virtual local area networking (VLANs) on an IEEE 802.3 Ethernet network. The standard defines a system of VLAN tagging for Ethernet frames and the accompanying procedures to be used by bridges and switches in handling such frames. The standard also contains provisions for a quality-of-service prioritization scheme commonly known as IEEE 802.1p and defines the Generic Attribute Registration Protocol.

Virtual Private LAN Service (VPLS) is a way to provide Ethernet-based multipoint to multipoint communication over IP or MPLS networks. It allows geographically dispersed sites to share an Ethernet broadcast domain by connecting sites through pseudowires. The term sites includes multiplicities of both servers and clients. The technologies that can be used as pseudo-wire can be Ethernet over MPLS, L2TPv3 or even GRE. There are two IETF standards track RFCs describing VPLS establishment.

Cisco Inter-Switch Link (ISL) is a Cisco Systems proprietary protocol that maintains VLAN information in Ethernet frames as traffic flows between switches and routers, or switches and switches. ISL is Cisco's VLAN encapsulation protocol and is supported only on some Cisco equipment over the Fast and Gigabit Ethernet links. It is offered as an alternative to the IEEE 802.1Q standard, a widely used VLAN tagging protocol, although the use of ISL for new sites is deprecated by Cisco.

<span class="mw-page-title-main">Network bridge</span> Device that creates a larger computer network from two smaller networks

A network bridge is a computer networking device that creates a single, aggregate network from multiple communication networks or network segments. This function is called network bridging. Bridging is distinct from routing. Routing allows multiple networks to communicate independently and yet remain separate, whereas bridging connects two separate networks as if they were a single network. In the OSI model, bridging is performed in the data link layer. If one or more segments of the bridged network are wireless, the device is known as a wireless bridge.

Multiple Registration Protocol (MRP), which replaced Generic Attribute Registration Protocol (GARP), is a generic registration framework defined by the IEEE 802.1ak amendment to the IEEE 802.1Q standard. MRP allows bridges, switches or other similar devices to register and de-register attribute values, such as VLAN identifiers and multicast group membership across a large local area network. MRP operates at the data link layer.

The Link Layer Discovery Protocol (LLDP) is a vendor-neutral link layer protocol used by network devices for advertising their identity, capabilities, and neighbors on a local area network based on IEEE 802 technology, principally wired Ethernet. The protocol is formally referred to by the IEEE as Station and Media Access Control Connectivity Discovery specified in IEEE 802.1AB with additional support in IEEE 802.3 section 6 clause 79.

Ethernet Automatic Protection Switching (EAPS) is used to create a fault tolerant topology by configuring a primary and secondary path for each VLAN.

Provider Backbone Bridge Traffic Engineering (PBB-TE) is a computer networking technology specified in IEEE 802.1Qay, an amendment to the IEEE 802.1Q standard. PBB-TE adapts Ethernet to carrier class transport networks. It is based on the layered VLAN tags and MAC-in-MAC encapsulation defined in IEEE 802.1ah, but it differs from PBB in eliminating flooding, dynamically created forwarding tables, and spanning tree protocols. Compared to PBB and its predecessors, PBB-TE behaves more predictably and its behavior can be more easily controlled by the network operator, at the expense of requiring up-front connection configuration at each bridge along a forwarding path. PBB-TE Operations, Administration, and Management (OAM) is usually based on IEEE 802.1ag. It was initially based on Nortel's Provider Backbone Transport (PBT).

IEEE 802.1ah is an amendment to the IEEE 802.1Q networking standard which adds support for Provider Backbone Bridges. It includes an architecture and a set of protocols for routing over a provider's network, allowing interconnection of multiple provider bridge networks without losing each customer's individually defined VLANs. It was initially created by Nortel before being submitted to the IEEE 802.1 committee for standardization. The final version was approved by the IEEE in June 2008 and has been integrated into IEEE 802.1Q-2011.

Carrier Ethernet is a marketing term for extensions to Ethernet for communications service providers that utilize Ethernet technology in their networks.

Data center bridging (DCB) is a set of enhancements to the Ethernet local area network communication protocol for use in data center environments, in particular for use with clustering and storage area networks.

IEEE 802.1aq is an amendment to the IEEE 802.1Q networking standard which adds support for Shortest Path Bridging (SPB). This technology is intended to simplify the creation and configuration of Ethernet networks while enabling multipath routing.

TRILL is an Internet Standard implemented by devices called TRILL switches. TRILL combines techniques from bridging and routing, and is the application of link-state routing to the VLAN-aware customer-bridging problem. Routing bridges (RBridges) are compatible with and can incrementally replace previous IEEE 802.1 customer bridges. TRILL Switches are also compatible with IPv4 and IPv6, routers and end systems. They are invisible to current IP routers, and like conventional routers, RBridges terminate the broadcast, unknown-unicast and multicast traffic of DIX Ethernet and the frames of IEEE 802.2 LLC including the bridge protocol data units of the Spanning Tree Protocol.

Fabric Connect, in computer networking usage, is the name used by Extreme Networks to market an extended implementation of the IEEE 802.1aq and IEEE 802.1ah-2008 standards.

Bridge Protocol Data Units (BPDUs) are frames that contain information about the spanning tree protocol (STP). A switch sends BPDUs using a unique source MAC address from its origin port to a multicast address with destination MAC.

Virtual Extensible LAN (VXLAN) is a network virtualization technology that attempts to address the scalability problems associated with large cloud computing deployments. It uses a VLAN-like encapsulation technique to encapsulate OSI layer 2 Ethernet frames within layer 4 UDP datagrams, using 4789 as the default IANA-assigned destination UDP port number. VXLAN endpoints, which terminate VXLAN tunnels and may be either virtual or physical switch ports, are known as VXLAN tunnel endpoints (VTEPs).

Time-Sensitive Networking (TSN) is a set of standards under development by the Time-Sensitive Networking task group of the IEEE 802.1 working group. The TSN task group was formed in November 2012 by renaming the existing Audio Video Bridging Task Group and continuing its work. The name changed as a result of the extension of the working area of the standardization group. The standards define mechanisms for the time-sensitive transmission of data over deterministic Ethernet networks.

References

  1. ↑ packard, Hewlett (2006). Multiple Instance Spanning-Tree Operation (PDF).
  2. ↑ IEEE, Standard (2004). IEEE Standard for Local and metropolitan area networks, Media Access Control (MAC) Bridges (PDF). IEEE Computer Society.
  3. ↑ IETF, RFC (1998). RFC 2271 SnmpAdminString object. IETF, D. Harrington. doi:10.17487/RFC2271.
  4. ↑ IETF, RFC (1999). RFC 2571 SnmpAdminString object. IETF, D. Harrington. doi:10.17487/RFC2571.
  5. ↑ IETF, RFC (2002). RFC 3411 SnmpAdminString object. IETF, D. Harrington. doi:10.17487/RFC3411.
  6. ↑ IETF, RFC (1997). HMAC: Keyed-Hashing for Message Authentication. IETF, H. Krawczyk. doi:10.17487/RFC2104.
  7. ↑ IETF, RFC (2011). Updated Security Considerations for the MD5 Message-Digest and the HMAC-MD5 Algorithms. IETF, S. Turner. doi:10.17487/RFC2104.
  8. ↑ Ibáñez, García, Azcorra, Guillermo, Alberto, Arturo (2002). Alternative Multiple Spanning Tree Protocol (AMSTP) for Optical Ethernet Backbones (PDF). IEEE Computer Society.{{cite book}}: CS1 maint: multiple names: authors list (link)
  9. ↑ Ibáñez, García, Azcorra, Soto, Guillermo, Alberto, Arturo, Ignacio (2007). Alternative Multiple Spanning Tree Protocol (AMSTP) for Optical Ethernet Backbones (PDF). Departamento de Ingeniería Telemática, Universidad Carlos III, Madrid, Spain, CAPITAL MEC Project.{{cite book}}: CS1 maint: multiple names: authors list (link)
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.