Distributed Tree Maintenance
Original Publication Date: 1992-Jun-01
Included in the Prior Art Database: 2005-Mar-22
Cidon, I: AUTHOR [+3]
A spanning tree contains the minimum number of links such that the network is still connected. Thus, it is good for the purpose of broadcasting messages over it, that is, one does not need to send extra messages on other (non-tree) links. This has been recognized long ago.
Distributed Tree Maintenance
tree contains the minimum number of links such
that the network is still connected. Thus, it is good for the
purpose of broadcasting messages over it, that is, one does not need
to send extra messages on other (non-tree) links. This has been
recognized long ago.
contributions of this disclosure are the idea and the
method to update this tree in the case of topological changes in the
network (failures and recoveries of links). Our algorithm is message
optimal, since it uses the tree itself in order to send the messages
of the algorithm.
the tree maintenance module assuming that some
topology maintenance module ensures that nodes on a tree know
eventually the topology of their tree, and neighboring edges. This
can be achieved, e.g., by using the APPN topology update protocol.
However, it is recommended to use the fast topology broadcast
algorithm that was designed especially to take advantage of the tree
presented in this article.
representation of the network is used and the actions
of the NCU are referred to as being actions of nodes.
For any link
(v,u) the only node who can put it into the tree
is its endpoint node v. (Node u does similarly for edge (u,v), so
each edge has two entries in the tree description.) This is done by
(1) updating the local topology map to show that this is a tree link;
(2) putting the tree's label on the adapter, in the switch (SS), so
that the switch will know to forward update messages over it; and (3)
notifying the other nodes so that they too can update the status of
the link (to be "tree") in their local topology map. Tasks (2) and
(3) are performed by generating a topology change (i.e., the edge
changes from non-tree status to tree status) which will be handled by
the topology update protocol. A node w that gets a notification from
the topology update protocol about an edge (u,v) becoming a tree
edge updates its topology map. Similarly, a topology update may be
either the failure or the recovery of a link, or the fact that it has
stopped being a tree link.
when the tree is temporarily disconnected (e.g., due
to a failure) it is actually a forest of node-disjoint trees, rather
than a single tree. The protocol strives to make this forest into
one tree that spans the whole (connected component of the) network.
also remembers which of its tree edges leads to its
parent. The protocol keeps the values of these parent variables (in
different nodes) consistent in the sense that if node v is the parent
of node u, then u is not the parent of v. (The one exception is
the time that a message from u is on its way to v to transfer
the parenthood from u to v). Thus each tree has a single node with
no parent. This node (whose parent = nil) is the tree root. It
coordinates the eff...