Information Technology Reference
In-Depth Information
A topology with loops such as that shown in Figure 20-2 can be useful as well as potentially harmful. A
loop implies the existence of multiple paths through the internetwork. A network with multiple paths
from source to destination can increase overall network fault tolerance through improved topological
flexibility.
The Spanning-Tree Algorithm
The Spanning-Tree Algorithm (STA) was developed by Digital, a key Ethernet vendor, to preserve the
benefits of loops while eliminating their problems. Digital's algorithm was subsequently revised by the
IEEE 802 committee and was published in the IEEE 802.1d specification. The Digital algorithm and the
IEEE 802.1d algorithm are not the same, nor are they compatible.
The STA designates a loop-free subset of the network's topology by placing those bridge ports that, if
active, would create loops into a standby (blocking) condition. Blocking bridge ports can be activated in
the event of primary link failure, providing a new path through the internetwork.
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-2 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 network
administrators can assign them manually.
Figure20-2 A Transparent Bridge Network Before STA Is Run
LAN X
20
D
LAN Z
20
D
Bridge 1
D10
20
R
10
R
Root Bridge
20
R
Bridge 2
Bridge 3
Bridge 4
LAN N
20
10
D
D10
10
Bridge 5
R
LAN Y
10
D = designated port
R = root port
V through Z = LANs
LAN V
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-2, 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
.
