Self-Healing Communication Trees

A computer program product encoded on a computer readable medium, operable to cause a first node comprising one or more computers and a plurality of active ports to perform operations comprising:

• (a) maintaining data representing a tree specific status for each of a plurality of trees, each of the plurality of trees having a distinct root,
• where the status for each tree includes a node state for the first node, a port state for each of the active ports, and a path-cost,
• where the node state identifies the first node as being one of discoverable, reachable, meta-stable, or stable,
• where the port state for each port is one of root-ward, pruned, leaf ward, or undiscovered, and the port state identifies each port as being a root-ward port, a pruned port, a leaf ward port, or an undiscovered port, respectively, and where no more than one port is a root-ward port, and
• where the path-cost represents a cost of reaching the root through the root-ward port;
• (b) receiving a first tree-update notification through a first active port, where the first tree-update notification identifies a first tree and a first from-there cost, and in response to receiving the first tree-update notification:
• determining a first from-here cost from the first from-there cost;
• updating the status for the first tree by performing the following operations:
• (i) if the first from-here cost is less than the path-cost:
• setting the path-cost to be equal to the first from-here cost,
• if a port distinct from the first active port is the root-ward port, changing the port state of the port to pruned,
• if the first active port is not the root-ward port, changing the state of the first port to root-ward,
• setting the node state to reachable,
• sending a first port-status notification identifying the first tree and indicating a first port status of reachable through the first port, where the first port-status notification corresponds to the first tree-update notification, and
• sending a second tree-update notification through all active ports other than the first port, where the second tree-update notification identifies the first tree and the first from-here cost;
• or
• (ii) if the first from-here cost is not less than the first path-cost:
• sending a second port-status notification identifying the first tree and indicating a second port status of pruned through the first active port once the node state is stable, where the second port-status notification corresponds to the first tree-update notification;
• (c) receiving a third port-status notification through a second active port, where the second port-status notification identifies a second tree and indicates a third port status, where the third port-status notification corresponds to a most recently sent tree-update notification for the second tree, and where the third port status is one of reachable, meta-stable, stable, or pruned, and in response to receiving the third port-status notification:
• updating the status for the second tree by setting the port state of the second active port to pruned if the third port status is pruned, and otherwise setting the port state of the second active port to be leaf ward;
• setting the node state for the second tree to reachable if a port-status notification corresponding to a most recently sent tree-update has not been received through each non root-ward port, otherwise setting the node state for the second tree to stable if a last port state notification corresponding to the most recently sent tree-update notification received through each non root-ward port indicates a port status of stable, and otherwise setting the node state to meta-stable;
• and
• (d) in response to a change in the node state for any tree, sending a fourth port-status notification corresponding to a most recently received tree-update notification through the root-ward port for the tree, where the fourth port-status notification identifies the tree and indicates a fourth port status, and where the fourth port status is stable if the node state is stable, where the fourth port status is meta-stable if the node state is meta-stable, and where otherwise the fourth port status is reachable.

A system comprising:

• a plurality of nodes, where each node comprises one or more computers, where each node has a plurality of active ports, where at least one port of each node is operatively coupled to a port of a node in the plurality of nodes, and where each node is configured to perform operations comprising:
• (a) maintaining data representing a tree-specific status for each of a plurality of trees, each of the plurality of trees having a distinct root,
• where the status for each tree includes a node state for the node, a port state for each of the active ports, and a path-cost,
• where the node state identifies the node as being one of discoverable, reachable, meta-stable, or stable,
• where the port state for each port is one of root-ward, pruned, leaf-ward, or undiscovered, and the port state identifies each port as being a root-ward port, a pruned port, a leaf-ward port, or an undiscovered port, respectively, and where no more than one port is a root-ward port, and
• where the path-cost represents a cost of reaching the root through the root-ward port;
• (b) receiving a first tree-update notification through a first active port, where the first tree-update notification identifies a first tree and a first from-there cost, and in response to receiving the first tree-update notification:
• determining a first from-here cost from the first from-there cost;
• updating the status for the first tree by performing the following operations:
• (i) if the first from-here cost is less than the path-cost:
• setting the path-cost to be equal to the first from-here cost,
• if a port distinct from the first active port is the root-ward port, changing the port state of the port to pruned,
• if the first active port is not the root-ward port, changing the state of the first port to root-ward,
• setting the node state to reachable,
• sending a first port-status notification identifying the first tree and indicating a first port status of reachable through the first port, where the first port-status notification corresponds to the first tree-update notification, and
• sending a second tree-update notification through all active ports other than the first port, where the second tree-update notification identifies the first tree and the first from-here cost;
• or
• (ii) if the first from-here cost is not less than the first path-cost:
• sending a second port-status notification identifying the first tree and indicating a second port status of pruned through the first active port once the node state is stable, where the second port-status notification corresponds to the first tree-update notification;
• (c) receiving a third port-status notification through a second active port, where the second port-status notification identifies a second tree and indicates a third port status, where the third port-status notification corresponds to a most recently sent tree-update notification for the second tree, and where the third port status is one of reachable, meta-stable, stable, or pruned, and in response to receiving the third port-status notification:
• updating the status for the second tree by setting the port state of the second active port to pruned if the third port status is pruned, and otherwise setting the port state of the second active port to be leaf-ward;
• setting the node state for the second tree to reachable if a port-status notification corresponding to a most recently sent tree-update has not been received through each non root-ward port, otherwise setting the node state for the second tree to stable if a last port state notification corresponding to the most recently sent tree-update notification received through each non root-ward port indicates a port status of stable, and otherwise setting the node state to meta-stable;
• and
• (d) in response to a change in the node state for any tree, sending a fourth port-status notification corresponding to a most recently received tree-update notification through the root-ward port for the tree, where the fourth port-status notification identifies the tree and indicates a fourth port status, and where the fourth port status is stable if the node state is stable, where the fourth port status is meta-stable if the node state is meta-stable, and where otherwise the fourth port status is reachable.