System and methods for computing flooding topology

1. A method for computing a flooding topology (FT) in a network device, comprising:

selecting a node R0 from a network;

initializing the FT with the node R0;

initializing a candidate queue (Cq);

implementing a first loop of the method, comprising:

removing a first node from the Cq and adding the first node to the FT;

determining whether the FT includes all nodes in the network;

terminating the first loop when the FT includes all the nodes in the network; and

appending to the Cq those nodes that are coupled in the network to the first node and are not in the FT when the FT does not include all the nodes in the network; and

adding a link to any node in the FT having only one link in the FT.

2. The method of claim 1 , wherein the first loop of the method further comprises:

determining whether the Cq is empty when the FT does not include all the nodes in the network; and

when the Cq is empty:

transmitting a first message to an administrator of the network;

transmitting a second message to a component in the network device, the first and second messages indicating an existence of nodes in the network that are unconnected to other nodes of the network; and

terminating the first loop.

3. The method of claim 1 , wherein adding the link to any node in the FT having only one link in the FT comprises:

implementing a second loop of the method, comprising:

determining whether the FT includes a node Q having only one link in the FT;

terminating the second loop with all the nodes in the FT having more than one link in the FT when the FT does not include the node Q; and

when the FT does include the node Q:

creating a set of all nodes that are coupled in the network to the node Q;

selecting a node L in the set, the node L having (i) a lowest number of links in the FT, and (ii) a lowest nodeID when two or more nodes have the same lowest number of links in the FT, where nodeID is an identifier of the node L in a topology of the network;

incrementing by 1 a degree of the node Q in the FT;

incrementing by 1 the degree of the node L in the FT; and

adding a link between the node Q and the node L to the FT.

4. The method of claim 1 , wherein the node R0 has a lowest nodeID in the network.

5. The method of claim 1 , wherein the Cq is initialized with nodes ordered from lowest nodeID to highest nodeID.

6. The method claim 1 , wherein nodes appended to the Cq are ordered from lowest nodeID to highest nodeID.

7. A method for computing a flooding topology (FT) in a network device, comprising:

setting an initial value for a maximum degree (MaxD);

implementing a first loop of the method, comprising:

selecting a node R0 from a network;

initializing the FT with the node R0;

adding nodes from the network to the FT;

determining whether the FT includes all nodes in the network; and

incrementing the value of the MaxD and repeating the steps of the first loop until the FT includes all the nodes in the network; and

implementing a second loop of the method when the FT includes all the nodes in the network, comprising:

adding a link to any node in the FT having only one link in the FT and coupled in the network to a node having a number of links less than the value of the MaxD;

determining whether all the nodes in the FT have more than one link in the FT; and

incrementing the value of the MaxD and repeating the first loop and the second loop until all the nodes in the FT have more than one link in the FT.

8. The method of claim 7 , wherein adding the nodes from the network to the FT comprises:

initializing a candidate queue (Cq) to include all nodes that are coupled in the network to the node R0, the nodes being ordered in the Cq by a nodeID of each node, where nodeID is an identifier of the node in a topology of the network; and

implementing a third loop of the method, comprising:

determining whether the Cq includes a node X, the node X being a first node in the Cq having a node Y in a Previous Hops (PHs) of the node X, the node Y having a degree less than the value of the MaxD;

terminating the third loop with the FT not including all the nodes in the network when the Cq does not include the node X;

removing the node X from the Cq and adding the node X to the FT;

determining whether the FT includes all the nodes in the network;

modifying the Cq when the FT does not include all the nodes in the network; and

terminating the third loop when the FT includes all the nodes in the network.

9. The method of claim 8 , wherein the Cq is initialized with nodes ordered from lowest nodeID to highest nodeID.

10. The method of claim 8 , wherein modifying the Cq when the FT does not include all the nodes in the network comprises:

creating a queue of all nodes that are coupled in the network to the node X and are not in the FT, the queue ordered by the nodeID of the nodes in the queue; and

for each node Z in the queue:

determining whether the node Z is in the Cq;

adding the node X to the PHs of the node Z in the Cq when the node Z is in the Cq; and

appending the node Z to the Cq when the node Z is not in the Cq.

11. The method of claim 10 , wherein nodes appended to the Cq are ordered from lowest nodeID to highest nodeID.

12. The method of claim 7 , wherein adding the link to any node in the FT having only one link in the FT and coupled in the network to the node having a number of links less than the value of the MaxD comprises:

implementing a fourth loop of the method comprising:

determining whether the FT includes a node Q having only one link in the FT;

