Performing a finishing operation to improve the quality of a resulting hash

• US 10,193,806 B2
• Filed: 03/31/2014
• Issued: 01/29/2019
• Est. Priority Date: 03/31/2014
• Status: Active Grant

• Current Assignee: Nicira Incorporated (Broadcom, Inc.)
• Original Assignee: Nicira Incorporated (Broadcom, Inc.)
• Inventors: Rajahalme, Jarno
• Primary Examiner(s): Choudhury, Azizul
• Application Number:
  US14/231,619
• Publication Number:
  US 20150281082A1
• Time in Patent Office: 1,765 Days
• Field of Search: None
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

Some embodiments provide a physical forwarding element that hashes portions of packet headers using several novel hashing techniques. The techniques include a novel set of finishing operations that improve the quality of resulting hashes by increasing their distribution and improving their apparent-randomness. In some embodiments, the finishing operation includes at least one of multiplying the hash by a prime number to increase distribution of the bits of the hash, accumulating a length of the portion into the hash, and combining higher bits of the hash with lower bits of the hash in order to increase the entropy of the lower bits of the hash.

Claims

1. A non-transitory machine readable medium storing a program that, when executed by at least one processing unit, generates a hash of a portion of a packet to process a packet, the program comprising sets of instructions for:

generating a first hash from at least a portion of a packet header;

performing a finishing operation on the first hash to produce a resulting second hash, wherein the finishing operation comprises accumulating a length of the portion of the packet header into the hash by hashing a combination of the first hash and the length of the portion of the packet header; and

processing the packet based on the resulting second hash.

2. The non-transitory machine readable of claim 1, wherein the program further comprises a set of instructions for padding the portion with bits such that the padded portion is equal in length to at least one half of an input size of one of the processing units prior to generating the first hash.

3. The non-transitory machine readable of claim 1, wherein the set of instructions for generating the first hash from the portion of the packet header comprises a set of instructions for using an instruction set based on a cyclic redundancy check (CRC) to generate the first hash.

4. The non-transitory machine readable medium of claim 1, wherein the set of instructions for performing a finishing operation comprises a set of instructions for performing a set of finishing operations, wherein the set of finishing operations further comprises combining higher bits of the hash with lower bits of the hash in order to increase the entropy of the lower bits of the hash.

5. The non-transitory machine readable medium of claim 1, wherein the set of instructions for performing a finishing operation comprises a set of instructions for performing a set of finishing operations, wherein the set of finishing operations further comprises multiplying the hash by a prime number to increase distribution of the bits of the hash.

6. A non-transitory machine readable medium storing a program that, when executed by at least one processing unit, generates a hash for a packet, the program comprising sets of instructions for:

receiving a portion of a header of the packet from which to generate the hash for the packet;

determining whether to hash the portion as a whole or hash a plurality of sections of the portion individually to generate the hash for the packet;

generating the hash for the packet by hashing the portion as a whole when the determination is made to hash the portion as a whole; and

when the determination is made to hash the plurality of sections of the portion individually;

dividing the portion of the packet into the plurality of sections; and

individually hashing each of the sections of the portion to generate resultant hashes and generating the hash for the packet by merging the resultant hashes from the individually hashed sections.

7. The non-transitory machine readable medium of claim 6, wherein the program further comprises a set of instructions for performing a set of finishing operations on the generated hash.

8. The non-transitory machine readable medium of claim 7, wherein the set of finishing operations comprises an operation that accumulates a length of the portion into the generated hash.

9. The non-transitory machine readable medium of claim 7, wherein the set of finishing operations comprises an operation that combines higher bits of the generated hash with lower bits of the generated hash.

10. The non-transitory machine readable medium of claim 6, wherein the hash is generated using an instruction set based on a cyclic redundancy check (CRC).

11. The non-transitory machine readable medium of claim 6, wherein the set of instructions for determining whether to hash the portion as a whole or hash the plurality of sections of the portion individually comprises a set of instructions for comparing a size of the portion with a size of input of one of the processing units.

12. For a forwarding element, a method of generating a hash to process a packet, the method comprising:

generating a hash from at least a portion of a packet header;

performing a finishing operation on the hash to produce a resulting hash, wherein the finishing operation comprises multiplying the hash by a prime number to increase distribution of the bits of the hash; and

processing the packet based on the resulting hash.

13. The method of claim 12 further comprising, prior to generating the hash, padding the portion with bits such that the padded portion is equal in length to at least one half of an input size of a processing unit of the forwarding element.

14. The method of claim 12, wherein performing the finishing operation comprises performing a set of finishing operations, wherein the set of finishing operations further comprises accumulating a length of the portion of the packet header into the hash.

15. The method of claim 12, wherein performing the finishing operation comprises performing a set of finishing operations, wherein the set of finishing operations further comprises combining higher bits of the hash with lower bits of the hash in order to increase the entropy of the lower bits of the hash.

16. A method for generating a hash for a packet, the method comprising:

receiving a portion of a header of the packet from which to generate the hash for the packet;

determining whether to hash the portion as a whole or hash a plurality of sections of the portion individually to generate the hash for the packet; and

when the determination is made to hash the plurality of sections of the portion individually;

dividing the portion of the packet into a plurality of sections; and

individually hashing each of the sections of the portion to generate resultant hashes and generating the hash for the packet by merging the resultant hashes from the individually hashed sections,

wherein when the determination is made to hash the portion as a whole, the hash for the packet is generated by hashing the portion as a whole.

17. The method of claim 16 further comprising performing a set of finishing operations on the generated hash for the packet, the set of finishing operations comprising an operation that accumulates a length of the portion into the generated hash for the packet.

18. The method of claim 16 further comprising performing a set of finishing operations on the generated hash for the packet, the set of finishing operations comprising an operation that combines higher bits of the generated hash with lower bits of the generated hash.

19. The method of claim 16, wherein determining whether to hash the entire portion as a whole or hash the plurality of sections of the portion individually comprises a set of instructions for comparing a size of the portion with a size of input of one of the processing units.

20. The method of claim 16, wherein the hash is generated using an instruction set based on a cyclic redundancy check (CRC).