Resilient Hashing With Multiple Hashes

A network device comprising:

• a processor configured to:
• maintain a first hash table comprising mappings between a first set of hash indices and a set of bit values, wherein for each mapping in the first hash table:
• the mapping's hash index corresponds to one of a group of next-hop destinations to which network packets received by the network device may be transmitted, and
• the mapping's bit value indicates whether the mapping's hash index corresponds to an active or inactive next-hop destination;
• maintain a second hash table comprising mappings between a second set of hash indices and active next-hop destinations in the group of next-hop destinations;
• receive a network packet;
• compute a first hash value using a portion of the network packet and a first hash function;
• match the first hash value to a first mapping in the first hash table based on the first mapping's hash index;
• and
• when the first mapping's bit value indicates that the first mapping's hash index corresponds to an active next-hop destination:
• match the first hash value to a second mapping in the second hash table based on the second mapping's hash index;
• and
• send the network packet to the second mapping's active next-hop destination.

A non-transitory computer readable storage medium having stored thereon program code executable by a network device, the program code comprising:

• code that causes the network device to maintain a first hash table comprising mappings between a first set of hash indices and a set of bit values, wherein for each mapping in the first hash table:
• the mapping's hash index corresponds to one of a group of next-hop destinations to which network packets received by the network device may be transmitted, and
• the mapping's bit value indicates whether the mapping's hash index corresponds to an active or inactive next-hop destination;
• code that causes the network device to maintain a second hash table comprising mappings between a second set of hash indices and active next-hop destinations in the group of next-hop destinations;
• code that causes the network device to receive a network packet;
• code that causes the network device to compute a first hash value using a portion of the network packet and a first hash function;
• code that causes the network device to match the first hash value to a first mapping in the first hash table based on the first mapping's hash index;
• and
• when the first mapping's bit value indicates that the first mapping's hash index corresponds to an active next-hop destination:
• code that causes the network device to match the first hash value to a second mapping in the second hash table based on the second mapping's hash index;
• and
• code that causes the network device to send the network packet to the second mapping's active next-hop destination.