# An algorithm for distributed computation of a spanningtree in an extended LAN

@inproceedings{Perlman1985AnAF, title={An algorithm for distributed computation of a spanningtree in an extended LAN}, author={Radia J. Perlman}, booktitle={SIGCOMM 1985}, year={1985} }

A protocol and algorithm are given in which bridges in an extended Local Area Network of arbitrary topology compute, in a distributed fashion, an acyclic spanning subset of the network. The algorithm converges in time proportional to the diameter of the extended LAN, and requires a very small amount of memory per bridge, and communications bandwidth per LAN, independent of the total number of bridges or the total number of links in the network. Algorhyme I think that I shall never see A graph… Expand

#### Topics from this paper

#### 171 Citations

A Simple Algorithm for Computing Minimum Spanning Trees in the Internet

- Computer Science
- Inf. Sci.
- 1997

A new fully distributed algorithm to build a minimum spanning tree (MST) in a generic communication network that is robust (there are no singularities subject to failures) and scalable (every node stores a limited amount of local information that is independent of the size of the network). Expand

Pitfalls in the design of distributed routing algorithms

- Computer Science
- SIGCOMM
- 1988

An alternative distributed algorithm to compute a spanning tree dynamically, which initially appears simpler than the IEEE 802.1 algorithm; it is shown that it has subtle failure modes that makes it unattractive in practice, and some failure modes are characteristic of a broader class of distributed graph algorithms. Expand

Reconfiguration of spanning trees in networks in the presence of node failures

- Computer Science
- [1993] Proceedings. The 13th International Conference on Distributed Computing Systems
- 1993

Two classes of contention resolution algorithms applicable for environments with a potentially large number of fragments are presented, based on preestablished ranking among fragments and random arbitration among fragments, and are useful in supporting data multicasting across workstations and distributed computations involving data on different machines. Expand

The multicast policy and its relationship to replicated data placement

- Computer Science
- TODS
- 1991

A new method is proposed by which a processor in the network should multicast a write of a logical data-item, to all the processors that store replicas of the items, and it is shown that the minimum spanning tree write is optimal from the communication cost point of view. Expand

A Loop-Free Extended Bellman-Ford Routing Protocol Without Bouncing Effect

- Computer Science
- SIGCOMM
- 1989

A protocol that maintains the shortest-path routes in a dynamic topology, that is, in an environment where links and nodes can fail and recover at arbitrary times, and avoids the bouncing effect and the looping problem that occur in the previous approaches of the distributed implementation of Bellman-Ford algorithm. Expand

Extended bridge algorithms for large networks

- Computer Science
- IEEE Network
- 1988

The reduced broadcast bridge algorithm alleviates the problem of extraneous broadcasting in large networks built from bridges and packet switches and application to the broadband integrated services digital network (BISDN) is proposed. Expand

Layered routing in irregular networks

- Computer Science
- IEEE Transactions on Parallel and Distributed Systems
- 2006

This work presents a method called layered routing, which gives rise to a series of routing algorithms, some of which perform considerably better than previous ones, and shows how the method can be used to improve the performance of irregular networks, both through load balancing and by guaranteeing shortest-path routing. Expand

Deadlock-Free Multicasting in Irregular Networks Using Prefix Routing

- Computer Science
- The Journal of Supercomputing
- 2005

It is shown that the proposed routing scheme is deadlock- and livelock-free and extended to multicasting in which the multicast packet is first forwarded up the tree to the longest common prefix (LCP) of destinations in the multicasts. Expand

Distributed protocols for spanning tree construction and leader election

- Computer Science
- ArXiv
- 2015

This work presents fast deterministic distributed protocols in synchronous networks for leader election and spanning tree construction running in time O(D\log L+L), where L is the size of the minimal identifier and D is the diameter of a network. Expand

Topological design of interconnected LAN-MAN networks

- Computer Science
- [Proceedings] IEEE INFOCOM '92: The Conference on Computer Communications
- 1992

The authors describe a methodology for designing interconnected local area network/metropolitan area network (LAN-MAN) networks with the objective of minimizing the average network delay and find the solutions are not very far from the global minimum. Expand

#### References

SHOWING 1-7 OF 7 REFERENCES

A Local Communications Network Based on Interconnected Tocen-Access Rings: A Tutorial

- Engineering, Computer Science
- IBM J. Res. Dev.
- 1983

This paper is a tutorial of the fundamental aspects of the architecture, physical components, and operation of a token-ring LAN, with particular emphasis on the fault detection and isolation capabilities that are possible, as well as the aspects that allow for work expansion and growth. Expand

Interconnection of broadband local area networks

- Computer Science
- SIGCOMM
- 1983

This paper describes the design and implementation of a controlled flooding technique in Sytek's LocalNet(TM) systems along with several refinements which increase performance and keep the worst case load for route discovery below a few percent of network capacity. Expand

Incorporation of multiaccess links into a routing protocol

- Computer Science
- SIGCOMM
- 1983

Protocols and algorithms for efficiently dealing with the characteristics of various types of multiaccess links, when they are included as links in a general topology net are presented. Expand

Pup: An Internetwork Architecture

- Computer Science
- IEEE Trans. Commun.
- 1980

This report explores important design issues, sets forth principles that have guided the Pup design, discusses the present implementation in moderate detail, and summarizes experience with an operational internetwork. Expand

48-bit absolute internet and Ethernet host numbers

- Computer Science
- SIGCOMM
- 1981

This paper describes how the host numbering scheme was designed in the context of an overall internetwork and distributed systems architecture. Expand

Transparent interconnection of local area networks with bridges

- Geography
- 1984

Description de l'architecture des principes de fonctionnement et des services prevus par un bridge qui utilise un espace d'adresse plat et est auto-configurant

An Internetwork Architecture,

- IEEE Transactions on Communications,
- 1980