Self-healing tree network

1. A method for automatically detecting and self-recovering from a network isolation condition in a network comprising a plurality of network nodes and a group of one or more root nodes, the method comprising:

configuring the group of root nodes to periodically generate beacon packets;

configuring each of the plurality of network nodes to have finite states consisting of an idle state, a discovery state, a reconfiguration state, a search state, a wait state, and a registration state;

receiving, during said idle state, at said each of the plurality of network nodes a first beacon packet originating from the group of root nodes through an adjacent node of said each of the plurality of network nodes, wherein said adjacent node of said each of the plurality of network nodes is designated as a parent node of said each of the plurality of network nodes;

storing at said each of the plurality of network nodes an aging indicator for the first beacon packet after a first aging interval;

resetting said aging indicator at said each of the plurality of network nodes when a second beacon packet is received through said adjacent node of said each of the plurality of network nodes and source address of said second beacon packet matches source address of said first beacon packet;

if said aging indicator is not reset by said second beacon packet received through said adjacent node of said each of the plurality of network nodes after a second aging interval greater than the first aging interval, then:

indicating said network isolation condition during said idle state;

listening, by said each of the plurality of network nodes during said search state, for a new beacon packet originating from the group of root nodes, and said new beacon packet is received through a different adjacent node of said each of the plurality of network nodes;

entering, by said each of the plurality of network nodes, said wait state in response to receiving said new beacon packet;

verifying, during said discovery state, said different adjacent node of said each of the plurality of network nodes is not a descendant node of said each of the plurality of network nodes;

in response to said verifying, transmitting, during said registration state, a registration request to said different adjacent node to establish said different adjacent node as a new parent node of said each of the plurality of network nodes when said different adjacent node of said each of the plurality of network nodes is not the descendant node of said each of the plurality of network nodes;

receiving an approval, in reconfiguration state, from said different adjacent node of said each of the plurality of network nodes in response to said registration request;

deleting a parent status of said adjacent node of said each of the plurality of network nodes; and

storing an indication of said different adjacent node as said new parent node at said each of the plurality of network nodes.

2. The method of claim 1 , wherein each of the beacon packets comprises a universal destination address for validating the beacon packets.

3. The method of claim 1 , said receiving further comprising:

receiving the new beacon packet from another adjacent node of the each of the plurality of network nodes other than the parent node; and

dropping the new beacon packet received from said another adjacent node of the each of the plurality of network nodes when the network isolation condition is not indicated.

4. The method of claim 1 , said transmitting further comprising:

transmitting a discovery message upstream; and

receiving a reply to the discovery message from said another adjacent node of the each of the plurality of network nodes on an upstream port.

5. The method of claim 1 , wherein the second aging interval is at least twice the first aging interval.

6. The method of claim 1 , further comprising:

continuously receiving a plurality of beacon packets that are individually transmitted by at least one of the root nodes at an interval that is shorter than the first aging interval.

7. The method of claim 1 , further comprising:

transmitting the first beacon packet received from the parent node to all neighboring network nodes.

8. The method of claim 1 , further comprising:

receiving a network reconfiguration command; and

selecting the new parent node that is not the descendant node within the network in response to the network reconfiguration command.

9. The method of claim 8 , further comprising:

operating in a discovery state after receiving the network reconfiguration command until an ancestor-descendant relationship is identified.

10. The method of claim 1 , said storing performed by a network switching element of a node without any processing by a central processing unit (CPU) of the node.

11. The method of claim 1 , wherein the network comprises an Ethernet protocol network.

12. The method of claim 1 , wherein the age indicator is stored in an age field of a packet address table.

13. The method of claim 1 , further comprising:

storing the age indicator for a plurality of stored data packets other than the first beacon packet at the first aging interval.

14. A computer readable storage medium encoded with processing instructions for implementing a method for automatically detecting and self-recovering from a network isolation condition in a network comprising a plurality of network nodes and a group of one or more root nodes, the method comprising:

