System information

Troubleshooting Transparent Bridging Environments 20-423
The Spanning-Tree Algorithm
The STA uses a conclusion from graph theory as a basis for constructing a loop-free subset of the
network’s topology. Graph theory states the following: “For any connected graph consisting of nodes
and edges connecting pairs of nodes, there is a spanning tree of edges that maintains the connectivity
of the graph but contains no loops.”
Figure 20-3 illustrates how the STA eliminates loops. The STA calls for each bridge to be assigned
a unique identifier. Typically, this identifier is one of the bridge’s Media Access Control (MAC)
addresses plus a priority. Each port in every bridge is also assigned a unique (within that bridge)
identifier (typically, its own MAC address). Finally, each bridge port is associated with a path cost.
The path cost represents the cost of transmitting a frame onto a LAN through that port. In
Figure 20-3, path costs are noted on the lines emanating from each bridge. Path costs are usually
default values, but they can be assigned manually by network administrators.
Figure 20-3 A Transparent Bridge Network Before STA Is Run
The first activity in spanning-tree computation is the selection of the root bridge, which is the bridge
with the lowest-value bridge identifier. In Figure 20-3, the root bridge is Bridge 1. Next, the root port
on all other bridges is determined. A bridge’s root port is the port through which the root bridge can be
reached with the least aggregate path cost. The value of the least aggregate path cost to the root is called
the root path cost.
Finally, designated bridges and their designated ports are determined. A designated bridge is the
bridge on each LAN that provides the minimum root path cost. A LAN’s designated bridge is the
only bridge allowed to forward frames to and from the LAN for which it is the designated bridge. A
LAN’s designated port is the port that connects it to the designated bridge.
In some cases, two or more bridges can have the same root path cost. For example, in Figure 20-3,
Bridges 4 and 5 can both reach Bridge 1 (the root bridge) with a path cost of 10. In this case, the
bridge identifiers are used again, this time to determine the designated bridges. Bridge 4’s LAN V
port is selected over Bridge 5’s LAN V port.
Using this process, all but one of the bridges directly connected to each LAN are eliminated, thereby
removing all two-LAN loops. The STA also eliminates loops involving more than two LANs, while
still preserving connectivity. Figure 20-4 shows the results of applying the STA to the network shown
in Figure 20-3. Figure 20-4 shows the tree topology more clearly. Comparing this figure to the
pre-spanning-tree figure shows that the STA has placed both Bridge 3’s and Bridge 5’s ports to LAN
V in standby mode.
Bridge
2
Bridge
1
Z
X
V
N
Y
10
20
20
20
D
D
Bridge
5
10
10
R
R
D10
Bridge
3
20
20
R
Bridge
4
10
10
R
D
D = Designated port
R = Root port
V through Z = LANs