I. Functions of STP
Spanning tree protocol (STP) is a protocol conforming to IEEE 802.1d.
It aims to eliminate loops on data link layer in a local area network (LAN).
Devices running this protocol detect loops in the network by exchanging packets
with one another and eliminate the loops detected by blocking specific ports
until the network is pruned into one with tree topology. As a network with tree
topology is loop-free, it prevents packets in it from being duplicated and forwarded
endlessly and prevents device performance degradation.
Currently, in addition to the protocol conforming
to IEEE 802.1d, STP also refers to the protocols based on IEEE 802.1d, such as
RSTP, and MSTP.
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 calculation.
In STP, BPDUs come in two types:
l
Configuration BPDUs, used to calculate spanning
trees and maintain the spanning tree topology.
l
Topology change notification (TCN) BPDUs, used
to notify concerned devices of network topology changes, if any.
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 configuration BPDUs periodically. Other devices just
forward the configuration BPDUs received. 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 used for communicating with 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.
Table 1-1
Designated bridge and designated port
|
Classification
|
Designated bridge
|
Designated port
|
|
For a device
|
A designated bridge is a device that is
directly connected to a switch and is responsible for forwarding BPDUs to
this switch.
|
The port through which the designated
bridge forwards BPDUs to this device
|
|
For a LAN
|
A designated bridge is a device responsible
for forwarding BPDUs to this LAN segment.
|
The port through which the designated bridge
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 Device A, Device B, and Device C
respectively.
l
If Device A forwards BPDUs to Device B through
AP1, the designated bridge for Device B is Device A, and the designated port is
the port AP1 on Device A.
l
Two devices are connected to the LAN: Device B
and Device C. If Device B forwards BPDUs to the LAN, the designated bridge for
the LAN is Device B, and the designated port is the port BP2 on Device B.
Figure 1-1 A
schematic diagram of designated bridges and designated ports
All the ports on the root bridge are designated ports.
4)
Path cost
Path cost is a value used for measuring
link capacity. By comparing the path costs of different links, STP selects the
most robust links and blocks the other links to prune the network into a tree.
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 calculation. 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: lifetime for the configuration BPDUs
to be propagated within the network.
l
Max age, lifetime for the configuration BPDUs to
be kept in a switch.
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)
5)
Detailed calculation process of the STP
algorithm
l
Initial state
Upon initialization
of a device, each device generates a BPDU with itself as the root bridge, 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:
Table 1-2
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 BPDUs have the same root
path cost, the following configuration BPDU priority is compared sequentially: designated
bridge IDs, designated port IDs, and then the IDs of the ports on which the
configuration BPDUs are received. The switch with a higher priority is elected
as the root bridge.
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 its own bridge 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:
Table 1-3
Selection of the root port and designated ports
|
Step
|
Description
|
|
1
|
A
non-root-bridge device takes the port on which the optimum configuration BPDU
was received as the root port.
|
|
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 calculated configuration
BPDU with the configuration BPDU on the port whose role is to be determined,
and acts as follows based on the comparison result:
l
If the calculated configuration BPDU is
superior, this port will serve as the designated port, and the configuration
BPDU on the port will be replaced with the calculated configuration BPDU,
which will be sent out periodically.
l
If the configuration BPDU on the port is
superior, the device stops updating the configuration BPDUs of the port and blocks
the port, so that the port only receives configuration BPDUs, but does not forward
data or send configuration BPDUs.
|
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. The
priority of Device A is 0, the priority of Device B is 1, the priority of
Device 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.
Table 1-4
Initial state of each device
|
Device
|
Port name
|
BPDU of port
|
|
Device A
|
AP1
|
{0, 0, 0, AP1}
|
|
AP2
|
{0, 0, 0, AP2}
|
|
Device B
|
BP1
|
{1, 0, 1, BP1}
|
|
BP2
|
{1, 0, 1, BP2}
|
|
Device 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.
Table 1-5
Comparison process and result on each device
|
Device
|
Comparison process
|
BPDU of port after comparison
|
|
Device A
|
l
Port AP1 receives the configuration BPDU of
Device B {1, 0, 1, BP1}. Device 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
Device C {2, 0, 2, CP1}. Device 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
Device A finds that both the root bridge and
designated bridge in the configuration BPDUs of all its ports are Device 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}
|
|
Device B
|
l Port BP1 receives the configuration BPDU of Device A {0, 0, 0,
AP1}. Device 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 Device C {2, 0, 2,
CP2}. Device 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
Device 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), Device B calculates a designated port
configuration BPDU for BP2 {0, 5, 1, BP2}.
l
Device B compares the calculated configuration
BPDU {0, 5, 1, BP2} with the configuration BPDU of BP2. If the calculated BPDU
is superior, BP2 will act as the designated port, and the configuration BPDU
on this port will be replaced with the calculated configuration BPDU, which
will be sent out periodically.
|
Root port BP1:
{0, 0, 0, AP1}
Designated port BP2:
{0, 5, 1, BP2}
|
|
Device C
|
l Port CP1 receives the configuration BPDU of Device A {0, 0, 0,
AP2}. Device 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 Device B
{1, 0, 1, BP2} before the message was updated. Device 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 Device C compares the calculated 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 calculated 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 Device B
{0, 5, 1, BP2}. Because the received configuration BPDU is superior to its
old one, Device C launches a BPDU update process.
l At the same time, port CP1 receives configuration BPDUs periodically
from Device A. Device 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 calculated 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 Device A until a spanning tree calculation
process is triggered by a new condition, for example, the link from Device B
to Device 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 Device A as the root bridge is
stabilized, as shown in Figure
1-3.
Figure 1-3 The
final calculated spanning tree
To facilitate
description, the spanning tree calculation process in this example is
simplified, while the actual process is more complicated.
6)
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 generates configuration
BPDUs with itself as the root bridge and sends configuration BPDUs and TCN
BPDUs. This triggers a new spanning tree calculation so that a new path is
established to restore the network connectivity.
However, the newly calculated 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.
7)
STP timers
The following three time parameters are important
for STP calculation:
l
Forward delay, the period a device waits before state
transition.
A link failure triggers a new round of spanning
tree calculation and results in changes of the spanning tree. However, as new
configuration BPDUs cannot be propagated throughout the network immediately, if
the new root port and designated port begin to forward data as soon as they are
elected, loops may temporarily occur.
For this reason, the protocol uses a state
transition mechanism. Namely, a newly elected root port and the designated ports
must go through a period, which is twice the forward delay time, before they transit
to the forwarding state. The period allows the new configuration BPDUs to be
propagated throughout the entire network.
l
Hello time, the interval for sending hello
packets. Hello packets are used to check link state.
A switch sends hello packets to its
neighboring devices at a regular interval (the hello time) to check whether the
links are faulty.
l
Max time, lifetime of the configuration BPDUs stored
in a switch. A configuration BPDU that has “expired” is discarded
by the switch.
1.2 MSTP Overview
I. 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 transiting to the forwarding state, even if it is a
port on a point-to-point link or it is an edge port (an edge port refers to a
port that 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, the state of a root port can transit
fast under the following conditions: the old root port on the device has
stopped forwarding data and the upstream designated port has started forwarding
data.
l
In RSTP, the state of a designated port can
transit fast under the following conditions: 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.
RSTP supports rapid convergence. Like STP,
it is of the following disadvantages: all bridges in a LAN are on the same
spanning tree; redundant links cannot be blocked by VLAN; the packets of all
VLANs are forwarded along the same spanning tree.
II. 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. MSTP introduces
“instance” (integrates multiple VLANs into a set) and can bind
multiple VLANs to an instance, thus saving communication overhead and improving
resource utilization.
l
MSTP divides a switched network into multiple
regions, each containing multiple spanning trees that are independent of one
another.
l
MSTP prunes a ring network into a network with
tree topology, preventing packets from being duplicated and forwarded in a
network endlessly. Furthermore, it offers multiple redundant paths for
forwarding data, and thus achieves load balancing for forwarding VLAN data.
l
MSTP is compatible with STP and RSTP.
1.2.2 Basic MSTP
Terminologies
Figure 1-4 illustrates basic
MSTP terms (assuming that MSTP is enabled on each switch in this figure).
Figure 1-4 Basic MSTP terminologies
I. MST region
A multiple spanning tree region (MST region)
comprises multiple physically-interconnected MSTP-enabled switches and the
corresponding network segments connected to these switches. These switches have
the same region name, the same VLAN-to-MSTI mapping configuration and the same MSTP
revision level.
A switched network can contain multiple MST
regions. You can group multiple switches into one MST region by using the
corresponding MSTP configuration commands.
As shown in Figure 1-4, all the switches in region A0
are of the same MST region-related configuration, including:
l
Region name
l
VLAN-to-MSTI mapping (that is, VLAN 1 is mapped
to MSTI 1, VLAN 2 is mapped to instance 2, and the other VLANs are mapped to
CIST.)
l
MSTP revision level (not shown in Figure 1-4)
II. MSTI
A multiple spanning tree instance (MSTI)
refers to a spanning tree in an MST region.
Multiple spanning trees can be established
in one MST region. These spanning trees are independent of each other. For
example, each region in Figure
1-4 contains multiple spanning trees known as MSTIs. Each of
these spanning trees corresponds to a VLAN.
III. VLAN mapping table
A VLAN
mapping table is a property of an MST region. It contains information about how
VLANs are mapped to MSTIs. For example, in Figure 1-4, the VLAN mapping table of
region A0 is: VLAN 1 is mapped to MSTI 1; VLAN 2 is mapped to MSTI 2; and other
VLANs are mapped to CIST. In an MST region, load balancing is implemented according
to the VLAN mapping table.
IV. IST
An internal spanning tree (IST) is a
spanning tree in an MST region.
ISTs together with the common spanning tree
(CST) form the common and internal spanning tree (CIST) of the entire switched
network. An IST is a special MSTI; it is a branch of CIST in the MST region.
In Figure 1-4, each MST region has an IST,
which is a branch of the CIST.
V. CST
A CST is a single spanning tree in a
switched network that connects all MST regions in the network. If you regard each
MST region in the network as a switch, then the CST is the spanning tree
generated by STP or RSTP running on the "switches".
VI.
