Method, apparatus and networking equipment for performing flow hashing using quasi cryptographic hash functions

• US 8,244,909 B1
• Filed: 06/18/2009
• Issued: 08/14/2012
• Est. Priority Date: 06/18/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Hanson, Peter, Anderson, Glen
• Primary Examiner(s): Etienne, Ario
• Assistant Examiner(s): Lai, Michael C
• Application Number:
  US12/487,383
• Time in Patent Office: 1,153 Days
• Field of Search: 709/238, 370/389, 370/235, 711/216, 380/46, 380/47, 380/268, 713/168, 713/176, 714/762, 708/252
• US Class Current: 709/238
• CPC Class Codes: H04L 45/12 Shortest path evaluation

Abstract

A method, apparatus and networking equipment for performing flow hashing is provided. The method may include obtaining, at a network node, a key for a packet; forming, at the network node, a first pseudorandom number as a function of a first polynomial generator and the key; forming, at the network node, a second pseudorandom number as a function of a second polynomial generator and the key; combining, at the network node, the first and second pseudorandom numbers to form a third pseudorandom number; and selecting, at the network node, as a function of the third pseudorandom number, a path to which to forward the packet.

Claims

1. A method comprising:

obtaining, at a network node, a key for a packet;

forming, at the network node, a first pseudorandom number as a function of a first polynomial generator and the key;

forming, at the network node, a second pseudorandom number as a function of a second polynomial generator and the key;

combining, at the network node, the first and the second pseudorandom numbers to form a third pseudorandom number, wherein combining the first and the second pseudorandom numbers to form the third pseudorandom number comprises invoking at least one polynomial operation where the first and the second pseudorandom numbers are operands for the at least one polynomial operation; and

selecting, at the network node, as a function of the third pseudorandom number, a path to which to forward the packet, wherein;

the third pseudorandom number comprises a most significant byte and a least significant byte; and

selecting the path as a function of the third pseudorandom number comprises selecting the path based on the most significant byte of the third pseudorandom number.

2. The method of claim 1, wherein the key comprises at least one bit from a header of the packet.

3. The method of claim 2, wherein the at least one bit comprises at least one bit selected from any of a source internet-protocol address, destination internet-protocol addresses, source transmission-control-protocol-port number, destination transmission-control-protocol-port number, and network protocol of the header of the packet.

4. The method of claim 1, wherein forming a first pseudorandom number comprises:

forming, at the network node, a first hash value by applying the key to a first hash function, and wherein forming a second pseudorandom number comprises;

forming, at the network node, a second hash value by applying the key to a second hash function.

5. The method of claim 4, wherein the first and second hash functions are first and second cyclic redundancy checks.

6. The method of claim 4, wherein the first and second hash functions have different periods.

7. The method of claim 1, wherein combining the first and second pseudorandom numbers comprises:

using any of polynomial addition, polynomial multiplication, polynomial subtraction, modulo and finite field operations to combine the first and second pseudorandom numbers.

8. A method comprising:

obtaining, at a network node, a key for a packet;

forming, at the network node, a first pseudorandom number as a function of a first polynomial generator and the key;

forming, at the network node, a second pseudorandom number as a function of a second polynomial generator and the key;

forming, at the network node, a rotation code equal to one of a number of rotations of the first polynomial generator;

combining, at the network node, the first pseudorandom number, the second pseudorandom number and the rotation code to form a third pseudorandom number, wherein combining the first pseudorandom number, the second pseudorandom number, and the rotation code to form the third pseudorandom number comprises invoking at least one polynomial operation where the first pseudorandom number, the second pseudorandom number, and the rotation code are operands for the at least one polynomial operation; and

selecting, at the network node, as a function of the third pseudorandom number, a path to which to forward the packet, wherein;

the third pseudorandom number comprises a most significant byte and a least significant byte; and

selecting the path as a function of the third pseudorandom number comprises selecting the path based on the most significant byte of the third pseudorandom number.

9. The method of claim 8, wherein both of the first and second polynomial generators are primitive and have the same period.

10. The method of claim 9, wherein forming a rotation code comprises:

forming, at the network node, a fourth pseudorandom number as a function of a fourth polynomial generator and the key.

11. The method of claim 10, wherein the fourth polynomial generator is relatively prime to the first and second polynomial generators, and wherein forming a rotation code further comprises:

converting the fourth pseudorandom number to a pseudorandom rotation.

12. A method comprising:

obtaining, at a network node, a key for a packet;

forming, at the network node, a first pseudorandom number as a function of a first polynomial generator and the key;

forming, at the network node, a rotation code equal to one of a number of rotations of the first polynomial generator;

combining, at the network node, the first pseudorandom number and the rotation code to form a second pseudorandom number, wherein combining the first pseudorandom number and the rotation code to form the second pseudorandom number comprises invoking at least one polynomial operation where the first pseudorandom number and the rotation code are operands for the at least one polynomial operation; and

selecting, at the network node, as a function of the second pseudorandom number, a path to which to forward the packet, wherein;

the second pseudorandom number comprises a most significant byte and a least significant byte; and

selecting the path as a function of the second pseudorandom number comprises selecting the path based on the most significant byte of the second pseudorandom number.

