# US 2019/0104054 A1 · Routing packets based on congestion of minimal and non-minimal routes

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

- Number: US 2019/0104054 A1
- Document ID: US20190104054A1
- Status: Published application
- Kind: A1
- Application number: 15/719,928
- Filed: 2017-09-29
- Published: 2019-04-04
- Earliest claimed: 2017-09-29
- Assignees: Hewlett Packard Enterprise Development LP
- Applicants: Hewlett Packard Enterprise Development LP
- Inventors: Nicholas George McDonald; Michael Isaev
- Web page: https://patentgrep.com/patent/US20190104054A1

## CPC

- H04L 45/122: by minimising distances, e.g. by selecting a route with minimum of number of hops
- H04L 45/24: Multipath
- H04L 47/12: Avoiding congestion; Recovering from congestion
- H04L 45/125: based on throughput or bandwidth
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Examples relate to routing packets based on the actual congestion sensed in the minimal and the non-minimal candidate routes between a source network device and a destination network device. A packet is received at a network device in a network and all possible minimal and non-minimal candidate routes for the packet to be routed to the destination network device are determined. An adaptive weight is assigned to the non-minimal candidate routes, wherein the adaptive weight is a function of congestion of the minimal candidate routes and the non-minimal candidate routes. An optimal route is selected among the plurality of candidate routes and the packet is routed to the destination device using the optimal route.

## Claims

### Claim 1

A method, comprising:
receiving a packet at a network device of a plurality of network devices in a network, wherein the packet is to be routed to a destination network device;
determining, by a routing engine of the network device, all possible candidate routes for the packet to be routed to the destination network device, the candidate routes comprising minimal candidate routes and non-minimal candidate routes;
assigning, by the routing engine, an adaptive weight to the non-minimal candidate routes wherein the adaptive weight is a function of congestion of the minimal candidate routes and the non-minimal candidate routes; and
routing, by the routing engine, the packet to the destination device using an optimal route among the candidate routes.

### Claim 2 (depends on 1)

The method of claim 1, comprising determining the adaptive weight to be assigned to a particular non-minimal candidate route based on a combination of the function of the congestion of the minimal candidate routes and the non-minimal candidate routes and a number of hops of the particular non-minimal candidate route.

### Claim 3 (depends on 2)

The method of claim 2, wherein the adaptive weight of the particular non-minimal candidate route is calculated by multiplying an output of the function of the congestion of the minimal candidate routes and the non-minimal candidate routes and the number of hops of the particular non-minimal candidate route.

### Claim 4 (depends on 1)

The method of claim 1, comprising calculating the function of the congestion of the minimal candidate routes and the non-minimal candidate routes by adding a product of a scalar and a difference between a congestion of a fully congested minimal candidate route and a current congestion of the candidate minimal routes to the congestion of the non-minimal route.

### Claim 5 (depends on 1)

The method of claim 1, comprising calculating the function of congestion of the minimal candidate routes and the non-minimal candidate routes as the difference between the congestion of the non-minimal candidate routes and the congestion of the minimal candidate routes.

### Claim 6 (depends on 1)

The method of claim 1, comprising calculating the function of congestion of the minimal candidate routes and the non-minimal candidate routes as a ratio between the congestion of the non-minimal candidate routes and the congestion of the minimal candidate routes.

### Claim 7 (depends on 1)

The method of claim 1, wherein the function of congestion of the minimal candidate routes and the non-minimal candidate routes is a heuristic function comprising:
determining a congestion threshold;
determining whether the congestion of the minimal candidate routes is less than the congestion threshold;
returning infinity when the congestion of the minimal candidate routes is below the congestion threshold; and
returning the congestion of the non-minimal candidate when the congestion of the minimal candidate routes is higher than or equal to the congestion threshold.

### Claim 8 (depends on 1)

The method of claim 1, wherein selecting, by the routing engine, the optimal route among the candidate routes comprises selecting, by the routing engine, the optimal route as the candidate route having a lowest estimated latency.

### Claim 9 (depends on 1)

The method of claim 1, wherein, when there is a plurality of minimal candidate routes, selecting, by the routing engine, the congestion of the minimal candidate routes from a group comprising:
a minimum congestion among the congestions of the minimal candidate routes;
a maximum congestion among the congestions of the minimal candidate routes;
an average of the congestions of the minimal candidate routes; and
a random congestion among the congestions of the minimal candidate routes.

