Routing packets based on congestion of minimal and non-minimal routes

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 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. The method of claim 1 , wherein, when there is a plurality of non-minimal candidate route, 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.

9. 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.

10. The non-transitory machine readable storage medium of claim 9 , 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.

11. The non-transitory machine readable storage medium of claim 9 , 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.

12. The non-transitory machine readable storage medium of claim 9 , 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.

13. The non-transitory machine readable storage medium of claim 9 , 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.

14. 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.

15. The network device of claim 14 , 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.

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