# US 2023/0155929 A1 · Parameterized Method for Network Subgraph Root Node Selection

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2023/0155929 A1
- Document ID: US20230155929A1
- Status: Published application
- Kind: A1
- Application number: 18/154,706
- Filed: 2023-01-13
- Published: 2023-05-18
- Earliest claimed: 2020-07-13
- Assignees: Huawei Technologies Co., Ltd.
- Applicants: Huawei Technologies Co., Ltd.
- Inventors: Donald Eggleston Eastlake, III
- Web page: https://patentgrep.com/patent/US20230155929A1

## CPC

- H04L 45/124: {using a combination of metrics}
- H04L 45/24: Multipath
- H04L 45/42: Centralised routing
- H04L 45/488: using root node determination
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A method and network device for root selection, where the method includes: obtaining link costs of links connecting a plurality of nodes in the network; selecting a weighting parameter based at least partly on the link costs; calculating node costs corresponding to each of the plurality of the nodes based on the link costs and the weighting parameter; and selecting a node as the root node based on the node costs, wherein the root node is selected from the plurality of nodes.

## Claims

### Claim 1

A method of selecting a root node for a to-be-constructed subgraph of a network, the method comprising:
obtaining link costs of links connecting a plurality of nodes in the network;
selecting a weighting parameter based on the link costs;
calculating node costs for each of the plurality of the nodes based on the link costs and the weighting parameter; and
selecting a node from the plurality of nodes as the root node based on the node costs.

### Claim 2 (depends on 1)

The method of claim 1, wherein selecting the node as the root node comprises selecting at least one node having a lowest node cost.

### Claim 3 (depends on 1)

The method of claim 1, wherein selecting the weighting parameter is based on a first quantity of links connected to each node and a second quantity of links that are of lower link costs than other links in the network.

### Claim 4 (depends on 1)

The method claim 1, wherein a node cost for calculating the node costs for each of the plurality of nodes is calculated using a formula comprising:
Node
⁢
Cost
=
HarmonicMean
(
C
⁢
1
k
,
C
⁢
2
k
,
C
⁢
3
k
,
…
)
NumberOfLinks
,
where C1, C2, C3, . . . represent the links costs, where k represents the weighting parameter, and where the Number of Links is a quantity of links connected to the node for which the node cost is calculated.

### Claim 5 (depends on 4)

The method of claim 4, wherein C1, C2, C3, . . . are integers greater than zero.

### Claim 6 (depends on 5)

The method of claim 5, wherein selecting the weighting parameter comprises setting k to a value greater than 1.

### Claim 7 (depends on 5)

The method of claim 5, wherein selecting the weighting parameter comprises setting k to a value between 0 and 1.

### Claim 8 (depends on 5)

The method of claim 5, wherein selecting the weighting parameter comprises setting k to a value equal to 1.

### Claim 9

A network device for root node selection, comprising:
a storage device;
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 link costs of links connecting a plurality of nodes in a network;
select a weighting parameter based on the link costs;
calculate node costs for each of the plurality of the nodes based on the link costs and the weighting parameter; and
selecting a node from the plurality of nodes as a root node based on the node costs.

### Claim 10 (depends on 9)

The network device of claim 9, wherein the network device selects the node as the root node by selecting at least one node having a lowest node cost.

### Claim 11 (depends on 9)

The network device of claim 9, wherein the network device selects the weighting parameter based on a first quantity of links connected to each node and a second quantity of links that are of lower link costs than other links in the network.

### Claim 12 (depends on 9)

The network device of claim 9, wherein a node cost for calculating the node costs for each of the plurality of nodes is calculated using a formula comprising:
Node
⁢
Cost
=
HarmonicMean
(
C
⁢
1
k
,
C
⁢
2
k
,
C
⁢
3
k
,
…
)
NumberOfLinks
,
where C1, C2, C3, . . . represent the links costs, where k represents the weighting parameter, and where the Number of Links is a quantity of links connected to the node for which the node cost is calculated.

### Claim 13 (depends on 12)

The network device of claim 12, wherein C1, C2, C3, . . . are integers greater than zero.

### Claim 14 (depends on 13)

The network device of claim 13, wherein the network device selects the weighting parameter by setting k to a value greater than 1.

### Claim 15 (depends on 13)

The network device of claim 13, wherein the network device selects the weighting parameter by setting k to a value between 0 and 1.

### Claim 16 (depends on 13)

The network device of claim 13, wherein the network device selects the weighting parameter by setting k to a value equal to 1.

### Claim 17

A 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 a root node, the method comprising:
obtaining link costs of links connecting a plurality of nodes in the network;
selecting a weighting parameter based on the link costs;
calculating node costs for each of the plurality of the nodes based on the link costs and the weighting parameter; and
selecting a node from the plurality of nodes as the root node based on the node costs.

### Claim 18 (depends on 17)

The computer readable medium of claim 17, wherein selecting the node as the root node comprises selecting at least one node having a lowest node cost.

### Claim 19 (depends on 17)

The computer readable medium of claim 17, wherein selecting the weighting parameter is based on a first quantity of links connected to each node and a second quantity of links that are of lower link costs than other links in the network.

### Claim 20 (depends on 17)

The computer readable medium of claim 17, wherein a node cost for calculating the node costs for each of the plurality of nodes is calculated using a formula comprising:
Node
⁢
Cost
=
HarmonicMean
(
C
⁢
1
k
,
C
⁢
2
k
,
C
⁢
3
k
,
…
)
NumberOfLinks
,
where C1, C2, C3, . . . represent the links costs, where k represents the weighting parameter, and where the Number of Links is a quantity of links connected to the node for which the node cost is calculated.