configuring the group of root nodes to periodically generate beacon packets;

configuring each of the plurality of network nodes to have finite states consisting of an idle state, a discovery state, a reconfiguration state, a search state, a wait state, and a registration state;

receiving, during said idle state, at said each of the plurality of network nodes a first beacon packet originating from the group of root nodes through an adjacent node of said each of the plurality of network nodes, wherein said adjacent node of said each of the plurality of network nodes is designated as a parent node of said each of the plurality of network nodes;

storing at said each of the plurality of network nodes an aging indicator for the first beacon packet after a first aging interval;

resetting said aging indicator at said each of the plurality of network nodes when a second beacon packet is received through said adjacent node of said each of the plurality of network nodes and source address of said second beacon packet matches source address of said first beacon packet;

if aging indicator is not reset by said second beacon packet received through said adjacent node of said each of the plurality of network nodes after a second aging interval greater than the first aging interval, then:

indicating said network isolation condition during said idle state;

listening, by said each of the plurality of network nodes during said search state, for a new beacon packet originating from the group of root nodes, and said new beacon packet is received through a different adjacent node of said each of the plurality of network nodes;

entering, by said each of the plurality of network nodes, said wait state in response to receiving said new beacon packet;

verifying, during said discovery state, said different adjacent node of said each of the plurality of network nodes is not a descendant node of said each of the plurality of network nodes;

in response to said verifying, transmitting, during said registration state, a registration request to said different adjacent node to establish said different adjacent node as a new parent node of said each of the plurality of network nodes when said different adjacent node of said each of the plurality of network nodes is not the descendant node of said each of the plurality of network nodes;

receiving an approval, in reconfiguration state, from said different adjacent node of said each of the plurality of network nodes in response to said registration request;

deleting a parent status of said adjacent node of said each of the plurality of network nodes; and

storing an indication of said different adjacent node as said new parent node at said each of the plurality of network nodes.

15. An apparatus for automatically detecting and self-recovering from a network isolation condition in a network comprising a plurality of network nodes and a group of one or more root nodes, the apparatus comprising:

means for configuring the group of root nodes to periodically generate beacon packets;

means for configuring each of the plurality of network nodes to have finite states consisting of an idle state, a discovery state, a reconfiguration state, a search state, a wait state, and a registration state;

means for receiving, during said idle state, at said each of the plurality of network nodes a first beacon packet originating from the group of root nodes through an adjacent node of said each of the plurality of network nodes, wherein said adjacent node of said each of the plurality of network nodes is designated as a parent node of said each of the plurality of network nodes;

means for storing at said each of the plurality of network nodes an aging indicator for the first beacon packet after a first aging interval;

means for resetting said aging indicator at said each of the plurality of network nodes when a second beacon packet is received through said adjacent node of said each of the plurality of network nodes and source address of said second beacon packet matches source address of said first beacon packet;

means for, if said aging indicator is not reset by said second beacon packet received through said adjacent node of said each of the plurality of network nodes after a second aging interval greater than the first aging interval, then:

indicating said network isolation condition during said idle state;

listening, by said each of the plurality of network nodes during said search state, for a new beacon packet originating from the group of root nodes, and said new beacon packet is received through a different adjacent node of said each of the plurality of network nodes;

entering, by said each of the plurality of network nodes, said wait state in response to receiving said new beacon packet;

verifying, during said discovery state, said different adjacent node of said each of the plurality of network nodes is not a descendant node of said each of the plurality of network nodes;

in response to said verifying, transmitting, during said registration state, a registration request to said different adjacent node to establish said different adjacent node as a new parent node of said each of the plurality of network nodes when said different adjacent node of said each of the plurality of network nodes is not the descendant node of said each of the plurality of network nodes;

receiving an approval, in reconfiguration state, from said different adjacent node of said each of the plurality of network nodes in response to said registration request;

deleting a parent status of said adjacent node of said each of the plurality of network nodes; and

storing an indication of said different adjacent node as said new parent node at said each of the plurality of network nodes.