Fat tree adaptive routing

1 . A method, comprising:

receiving, by a network device in a network having a plurality of network devices configured in a fat-tree topology, a data flow comprising a plurality of packets at an edge port of the network device;

determining whether to apply a destination-based hash function to the data flow based on a rule;

in response to determining that the destination-based hash function is to be applied to the data flow:

applying the destination-based hash function to one or more header fields of a respective packet of the data flow to determine a hash value;

determining an entry indexed based on the hash value in a data structure stored at the network device, the data structure storing respective port identifiers of egress ports of the network device;

determining a port identifier specified in the entry indexed based on the hash value; and

forwarding the packet via an egress port corresponding to the port identifier.

2 . The method of claim 1 , wherein the one or more header fields comprise a layer-2 header field and a layer-3 header field.

3 . The method of claim 1 , wherein determining whether to apply the destination-based hash function comprises determining whether the egress port is part of a path of a set of equal-cost multiple paths (ECMP) to a destination of the data flow.

4 . The method of claim 1 , wherein determining whether to apply the destination-based hash function comprises determining whether the egress port is coupled to a link of a link-aggregation group (LAG) via which a destination of the data flow is reachable.

5 . The method of claim 1 , wherein the rule is a translation function rule; and

wherein the method further comprises:

applying, by the network device, a the translation function rule to the packet to determine a first value and a second value to be used for forwarding of the packet;

determining a subset of bits of the hash value based on the second value; and

determining an index for the entry based on the first value and the subset of the bits of the hash value.

6 . The method of claim 5 , wherein determining the subset of bits of the hash value further comprises multiplying the hash value by the second value; and

wherein determining the index for the entry further comprises adding the first value to a third value indicated by the subset of the bits of the hash value.

7 . The method of claim 5 , wherein applying the translation function rule comprises determining the first value and the second value by looking up a destination address of the packet in a translation table stored at th network device.

8 . The method of claim 1 , wherein applying the destination-based hash function comprises applying a Cyclic Redundancy Check (CRC) function to compress the one or more header fields into the hash value.

9 . A network device in a network having a plurality of network devices configured in a fat-tree topology, comprising:

a processor;

an input port of a switch to receive a data flow comprising plurality of packets;

a plurality of output ports;

a memory storing a data structure comprising respective port identifiers of the output ports; and

a non-transitory computer-readable storage medium storing instructions that when executed by the processor cause the network device to:

determine whether to apply a destination-based hash function to the data flow based on a rule;

in response to determining that the destination-based hash function is to be applied to the data flow:

apply the destination-based hash function to one or more header fields of a respective packet of the data flow to determine a hash value;

determine an entry indexed based on the hash value in the data structure;

determine a port identifier specified in the entry indexed based on the hash value;

select an output port from the plurality of output ports based on the port identifier; and

forward the packet via the output port.

10 . The network device of claim 9 , wherein the one or more header fields comprise a layer-2 header field and a layer-3 header field.

11 . The network device of claim 9 , wherein determining whether to apply the destination-based hash function comprises determining whether the output port is part of a path of a set of equal-cost multiple paths (ECMP) to a destination of the data flow.

12 . The network device of claim 9 , wherein determining whether to apply the destination-based hash function comprises determining whether the output port is coupled to a link of a link-aggregation group (LAG) via which a destination of the data flow is reachable.

13 . The network device of claim 9 , wherein the rule is a translation function rule; and

wherein the instructions when executed by the processor cause the network device further to:

apply a the translation function rule to the packet to determine a first value and a second value to be used for forwarding of the packet;

determine a subset of bits of the hash value based on the second value; and

determine an index for the entry based on the first value and the subset of the bits of the hash value.

14 . The network device of claim 13 , wherein the instructions when executed by the processor cause the network device further to:

multiply the hash value by the second value to determine the subset of bits of the hash value; and

add the first value to a third value indicated by the subset of the bits of the hash value to determine the index for the entry.

15 . The network device of claim 13 , wherein the instructions when executed by the processor cause the network device further to determine the first value and the second value by looking up a destination address of the packet in a translation table stored at the network device.

16 . The network device of claim 9 , wherein the instructions are further to apply a Cyclic Redundancy Check (CRC) function to compress the one or more header fields into the hash value to apply the destination-based hash function.

17 . A non-transitory computer-readable storage medium storing instructions that when executed by a processor of a network device in a network having a plurality of network devices configured in a fat-tree topology cause the processor to perform a method, the method comprising:

receiving a data flow comprising a plurality of packets at an edge port of the network device;

determining whether to apply a destination-based hash function to the data flow based on a rule;

in response to determining that the destination-based hash function is to be applied to the data flow:

applying the destination-based hash function to one or more header fields of a respective packet of the data flow to determine a hash value;

determining an entry indexed based on the hash value in a data structure stored at the network device, the data structure storing respective port identifiers of a plurality of egress ports of the network device;

determining a port identifier specified in the entry indexed based on the hash value;

identifying an egress port from the plurality of egress ports based on the port identifier; and

forwarding the packet via the egress port.

18 . The non-transitory computer-readable storage medium of claim 17 , wherein the rule is a translation function rule; and

wherein the method further comprises:

applying a the translation function rule to the packet to determine a first value and a second value to be used for forwarding of the packet;

determining a subset of bits of the hash value based on the second value; and

determining an index for the entry based on the first value and the subset of the bits of the hash value.

19 . The non-transitory computer-readable storage medium of claim 18 , wherein the method further comprises multiplying the hash value by the second value to determine the subset of bits of the hash value; and

wherein determining the index for the entry comprises adding the first value to a third value indicated by the subset of the bits of the hash value.

20 . The non-transitory computer-readable storage medium of claim 17 , wherein applying the destination-based hash function comprises applying a Cyclic Redundancy Check (CRC) function to compress the one or more header fields into the hash value.