SYSTEMS AND METHODS FOR DETERMINING A GOOD RSS KEY

• US 20110153861A1
• Filed: 12/23/2009
• Published: 06/23/2011
• Est. Priority Date: 12/23/2009
• Status: Active Grant

• Current Assignee: Citrix Systems, Inc. (Cloud Software Group)
• Original Assignee: Citrix Systems, Inc. (Cloud Software Group)
• Inventors: Chauhan, Abhishek
• Granted Patent: US 8,082,359 B2
• Time in Patent Office: Days
• US Class Current: 709/232
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures
• CPC Class Codes: H04L 69/166 IP fragmentation; TCP segmentation
• CPC Class Codes: H04L 69/18 Multiprotocol handlers, e.g. single devices capable of handling multiple protocols
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

The present application is directed towards systems and methods for ensuring equal distribution of packet flows among a plurality of cores in a multi-core system by identifying a rank of a matrix created from a hash key. If the rank of the matrix is equal to or greater than a divisor of a modulo operation applied to the results of the hash function, then the hash key may be used to ensure equal distribution of packet flows.

Claims

1. A method for identifying a random key to use in a distribution of packet flows among a plurality of cores in a multi-core system, the method comprising:

receiving, by a flow distributor executing on a multi-core system, a first random number key for a hash function;

creating, by the flow distributor, a first n-rowed matrix from the first random number key, a first row of the first matrix comprising m-bits of the first random number key starting from a first position, and each successive row comprising m-bits of the first random number key starting from a position shifted from a previous position by a predetermined value;

identifying, by the flow distributor, a rank of the first matrix;

determining, by the flow distributor, that the rank of the first matrix is less than the number n of rows of the first matrix; and

requesting, by the flow distributor and responsive to the determination, a second random number key for the hash function.

2. The method of claim 1, further comprising:

receiving, by the flow distributor and responsive to the request, the second random number key for the hash function;

creating, by the flow distributor, a second n-rowed matrix from the second random number key, wherein a first row of the second matrix comprises m-bits of the second random number key starting from a first position, and each successive row comprises m-bits of the second random number key starting from a position shifted from the previous position by a predetermined value;

identifying, by the flow distributor, a rank of the second matrix;

determining, by the flow distributor, that the rank of the second matrix is equal to the number n of rows of the second matrix; and

distributing, by the flow distributor, one or more packet flows among a plurality of cores of the multi-core system, responsive to a Toeplitz hash with inputs comprising the second random number key and one or more header fields from the one or more packet flows.

3. The method of claim 2, further comprising:

creating, by the flow distributor, a third j-rowed matrix from the second random number key, wherein a first row of the third matrix comprises k-bits of the second random number key starting from a second position, and each successive row comprises k-bits of the second random number key starting from a position shifted from the previous position by a predetermined value;

identifying, by the flow distributor, a rank of the third matrix; and

determining, by the flow distributor, that the rank of the third matrix is equal to the number j of rows of the third matrix.

4. The method of claim 2, wherein distributing the one or more packet flows among the plurality of cores of the multi-core system further comprises identifying a destination core for a packet flow based on a distribution table, and the entry of the destination table is determined responsive to a modulus of the Toeplitz hash.

5. The method of claim 1, wherein identifying a rank of the first matrix comprises converting, by the flow distributor, the first matrix to echelon form.

6. The method of claim 1, wherein identifying a rank of the first matrix comprises performing, by the flow distributor, a forward elimination algorithm on the matrix.

7. The method of claim 1, wherein identifying a rank of the first matrix comprises identifying a first pivot row of the matrix by:

identifying, by the flow distributor, a first pivot row of the matrix by locating the first row of the matrix to have a nonzero element, scanning the elements of each column downwards starting from a most significant bit column and proceeding to a least significant bit column;

flipping the first pivot row of the matrix with the first row of the matrix; and

for each remaining row of the matrix with a nonzero element in a pivot column, replacing the row with the result of an exclusive-or (XOR) of the first pivot row and said row.

