Automatic route learning in network bridges
Bridges decide whether to forward packets from network to network based on an internal table, mapping each host to a port on the bridge. A packet is forwarded if the table states that the destination host is on a different port from where the packet came from.
This is simple for networks with a single bridge between them, as there is only one route from one host to any other. If there are several routes through several bridges from one host to another this technique fails, as the packet will be forwarded by both bridges and duplicated. More complex loops involving many different networks and bridges between them only serve to complicate matters further.
The problem is overcome by the bridges automatically generating a spanning tree covering the entire network, defining a single route between any two hosts.
Each bridge is given a unique numerical identifier. The bridge with the lowest identifier acts as the root bridge. By exchanging identifiers and hop counts, the bridges can arrive at a spanning tree to ensure traffic is not duplicated.
Initially all of the bridges believe they are the root bridge of the network, and begin broadcasting messages announcing their identifier. If a bridge receives a message from another bridge with a lower identifier, it knows it is not the root bridge. It forwards this message on to the other networks, including the number of hops from it to the root bridge. These messages spread throughout the network, so eventually each bridge will know how far from the root bridge they are, and if there are multiple routes will know the shortest route. This is the route it will use to forward all traffic; any other routes will be disabled.
In some cases this will result in some bridges being disabled completely, as the two networks they connect may have other shorter routes to the root bridge. While this may not be ideal, as traffic will have to take a more circuitous route from one host to another, it ensures traffic will not be duplicated in transit.
When the network has settled to a steady state, only the root bridge generates periodic messages to other bridges, which increment the hop count and pass them on accordingly. This ensures that any errors are detected; if a link breaks the shortest route to the root bridge will change, and traffic will be rerouted properly. If a bridge stops receiving any messages from the route it can be assumed that a link has broken in such a way that there are no alternative routes; in this case it will claim to be the root bridge and begin generating messages to build a spanning tree of the new fragmented network.
The spanning tree algorithm may not result in an optimal traffic flow; traffic may be routed over many hops through the root bridge rather than a single link, if both networks have different shortest paths to the root bridge. In the example below, traffic from network 3 destined for network 4 will pass through bridges B2, B1 and B3, rather than simply B4, as B2 is closer to the root than B4. Bridge B4 will be effectively disabled.
------ B1 ------
Net1 | | Net2
Net3 | | Net4
------- B4 -----
However it always results in a correct network, ensuring no packets are duplicated, and giving a degree of automatic fault recovery.
If an optimal network is required, there are other, better network topologies than just using many bridges.