Browse Prior Art Database

Distributed Minimal Spanning Tree Algorithm

IP.com Disclosure Number: IPCOM000107199D
Original Publication Date: 1992-Jan-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 7 page(s) / 274K

Publishing Venue

IBM

Related People

Boyles, RW: AUTHOR [+2]

Abstract

Disclosed is an efficient algorithm that builds a minimal spanning tree of a network or sub-network, with a significant reduction in computational complexity. At each individual node, the computational complexity of this distributed minimal spanning tree algorithm can be generalized as (Average_node_degree)x(Log N). For comparison, the corresponding computational complexity of a non-distributed minimal spanning tree algorithm would be (N)x(Average_node_degree)x(Log N). Note that there is an N-fold improvement (N is the number of nodes in the tree).

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 19% of the total text.

Distributed Minimal Spanning Tree Algorithm

       Disclosed is an efficient algorithm that builds a minimal
spanning tree of a network or sub-network, with a significant
reduction in computational complexity.  At each individual node, the
computational complexity of this distributed minimal spanning tree
algorithm can be generalized as (Average_node_degree)x(Log N).  For
comparison, the corresponding computational complexity of a
non-distributed minimal spanning tree algorithm would be
(N)x(Average_node_degree)x(Log N).  Note that there is an N-fold
improvement (N is the number of nodes in the tree).

      In many networks, it is often desirable to establish a minimal
spanning tree (MST) containing all the nodes of a network, or a
subset of those nodes.  In this algorithm, the minimal spanning tree
is formed by selecting the links between the nodes in a network or
sub-network so as to minimize the total weight of all links
comprising the minimal spanning tree.  (The term "links" is used here
in a generic sense.  If the MST connects all nodes in the network, a
"link" between two nodes is the actual link that directly connects
the two nodes.  If the MST connects a subset of nodes, a "link"
between two MST nodes is the shortest path connecting the two nodes.
The shortest path is the path, among all the paths connecting the two
nodes, with minimal total link weight.  (A path may consist of one or
multiple node-to-node links.)) Link weights may represent connection
cost, link loading, link delay, distance, or other factors.
Therefore, a minimal spanning tree will represent the most efficient
connection of a number of nodes for a particular link weight scheme.

      With conventional methods, there are two general approaches for
the MST calculation.  One is to determine the MST at each node.  The
other is to determine the MST at one or a few centralized nodes and
then broadcast the MST data to the other nodes comprising the MST.
In either case, at each of the nodes doing the MST calculation, the
computational complexity for determining the minimal spanning tree of
N nodes is:  O(N)x(d_ave)x(Log N)) where d_ave is the average node
degree (the average number of links connecting to a node), and O is
an annotation indicating order of complexity.

      This article suggests a distributed implementation procedure
for calculating the MST.  Beginning from an arbitrary root node,
every node determines only one "twig" for the MST. (A "twig"
represents any one of the N-1 links chosen for the MST.)  One end
node of the twig is the node where the twig is calculated, and
relevant information is passed to the node that is on the other end
of the twig. The node receiving this information calculates the next
twig and passes the information to the node at the other end of this
new twig.  This process is continued until all (N-1) twigs of the MST
have been chosen.  Since every node on the MST calculates no more
than one twig, the...