Consistent hashing for network traffic dispatching

Patent metadata

Field	Value
Publication number	US-11765025-B2
Application number	US-202117353775-A
Country	US
Kind code	B2
Filing date	Jun 21, 2021
Priority date	Jun 3, 2014
Publication date	Sep 19, 2023
Grant date	Sep 19, 2023

Abstract

A method is provided that uses a consistent hashing technique to dispatch incoming packets in a stable system prior to adding of a node. The method uses a hash table and assigns hash buckets in the table to each network node. A set of fields in each incoming packet is hashed and is used to identify the corresponding hash bucket. The packets are then dispatched to the network nodes based on the nodes' hash buckets. During an observation period, the method identifies the ongoing sessions by creating a bit vector table that is used to identify the old and new sessions during a re-dispatching period. The method uses the consistent hashing method and the probabilistic method dispatch the incoming packets such that each packet that belongs to an old session is dispatched to the same old node that has been processing the other packets of the session.

First claim

We claim:

1. A method of load balancing data message flows among a plurality of nodes during a first time period in which a particular node is being removed from the plurality of nodes, wherein before the removal, the plurality of nodes with the particular node is a first set of nodes and after the removal, the plurality of nodes without the removed particular node is a second set of nodes, the method comprising:
receiving a plurality of data message flows;
during an observation sub-period of the first time period, (i) computing, for each data message flow, a probabilistic filter value that is stored as an entry in a probabilistic filter that identifies flows received during the observation sub-period and (ii) distributing the flows among the first set of nodes including the particular node that is being removed; and
during a re-dispatching sub-period of the first time period after the particular node has been removed, distributing the data message flows among the second set of nodes (i) when the packet's flow does not match an entry in the probabilistic filter or (ii) when the packet's flow matches an entry in the probabilistic filter but the packet is part of a packet flow that started during the re-dispatching sub-period.

2. The method of claim 1 , wherein the probabilistic filter is a bloom filter.

3. The method of claim 1 further comprising during the re-dispatching sub-period, distributing the data message flows among the first set of nodes when the packet's flow matches an entry in the probabilistic filter and the packet is part of a flow that started before the re-dispatch period.

4. The method of claim 1 , wherein all the nodes in the plurality of nodes perform a common compute or service operation on received packet flows.

5. The method of claim 1 , wherein each entry in the probabilistic filter for each particular packet flow comprises a plurality of values generated by applying a plurality of hash functions to a set of attributes of the particular packet flow.

6. The method of claim 5 , wherein the set of attributes of the particular packet flow comprises the five tuple identifier of the packet flow.

7. The method of claim 1 , wherein receiving, computing and distributing are performed by a load balancer.

8. A non-transitory machine readable medium storing a program for load balancing data message flows among a plurality of nodes during a first time period in which a particular node is being removed from the plurality of nodes, wherein before the removal, the plurality of nodes with the particular node is a first set of nodes and after the removal, the plurality of nodes without the removed particular node is a second set of nodes, the program executable by a set of processing units, the program comprising sets of instructions for:
receiving a plurality of data message flows;
during an observation sub-period of the first time period, (i) computing, for each data message flow, a probabilistic filter value that is stored as an entry in a probabilistic filter that identifies flows received during the observation sub-period and (ii) distributing the flows among the first set of nodes including the particular node that is being removed; and
during a re-dispatching sub-period of the first time period after the particular node has been removed, distributing the data message flows among the second set of nodes (i) when the packet's flow does not match an entry in the probabilistic filter or (ii) when the packet's flow matches an entry in the probabilistic filter but the packet is part of a packet flow that started during the re-dispatching sub-period.

9. The non-transitory machine readable medium of claim 8 , wherein the probabilistic filter is a bloom filter.

10. The non-transitory machine readable medium of claim 8 , wherein the program further comprises a set of instructions for distributing, during the re-dispatching sub-period, the data message flows among the first set of nodes when the packet's flow matches an entry in the probabilistic filter and the packet is part of a flow that started before the re-dispatch period.

11. The non-transitory machine readable medium of claim 8 , wherein all the nodes in the plurality of nodes perform a common compute or service operation on received packet flows.

12. The non-transitory machine readable medium of claim 8 , wherein each entry in the probabilistic filter for each particular packet flow comprises a plurality of values generated by applying a plurality of hash functions to a set of attributes of the particular packet flow.

13. The non-transitory machine readable medium of claim 12 , wherein the set of attributes of the particular packet flow comprises the five tuple identifier of the packet flow.

14. The non-transitory machine readable medium of claim 8 , wherein the program is a load balancer.

Assignees

• Nicira Inc

Inventors

• Hong Xinhua
• Jain Jayant
• Parthasarathy Mohan
• Sengupta Anirban

Classifications

• H04L67/1023 Primary

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

• H04L41/0806 Primary

  for initial configuration or provisioning, e.g. plug-and-play · CPC title

• H04L45/7453

  using hashing · CPC title

• H04L67/1001

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

• H04L41/0889

  Techniques to speed-up the configuration process · CPC title