To increase reliability, some sites use two or more bridges in parallel between pairs of LANs, as shown in Fig. 4-43. This arrangement, however, also introduces some additional problems
because it creates loops in the topology.
A simple example of these problems can be seen by observing how a frame, F, with unknown
destination is handled in Fig. 4-43. Each bridge, following the normal rules for handling
unknown destinations, uses flooding, which in this example just means copying it to LAN 2.
Shortly thereafter, bridge 1 sees F2, a frame with an unknown destination, which it copies to
LAN 1, generating F3 (not shown). Similarly, bridge 2 copies F1 to LAN 1 generating F4 (also
not shown). Bridge 1 now forwards F4 and bridge 2 copies F3. This cycle goes on forever.
The solution to this difficulty is for the bridges to communicate with each other and overlay the actual topology with a spanning tree that reaches every LAN. In effect, some potential
connections between LANs are ignored in the interest of constructing a fictitious loop-free
topology. For example, in Fig. 4-44(a) we see nine LANs interconnected by ten bridges. This configuration can be abstracted into a graph with the LANs as the nodes. An arc connects any two LANs that are connected by a bridge. The graph can be reduced to a spanning tree by
dropping the arcs shown as dotted lines in Fig. 4-44(b). Using this spanning tree, there is
exactly one path from every LAN to every other LAN. Once the bridges have agreed on the
spanning tree, all forwarding between LANs follows the spanning tree. Since there is a unique path from each source to each destination, loops are impossible.
Figure 4-44. (a) Interconnected LANs. (b) A spanning tree covering
the LANs. The dotted lines are not part of the spanning tree.
To build the spanning tree, first the bridges have to choose one bridge to be the root of the
tree. They make this choice by having each one broadcast its serial number, installed by the
manufacturer and guaranteed to be unique worldwide. The bridge with the lowest serial
number becomes the root. Next, a tree of shortest paths from the root to every bridge and
LAN is constructed. This tree is the spanning tree. If a bridge or LAN fails, a new one is
computed.
The result of this algorithm is that a unique path is established from every LAN to the root and thus to every other LAN. Although the tree spans all the LANs, not all the bridges are
necessarily present in the tree (to prevent loops). Even after the spanning tree has been
established, the algorithm continues to run during normal operation in order to automatically
detect topology changes and update the tree. The distributed algorithm used for constructing
the spanning tree was invented by Radia Perlman and is described in detail in (Perlman, 2000). It is standardized in IEEE 802.1D.
Spanning Tree Bridges
4/
5
Oleh
Unknown
