Pitfalls in the design of distributed routing algorithms
Radia Perlman, George Varghese · 1988
The bridge algorithm adopted by the IEEE 802.1 committee for interconnecting 802 LANs requires the topology of the Extended LAN to be a Spanning Tree. A distributed algorithm to compute a spanning tree dynamically has already been published [1], and adopted by the IEEE 802.1 committee [2]. In this paper, however, we describe an alternative distributed algorithm to compute a spanning tree. This algorithm, variants of which have been implemented, initially appears simpler than the IEEE 802.1 algorithm; we show, however, that it has subtle failure modes that makes it unattractive in practice.