Cisco Systems RJ-45-to-AUX manual Edsger Dijkstra’s Graph Theory, 201

and Electronics Engineers (IEEE) a protocol similar to STP to become a networking standard. However, after the IEEE 802 committee revised it into what is now known as the IEEE 802.1D standard (Spanning Tree Protocol), the protocol differed just enough from DEC’s version that they were incompatible.

Danger! Data Loops!

Data loops can easily become a network disaster. A transparent bridge always likes to retransmit a broadcast it receives and never mark the frame with a time to live (TTL) or an identifier that says “Hey I started here!” or “I’ve been around here a few times already.” The result? Your transparent bridge keeps re−creating broadcasts in an expanding fashion. The bridge actually begins rebroadcasting broadcasts. Think this situation will last forever? Not likely—the bridges will eventually cause a broadcast storm and bring down the entire network.

STP fixes this problem and forces all the redundant data paths into a blocked state. By blocking the paths to destinations other than the given root path, STP creates only one path through the network. If any of the forwarding paths through one of the network segments in the spanning tree become unreachable, STP will reconfigure the spanning−tree topology and use the once blocked links in the network. STP calculates the network topology using the Spanning−Tree Algorithm (STA).

To avoid confusion, let me clarify that the Spanning−Tree Protocol and the Spanning−Tree Algorithm are two separate entities. STA chooses a reference point in the network and calculates the redundant paths to that reference point. If the STA finds a redundant path, it will choose one path to forward and the redundant paths to block. Using this process, STP and the STA effectively sever all the redundant links within the network.

STA is based on the graph theory developed by Edsger Dijkstra to construct a loop−free subset of the network topology. Let’s take a look at this theory.

Edsger Dijkstra’s Graph Theory

The STA uses solutions obtained by a graph theory also known as the Shortest Path Algorithm. As I mentioned earlier, this algorithm is used to construct a loop−free subset of the network’s topology. The same theory is also used in other link state protocols, such as Open Shortest Path First (OSPF), to calculate routing solutions. The theory states that for a connected graph consisting of interfaces and edges connecting pairs of interfaces, a spanning tree of the edges maintains the connectivity of the graph while containing no loops.

The algorithm provides a directed graph where each link is represented by vertices and weighted edges, as shown in Figure 10.2. Each link represents a cost. The weighted edges, which usually have more hops in the link than do the straight−through points, are assigned higher values. Each link in the path has a value, and the total of the values to a given point or destination is the total weighted value of the path. The lowest total weighted value represents the most efficient path from one point to another point.

201