Routing packets based on congestion of minimal and non-minimal routes
AssigneeHewlett Packard Enterprise Development LP
InventorsNicholas George McDonald, Michael Isaev
Life of this patent
Estimating the term…
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.
Claims16
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 a non-minimal candidate route of the non-minimal candidate routes wherein the adaptive weight assigned to a particular non-minimal candidate route is determined based on a combination of a function of congestion of the minimal candidate routes and the non-minimal candidate routes and a number of hops of the particular non-minimal candidate route;
- and
- routing, by the routing engine, the packet to the destination device using an optimal route among the candidate routes;
- 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.
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 a non-minimal candidate route of the non-minimal candidate routes wherein the adaptive weight assigned to a particular non-minimal candidate route is determined based on a function of congestion of the minimal candidate routes and the non-minimal candidate routes and a number of hops of the particular non-minimal candidate route;
- and
- route the packet to the destination device using an optimal route among the candidate routes, the optimal route having a lowest estimated latency;
- 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.
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 a non-minimal candidate route of the non-minimal candidate routes, wherein the adaptive weight assigned to a particular non-minimal candidate routes is determined based on a combination of a function of congestion of the minimal candidate routes and the non-minimal candidate routes and a number of hops of the particular non-minimal candidate route;
- and
- route the packet to the destination device using an optimal route among the candidate routes,
- wherein the routing engine is to determine the adaptive weight to be assigned to a particular non-minimal candidate route by multiplying 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.
Dependencies are inferred from the claim text.