spanning tree algorithm


Also found in: Acronyms.

spanning tree algorithm

An IEEE 802.1 standard under consideration which will provide distributed routing over multiple LANs connected by bridges.
This article is provided by FOLDOC - Free Online Dictionary of Computing (foldoc.org)

spanning tree protocol

An algorithm that runs in network bridges and switches to prevent loops, in which packets keep going around in circles. In a small network with one or two switches, the spanning tree protocol (STP) has little value; however, in a large network where many switches are connected to each other via bridges, redundant paths can cause loops.

The algorithm creates a hierarchical "tree" that "spans" the entire network. It determines all redundant paths and makes only one of them active at any given time. In addition, if there are redundant paths and one of them fails, it allows the other to take over. The spanning tree protocol is part of the IEEE 802.1 network management standard. See IEEE 802 and BPDU.
Copyright © 1981-2019 by The Computer Language Company Inc. All Rights reserved. THIS DEFINITION IS FOR PERSONAL USE ONLY. All other reproduction is strictly prohibited without permission from the publisher.
Mentioned in ?
References in periodicals archive ?
ALGORITHM 1: Conflict aware spanning tree algorithm. Input: feasible wireless links set F, racks set R Output: A: The spanning tree; B: The racks in A (1) A = [empty set], B = [empty set] [DELTA] B is the racks covered by A; (2) Tabu list T = [empty set]; (3) while A does not form a spanning tree do (4) if no links available for selection then (5) break; (6) end (7) Randomly select a link l(u, v) from F, where r(u) [member of] B and r(v) [member of] R - B [DELTA] r(u) and r(v) are the racks which setup wireless radio u and v respectively, i.e.
Any spanning tree algorithm can be used to determine the spanning tree on the mobile graph.
The LET-DG algorithm is a distributed implementation of the maximum spanning tree algorithm [21] on a weighted network graph with the edge weights modeled as the predicted link expiration time (LET) of the constituent end nodes.
end While return rd-MST ([V.sup.rd], [E.sup.rd]) End The run-time complexity of the rd-MST algorithm is O([absolute value of E] x log [[absolute value of E]) + O([absolute value of V] + [absolute value of E]) = O([absolute value of V] + [absolute value of E] x log [absolute value of E]), where O([absolute value of E] x log [absolute value of E]) is the run-time complexity of the Kruskal's minimum-weight spanning tree algorithm [8] and O([absolute value of V] + [absolute value of E]) is the run-time complexity of Breadth- First Search [8], both on a graph of [absolute value of V] vertices and [absolute value of E] edges.
LANLine 5220 supports the IEEE spanning tree algorithm, providing fault tolerance to the network.
Packets also improve the F-heap minimum spanning tree algorithm, giving the fastest algorithm currently known for this problem.
We will discuss the (i) Dijkstra's shortest path algorithm and its modifications for finding stable paths and bottleneck paths; (ii) Prim's minimum spanning tree algorithm and its modification for finding all pairs smallest and largest bottleneck paths; (iii) Minimum Steiner tree algorithm to connect a source node to all the receivers of a multicast group; (iv) A node-degree based algorithm to construct an approximate minimum connected dominating set (CDS) for sending information from one node to all other nodes in the network," and (v) Algorithms to find a sequence of link-disjoint, node-disjoint and zone-disjoint multi-path routes in MANETs.
Beginning with a discussion of networking standards and basic hardware and cabling, the work covers topics such as ethernet networking, spanning tree algorithms, IP protocols such as TCP, UDP and SCTP, address resolutions systems, routing, virtual local networks, IP on PPP connections, network administration, security and flow management.
Nonprojective Dependency Parsing Using Spanning Tree Algorithms. In Proceedings of the Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing.