1.1 MSTP
Overview
I. Functions of STP
The spanning tree protocol (STP) is a protocol used to eliminate
loops in a local area network (LAN). Devices running this protocol detect any
loop in the network by exchanging information with one another and eliminate
the loop by properly blocking certain ports until the loop network is pruned
into a loop-free tree, thereby avoiding proliferation and infinite recycling of
packets in a loop network.
II. Protocol Packets of STP
STP uses bridge protocol data units
(BPDUs), also known as configuration messages, as its protocol packets.
STP identifies the network topology by
transmitting BPDUs between STP compliant network devices. BPDUs contain
sufficient information for the network devices to complete the spanning tree
computing.
In STP, BPDUs come in two types:
l
Configuration BPDUs, used to maintain the
spanning tree topology.
l
Topology change notification (TCN) BPDUs, used
to notify concerned devices of network topology changes, if any.
III. Basic concepts in STP
1)
Root bridge
A tree network must have a root; hence the
concept of “root bridge” has been introduced in STP.
There is one and only one root bridge in
the entire network, and the root bridge can change alone with changes of the
network topology. Therefore, the root bridge is not fixed.
Upon network convergence, the root bridge
generates and sends out at a certain interval a BPDU and other devices just
forward this BPDU. This mechanism ensures the topological stability.
2)
Root port
On a non-root
bridge device, the root port is the port with the lowest path cost to the root
bridge. The root port is responsible for forwarding data to the root bridge. A
non-root-bridge device has one and only one root port. The root bridge has no
root port.
3)
Designated bridge and designated port
Refer to the following table for the
description of designated bridge and designated port.
Description of designated bridge and
designated port
|
Classification
|
Designated bridge
|
Designated port
|
|
For a device
|
The device directly connected
with this device and responsible for forwarding BPDUs
|
The port through which the
designated bridge forwards BPDUs to this device
|
|
For a LAN
|
The device responsible for
forwarding BPDUs to this LAN segment
|
The port through which the
designated forwards BPDUs to this LAN segment
|
Figure 1-1 shows designated bridges and
designated ports. In the figure, AP1 and AP2, BP1 and BP2, and CP1 and CP2 are
ports on Switch A, Switch B, and Switch C respectively.
l
If Switch A forwards BPDUs to Switch B through
AP1, the designated bridge for Switch B is Switch A, and the designated port is
the port AP1 on Switch A.
l
Two devices are connected to the LAN: Switch B
and Switch C. If Switch B forwards BPDUs to the LAN, the designated bridge for
the LAN is Switch B, and the designated port is the port BP2 on Switch B.
Figure 1-1 A
schematic diagram of designated bridges and designated ports
All the ports on
the root bridge are designated ports.
IV. How STP
works
STP identifies the network topology by
transmitting configuration BPDUs between network devices. Configuration BPDUs
contain sufficient information for network devices to complete the spanning
tree computing. Important fields in a configuration BPDU include:
l
Root bridge ID: consisting of root bridge
priority and MAC address.
l
Root path cost: the cost of the shortest path to
the root bridge.
l
Designated bridge ID: designated bridge priority
plus MAC address.
l
Designated port ID, designated port priority
plus port name.
l
Message age: age of the configuration BPDU
l
Max age: maximum age of the configuration BPDU.
l
Hello time: configuration BPDU interval.
l
Forward delay: forward delay of the port.
For the convenience of description, the description and examples
below involve only four parts of a configuration BPDU:
l
Root bridge ID (in the form of device priority)
l
Root path cost
l
Designated bridge ID (in the form of device
priority)
l
Designated port ID (in the form of port name)
1)
Specific computing process of the STP algorithm
l
Initial state
Upon initialization
of a device, each port generates a BPDU with itself as the root, in which the
root path cost is 0, designated bridge ID is the device ID, and the designated
port is the local port.
l
Selection of the optimum configuration BPDU
Each device sends out its configuration
BPDU and receives configuration BPDUs from other devices.
The process of selecting the optimum
configuration BPDU is as follows:
Selection of the optimum configuration BPDU
|
Step
|
Description
|
|
1
|
Upon
receiving a configuration BPDU on a port, the device performs the following
processing:
l If the received configuration BPDU has a lower priority than that
of the configuration BPDU generated by the port, the device will discard the
received configuration BPDU without doing any processing on the configuration
BPDU of this port.
l If the received configuration BPDU has a higher priority than that
of the configuration BPDU generated by the port, the device will replace the
content of the configuration BPDU generated by the port with the content of
the received configuration BPDU.
|
|
2
|
The
device compares the configuration BPDUs of all the ports and chooses the
optimum configuration BPDU.
|
Principle for configuration BPDU comparison:
l
The configuration BPDU that has the lowest root
bridge ID has the highest priority.
l
If all the configuration BPDUs have the same
root bridge ID, they will be compared for their root path costs. If the root
path cost in a configuration BPDU plus the path cost corresponding to this port
is S, the configuration BPDU with the smallest S value has the highest
priority.
l
If all configuration BPDU have the same root
path cost, they will be compared for their designated bridge IDs, then their
designated port IDs, and then the IDs of the ports on which they are received.
The smaller the ID, the higher message priority.
l
Selection of the root bridge
At network initialization, each
STP-compliant device on the network assumes itself to be the root bridge, with
the root bridge ID being their own device ID. By exchanging configuration
BPDUs, the devices compare one another’s root bridge ID. The device with
the smallest root bridge ID is elected as the root bridge.
l
Selection of the root port and designated ports
The process of
selecting the root port and designated ports is as follows:
Selection of the root port and designated
ports
|
Step
|
Description
|
|
1
|
The
root port is the port on which the optimum configuration BPDU was received.
|
|
2
|
Based
on the configuration BPDU and the path cost of the root port, the device
calculates a designated port configuration BPDU for each of the rest ports.
l The root bridge ID is replaced with that of the configuration BPDU
of the root port.
l The root path cost is replaced with that of the configuration BPDU
of the root port plus the path cost corresponding to the root port.
l The designated bridge ID is replaced with the ID of this device.
l The designated port ID is replaced with the ID of this port.
|
|
3
|
The device compares the computed
configuration BPDU with the configuration BPDU on the corresponding port, and
performs processing accordingly based on the comparison result:
l
If the configuration BPDU is superior, the
device will block this port without changing its configuration BPDU, so that
the port will only receive BPDUs, but not send any, and will not forward
data.
l
If the computed configuration BPDU is
superior, this port will serve as the designated port, and the configuration
BPDU on the port will be replaced with the computed configuration BPDU, which
will be sent out periodically.
|
When the network topology is stable, only the root port and
designated ports forward traffic, while other ports are all in the blocked
state – they only receive STP packets but do not forward user traffic.
Once the root bridge, the root port on each
non-root bridge and designated ports have been successfully elected, the entire
tree-shaped topology has been constructed.
The following is an example of how the STP
algorithm works. The specific network diagram is shown in Figure 1-2. In the
feature, the priority of Switch A is 0, the priority of Switch B is 1, the
priority of Switch C is 2, and the path costs of these links are 5, 10 and 4
respectively.
Figure 1-2 Network diagram for STP
algorithm
l
Initial state of each device
The following table
shows the initial state of each device.
Initial state of each device
|
Device
|
Port name
|
BPDU of port
|
|
Switch A
|
AP1
|
{0, 0, 0, AP1}
|
|
AP2
|
{0, 0, 0, AP2}
|
|
Switch B
|
BP1
|
{1, 0, 1, BP1}
|
|
BP2
|
{1, 0, 1, BP2}
|
|
Switch C
|
CP1
|
{2, 0, 2, CP1}
|
|
CP2
|
{2, 0, 2, CP2}
|
l
Comparison process and result on each device
The following table
shows the comparison process and result on each device.
Comparison process and result on each
device
|
Device
|
Comparison process
|
BPDU of port after comparison
|
|
Switch A
|
l
Port AP1 receives the configuration BPDU of
Switch B {1, 0, 1, BP1}. Switch A finds that the configuration BPDU of the
local port {0, 0, 0, AP1} is superior to the configuration received message,
and discards the received configuration BPDU.
l
Port AP2 receives the configuration BPDU of
Switch C {2, 0, 2, CP1}. Switch A finds that the BPDU of the local port {0,
0, 0, AP2} is superior to the received configuration BPDU, and discards the
received configuration BPDU.
l
Switch A finds that both the root bridge and
designated bridge in the configuration BPDUs of all its ports are Switch A
itself, so it assumes itself to be the root bridge. In this case, it does not
make any change to the configuration BPDU of each port, and starts sending
out configuration BPDUs periodically.
|
AP1: {0, 0, 0, AP1}
AP2: {0, 0, 0, AP2}
|
|
Switch B
|
l
Port BP1 receives the configuration BPDU of
Switch A {0, 0, 0, AP1}. Switch B finds that the received configuration BPDU
is superior to the configuration BPDU of the local port {1, 0,1, BP1}, and
updates the configuration BPDU of BP1.
l
Port BP2 receives the configuration BPDU of
Switch C {2, 0, 2, CP2}. Switch B finds that the configuration BPDU of the
local port {1, 0, 1, BP2} is superior to the received configuration BPDU, and
discards the received configuration BPDU.
|
BP1: {0, 0, 0, AP1}
BP2: {1, 0, 1, BP2}
|
|
l
Switch B compares the configuration BPDUs of
all its ports, and determines that the configuration BPDU of BP1 is the
optimum configuration BPDU. Then, it uses BP1 as the root port, the
configuration BPDUs of which will not be changed.
l
Based on the configuration BPDU of BP1 and the
path cost of the root port (5), Switch B calculates a designated port
configuration BPDU for BP2 {0, 5, 1, BP2}.
l
Switch B compares the computed configuration
BPDU {0, 5, 1, BP2} with the configuration BPDU of BP2. If the computed BPDU
is superior, BP2 will act as the designated port, and the configuration BPDU
on this port will be replaced with the computed configuration BPDU, which
will be sent out periodically.
|
Root port BP1:
{0, 0, 0, AP1}
Designated port BP2:
{0, 5, 1, BP2}
|
|
Switch C
|
l
Port CP1 receives the configuration BPDU of
Switch A {0, 0, 0, AP2}. Switch C finds that the received configuration BPDU
is superior to the configuration BPDU of the local port {2, 0, 2, CP1}, and
updates the configuration BPDU of CP1.
l
Port CP2 receives the configuration BPDU of
port BP2 of Switch B {1, 0, 1, BP2} before the message was updated. Switch C
finds that the received configuration BPDU is superior to the configuration
BPDU of the local port {2, 0, 2, CP2}, and updates the configuration BPDU of
CP2.
|
CP1: {0, 0, 0, AP2}
CP2: {1, 0, 1, BP2}
|
|
By comparison:
l
The configuration BPDUs of CP1 is elected as
the optimum configuration BPDU, so CP1 is identified as the root port, the
configuration BPDUs of which will not be changed.
l
Switch C compares the computed designated port
configuration BPDU {0, 10, 2, CP2} with the configuration BPDU of CP2, and
CP2 becomes the designated port, and the configuration BPDU of this port will
be replaced with the computed configuration BPDU.
|
Root port CP1:
{0, 0, 0, AP2}
Designated port CP2:
{0, 10, 2, CP2}
|
|
l
Next, port CP2 receives the updated
configuration BPDU of Switch B {0, 5, 1, BP2}. Because the received
configuration BPDU is superior to its old one, Switch C launches a BPDU
update process.
l
At the same time, port CP1 receives
configuration BPDUs periodically from Switch A. Switch C does not launch an
update process after comparison.
|
CP1: {0, 0, 0, AP2}
CP2: {0, 5, 1, BP2}
|
|
By comparison:
l
Because the root path cost of CP2 (9) (root
path cost of the BPDU (5) + path cost corresponding to CP2 (4)) is smaller
than the root path cost of CP1 (10) (root path cost of the BPDU (0) + path
cost corresponding to CP2 (10)), the BPDU of CP2 is elected as the optimum
BPDU, and CP2 is elected as the root port, the messages of which will not be
changed.
l
After comparison between the configuration
BPDU of CP1 and the computed designated port configuration BPDU, port CP1 is
blocked, with the configuration BPDU of the port remaining unchanged, and the
port will not receive data from Switch A until a spanning tree computing
process is triggered by a new condition, for example, the link from Switch B
to Switch C becomes down.
|
Blocked port CP2:
{0, 0, 0, AP2}
Root port CP2:
{0, 5, 1, BP2}
|
After the comparison processes described in
the table above, a spanning tree with Switch A as the root bridge is
stabilized, as shown in Figure 1-3.
Figure 1-3 The
final computed spanning tree
To facilitate
description, the spanning tree computing process in this example is simplified,
while the actual process is more complicated.
2)
The BPDU forwarding mechanism in STP
l
Upon network initiation, every switch regards
itself as the root bridge, generates configuration BPDUs with itself as the
root, and sends the configuration BPDUs at a regular interval of hello time.
l
If it is the root port that received the
configuration BPDU and the received configuration BPDU is superior to the
configuration BPDU of the port, the device will increase message age carried in
the configuration BPDU by a certain rule and start a timer to time the
configuration BPDU while it sends out this configuration BPDU through the
designated port.
l
If the configuration BPDU received on the
designated port has a lower priority than the configuration BPDU of the local
port, the port will immediately sends out its better configuration BPDU in
response.
l
If a path becomes faulty, the root port on this
path will no longer receive new configuration BPDUs and the old configuration
BPDUs will be discarded due to timeout. In this case, the device will generate
a configuration BPDU with itself as the root and sends out the BPDU. This
triggers a new spanning tree computing process so that a new path is
established to restore the network connectivity.
However, the newly computed configuration
BPDU will not be propagated throughout the network immediately, so the old root
ports and designated ports that have not detected the topology change continue
forwarding data through the old path. If the new root port and designated port begin
to forward data as soon as they are elected, a temporary loop may occur. For
this reason, STP uses a state transition mechanism. Namely, a newly elected
root port or designated port requires twice the forward delay time before
transitioning to the forwarding state, when the new configuration BPDU has been
propagated throughout the network.
I. Why MSTP
1)
Disadvantages of STP and RSTP
STP does not support rapid state transition
of ports. A newly elected root port or designated port must wait twice the
forward delay time before transitioning to the forwarding state, even if it is
a port on a point-to-point link or it is an edge port, which directly connects
to a user terminal rather than to another device or a shared LAN segment.
The rapid spanning tree protocol (RSTP) is
an optimized version of STP. RSTP allows a newly elected root port or
designated port to enter the forwarding state much quicker under certain
conditions than in STP. As a result, it takes a shorter time for the network to
reach the final topology stability.
l
In RSTP, a newly elected root port can enter the
forwarding state rapidly if this condition is met: The old root port on the
device has stopped forwarding data and the upstream designated port has started
forwarding data.
l
In RSTP, a newly elected designated port can
enter the forwarding state rapidly if this condition is met: The designated
port is an edge port or a port connected with a point-to-point link. If the
designated port is an edge port, it can enter the forwarding state directly; if
the designated port is connected with a point-to-point link, it can enter the
forwarding state immediately after the device undergoes handshake with the
downstream device and gets a response.
Although RSTP support rapid network
convergence, it has the same drawback as STP does: All bridges within a LAN
share the same spanning tree, so redundant links cannot be blocked based on
VLANs, and the packets of all VLANs are forwarded along the same spanning tree.
2)
Features of MSTP
The multiple spanning tree protocol (MSTP)
overcomes the shortcomings of STP and RSTP. In addition to support for rapid
network convergence, it also allows data flows of different VLANs to be
forwarded along their own paths, thus providing a better load sharing mechanism
for redundant links.
MSTP features the following:
l
MSTP supports mapping VLANs to MST instances by
means of a VLAN-to-instance mapping table.
l
MSTP divides a switched network into multiple
regions, each containing multiple spanning trees that are independent of one
another.
l
MSTP prunes loop networks into a loop-free tree,
thus avoiding proliferation and endless recycling of packets in a loop network.
In addition, it provides multiple redundant paths for data forwarding, thus
supporting load balancing of VLAN data in the data forwarding process.
l
MSTP is compatible with STP and RSTP.
II. Some concepts in MSTP
As shown in Figure 1-4, there are four
multiple spanning tree (MST) regions, each made up of four switches running
MSTP. In light with the diagram, the following paragraphs will present some
concepts of MSTP.
Figure 1-4 Basic concepts in MSTP
1)
MST region
An MST region is composed of multiple
devices in a switched network and network segments among them. These devices
have the following characteristics:
l
All are MSTP-enabled,
l
They have the same region name,
l
They have the same VLAN-to-instance mapping
configuration,
l
They have the same MSTP revision level
configuration, and
l
They are physically linked with one another.
In area A0 in Figure 1-4, for example, all
the device have the same MST region configuration: the same region name, the
same VLAN-to-instance mapping (VLAN1 is mapped to MST instance 1, VLAN2 to MST
instance 2, and the rest to the command and internal spanning tree (CIST). CIST
refers to MST instance 0), and the same MSTP revision level (not shown in the
figure).
Multiple MST regions can exist in a
switched network. You can use an MSTP command to group multiple devices to the
same MST region.
2)
VLAN-to-instance mapping table
As an attribute of an MST region, the
VLAN-to-instance mapping table describes the mapping relationships between
VLANs and MST instances. In Figure 1-4, for example, the VLAN-to-instance
mapping table of region A0 describes that the same region name, the same
VLAN-to-instance mapping (VLAN1 is mapped to MST instance 1, VLAN2 to MST
instance 2, and the rest to CIST.
3)
IST
Internal spanning tree (IST) is a spanning
tree that runs in an MSTP region, with the instance number of 0. ISTs in all
MST regions the common spanning tree (CST) jointly constitute the common and
internal spanning tree (CIST) of the entire network. An IST is a section of the
CIST in an MST region. In Figure 1-4, for example, the CIST has a section is
each MST region, and this section is the IST in each MST region.
4)
CST
The CST is a single spanning tree that connects all MST regions in a
switched network. If you regard each MST region as a “device”, the
CST is a spanning tree computed by these devices through MSTP. For example, the
red lines in Figure 1-4 describe the CST.
5)
CIST
Jointly constituted by ISTs and the CST,
the CIST is a single spanning tree that connects all devices in a switched
network. In Figure 1-4, for example, the ISTs in all MST regions plus the
inter-region CST constitute the CIST of the entire network.
6)
MSTI
Multiple spanning trees can be generated in
an MST region through MSTP, one spanning tree being independent of another.
Each spanning tree is referred to as a multiple spanning tree instance (MSTI).
In Figure 1-4, for example, multiple spanning tree can exist in each MST
region, each spanning tree corresponding to a VLAN. These spanning trees are
called MSTIs.
7)
Regional root bridge
The root bridge of the IST or an MSTI
within an MST region is the regional root bridge of the MST or that MSTI. Based
on the topology, different spanning trees in an MST region may have different
regional roots. For example, in region D0 in Figure 1-4, the regional root of
instance 1 is device B, while that of instance 2 is device C.
8)
Common root bridge
The root bridge of the CIST is the common
root bridge. In Figure 1-4, for example, the common root bridge is a device in
region A0.
9)
Boundary port
A boundary port is a port that connects an
MST region to another MST configuration, or to a single spanning-tree region
running STP, or to a single spanning-tree region running RSTP.
During MSTP computing, a boundary port
assumes the same role on the CIST and on MST instances. Namely, if a boundary
port is master port on the CIST, it is also the master port on all MST
instances within this region. In Figure 1-4, for example, if a device in region
A0 is interconnected with the first port of a device in region D0 and the
common root bridge of the entire switched network is located in region A0, the
first port of that device in region D0 is the boundary port of region D0.
10)
Roles of ports
In the MSTP computing process, port roles
include designated port, root port, master port, alternate port, backup port,
and so on.
l
Root port: a port responsible for forwarding
data to the root bridge.
l
Designated port: a port responsible for
forwarding data to the downstream network segment or device.
l
Master port: A port on the shortest path from
the entire region to the common root bridge, connect the MST region to the common
root bridge.
l
Alternate port: The standby port for a root port
or master port. If a root port or master port is blocked, the alternate port
becomes the new root port or master port.
l
Backup port: If a loop occurs when two ports of
the same device are interconnected, the device will block either of the two
ports, and the backup port is that port to be blocked.
A port can assume different roles in
different MST instances.
Figure 1-5 Port roles
Figure 1-5 helps understand these concepts.
Where,
l
Devices A, B, C, and D constitute an MST region.
l
Port 1 and port 2 of device A connect to the
common root bridge.
l
Port 5 and port 6 of device C form a loop.
l
Port 3 and port 4 of device D connect downstream
to other MST regions.
III. How MSTP works
MSTP divides an entire Layer 2 network into
multiple MST regions, which are interconnected by a computed CST. Inside an MST
region, multiple spanning trees are generated through computing, each spanning
tree called an MST instance. Among these MST instances, instance 0 is the IST,
while all the others are MSTIs. Similar to RSTP, MSTP uses configuration BPDUs
to compute spanning trees. The only difference between the two protocols being
in that what is carried in an MSTP BPDU is the MSTP configuration on the device
from which this BPDU is sent.
1)
CIST computing
By comparison of “configuration
BPDUs”, one device with the highest priority is elected as the root
bridge of the CIST. MSTP generates an IST within each MST region through
computing, and, at the same time, MSTP regards each MST region as a single
device and generates a CST among these MST regions through computing. The CST
and ISTs constitute the CIST of the entire network.
2)
MSTI computing
Within an MST region, MSTP generates
different MSTIs for different VLANs based on the VLAN-to-instance mappings.
MSTP performs a separate computing process,
which is similar to spanning tree computing in STP, for each spanning tree. For
details, refer to “1.1.1 IV. How STP works” in section 1.1.1.
In MSTP, a VLAN packet is forwarded along
the following paths:
l
Within an MST region, the packet is forwarded
along the corresponding MSTI.
l
Between two MST regions, the packet is forwarded
along the CST.
IV. Implementation of MSTP on
devices
MSTP is compatible with STP and RSTP. STP
and RSTP protocol packets can be recognized by devices running MSTP and used
for spanning tree computing.
In addition to basic MSTP functions, many
management-facilitating special functions are provided, as follows:
l
Root bridge hold
l
Root bridge backup
l
Root guard
l
BPDU guard
l
Loop guard
1.2 Configuration Task List
Before configuration, you need to know the
position of each device in each MST instance: root bridge or leave node. In
each instance, one, and only one device acts as the root bridge, while all
others as leaf nodes.
If both GVRP and
MSTP are enabled on a device at the same time, GVRP packets will be forwarded
along the CIST. Therefore, if both GVRP and MSTP are running on the same device
and you wish to advertise a certain VLAN within the network through GVRP, make
sure that this VLAN is mapped to the CIST (instance 0) when configuring the
VLAN-to-instance mapping table.
1.3 Configuring the Root Bridge
1.3.1 Configuring an MST Region
I. Configuration procedure
Follow these steps to configure an MST
region:
