Apparatus and method for efficient hashing in networks

• US 6,870,849 B1
• Filed: 07/06/2000
• Issued: 03/22/2005
• Est. Priority Date: 07/06/2000
• Status: Expired due to Term

• Current Assignee: Parity Networks LLC
• Original Assignee: Sherwood Partners Incorporated
• Inventors: Callon, Ross W., Carlson, James D., Ehlert, Douglas C., Peduel, Yuval
• Primary Examiner(s): Vu, Huy D.
• Assistant Examiner(s): RYMAN, DANIEL J
• Application Number:
  US09/610,278
• Time in Patent Office: 1,720 Days
• Field of Search: 370/389, 370/392, 370/393, 370/395.32, 370/395.7, 370/394, 370/497, 711/216
• US Class Current: 370/395.32
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

Abstract

An apparatus and method for efficient hashing uses both an identifying portion of a data packet, e.g., source and destination ID, and an identifying value of the node, e.g., the IP address of the node, to generate a hash result. By inserting a unique value into the hash operation at each node, the invention effectively provides for a different hash implementation at each node. As a result, in situations where multiple paths or multiple links within a path are available to forward packets, traffic can be split over the multiple paths and links. Inefficient utilization of network links found in prior systems which use the same hash operation at each node are eliminated.

Claims

1. A method of transferring data on a network, said network including a plurality of nodes connected by a plurality of links, at least one node being connected to more than one link over which the data can be transferred out of the at least one node, the method comprising:

providing the data with an identifying portion which identifies a source node and a destination node for, the data;

associating the at least one node with a node identifying value to distinguish the at least one node from other nodes on the network; and

using the identifying portion of the data and the node identifying value, calculating a link selection value which identifies one of the more than one links connected to the at least one node to transfer the data out of the at least one node, wherein the link selection value is calculated by combining the identifying portion of the data and the node identifying value through a logical operation.

2. The method of claim 1 wherein the data is a packet of data.

3. The method of claim 2 wherein the packet is an Internet Protocol (IP) packet.

4. The method of claim 2 wherein the identifying portion of the data is at least a portion of a header of the packet.

5. The method of claim 4 wherein the identifying portion of the data includes a source node ID portion of the header.

6. The method of claim 4 wherein the identifying portion of the data includes a destination node ID portion of the header.

7. The method of claim 4 wherein the identifying portion of the data includes a protocol field of the header.

8. The method of claim 1 wherein the node identifying value is an Internet Protocol (IP) address of the at least one node.

9. The method of claim 1 wherein the logical operation comprises a hash operation.

10. The method of claim 9 wherein the identifying portion of the data includes a source node ID portion of the header.

11. The method of claim 9 wherein the identifying portion of the data includes a destination node ID portion of the header.

12. The method of claim 9 wherein the identifying portion of the data includes a protocol field of the header.

13. The method of claim 9 wherein the hash operation comprises performing a cyclic redundancy check (CRC) on the identifying portion of the data and the node identifying value.

14. An apparatus for transferring data on a network, said network including a plurality of nodes connected by a plurality of links, at least one node being connected to a plurality of links over which the data can be transferred out of the at least one node, the data being provided with an identifying portion which identifies a source node and a destination node for the data, and the at least one node being associated with a node identifying value to distinguish the at least one node from other nodes on the network, the apparatus comprising:

an output interface over which the data can be forwarded to one of the plurality of links; and

a processing device for calculating a link selection value using the identifying portion of the data and the node identifying value, said link selection value identifying one of the plurality of links connected to the at least one node to transfer the data out of the at least one node, wherein the link selection value is calculated by combining the identifying portion of the data and the node identifying value through a logical operation.

15. The apparatus of claim 14 wherein the data transferred by the apparatus is a packet of data.

16. The apparatus of claim 15 wherein the packet of data transferred by the apparatus is an Internet Protocol (IP) packet.

17. The apparatus of claim 15 wherein the identifying portion of the data used by the processing device to generate the link selection value is at least a portion of a header of the packet.

18. The apparatus of claim 17 wherein the identifying portion of the data used by the processing device to generate the link selection value includes a source node ID portion of the header.

19. The apparatus of claim 17 wherein the identifying portion of the data used by the processing device to generate the link selection value includes a destination node ID portion of the header.

20. The apparatus of claim 17 wherein the identifying portion of the data used by the processing device to generate the link selection value includes a protocol field of the header.

21. The apparatus of claim 14 wherein the node identifying value used by the processing device to generate the link selection value is an Internet Protocol (IP) address of the at least one node.

22. The apparatus of claim 14 wherein the logical operation performed by the processing device includes a hash operation.

23. The apparatus of claim 22 wherein the identifying portion of the data used by the processing device to generate the link selection value includes a source node ID portion of the header.

24. The apparatus of claim 22 wherein the identifying portion of the data used by the processing device to generate the link selection value includes a destination node ID portion of the header.

25. The apparatus of claim 22 wherein the identifying portion of the data used by the processing device to generate the link selection value includes a protocol field of the header.

26. The apparatus of claim 22 wherein the hash operation performed by the processing device comprises a cyclic redundancy check (CRC) on the identifying portion of the data and the node identifying value.