8. The method of claim 7, further comprising identifying an additional pivot row by locating a first row of the remaining rows of the matrix to have a nonzero element, flipping the located row with a row corresponding to the order in which the pivot row was located, and for each remaining row of the matrix, replacing the row with the result of an XOR of the additional pivot row and said row.

9. The method of claim 7, wherein identifying a rank of the first matrix comprises determining the number of identified pivot rows of the matrix.

10. The method of claim 1, wherein the value of n is geometrically proportional to the number of entries in an indirection table.

11. A system for identifying a random key to use in a distribution of packet flows among a plurality of cores in a multi-core system, the system comprising:

a flow distributor executing on a multi-core system, the flow distributor comprising;

means for receiving a first random number key for a hash function;

means for creating a first n-rowed matrix from the first random number key, wherein a first row of the first matrix comprises m-bits of the first random number key starting from a first position, and each successive row comprises m-bits of the first random number key starting from a position shifted from a previous position by a predetermined value;

means for identifying a rank of the first matrix;

means for determining that the rank of the first matrix is less than the number n of rows of the first matrix; and

means for requesting, responsive to the determination, a second random number key for the hash function.

12. The system of claim 11, wherein the flow distributor further comprises:

means for receiving, responsive to the request, the second random number key for the hash function;

means for creating a second n-rowed matrix from the second random number key, wherein a first row of the second matrix comprises m-bits of the second random number key starting from a first position, and each successive row comprises m-bits of the second random number key starting from a position shifted from the previous position by a predetermined value;

means for identifying a rank of the second matrix;

means for determining that the rank of the second matrix is equal to the number n of rows of the second matrix; and

means for distributing one or more packet flows among a plurality of cores of the multi-core system, responsive to a Toeplitz hash with inputs comprising the second random number key and one or more header fields from the one or more packet flows.

13. The system of claim 12, wherein the flow distributor further comprises:

means for creating a third j-rowed matrix from the second random number key, wherein a first row of the third matrix comprises k-bits of the second random number key starting from a second position, and each successive row comprises k-bits of the second random number key starting from a position shifted from the previous position by a predetermined value;

means for identifying a rank of the third matrix; and

means for determining that the rank of the third matrix is equal to the number j of rows of the third matrix.

14. The system of claim 12, wherein the means for distributing the one or more packet flows among the plurality of cores of the multi-core system comprises means for identifying a destination core for a packet flow based on a distribution table, and the entry of the destination table is determined responsive to a modulus of the Toeplitz hash.

15. The system of claim 11, wherein the means for identifying a rank of the first matrix comprises means for converting the first matrix to echelon form.

16. The system of claim 11, wherein the means for identifying a rank of the first matrix comprises means for performing a forward elimination algorithm on the matrix.

17. The system of claim 11, wherein the means for identifying a rank of the first matrix comprises means for identifying a first pivot row of the matrix by:

identifying a first pivot row of the matrix by locating the first row of the matrix to have a nonzero element, scanning the elements of each column downwards starting from a most significant bit column and proceeding to a least significant bit column;

flipping the first pivot row of the matrix with the first row of the matrix; and

for each remaining row of the matrix with a nonzero element in a pivot column, replacing the row with the result of an exclusive-or (XOR) of the first pivot row and said row.

18. The system of claim 17, wherein the means for identifying a rank of the first matrix further comprises means for identifying an additional pivot row by locating a first row of the remaining rows of the matrix to have a nonzero element, flipping the located row with a row corresponding to the order in which the pivot row was located, and for each remaining row of the matrix, replacing the row with the result of an XOR of the additional pivot row and said row.

19. The system of claim 17, wherein the means for identifying a rank of the first matrix comprises means for determining the number of identified pivot rows of the matrix.

20. The system of claim 11, wherein the flow distributor further comprises an indirection table, and the value of n is geometrically proportional to the number of entries in the indirection table.