Method and system for performing a hash transformation to generate a hash pointer for an address input by using rotation

• US 20030182448A1
• Filed: 03/21/2002
• Published: 09/25/2003
• Est. Priority Date: 03/21/2002
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Gooch, Mark, Edwards, Aled
• Granted Patent: US 7,126,948 B2
• Time in Patent Office: Days
• US Class Current: 709/245
• CPC Class Codes: H04L 12/56 Packet switching systems
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

Abstract

A method for performing a hash transformation in a network device to generate a hash pointer for an address input by using rotation. The method includes to step of receiving an address input. Rotated copies of the address input are subsequently logically combined in accordance with a key to generate a hashing result corresponding to the address input. The hash result is subsequently output.

Claims

1. A method for performing a hash transformation in a network device to generate a hash pointer for an address input, comprising:

receiving the address input;

logically combining rotated versions of the address input in accordance with a key to generate a hash result corresponding to the address input; and

outputting the hash result for use with a routing table of the network device.

2. The method of claim 1 wherein the address input is a 32 bit address input.

3. The method of claim 2 wherein the hash result is a 5 bit hash result.

4. The method of claim 1 wherein the address input is a 12 bit address input.

5. The method of claim 4 wherein the hash result is a 3 bit hash result.

6. The method of claim 1 wherein the hash transformation is configured to be executed within a single clock cycle such that the hash result is generated within the single clock cycle.

7. A hash transformation system for performing a hash transformation in a network device comprising:

an input for receiving an address;

a rotator unit coupled to the input for rotating the address to generate rotated versions of the address;

a key register for storing a key;

a combiner coupled to the key register for logically XORing the rotated versions of the address in accordance with the key to generate a hash result; and

an output coupled to the combiner for transmitting the hash result.

8. The system of claim 7 wherein the address is a 32 bit input.

9. The method of claim 8 wherein the hash result is a 5 bit hash result.

10. The method of claim 7 wherein the address is a 12 bit input.

11. The method of claim 10 wherein the hash result is a 3 bit hash result.

12. A hash transformation system for performing a hash transformation in a network device comprising:

means for receiving an address input;

means for rotating the address input to generate rotated versions of the address input;

means for logically combining the rotated versions of the address input in accordance with a key to generate a hashing result corresponding to the address input; and

means for outputting the hash result.

13. The system of claim 12 wherein the hash transformation is configured to be executed within a single clock cycle such that the hash result is generated within the single clock cycle.

14. A parallel hash transformation system for generating a hash pointer for an address input, comprising:

an input configured to accept an address;

a plurality of parallel hash units coupled to the input to receive respective portions of the address, the hash units configured to execute a hash transformation on the respective portions of the address in parallel and generate respective hash outputs, each of the parallel hash units further comprising;

a unit input for receiving the respective portion;

a rotator unit coupled to the unit input for rotating the portion to generate rotated address portions;

a key register for storing a key;

a logical operator for logically combining the rotated address portions in accordance with the key to generate the hash output; and

a unit output for transmitting the hash output;

a combination unit coupled to receive the respective hash outputs, the combination unit configured to combine the respective hash outputs into a hash result; and

a system output configured coupled to the combination unit to transmit the hash result.

15. The method of claim 14 wherein the hash transformation is configured to be executed within a single clock cycle such that the hash result is generated within the single clock cycle.

16. The system of claim 14 wherein the hash transformations on the apportioned address inputs are configured to be executed in parallel within a single clock cycle such that the hash result is generated from the address input within the single clock cycle.

17. The system of claim 16 wherein the hash transformation system is implemented within a single hardware ASIC.

18. The system of claim 14 wherein the system is implemented within a router configured to use the hash result for storing routing addresses with a routing table.

19. The system of claim 14 wherein the system is implemented within a switch configured to use the hash result for storing forwarding information within a forwarding table.

20. The system of claim 14 wherein the logical operator for logically combining the rotated address portions in accordance with the key to generate the hash output is an exclusive-or logical operator.

21. A computer readable media having computer readable code which when executed by a network device cause the device to implement a method for performing a hash transformation to generate a hash pointer for an address input, comprising:

receiving an address input;

rotating the address input to generate rotated versions of the address input;

logically combining the rotated versions of the address input in accordance with the key to generate a hashing result corresponding to the address input; and

outputting the hash result.

22. The media of claim 21 wherein the hash transformation is configured to be executed within a single clock cycle such that the hash result is generated within the single clock cycle.