### Claim 10 (depends on 1)

The method of claim 1, wherein, when there is a plurality of non-minimal candidate routes, selecting, by the routing engine, the congestion of the non-minimal candidate routes from a group comprising:
a minimum congestion among the congestions of the non-minimal candidate routes;
a maximum congestion among the congestions of the non-minimal candidate routes;
an average of the congestions of the non-minimal candidate routes; and
a random congestion among the congestions of the non-minimal candidate routes.

### Claim 11

A non-transitory machine readable storage medium comprising instructions executable by a routing engine of a network device to:
in response to reception of a packet in the network device, determine all possible candidate routes for the packet to be routed to a destination network device, the candidate routes comprising minimal candidate routes and non-minimal candidate routes;
assign an adaptive weight to the non-minimal candidate routes wherein the adaptive weight is a function of congestion of the minimal candidate routes and the non-minimal candidate routes; and
route the packet to the destination device using an optimal route among the candidate routes, the optimal route having a lowest estimated latency.

### Claim 12 (depends on 11)

The non-transitory machine readable storage medium of claim 11, wherein the instructions to assign an adaptive weight to the non-minimal candidate routes comprise instructions to determine the adaptive weight to be assigned to a particular non-minimal candidate route based on a combination of the function of the congestion of the minimal candidate routes and the non-minimal candidate routes and a number of hops of the particular non-minimal candidate route.

### Claim 13 (depends on 12)

The non-transitory machine readable storage medium of claim 12, wherein instructions to determine the adaptive weight to be assigned to a particular non-minimal candidate route comprise instructions to calculate the adaptive weight by multiplying the function of the congestion of the minimal candidate routes and the non-minimal candidate routes and the number of hops of the particular non-minimal candidate route.

### Claim 14 (depends on 11)

The non-transitory machine readable storage medium of claim 11, wherein the instructions to assign an adaptive weight to the non-minimal candidate routes comprise instructions to determine the function of the congestion of the minimal candidate routes and the non-minimal candidate routes by adding a product of a scalar and a difference between a fully congested minimal candidate route and a current congestion of the candidate minimal routes to the congestion of the non-minimal route.

### Claim 15 (depends on 11)

The non-transitory machine readable storage medium of claim 11, wherein the instructions to assign an adaptive weight to the non-minimal candidate routes comprise further instructions to determine the function of congestion of the minimal candidate routes and the non-minimal candidate routes as the difference of the congestion of the non-minimal candidate routes and the congestion of the minimal candidate routes.

### Claim 16 (depends on 11)

The non-transitory machine readable storage medium of claim 11, wherein the instructions to assign an adaptive weight to the non-minimal candidate routes comprise further instructions to determine the function of congestion of the minimal candidate routes and the non-minimal candidate routes as a ratio between the congestion of the non-minimal candidate routes and the congestion of the minimal candidate routes.

### Claim 17 (depends on 11)

The non-transitory machine readable storage medium of claim 11, wherein the instructions to assign an adaptive weight to a particular non-minimal candidate route comprise further instructions to:
determine a congestion threshold;
determine whether the congestion of the minimal candidate routes is less than the congestion threshold;
return infinity when the congestion of the minimal candidate routes is below the congestion threshold; and
return the congestion of the non-minimal candidate routes when the congestion of the minimal candidate routes is higher or equal than the congestion threshold.

### Claim 18

A network device comprising:
at least one ingress port through which a packet is received;
at least one egress port through which the packet is forwarded to a destination device; and
a routing engine to:
determine all possible candidate routes for the packet to be routed to the destination network device, the candidate routes comprising minimal candidate routes and non-minimal candidate routes;
assign an adaptive weight to the non-minimal candidate routes, wherein the adaptive weight is a function of congestion of the minimal candidate routes and the non-minimal candidate routes; and
route the packet to the destination device using an optimal route among the candidate routes.

### Claim 19 (depends on 18)

The network device of claim 18, wherein the routing engine is to determine the adaptive weight to be assigned to a particular non-minimal candidate route based on a combination of the function of the congestion of the minimal candidate routes and the non-minimal candidate routes and a number of hops of the particular non-minimal candidate route.

### Claim 20 (depends on 18)

The network device of claim 18, wherein the routing engine is to the select the optimal route among all the candidate routes as the candidate route having a lowest estimated latency.