terminating the fourth loop with all the nodes in the FT having more than one link in the FT when the FT does not include the node Q;

determining whether the FT includes a node L coupled to the node Q in the network, the node L having (i) a lowest number of links in the FT, (ii) a lowest nodeID when two or more nodes have the same lowest number of links in the FT, and (iii) the degree less than the value of the MaxD, when the FT does include the node Q;

when the FT does include the node L:

incrementing by 1 the degree of the node Q in the FT;

incrementing by 1 the degree of the node L in the FT; and

adding the node L to the PHs of the node Q in the FT; and

terminating the fourth loop without all the nodes in the FT having more than one link in the FT when the FT does not include the node L.

13. The method of claim 7 , wherein the node R0 has a lowest nodeID in the network.

14. A method for computing a flooding topology (FT) in a network device, comprising:

setting an initial value for a maximum degree (MaxD);

obtaining information identifying a subset of nodes in a network having a constraint (ConMaxD) on a number of links in the FT of nodes in the subset of nodes;

implementing a first loop of the method, comprising:

selecting a node R0 from the network;

initializing the FT with the node R0;

adding nodes from the network to the FT;

determining whether the FT includes all the nodes in the network; and

incrementing the value of the MaxD and repeating the steps of the first loop until the FT includes all the nodes in the network; and

implementing a second loop of the method when the FT includes all the nodes in the network, comprising:

adding a link to any node Q in the FT, the node Q having only one link in the FT and coupled in the network to a node L, the node L being a node in the subset of nodes having a number of links in the FT less than the ConMaxD or being a node not in the subset of nodes having a number of links in the FT less than the MaxD;

determining whether all the nodes in the FT have more than one link in the FT; and

incrementing the value of the MaxD and repeating the first loop and the second loop until all the nodes in the FT have more than one link in the FT.

15. The method of claim 14 , wherein adding the nodes from the network to the FT comprises:

initializing a candidate queue (Cq) to include all nodes that are coupled in the network to the node R0, the nodes being ordered in the Cq by a nodeID of each node, where nodeID is an identifier of the node in a topology of the network; and

implementing a third loop of the method, comprising:

determining whether the Cq includes a node X, the node X being a first node in the Cq (i) having a node Y in a Previous Hops (PHs) of the node X, the node Y having a degree less than the ConMaxD, when the node X is a node in the subset of nodes, or (ii) having a node Y in the PHs of the node X, the node Y having a degree less than the MaxD, when the node X is a node not in the subset of nodes;

terminating the third loop with the FT not including all the nodes in the network when the Cq does not include the node X;

removing the node X from the Cq and adding the node X to the FT;

determining whether the FT includes all the nodes in the network;

modifying the Cq when the FT does not include all the nodes in the network; and

terminating the third loop when the FT includes all the nodes in the network.

16. The method of claim 15 , wherein the Cq is initialized with nodes ordered from lowest nodeID to highest nodeID.

17. The method of claim 15 , wherein modifying the Cq when the FT does not include all the nodes in the network comprises:

creating a queue of all nodes that are coupled in the network to the node X and are not in the FT, the queue ordered by the nodeID of the nodes in the queue; and

for each node Z in the queue:

determining whether the node Z is in the Cq;

adding the node X to the PHs of the node Z in the Cq when the node Z is in the Cq; and

appending the node Z to the Cq when the node Z is not in the Cq.

18. The method of claim 17 , wherein nodes appended to the Cq are ordered from lowest nodeID to highest nodeID.

19. The method of claim 14 , wherein adding a link to any node in the FT having only one link in the FT and coupled in the network to a node having a number of links less than the MaxD comprises:

implementing a fourth loop of the method comprising:

determining whether the FT includes a node Q having only one link in the FT;

terminating the fourth loop with all the nodes in the FT having more than one link in the FT when the FT does not include the node Q;

determining whether the FT includes a node L coupled to the node Q in the network, the node L having (i) a lowest number of links in the FT, (ii) a lowest nodeID when two or more ConMaxD, when the node L is a node in the subset of nodes, or (b) having a degree less than the MaxD, when the node L is a node not in the subset of nodes, when the FT does include the node Q;

when the FT does include the node L:

incrementing by 1 the degree of the node Q in the FT;

incrementing by 1 the degree of the node L in the FT; and

adding the node L to Previous Hops (PHs) of the node Q in the FT, where the PHs is a set of one or more nodes to which the node Q is linked in the FT; and

terminating the fourth loop without all the nodes in the FT having more than one link in the FT when the FT does not include the node L.

20. The method of claim 14 , wherein the node R0 has a lowest nodeID in the network.