High speed packet processing using a distributed hash table

• US 20160028630A1
• Filed: 07/25/2014
• Published: 01/28/2016
• Est. Priority Date: 07/25/2014
• Status: Active Grant

• Current Assignee: Cisco Systems, Inc.
• Original Assignee: Cisco Systems, Inc.
• Inventors: Wells, Ian
• Granted Patent: US 9,729,444 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/7453 using hashing

Abstract

In one embodiment, forwarding information with respect to a particular data packet is requested from a distributed hash table (DHT) that stores key-network flow information pairs. A plurality of nodes in a network participate in the DHT, each node locally stores network flow information as dictated by a hashing function of the DHT, and the network flow information can be used to process data packets in the network. Then, forwarding information is received from the DHT indicating a destination node of the plurality of nodes to which the particular data packet should be forwarded according to the hashing function of the DHT. The destination node stores network flow information that corresponds to the particular data packet. Finally, the particular data packet is forwarded toward the destination node in order for the particular data packet to be processed using the network flow information stored at the destination node.

Claims

1. A method, comprising:

requesting forwarding information with respect to a particular data packet from a distributed hash table (DHT) that stores key-network flow information pairs, wherein a plurality of nodes in a network participate in the DHT, each node of the plurality of nodes locally stores network flow information as dictated by a hashing function of the DHT, and the network flow information can be used to process data packets in the network;

receiving forwarding information from the DHT indicating a destination node of the plurality of nodes to which the particular data packet should be forwarded according to the hashing function of the DHT, wherein the destination node stores network flow information that corresponds to the particular data packet; and

forwarding the particular data packet toward the destination node in order for the particular data packet to be processed using the network flow information stored at the destination node.

2. The method as in claim 1, further comprising:

determining at least one secondary node of the plurality of nodes at which to redundantly store the network flow information that is also stored at the destination node according to the hashing function of the DHT.

3. The method as in claim 2, further comprising:

forwarding the particular data packet toward the destination node while the destination node participates in the DHT; and

forwarding the particular data packet toward the secondary node when the destination node is removed from the DHT.

4. The method as in claim 2, wherein the secondary node redundantly stores the network flow information that is also stored at the destination node and stores additional network flow information as dictated by the hashing function of the DHT.

5. The method as in claim 1, wherein when a new node is added to the plurality of nodes that participate in the DHT, the new node is mapped to at least one key of a keyspace according to the hashing function of the DHT, such that a key mapping order of the other nodes of the plurality of nodes is preserved.

6. The method as in claim 1, wherein when a node of the plurality of nodes is removed from the DHT, at least one key of a keyspace that was previously mapped to the node is re-mapped to other nodes of the plurality of nodes according to the hashing function of the DHT, such that a key mapping order of the other nodes of plurality of nodes is preserved.

7. The method as in claim 1, wherein the hashing function of the DHT uses information relating to a given data packet to generate a key and, based on the key, identifies a node of the plurality of nodes storing network flow information that can be used for processing the given data packet.

8. The method as in claim 7, wherein the information relating to the given data packet is information in a header of the given data packet.

9. The method as in claim 1, wherein a load balancer is linked to the hashing function of the DHT, such that the forwarding of the particular data packet toward the destination node is performed by the load balancer.

10. The method as in claim 1, wherein a router is linked to the hashing function of the DHT, such that the forwarding of the particular data packet toward the destination node is performed by the router.

11. The method as in claim 1, wherein each node in the network that is capable of processing data packets participates in the DHT.

12. The method as in claim 1, wherein the hashing function of the DHT is based on consistent hashing.

13. An apparatus, comprising:

one or more network interfaces to communicate with a network;

a processor coupled to the one or more network interfaces and adapted to execute a process; and

a memory configured to store program instructions which contain the process executable by the processor, the process comprising;

requesting forwarding information with respect to a particular data packet from a distributed hash table (DHT) that stores key-network flow information pairs, wherein a plurality of nodes in a network participate in the DHT, each node of the plurality of nodes locally stores network flow information as dictated by a hashing function of the DHT, and the network flow information can be used to process data packets in the network;

receiving forwarding information from the DHT indicating a destination node of the plurality of nodes to which the particular data packet should be forwarded according to the hashing function of the DHT, wherein the destination node stores network flow information that corresponds to the particular data packet; and

forwarding the particular data packet toward the destination node in order for the particular data packet to be processed using the network flow information stored at the destination node.

14. The apparatus as in claim 13, wherein the process further comprises:

determining at least one secondary node of the plurality of nodes at which to redundantly store the network flow information that is also stored at the destination node according to the hashing function of the DHT.

15. The apparatus as in claim 14, wherein the process further comprises:

forwarding the particular data packet toward the destination node while the destination node participates in the DHT; and

forwarding the particular data packet toward the secondary node when the destination node is removed from the DHT.

16. The apparatus as in claim 14, wherein the secondary node redundantly stores the network flow information that is also stored at the destination node and stores additional network flow information as dictated by the hashing function of the DHT.

17. The apparatus as in claim 13, wherein when a new node is added to the plurality of nodes that participate in the DHT, the new node is mapped to at least one key of a keyspace according to the hashing function of the DHT, such that a key mapping order of the other nodes of the plurality of nodes is preserved.

18. The apparatus as in claim 13, wherein when a node of the plurality of nodes is removed from the DHT, at least one key of a keyspace that was previously mapped to the node is re-mapped to other nodes of the plurality of nodes according to the hashing function of the DHT, such that a key mapping order of the other nodes of plurality of nodes is preserved.

19. The apparatus as in claim 13, wherein the hashing function of the DHT uses information relating to a given data packet to generate a key and, based on the key, identifies a node of the plurality of nodes storing network flow information that can be used for processing the given data packet.

20. The apparatus as in claim 19, wherein the information relating to the given data packet is information in a header of the given data packet.

21. The apparatus as in claim 13, wherein a load balancer is linked to the hashing function of the DHT, such that the forwarding of the particular data packet toward the destination node is performed by the load balancer.

22. The apparatus as in claim 13, wherein a router is linked to the hashing function of the DHT, such that the forwarding of the particular data packet toward the destination node is performed by the router.

23. The apparatus as in claim 13, wherein each node in the network that is capable of processing data packets participates in the DHT.

24. The apparatus as in claim 13, wherein the hashing function of the DHT is based on consistent hashing.

25. A tangible non-transitory computer readable medium storing program instructions that cause a computer to execute a process, the process comprising:

requesting forwarding information with respect to a particular data packet from a distributed hash table (DHT) that stores key-network flow information pairs, wherein a plurality of nodes in a network participate in the DHT, each node of the plurality of nodes locally stores network flow information as dictated by a hashing function of the DHT, and the network flow information can be used to process data packets in the network;

receiving forwarding information from the DHT indicating a destination node of the plurality of nodes to which the particular data packet should be forwarded according to the hashing function of the DHT, wherein the destination node stores network flow information that corresponds to the particular data packet; and

forwarding the particular data packet toward the destination node in order for the particular data packet to be processed using the network flow information stored at the destination node.