System and method for efectuating packet distribution among servers in a network

• US 9,485,183 B2
• Filed: 04/25/2014
• Issued: 11/01/2016
• Est. Priority Date: 04/25/2014
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Anand, Prashant, Bisht, Ashutosh, Arisoylu, Mustafa, Anand, Ashish
• Primary Examiner(s): Sinkantarakorn, Pao
• Assistant Examiner(s): PHILLIPS, MICHAEL K
• Application Number:
  US14/262,406
• Publication Number:
  US 20150312155A1
• Time in Patent Office: 921 Days
• US Class Current: 1/1
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 47/18 End to end
• CPC Class Codes: H04L 47/2483 involving identification of individual flows

Abstract

A packet distribution scheme for forwarding incoming packets to servers in a network. Depending on a hash value of the incoming flow'"'"'s identification parameters, a hash flow table or database is queried to determine the server to which the packet is to be forwarded. If multiple flows have the same hash index and are associated with different servers, a secondary flow table or database is queried for determining the server. In an example implementation, only the secondary flow table is configured to store fully qualified flow identification parameters whereas the hash flow table is operative to store reduced or compressed state information.

Claims

1. A packet distribution method operating at a packet distributor for forwarding communication flows to one or more servers, the method comprising:

receiving a packet of a communication flow;

hashing one or more flow identification parameters of the packet to obtain a hash index;

storing in a first database portion a plurality of hash indices based on hashing one or more flow identification parameters associated with a plurality of incoming communication flows being received, each hash index associated with a plurality of data fields;

if the communication flow is a new flow, processing the packet according to a new flow process at least based on values of one or more data fields of the plurality of data fields provided for the hash index in the first database portion;

if the communication flow is an existing flow, processing the packet according to an existing flow process at least based on the values of the one or more data fields provided for the hash index in the first database portion; and

if the received packet is an end-of-flow packet, processing the packet according to an end-of-flow process at least based on the values of the one or more data fields provided for the hash index in the first database portion,

wherein the plurality of data fields comprise (i) a single bit field (Flow-bit) configured to indicate whether there exists at least one communication flow having the flow identification parameters that hash to a specific hash index;

(ii) a server data field configured to identify a server of the one or more servers that is assigned to serve the at least one communication flow having the flow identification parameters that hash to the specific hash index; and

(iii) a counter data field that is incremented when flow identification parameters of two communication flows having a same server assignment hash to a same hash index resulting in a hash collision scenario, and further wherein a single hash index entry is provided in the first database portion operative for forwarding packets of the two communication flows in the hash collision scenario.

2. The packet distribution method as recited in claim 1, wherein the one or more flow identification parameters comprise a source Internet Protocol (IP) address, a destination IP address, a source port address, a destination port address, and a protocol identifier.

3. The packet distribution method as recited in claim 2, wherein the protocol identifier is one of a Transmission Control Protocol (TCP) and Stream Control Transmission Protocol (SCTP).

4. The packet distribution method as recited in claim 3, wherein the new flow is determined by examining a new flow identifier in the received packet.

5. The packet distribution method as recited in claim 3, wherein the received packet is determined as the end-of-flow packet by examining an end flow identifier in the received packet.

6. The packet distribution method as recited in claim 1, wherein the plurality of data fields of the first database portion further comprises another single bit field (Clash-bit) that is set when flow identification parameters of two communication flows assigned to different servers hash to an index resulting in another hash collision scenario.

7. The packet distribution method as recited in claim 6, wherein the existing flow process comprises, upon determining that the communication flow is an existing flow:

determining if the Clash-bit associated with the hash index of the packet is set in the first database portion; and

responsive to the determining that the Clash-bit is set, querying a second database portion to determine a set of fully qualified flow identification parameters for the communication flow and a server associated therewith for forwarding the packet.

8. The packet distribution method as recited in claim 6, wherein the new flow process comprises, upon determining that the communication flow is a new flow:

associating and identifying a particular server with the communication flow;

upon determining that the Flow-bit associated with the hash index is not set in the first database portion, performing;

setting the Flow-bit of the hash index;

setting the counter data field of the hash index to 1;

setting the server data field of the hash index to identify the particular server as being associated with the communication flow; and

forwarding the received packet to the particular server;

upon determining that the Flow-bit associated with the hash index is set in the first database portion and if the server data field of the hash index identifies a server that is different than the particular server, performing;

setting the Clash-bit of the hash index;

adding the communication flow to a second database portion at the hash index; and

forwarding the received packet to the particular server; and

upon determining that the Flow-bit associated with the hash index is set in the first database portion and if the server data field of the hash index already identifies the particular server, performing;

incrementing the counter data field by 1; and

forwarding the received packet to the particular server.

9. The packet distribution method as recited in claim 6, wherein the end-of-flow process comprises, upon determining that the received packet includes an end flow identifier:

upon determining that the Flow-bit associated with the hash index is not set in the first database portion, dropping the received packet;

upon determining that the Flow-bit associated with the hash index is set in the first database portion and determining that the Clash-bit associated with the hash index is not set, performing;

forwarding the received packet to the server identified in the server data field of the hash index;

if the counter data field of the hash index is determined to be greater than 1, reducing the counter data field by 1; and

if the counter data field of the hash index is determined to be not greater than 1, clearing the Flow-bit of the hash index; and

upon determining that the Flow-bit associated with the hash index is set in the first database portion and determining that the Clash-bit associated with the hash index is also set, performing;

querying a second database portion to determine if the second database portion contains the flow identification parameters of the communication flow, and if so, forwarding the received packet to a server identified in the second database portion as being associated with the communication flow and deleting the communication flow'"'"'s identification parameters from the second database portion; and

