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

• US 20030174710A1
• Filed: 03/14/2002
• Published: 09/18/2003
• Est. Priority Date: 03/14/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
• Granted Patent: US 7,085,271 B2
• Time in Patent Office: Days
• US Class Current: 370/395.32
• 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;

modifying the second address input using a rotation operation; 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 wherein the first address input and second address input include a respective source address and destination address.

3. The method of claim 2 further comprising:

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

4. The method of claim 2 further comprising:

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

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

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

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

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

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

10. 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;

a rotator unit coupled to the input, the rotator unit configured to modify the second address input 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.

11. The system of claim 10 wherein the first address and the second address comprise a source address and a destination address.

12. The system of claim 11 wherein the rotator unit is configured to modify the source address by using the rotation operation.

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

14. The system of claim 11 wherein the rotator unit is configured to modify the destination address by using the rotation operation.

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

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

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

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

19. The method of claim 10 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.

20. The system of claim 10 wherein the first address and the second address are 32 bit address inputs.

21. 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;

means for modifying the second address input using a rotation operation; 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.

22. The system of claim 21 wherein the first address input and second address input include a respective source address and destination address.

23. The system of claim 22 further comprising:

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

24. The system of claim 22 further comprising:

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

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

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

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

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

29. The system of claim 21 wherein the system is implemented within a single ASIC.

30. 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;

accessing a second address input;

changing the second address input using a rotation operation; 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.

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