Hash-Based Load Balancing in Large Multi-Hop Networks with Randomized Seed Selection
Methods and apparatus for improving hash-based load balancing with randomized seed selection are disclosed. The methods and apparatus described herein increase the number of unique fields in a hash key before the hash key is presented to a hash function. The methods include selecting one or more seed values based the output of a first arbitrary function having a first set of packet fields as input. The one or more seed values are combined with a second set of packet fields. A second arbitrary function generates a hash value based on the one or more seed values and the second set of packet fields. The hash value is applied as input to a hash function in a member selection module. The method enables per flow randomization attributes based on per packet attributes to perform aggregate member selection while remaining deterministic from a root-node or network perspective.
1 . A method for improving hash performance in a network device, comprising:
receiving, at the network device, a data packet having a plurality of fields;
selecting a first set of fields from the data packet;
generating a seed index based on the first set of fields using a first arbitrary function;
selecting a seed value from a set of seed values based on the seed index;
generating a hash input value based on the seed value and a second set of fields from the data packet using a second arbitrary function; and
generating an output based on the hash input value using a third arbitrary function.
2 . The method of claim 1 , wherein the output is used to select a path in a plurality of paths for transmitting the data packet.
3 . The method of claim 1 , wherein the first arbitrary function is a cyclic redundancy check.
4 . The method of claim 1 , wherein the first arbitrary function is a mapping table.
5 . The method of claim 1 , wherein the first arbitrary function is different than the second arbitrary function.
6 . The method of claim 1 , wherein the second arbitrary function is an XOR hash.
7 . The method of claim 1 , wherein the third arbitrary function is a hash function.
8 . The method of claim 1 , wherein the third arbitrary function is a modulo function.
9 . The method of claim 1 , further comprising:
prior to receiving a data packet, storing the set of seed values in a memory in the network device.
10 . The method of claim 1 , further comprising:
prior to receiving the data packet, generating the set of seed values.
11 . A computer program product comprising a non-transitory computer useable medium having computer program logic recorded thereon, the computer control logic when executed by a processor enabling the processor to process packet data according to a method, the method comprising:
selecting a first set of fields from a received data packet;
generating a seed index based on the first set of fields using a first arbitrary function;
selecting a seed value from a set of seed values based on the seed index;
generating a hash input value based on the seed value and a second set of fields from the data packet using a second arbitrary function;
generating an output based on the hash input value using a third arbitrary function; and
selecting a path in a plurality of paths for transmitting the data packet.
12 . The computer program product of claim 11 , wherein the first arbitrary function is a cyclic redundancy check.
13 . The computer program product of claim 11 , wherein the first arbitrary function is a mapping table.
14 . The computer program product of claim 11 , wherein the first arbitrary function is different than the second arbitrary function.
15 . The computer program product of claim 11 , wherein the second arbitrary function is an XOR hash.
16 . The computer program product of claim 11 , wherein the third arbitrary function is a hash function.
17 . The computer program product of claim 11 , wherein the third arbitrary function is a modulo function.
18 . The computer program product of claim 11 , further comprising:
prior to receiving a data packet, storing the set of seed values in a memory in the network device.
19 . The computer program product of claim 11 , further comprising:
prior to receiving the data packet, generating the set of seed values