13. The method of claim 12, wherein forming a rotation code comprises:

forming, at the network node, a third pseudorandom number as a function of a second polynomial generator and the key.

14. The method of claim 13, wherein the second polynomial generator is relatively prime to the first polynomial generator, and wherein forming a rotation code further comprises:

converting the second pseudorandom number to a pseudorandom rotation.

15. The method of claim 14, wherein the first polynomial generator is primitive and has a first period, and wherein second polynomial generator is primitive and has a second period.

16. An apparatus comprising:

memory operable to store executable instructions; and

a processor operable to obtain the executable instructions from memory and execute the executable instructions to;

obtain a key for a packet;

form a first pseudorandom number as a function of a first polynomial generator and the key;

form a second pseudorandom number as a function of a second polynomial generator and the key;

combine the first and the second pseudorandom numbers to form a third pseudorandom number, wherein the processor combines the first and the second pseudorandom numbers to form the third pseudorandom number by invoking at least one polynomial operation where the first and the second pseudorandom numbers are operands for the at least one polynomial operation; and

select, as a function of the third pseudorandom number, a path to which to forward the packet, wherein;

the third pseudorandom number comprises a most significant byte and a least significant byte; and

selection of the path as a function of the third pseudorandom number comprises selection of the path based on the most significant byte of the third pseudorandom number.

17. The apparatus of claim 16, wherein the key comprises at least one bit from a header of the packet.

18. The apparatus of claim 17, wherein the at least one bit comprises at least one bit selected from any of a source internet-protocol address, destination internet-protocol addresses, source transmission-control-protocol-port number, destination transmission-control-protocol-port number, and network protocol of the header of the packet.

19. The apparatus of claim 16, wherein the executable instructions to form a first pseudorandom number comprise executable instructions to:

form a first hash value by applying the key to a first hash function, and wherein the executable instructions to form a second pseudorandom number comprises executable instructions to;

form a second hash value by applying the key to a second hash function.

20. The apparatus of claim 19, wherein the first and second hash functions are first and second cyclic redundancy checks.

21. The apparatus of claim 19, wherein the first and second hash functions have different periods.

22. The apparatus of claim 16, wherein the executable instructions to combine the first and second pseudorandom numbers comprises executable instruction to:

combine the first and second pseudorandom numbers using any of polynomial addition, polynomial multiplication, polynomial subtraction, modulo and finite field operations.

23. A system comprising:

a parsing circuit configured to obtain a key for a packet; and

a memory in communication with the parsing circuit and a processor, the memory comprising logic that, when executed by the processor, causes the processor to;

form a first pseudorandom number as a function of a first polynomial generator and the key;

form a second pseudorandom number as a function of a second polynomial generator and the key;

form a rotation code equal to one of a number of rotations of the first polynomial generator;

combine the first pseudorandom number, the second pseudorandom number and the rotation code to form a third pseudorandom number, wherein the processor combines the first pseudorandom number, the second pseudorandom number, and the rotation code using by invoking at least one polynomial operation, where the first pseudorandom number, the second pseudorandom number, and the rotation code are operands for the at least one polynomial operation; and

select, as a function of the third pseudorandom number, a path to which to forward the packet, wherein;

the third pseudorandom number comprises a most significant byte and a least significant byte; and

selection of the path as a function of the third pseudorandom number comprises selection of the path based on the most significant byte of the third pseudorandom number.

24. The system of claim 23, wherein both of the first and the second polynomial generators are primitive and have the same period.

25. The system of claim 24, wherein memory further comprises logic configured to form a fourth pseudorandom number as a function of a fourth polynomial generator and the key.

26. The system of claim 25, wherein the fourth polynomial generator is relatively prime to the first and the second polynomial generators, and wherein the memory further comprises logic configured to convert the fourth pseudorandom number to a pseudorandom rotation.

27. A networking equipment comprising:

a parsing circuit configured to obtain a key for a packet; and

a memory in communication with the parsing circuit and a processor, the memory comprising logic that, when executed by the processor, causes the processor to;

form a first pseudorandom number as a function of a first polynomial generator and the key;

form a rotation code equal to one of a number of rotations of the first polynomial generator;

combine the first pseudorandom number and the rotation code to form a second pseudorandom number, where the processor combines the first pseudorandom number and the rotation code by invoking at least one polynomial operation, where the first pseudorandom number and the rotation code are operands for the at least one polynomial operation; and

select, as a function of the second pseudorandom number, a path to which to forward the packet, wherein;

the second pseudorandom number comprises a most significant byte and a least significant byte; and

selection of the path as a function of the second pseudorandom number comprises selection of the path based on the most significant byte of the second pseudorandom number.

28. The networking equipment of claim 27, wherein the memory further comprises logic configured to form a third pseudorandom number as a function of a second polynomial generator and the key.

29. The networking equipment of claim 27, wherein the second polynomial generator is relatively prime to the first polynomial generator, and wherein the memory further comprises logic configured to convert the second pseudorandom number to a pseudorandom rotation.

30. The networking equipment of claim 29, wherein the first polynomial generator is primitive and has a first period, and wherein second polynomial generator is primitive and has a second period.