Method and system for performing flow based hash transformation to generate hash pointers for a network device

• US 7,085,271 B2
• Filed: 03/14/2002
• Issued: 08/01/2006
• Est. Priority Date: 03/14/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
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Ahmed, Salman
• Application Number:
  US10/098,984
• Publication Number:
  US 20030174710A1
• Time in Patent Office: 1,601 Days
• Field of Search: 370/395.32, 370/392, 370/401, 711/216
• US Class Current: 370/392
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

A method for performing flow based address hash transformation in a network device to generate hash pointers. The method includes the steps of receiving a pair of addresses (source address input and destination address input) corresponding to one direction of a data flow. The destination address input is modified by using a rotation operation. Respective hash operations are subsequently performed on the source address input and modified destination address input. The rotation operation performed on the destination address input prevents aliasing between the hash results for the forward direction of a data flow and the reverse direction, thereby preventing hash pointer collisions.

Claims

1. A method for performing flow based address hash transformation in a network device to generate hash pointers, comprising:

receiving a first address input and a second address input, wherein the first address input and second address input include a respective source address and destination address;

modifying the second address input using a rotation operation on the source address of the second address input; and

performing a hash operation on the first address input and the modified second address input wherein the rotation operation prevents hash pointer collisions between a forward flow and a reverse flow between the first address input and the second address input.

2. The method of claim 1 further comprising:

modifying the second address input by using a rotation operation on the destination address of the second address input.

3. The method of claim 1 wherein the forward flow includes data flowing from a first client to a second client and the reverse flow includes data flowing from the second client to the first client.

4. The method of claim 3 wherein the hash operation on the first address input and the modified second address input generate a hash result that is used for flow based routing in the network device.

5. The method of claim 1 wherein the first address input and the second address input are 128-bit address inputs.

6. The method of claim 1 wherein the forward flow and the reverse flow comprise flows in a first direction between the first address input and the second address input, and a second direction between the first address input and the second address input.

7. The method of claim 1 wherein the first address input and the second address input are 32 bit address inputs.

8. A system for performing flow based address hash transformation in a network device to generate routing table entries, comprising:

an input for receiving a first address and a second address corresponding to a first data flow, wherein the first address and the second address comprise a source address and a destination address;

a rotator unit coupled to the input, the rotator unit configured to modifying the source address by using a rotation operation;

a hash unit coupled to the rotator unit to receive the first address and the modified second address, the hash unit configured to perform hash operations on the first address input and the modified second address input wherein the rotation operations prevent aliasing between a hash result for the first data flow and a hash result for a second data flow in an opposite direction of the first data flow; and

an output coupled to the hash unit to output hash results of the hash operations, wherein the hash results are used for flow based routing by the network device.

9. The system of claim 8 wherein the rotation operation performed on the source address comprises a rotation of the source address by a plurality of bit positions.

10. The system of claim 8 wherein the rotator unit is configured to modifying the destination address by using the rotation operation.

11. The system of claim 10 wherein the rotation operation performed on the destination address comprises a rotation of the destination address by a plurality of bit positions.

12. The system of claim 8 wherein the first data flow includes data flowing from a first client to a second client and the second data flow includes data flowing from the second client to the first client.

13. The system of claim 8 wherein the first hash result and the second hash result are output for indexing with a routing table used for flow based routing in the network device.

14. The system of claim 8 wherein the first address and the second address are 128-bit address inputs.

15. The system of claim 8 wherein the first data flow and the second data flow comprise flows in a forward direction between the first address input and the second address input and flows in a reverse direction between the first address input and the second address input.

16. The system of claim 8 wherein the first address and the second address are 32 bit address inputs.

17. A system for performing flow based address hash transformation in a network device to generate hash pointers, comprising:

means for receiving a first address input and a second address input, wherein the first address input and second address input include a respective source address and destination address;

means for modifying the second address input using a rotation operation on the source address of the second address input; and

means for performing a hash operation on the first address input and the modified second address input wherein the rotation operation prevents hash pointer collisions between a forward flow and a reverse flow between the first address input and the second address input.

18. The system of claim 17 further comprising:

means for modifying the second address input by using a rotation operation on the destination address of the second address input.

19. The system of claim 17 wherein the forward flow includes data flowing from a first client to a second client and the reverse flow includes data flowing from the second client to the first client.

20. The system of claim 17 wherein a hash result of the hash operation is used for flow based routing in the network device.

21. The system of claim 17 wherein the first address input and the second address input are 128-bit address inputs.

22. The system of claim 17 wherein the forward flow and the reverse flow comprise flows in a first direction between the first address input and the second address input or a second direction between the first address input and the second address input.

23. The system of claim 17 wherein the system is implemented within a single ASIC.

24. A computer readable media having computer readable code which when executed by a computer system of a network device cause the network device to implement a method for performing flow based address hash transformation, comprising:

accessing a first address input, wherein said first address input includes a source address;

accessing a second address input, wherein said second address input includes a destination address;

changing the second address input using a rotation operation on the source address of the second address input; and

executing a hash operation on the first address input and the modified second address input wherein the rotation operation prevents hash pointer collisions between a forward flow and a reverse flow between the first address input and the second address input.

25. The media of claim 24 wherein the hash generates a hash result used for flow based routing in the network device.