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

• US 7,126,948 B2
• Filed: 03/21/2002
• Issued: 10/24/2006
• Est. Priority Date: 03/21/2002
• Status: Expired due to Fees

• 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
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Ahmed, Salman
• Application Number:
  US10/104,888
• Publication Number:
  US 20030182448A1
• Time in Patent Office: 1,678 Days
• Field of Search: 370/395.2, 370/392, 370/401, 711/216
• US Class Current: 370/392
• 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, wherein the address input is a 12 bit 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, 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; and

outputting the hash result for use with a routing table of the network device, wherein the hash result is a 5 bit hash result.

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

3. 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.

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

an input for receiving an address, wherein the address is a 12 bit input;

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, 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; and

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

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

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

means for receiving an address input, wherein the address is a 12 bit 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, 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; and

means for outputting the hash result.

7. The system of claim 6 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.

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

an input configured to accent an address, 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;

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, 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, 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.

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

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

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

12. The system of claim 8 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.

13. 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, 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, comprising:

receiving an address input, wherein the address is a 12 bit 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.

14. The media of claim 13 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.