Apparatus and method for efficient hashing in networks
View Patent ↗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.
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.