# US 11,115,314 B2 · Establishing entry corresponding to equal cost paths

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

- Number: US 11,115,314 B2
- Document ID: US11115314B2
- Status: Granted
- Kind: B2
- Application number: 16/480,667
- Filed: 2018-01-25
- Published: 2019-12-19
- Granted: 2021-09-07
- Earliest claimed: 2017-01-25
- Assignees: New H3C Technologies Co., Ltd.
- Applicants: New H3C Technologies Co., Ltd.
- Inventors: Sansheng Yang
- Web page: https://patentgrep.com/patent/US11115314B2

## CPC

- H04L 45/24: Multipath
- H04L 45/03: by updating link state protocols
- H04L 45/123: {Evaluation of link metrics (techniques for monitoring network metrics H04L43/08)}
- H04L 45/54: {Organization of routing tables}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Methods of establishing an entry corresponding to equal cost paths, network devices and non-transitory machine-readable storage medium are provided. In one aspect, the network establishes a FIB entry, where the FIB entry includes the number of UCMP entries UCMP table corresponding to N paths configured to be equal cost with each other between the network device and a destination network device, where an address of the destination network device, and the number of the UCMP entries in the UCMP table is equal to a preset fixed value; and assigns at least one UCMP entry for each of the N paths based on respective weights of the paths and the fixed value, where the at least one ECMP entry corresponding to the path respectively includes index information corresponding to the path.

## Claims

### Claim 1

A method of establishing an entry corresponding to equal cost paths, comprising:
establishing, by a network device, a Forward Information DataBase (FIB) entry, wherein the FIB entry comprises the number of Unequal Cost Multipath (UCMP) entries in a UCMP table corresponding to N paths configured to be equal cost with each other between the network device and a destination network device, and an address of the destination network device, wherein the number of the UCMP entries in the UCMP table is equal to a preset fixed value, and N is an integer more than or equal to 2; and
assigning, by the network device, at least one UCMP entry for each of the N paths based on respective weights of the paths and the fixed value, wherein the at least one UCMP entry corresponding to the path respectively comprises index information corresponding to the path, a sum of the numbers of the respective UCMP entries corresponding to the N paths is equal to the fixed value,
wherein assigning the at least one UCMP entry for each of the N paths based on the respective weights of the paths and the fixed value comprises:
determining, by the network device, for each of the N paths, a first numerical value T of the path by multiplying the fixed value by the weight of the path to obtain a product and rounding down the product divided by a total weight, wherein the total weight is a sum of the respective weights of the N paths;
determining, by the network device, that a second numerical value D is equal to a difference between the fixed value and a sum of the respective first numerical values T of the N paths;
when the second numerical value D is equal to zero,
determining, by the network device, for each of the paths, the first numerical value T of the path to be the number of the at least one UCMP entry corresponding to the path;
when the second numerical value D is more than zero,
sorting, by the network device, the N paths based on the respective weights of the N paths,
determining, by the network device, for each of first D paths in the sorted N paths, the first numerical value T of the path plus 1 to be the number of the at least one UCMP entry of the path,
determining, by the network device, for each of remaining paths in the sorted N paths, the first numerical value T of the path to be the number of the at least one UCMP entry of the path.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
when the number of the paths is changed to be N′,
re-assigning, by the network device, at least one UCMP entry for each of the N′ paths based on the respective weights of the N′ paths and the fixed value, wherein N′ is an integer more than or equal to 2.

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
when a new path is added to the paths that are equal cost with each other,
determining, by the network device, for each of the N paths, the number of at least one decreased UCMP entry corresponding to the path, selecting at least one UCMP entry with the determined number from the at least one UMCP entry corresponding to the path,
assigning, by the device, the at least one selected UCMP entry to the added path.

### Claim 4 (depends on 3)

The method of claim 3, wherein determining, for each of the N paths, the number of at least one decreased UCMP entry corresponding to the path comprises:
determining, by the network device, the number N″ of the paths that are equal cost with each other after the new path is added, wherein N″ is an integer more than or equal to 2;
determining, by the network device, the number of at least one UCMP entry corresponding to each of the N″ paths based on the respective weights of the N″ paths and the fixed value;
determining, by the network device, for each of the N paths, that the number of the at least one decreased UCMP entry corresponding to the path is equal to a difference between the number of the at least one UCMP entry corresponding to the path in the N paths and the number of the at least one UCMP entry corresponding to the path in the N″ paths.

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
when a path is deleted from the paths which are equal cost with each other,
determining, by the network device, the number N′″ of the paths that are equal cost with each other after the path is deleted, wherein N′″ is an integer more than or equal to 2;
determining, by the network device, for each of the N′″ paths, the number of at least one increased UCMP entry corresponding to the path, selecting at least one UCMP entry with the determined number from the at least one UCMP entry corresponding to the deleted path, and assigning the selected at least one UCMP entry for the path.

### Claim 6 (depends on 5)

The method of claim 5, wherein determining, for each of the N′″ paths, the number of at least one increased UCMP entry corresponding to the path in the N′″ paths comprises:
obtaining, by the network device, at least one UCMP entry corresponding to each of the N′″ paths based on the respective weights of the N′″ paths and the fixed value;
determining, by the network device, for each of the N′″ paths, that the number of the at least one increased UCMP entry is equal to a difference between the number of the at least one UCMP entry corresponding to the path in the N′″ paths and the number of the at least one UCMP entry corresponding to the path in the N paths.

### Claim 7

