Resilient hashing with multiple hashes

Patent metadata

Field	Value
Publication number	US-10892991-B2
Application number	US-201916294851-A
Country	US
Kind code	B2
Filing date	Mar 6, 2019
Priority date	Mar 6, 2019
Publication date	Jan 12, 2021
Grant date	Jan 12, 2021

Abstract

Techniques for implementing resilient hashing with multiple hashes are provided. In one set of embodiments, a network device can maintain a first hash table comprising mappings between a first set of hash indices and a set of bit values. The network device can also maintain a second hash table comprising mappings between a second set of hash indices and active next-hop destinations. Upon receiving a network packet, the network device can compute a first hash and can match the first hash value to a first mapping in the first hash table based on the first mapping's hash index. When the first mapping's bit value indicates that the first mapping's hash index corresponds to an active next-hop destination, the network device can further match the first hash value to a second mapping in the second hash table and send the network packet to the second mapping's active next-hop destination.

First claim

What is claimed is:

1. A method of packet forwarding comprising:
maintaining, by a network device, 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;

maintaining, by the network device, 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;
receiving, by the network device, a network packet;
computing, by the network device, a first hash value using a portion of the network packet and a first hash function;
matching, by the network device, 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:
matching, by the network device, the first hash value to a second mapping in the second hash table based on the second mapping's hash index; and

sending, by the network device, the network packet to the second mapping's active next-hop destination.

2. The method of claim 1 further comprising, when the first mapping's bit value indicates that the first mapping's hash index corresponds to an inactive next-hop destination:
computing a second hash value using the portion of the network packet and a second hash function that is different from the first hash function;
matching the second hash value to a third mapping in the second hash table based on the third mapping's hash index; and
sending the network packet to the third mapping's active next-hop destination.

3. The method of claim 1 further comprising:
maintaining a third hash table comprising mappings that are identical to the first hash table; and
when the first mapping's bit value indicates that the first mapping's hash index corresponds to an inactive next-hop destination:
computing a second hash value using the portion of the network packet and a second hash function that is different from the first hash function;
matching the second hash value to a third mapping in the third hash table based on the third mapping's hash index; and
when the third mapping's bit value indicates that the third mapping's hash index corresponds to an active next-hop destination:
matching the second hash value to a fourth mapping in the second hash table based on the fourth mapping's hash index; and
sending the network packet to the fourth mapping's active next-hop destination.

4. The method of claim 3 further comprising, when the third mapping's bit value indicates that the third mapping's hash index corresponds to an inactive next-hop destination:
computing a third hash value using the portion of the network packet and a third hash function that is different from the first hash function and the second hash function;
matching the third hash value to a fifth mapping in the second hash table based on the fifth mapping's hash index; and
sending the network packet to the fifth mapping's active next-hop destination.

5. The method of claim 1 wherein a size of the first hash table is equal to a maximum group size for the group of next-hop destinations.

6. The method of claim 5 wherein the maximum group size is defined in a user-configurable file maintained on the network device.

7. The method of claim 6 wherein the user-configurable file further defines:
which next-hop destinations in the group of next-hop destinations are active; and
which next-hop destinations in the group of next-hop destinations are inactive.

8. The method of claim 5 wherein computing the first hash value comprises:
extracting a 5-tuple from the network packet including the network packet's source Internet Protocol (IP) address, source port, destination IP address, destination port, and protocol;
applying the 5-tuple to the first hash function to generate an intermediate hash value; and
computing the intermediate hash value modulo the maximum group size to generate the first hash value.

9. The method of claim 5 wherein a size of the second hash table is equal to the maximum group size multiplied by a replication factor.

10. The method of claim 9 wherein computing the second hash value comprises:
extracting a 5-tuple from the network packet including the network packet's source Internet Protocol (IP) address, source port, destination IP address, destination port, and protocol;
applying the 5-tuple to the second hash function to generate an intermediate hash value; and
computing the intermediate hash value modulo (the maximum group size multiplied by the replication factor) to generate the second hash value.

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

12. The network device of claim 11 wherein when the first mapping's bit value indicates that the first mapping's hash index corresponds to an inactive next-hop destination, the processor is further configured to:
compute a second hash value using the portion of the network packet and a second hash function that is different from the first hash function;
match the second hash value to a third mapping in the second hash table based on the third mapping's hash index; and
send the network packet to the third mapping's active next-hop destination.

13. The network device of claim 11 wherein the processor comprises an application-specific integrated circuit (ASIC).

14. The network device of claim 11 wherein the processor comprises a general purpose central processing unit (CPU).

15. The network device of claim 13 wherein the first hash table is implemented as a bit vector stored on the ASIC.

16. The network device of claim 13 wherein the second hash table is implemented as a direct index table stored on the ASIC.

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

Assignees

• Arista Networks Inc

Inventors

• Capper Simon
• Krishnamurthy Prashanth
• Kraiser Tula

Classifications

• H04L67/63

  Routing a service request depending on the request content or context · CPC title

• H04L61/5007

  Internet protocol [IP] addresses · CPC title

• H04L67/1001

  for accessing one among a plurality of replicated servers · CPC title

• H04L67/1023 Primary

  based on a hash applied to IP addresses or costs · CPC title

• G06F8/71

  Version control (security arrangements therefor G06F21/57); Configuration management · CPC title