System and methods for computing flooding topology
AssigneeHuawei Technologies Co., Ltd.
InventorHuaimo Chen
Life of this patent
Estimating the term…
Abstract
Methods of computing a flooding topology (FT) for a network are presented. The methods include a process for computing a FT that includes all nodes in the network and a process for ensuring that all nodes in the FT have at least two links in the FT. Some of the methods minimize a number of links of the nodes in the FT. Some of the methods also constrain some of the nodes in the FT to a maximum number of links. Some of the methods compute a first FT for nodes whose maximum number of links in the FT equal their number of links in the network, then compute a second FT for remaining nodes in the network, then combines the two FTs to compute a complete FT for the network.
Claims26
A network device, comprising:
- a memory configured to store instructions;
- and
- a processor coupled to the memory and configured to execute the instructions stored in the memory to cause the network device to:
- select a node R0 from a plurality of nodes;
- initialize a flooding topology (FT) with the node R0;
- initialize a candidate queue (Cq);
- implement a first loop, wherein the network device:
- removes a first node from the Cq and adding the first node to the FT;
- determines whether the FT includes all nodes in the plurality of nodes;
- terminates the first loop when the FT includes all the nodes in the plurality of nodes;
- and
- appends to the Cq those nodes that are coupled in the plurality of nodes to the first node and are not in the FT when the FT does not include all the nodes in the plurality of nodes;
- and
- adds a link to any node in the FT having only one link in the FT.
A network device, comprising:
- a memory configured to store instructions;
- and
- a processor coupled to the memory and configured to execute the instructions stored in the memory to cause the network device to:
- set an initial value for a maximum degree (MaxD);
- implement a first loop, wherein the network device:
- selects a node R0 from a plurality of nodes;
- initializes a flooding topology (FT) with the node R0;
- adds nodes from the plurality of nodes to the FT;
- determines whether the FT includes all nodes in the plurality of nodes;
- increments the value of the MaxD;
- and
- repeats the steps of the first loop until the FT includes all the nodes in the plurality of nodes;
- and
- implements a second loop when the FT includes all the nodes in the plurality of nodes, wherein the network device:
- adds a link to any node in the FT having only one link in the FT and coupled in the plurality of nodes to a node having a number of links less than MaxD;
- determines whether all the nodes in the FT have more than one link in the FT;
- and
- increments the value of the MaxD:
- and
- repeats the first loop and the second loop until all the nodes in the FT have more than one link in the FT.
A method for computing a flooding topology (FT) in a network device, comprising:
- selecting a node R0 from a plurality of nodes;
- 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 plurality of nodes;
- terminating the first loop when the FT includes all the nodes in the plurality of nodes;
- and
- appending to the Cq those nodes that are coupled in the plurality of nodes to the first node and are not in the FT when the FT does not include all the nodes in the plurality of nodes;
- and
- adding a link to any node in the FT having only one link in the FT.
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 plurality of nodes;
- initializing the FT with the node R0;
- adding nodes from the plurality of nodes to the FT;
- determining whether the FT includes all nodes in the plurality of nodes;
- and
- incrementing the value of the MaxD and repeating the steps of the first loop until the FT includes all the nodes in the plurality of nodes;
- and
- implementing a second loop of the method when the FT includes all the nodes in the plurality of nodes, comprising:
- adding a link to any node in the FT having only one link in the FT and coupled in the plurality of nodes to a node having a number of links less than 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.
Dependencies are inferred from the claim text.