A network device, comprising:
a processor, and
a non-transitory machine-readable storage medium storing machine executable instructions which are executable by the processor to:
establish a Forward Information DataBase (FIB) entry, wherein the FIB entry comprises the number of Unequal Cost Multipath (UCMP) entries in a UCMP table corresponding to N paths configured to be equal cost with each other between the network device and a destination network device, and an address of the destination network device, wherein the number of the UCMP entries in the UCMP table is equal to a preset fixed value, and N is an integer more than or equal to 2; and
assign at least one UCMP entry for each of the N paths based on respective weights of the paths and the fixed value, wherein the at least one UCMP entry corresponding to the path respectively comprises index information corresponding to the path, a sum of the numbers of the respective UCMP entries corresponding to the N paths is equal to the fixed value,
wherein the processor is caused by the machine-executable instructions to:
determine, for each of the N paths, a first numerical value T of the path by multiplying the fixed value by the weight of the path to obtain a product and rounding down the product divided by a total weight, wherein the total weight is a sum of the respective weights of the N paths;
determine that a second numerical value D is equal to a difference between the fixed value and a sum of the respective first numerical values T of the N paths; when the second numerical value D is equal to zero, determine, for each of the paths, the first numerical value T of the path to be the number of the at least one UCMP entry corresponding to the path;
when the second numerical value D is more than zero,
sort the N paths based on the respective weights of the N paths,
determine, for each of first D paths in the sorted N paths, the first numerical value T of the path plus 1 to be the number of the at least one UCMP entry of the path,
determine, for each of remaining paths in the sorted N paths, the first numerical value T of the path to be the number of the at least one UCMP entry of the path.

### Claim 8 (depends on 7)

The network device of claim 7, wherein the processor is caused by the machine-executable instructions further to:
when the number of the paths is changed to be N′,
re-assign at least one UCMP entry for each of the N′ paths based on the respective weights of the N′ paths and the fixed value, wherein N′ is an integer more than or equal to 2.

### Claim 9 (depends on 7)

The network device of claim 7, wherein the processor is caused by the machine-executable instructions further to:
when a new path is added to the paths that are equal cost with each other,
determine, for each of the N paths, the number of at least one decreased UCMP entry corresponding to the path,
select at least one UCMP entry with the determined number from the at least one UMCP entry corresponding to the path,
assign the at least one selected UCMP entry to the added path.

### Claim 10 (depends on 9)

The network device of claim 9, wherein the processor is caused by the machine-executable instructions to:
determine the number N″ of the paths that are equal cost with each other after the new path is added, wherein N″ is an integer more than or equal to 2;
determine the number of at least one UCMP entry corresponding to each of the N″ paths based on the respective weights of the N″ paths and the fixed value;
determine, for each of the N paths, that the number of the at least one decreased UCMP entry corresponding to the path is equal to a difference between the number of the at least one UCMP entry corresponding to the path in the N paths and the number of the at least one UCMP entry corresponding to the path in the N″ paths.

### Claim 11 (depends on 7)

The network device of claim 7, wherein the processor is caused by the machine-executable instructions further to:
when a path is deleted from the paths which are equal cost with each other,
determine the number N′″ of the paths that are equal cost with each other after the path is deleted, wherein N′″ is an integer more than or equal to 2;
determine, for each of the N′″ paths, the number of at least one increased UCMP entry corresponding to the path,
select at least one UCMP entry with the determined number from the at least one UCMP entry corresponding to the deleted path, and
assign the selected at least one UCMP entry for the path.

### Claim 12 (depends on 11)

The network device of claim 11, wherein the processor is caused by the machine-executable instructions to:
obtain, at least one UCMP entry corresponding to each of the N′″ paths based on the respective weights of the N′″ paths and the fixed value;
determine, for each of the N′″ paths, that the number of the at least one increased UCMP entry is equal to a difference between the number of the at least one UCMP entry corresponding to the path in the N′″ paths and the number of the at least one UCMP entry corresponding to the path in the N paths.

### Claim 13

A non-transitory machine-readable storage medium storing machine executable instructions which are invoked and executed by a processor of a network device to:
establish a Forward Information DataBase (FIB) entry, wherein the FIB entry comprises the number of Unequal Cost Multipath (UCMP) entries in a UCMP table corresponding to N paths configured to be equal cost with each other between the network device and a destination network device, and an address of the destination network device, wherein the number of the UCMP entries in the UCMP table is equal to a preset fixed value, and N is an integer more than or equal to 2; and
assign at least one UCMP entry for each of the N paths based on respective weights of the paths and the fixed value, wherein the at least one UCMP entry corresponding to the path respectively comprises index information corresponding to the path, a sum of the numbers of the respective UCMP entries corresponding to the N paths is equal to the fixed value,
wherein assigning the at least one UCMP entry for each of the N paths based on the respective weights of the paths and the fixed value comprises:
determining, by the network device, for each of the N paths, a first numerical value T of the path by multiplying the fixed value by the weight of the path to obtain a product and rounding down the product divided by a total weight, wherein the total weight is a sum of the respective weights of the N paths;
determining, by the network device, that a second numerical value D is equal to a difference between the fixed value and a sum of the respective first numerical values T of the N paths;
when the second numerical value D is equal to zero,
determining, by the network device, for each of the paths, the first numerical value T of the path to be the number of the at least one UCMP entry corresponding to the path;
when the second numerical value D is more than zero,
sorting, by the network device, the N paths based on the respective weights of the N paths,
determining, by the network device, for each of first D paths in the sorted N paths, the first numerical value T of the path plus 1 to be the number of the at least one UCMP entry of the path,
determining, by the network device, for each of remaining paths in the sorted N paths, the first numerical value T of the path to be the number of the at least one UCMP entry of the path.