Back to results
US 12,750,303 B2Granted
Method for network subgraph link selection
AssigneeHuawei Technologies Co., Ltd.
InventorDonald Eggleston Eastlake, III
Life of this patent
Estimating the term…
Abstract
A method and network device for selecting links of a network subgraph, where the method includes: obtaining link costs of links in a network; obtaining node costs of nodes connected by each of the links in the network, where the node costs comprise a first node cost of a first node and a second node cost of a second node selected from the nodes; selecting a weighting parameter based on the link costs, the node costs, or both; calculating link and node costs for each of the links, where the link and node costs are calculated based on the link costs, the node costs, the weighting parameter, or any combination thereof; and selecting a link having a lowest link and node cost among the links.
Claims12
A method of selecting links for a network subgraph, the method comprising:
- obtaining at least two link costs of at least two links selected from a plurality of links in a network;
- obtaining at least two node costs of at least two nodes connected by links of the plurality of links in the network;
- selecting a weighting parameter based on the at least two link costs, the at least two node costs, or both;
- calculating link costs and node costs based on any combination of the at least two link costs, the at least two node costs, and the selected weighting parameter;
- selecting a link having a lowest link and node cost among the plurality of links, wherein selecting the link is performed without computing any global metric over the entire network, network subgraph, or path;
- storing the selected link on a node of the network;
- and
- transmitting data by the node using the selected link, and
- wherein either:
- calculating a link and node cost for a candidate link selected from a link of the plurality of links in the network is based on a following equation:
- Link
-
- and
-
- Nodes
-
- Cost
- =
- 1
- 1
- N
-
- 1
-
- C
- +
- 2
- *
- k
-
- 2
- L
-
- C
- +
- 1
- N
-
- 2
-
- C
- ,
- wherein N1C denotes a first node cost of a first node in the at least two nodes, wherein N2C denotes a second node cost of a second node in the at least two nodes, wherein LC denotes a link cost of the candidate link, and wherein k2 denotes the weighting parameter, or
- wherein at least one link of the plurality of links in the network is a multi-point link that connects more than two nodes, and wherein calculating a link and node cost for the multi-point link is based on following equation:
- Link
-
- and
-
- Nodes
-
- Cost
- =
- 1
- n
- *
- k
-
- 2
- L
-
- C
- +
- ∑
- i
- =
- 1
- n
- 1
- N
-
- i
-
- C
- ,
- wherein n denotes a quantity of nodes to which the multi-point link connects, wherein LC denotes a link cost of the multi-point link, wherein k2 denotes the weighting parameter, and wherein NiC denotes a node cost of an ith node.
72 more elements
A network device for selecting links of a network subgraph, comprising:
- a storage device;
- and
- a processor coupled to the storage device and configured to execute instructions on the storage device such that when executed, cause the network device to:
- obtain at least two link costs of at least two links selected from a plurality of links in a network;
- obtain at least two node costs of at least two nodes connected by links of the plurality of links in the network;
- select a weighting parameter based on the at least two link costs, the at least two node costs, or both;
- calculate link costs and node costs based on any combination of the at least two link costs, the at least two node costs, and the weighting parameter;
- select a link having a lowest link and node cost among the plurality of links, wherein selecting the link is performed without computing any global metric over the entire network, network subgraph, or path;
- store the selected link on a node of the network;
- and
- transmit data by the node using the selected link, and
- wherein either:
- calculating a link and node cost for a candidate link selected from a link of the plurality of links in the network is based on a following equation:
- Link
-
- and
-
- Nodes
-
- Cost
- =
- 1
- 1
- N
-
- 1
-
- C
- +
- 2
- *
- k
-
- 2
- L
-
- C
- +
- 1
- N
-
- 2
-
- C
- ,
- wherein N1C denotes a first node cost of a first node in the at least two nodes, wherein N2C denotes a second node cost of a second node in the at least two nodes, wherein LC denotes a link cost of the candidate link, and wherein k2 denotes the weighting parameter, or
- wherein at least one link of the plurality of links in the network is a multi-point link that connects more than two nodes, and wherein calculating a link and node cost for the multi-point link is based on following equation:
- Link
-
- and
-
- Nodes
-
- Cost
- =
- 1
- n
- *
- k
-
- 2
- L
-
- C
- +
- ∑
- i
- =
- 1
- n
- 1
- N
-
- i
-
- C
- ,
- wherein n denotes a quantity of nodes to which the multi-point link connects, wherein LC denotes a link cost of the multi-point link, wherein k2 denotes the weighting parameter, and wherein NiC denotes a node cost of an ith node.
75 more elements
A non-transitory computer readable medium configured to store instructions that, when executed by a processor of a network device, cause the network device to perform a method for selecting links of a network subgraph, the method comprising:
- obtaining at least two link costs of at least two links selected from a plurality of links in a network;
- obtaining at least two node costs of at least two nodes connected by links of the plurality of links in the network;
- selecting a weighting parameter based on the at least two link costs, the at least two node costs, or both;
- calculating link and node costs based on any combination of the at least two links, the at least two node costs, and the weighting parameter;
- and
- selecting a link having a lowest link and node cost among the plurality of links, wherein selecting the link is performed without computing any global metric over the entire network, network subgraph, or path;
- storing the selected link on a node of the network;
- and
- transmitting data by the node using the selected link, and
- wherein either:
- calculating a link and node cost for a candidate link selected from a link of the plurality of links in the network is based on a following equation:
- Link
-
- and
-
- Nodes
-
- Cost
- =
- 1
- 1
- N
-
- 1
-
- C
- +
- 2
- *
- k
-
- 2
- L
-
- C
- +
- 1
- N
-
- 2
-
- C
- ,
- wherein N1C denotes a first node cost of a first node in the at least two nodes, wherein N2C denotes a second node cost of a second node in the at least two nodes, wherein LC denotes a link cost of the candidate link, and wherein k2 denotes the weighting parameter, or
- wherein at least one link of the plurality of links in the network is a multi-point link that connects more than two nodes, and wherein calculating a link and node cost for the multi-point link is based on following equation:
- Link
-
- and
-
- Nodes
-
- Cost
- =
- 1
- n
- *
- k
-
- 2
- L
-
- C
- +
- ∑
- i
- =
- 1
- n
- 1
- N
-
- i
-
- C
- ,
- wherein n denotes a quantity of nodes to which the multi-point link connects, wherein LC denotes a link cost of the multi-point link, wherein k2 denotes the weighting parameter, and wherein NiC denotes a node cost of an ith node.
73 more elements
Dependencies are inferred from the claim text.