Distributed Tree Maintenance
Original Publication Date: 1992-Jun-01
Included in the Prior Art Database: 2005-Mar-22
Cidon, I: AUTHOR [+3]
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.
Distributed Tree Maintenance
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.
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).
assumptions are necessary for the tree
. 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
. 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"
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....