Browse Prior Art Database

Distributed Tree Maintenance

IP.com Disclosure Number: IPCOM000108479D
Original Publication Date: 1992-Jun-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 6 page(s) / 260K

Publishing Venue

IBM

Related People

Cidon, I: AUTHOR [+4]

Abstract

Disclosed is a message-optimal distributed algorithm to maintain a spanning tree in a communications network with changing topology. This enables efficient broadcast (on the tree). In particular, it can be used, together with a specific feature in the communications processor, to achieve a fast and message-efficient broadcast in fast packet networks.

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

Distributed Tree Maintenance

       Disclosed is a message-optimal distributed algorithm to
maintain a spanning tree in a communications network with changing
topology.  This enables efficient broadcast (on the tree).  In
particular, it can be used, together with a specific feature in the
communications processor, to achieve a fast and message-efficient
broadcast in fast packet networks.

      A spanning tree is an optimal structure that enables the
efficient transmission of a message to every node in a communications
network.  A spanning tree contains the minimum number of links such
that the network is still connected, i.e., it has no cycles (loops).
Thus, it is a good medium for the purpose of broadcasting messages;
no messages need to be sent on non-tree links.  This was recognized
long ago.  The main contribution of this disclosure is a way to
update a spanning tree after network topology changes (link and node
failures and recoveries). The algorithm is message-optimal, since it
uses the tree itself in order to send the messages of the algorithm.
Throughout, the network is represented by a graph consisting of nodes
(network control processors) interconnected by edges (bidirectional
pairs of unidirectional transmission links).  Thus, an edge
connecting nodes a and b is called (a, b).

      The following assumptions are necessary for the tree
algorithm's operation:
       .   Topology updates are reliable.  That is, some topology
maintenance algorithm exists, ensuring that nodes on a tree
eventually know the topology of their tree and neighboring edges.
Many algorithms may serve this purpose.
       .   Topology updates arrive at a node only over edges of the
spanning tree.
       .   All the edges in the network have weights, and there is a
strict total ordering of edges according to weight.  That is, no two
edges may have the same weight.
       .   A reliable point-to-point connection exists between
adjacent nodes on the tree.  This connection is brought up between
adjacent nodes a and b on edge (a, b) when they begin negotiating the
inclusion of (a, b) in the tree.  If the nodes ultimately decide not
to include the edge in the tree, this connection is brought down.
Otherwise, as long as the edge remains a candidate, or remains on the
tree if it is included in the tree, this connection provides a way to
detect failure of the neighbor or the edge.
       .   Every node has a unique node ID and each node knows the
node IDs of adjacent nodes.  (It may be observed that as a
consequence of this unique naming, the names of the nodes in the
network can be arranged in ascending alphanumeric order, allowing any
node to determine which of two nodes has the "higher" or "lower"
name).

      The following are invariants of the algorithm, that is, every
step of the algorithm preserves the truth of these statements:
       .   Each tree has a unique node, called the root....