if it is determined there are no additional flows having the same hash index in the second database portion, clearing the Clash-bit of the hash index in the first database portion; and

if querying the second database portion yields that the communication flow does not exist in the second database portion, forwarding the received packet to the server identified in the server data field of the hash index in the first database portion; and

if the counter data field of the hash index is determined to be greater than 1, reducing the counter data field by 1; and

if the counter data field of the hash index is determined to be not greater than 1, moving one flow entry from the second database portion to the first database portion.

10. A packet distributor node configured to forward communication flows to one or more servers, the packet distributor node comprising:

one or more processors coupled to a persistent memory;

a hash flow table (HFT) module forming a portion of the persistent memory, the HFT module configured to store a plurality of hash indices based on hashing one or more flow identification parameters associated with a plurality of incoming communication flows being received at the packet distributor node, each hash index associated with a plurality of data fields;

a supplementary flow table (SFT) module forming a portion of the persistent memory and configured to store fully qualified flow identification parameters with respect to communication flows that are assigned to different servers and have the same hash indices;

a server association module forming a portion of the persistent memory and configured to associate a server to an incoming communication flow received at the packet distributor node;

a flow identification module forming a portion of the persistent memory and configured to identify whether an incoming packet is for an existing communication flow, a new communication flow or an end-of-flow packet to indicate termination of the existing communication flow; and

a packet processing module configured to process an incoming packet of a communication flow at least based on values of one or more data fields of the plurality of data fields associated with a hash index of the incoming packet'"'"'s flow identification parameters,

wherein the plurality of data fields comprise (i) a single bit field (Flow-bit) configured to indicate whether there exists at least one communication flow having the flow identification parameters that hash to a specific hash index;

(ii) a server data field configured to identify a server of the one or more servers that is assigned to serve the at least one communication flow having the flow identification parameters that hash to specific the hash index; and

(iii) a counter data field that is incremented when flow identification parameters of two communication flows having a same server assignment hash to a same hash index resulting in a hash collision scenario, and further wherein a single hash index entry is provided in the first hash flow table operative for forwarding packets of the two communication flows in the hash collision scenario.

11. The packet distributor node as recited in claim 10, wherein the one or more flow identification parameters comprise a source Internet Protocol (IP) address, a destination IP address, a source port address, a destination port address, and a protocol identifier.

12. The packet distributor node as recited in claim 11, wherein the protocol identifier is one of a Transmission Control Protocol (TCP) and Stream Control Transmission Protocol (SCTP).

13. The packet distributor node as recited in claim 12, wherein the flow identification module is adapted to determine a new communication flow by examining a new flow identifier in the incoming packet.

14. The packet distributor node as recited in claim 12, wherein the flow identification module is adapted to determine an end-of-flow packet by examining an end flow identifier in the incoming packet.

15. The packet distributor node as recited in claim 10, wherein the plurality of data fields of the HFT module further comprises another single bit field (Clash-bit) that is set when flow identification parameters of two communication flows assigned to different servers hash to an index resulting in another hash collision scenario, the Clash-bit operating to trigger querying the SFT when the Clash-bit is set.

16. A non-transitory computer-readable medium containing instructions stored thereon which, when executed by one or more processors of a packet distributor node, facilitate forwarding of communication flows to one or more servers, the non-transitory computer-readable medium comprising:

a code portion for hashing one or more flow identification parameters of an incoming packet of a communication flow to obtain a hash index;

a code portion for storing in a first database portion a plurality of hash indices based on hashing one or more flow identification parameters associated with a plurality of incoming communication flows being received, each hash index associated with a plurality of data fields;

a code portion, operative upon determining that the communication flow is a new flow, for processing the incoming packet according to a new flow process at least based on values of one or more data fields of the plurality of data fields provided for the hash index in a first database portion

a code portion, operative upon determining that the communication flow is an existing flow, for processing the incoming packet according to an existing flow process at least based on the values of the one or more data fields provided for the hash index in the first database portion; and

a code portion, operative upon determining that the incoming packet is an end-of-flow packet, for processing the packet according to an end-of-flow process at least based on the values of the one or more data fields provided for the hash index in the first database portion,

wherein the plurality of data fields comprise (i) a single bit field (Flow-bit) configured to indicate whether there exists at least one communication flow having the flow identification parameters that hash to a specific hash index;

(ii) a server data field configured to identify a server of the one or more servers that is assigned to serve the at least one communication flow having the flow identification parameters that hash to the specific hash index; and

(iii) a counter data field that is incremented when flow identification parameters of two communication flows having a same server assignment hash to a same hash index resulting in a hash collision scenario, and further wherein a single hash index entry is provided in the first database portion operative for forwarding packets of the two communication flows in the hash collision scenario.

17. The non-transitory computer-readable medium as recited in claim 16, wherein the one or more flow identification parameters comprise a source Internet Protocol (IP) address, a destination IP address, a source port address, a destination port address, and a protocol identifier.

18. The non-transitory computer-readable medium as recited in claim 17, wherein the protocol identifier is one of a Transmission Control Protocol (TCP) and Stream Control Transmission Protocol (SCTP).

19. The non-transitory computer-readable medium as recited in claim 18, further comprising a code portion configured to determine a new flow by examining a new flow identifier in the incoming packet.

20. The non-transitory computer-readable medium as recited in claim 18, further comprising a code portion configured to determine an end-of-flow packet by examining an end flow identifier in the incoming packet.

21. The non-transitory computer-readable medium as recited in claim 16, wherein the plurality of data fields of the first database portion further comprises another single bit field (Clash-bit) that is set when flow identification parameters of two communication flows assigned to different servers hash to an index resulting in another hash collision scenario, the Clash-bit operating to trigger querying a second database portion when the Clash-bit is set.