LOAD BALANCING HASH COMPUTATION FOR NETWORK SWITCHES

• US 20120136999A1
• Filed: 11/29/2011
• Published: 05/31/2012
• Est. Priority Date: 11/30/2010
• Status: Active Grant

• Current Assignee: Marvell Israel Limited (Marvell Technology Group Limited)
• Original Assignee: Marvell Israel Limited (Marvell Technology Group Limited)
• Inventors: Roitshtein, Amir, Mizrahi, Tal
• Granted Patent: US 8,756,424 B2
• Time in Patent Office: Days
• US Class Current: 709/225
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/193 at the transport layer, e.g. TCP related
• CPC Class Codes: H04L 47/41 by acting on aggregated flows or links
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 49/50 Overload detection or protection within a single switching element
• CPC Class Codes: H04L 63/061 for key exchange, e.g. in peer-to-peer networks cryptographic mechanisms or cryptographic arrangements for key agreement H04L9/0838
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
• CPC Class Codes: H04L 9/0816 Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use
• CPC Class Codes: H04L 9/0819 Key transport or distribution, i.e. key establishment techniques where one party creates or otherwise obtains a secret value, and securely transfers it to the other(s) network architectures or network communication protocols for key distribution in a packet data network H04L63/062

Abstract

Techniques to avoid polarization in a communication network include a network switch or device having a first interface to receive a data unit or packet, and a second interface via which the packet is transmitted from the network device. The network device includes a hash value generator configured to generate, using a depolarizer, a depolarized key from an initial key (where the initial key is based on contents of the packet and the depolarizer is unique to the network device), and to generate a hash value based on the depolarized key and the packet by using a hash function that is common to all network devices in the network. The hash value may be optionally modified to load balance egress traffic of the network device. The network device selects an egress link or port, such as by determining an index into an egress table based on the (modified) hash value.

Claims

1. A method for avoiding polarization in a communication network, the method comprising:

receiving a data unit at a network device included in the communication network, the network device associated with a link aggregate group included in the communication network;

determining an initial key based on information included in the data unit;

generating a depolarized initial key based on the initial key by using a depolarizer that is unique, within the communication network, to the network device;

performing a hash function on the depolarized initial key to obtain a hash value for the data unit;

determining, based on the hash value, a communication link in the link aggregate group; and

causing the data unit to be transmitted over the communication link.

2. The method of claim 1, wherein generating the depolarized initial key by using the depolarizer comprises applying a depolarizing function to the initial key to generate the depolarized initial key.

3. The method of claim 2, wherein applying the depolarizing function to the initial key comprises applying an essentially bijective function to the initial key.

4. The method of claim 3, wherein applying the essentially bijective function to the initial key comprises applying one of:

an additive function, a remapping function, or an exclusive-or (XOR) function to the initial key.

5. The method of claim 4, wherein applying the additive function to the initial key comprises applying a randomly or pseudo-randomly generated sequence of bits that is unique, within the communication network, to the initial key.

6. The method of claim 1, wherein:

the hash value is a first hash value;

the method further comprises;

modifying, based on a client of the first hash value, the first hash value to generate a modified hash value to avoid polarization within the network device, and

determining the communication link based on the modified hash value instead of the first hash value; and

the client is included in the network device, corresponds to the data unit, and is configured to perform a function used in forwarding the data unit using the modified hash value.

7. The method of claim 6, wherein modifying the first hash value based on the client of the first hash value comprises selecting, based on a type of the client, a subset of bits included in the first hash value to generate the modified hash value.

8. The method of claim 7, wherein selecting the subset of bits included in the first hash value comprises selecting one of a plurality of mutually exclusive subsets of bits included in the first hash value.

9. The method of claim 1, wherein performing the hash function comprises performing a common hash function that is used in each network device of a plurality of network devices included in the communication network.

10. The method of claim 9, wherein performing the common hash function comprises performing a specific common hash function configured to generate a hash value having a length sufficient to provide a distribution of data unit traffic having a desired level of uniformity.

11. A network device for avoiding polarization in a communication network, the network device comprising:

a first network interface configured to receive a data unit;

a hash value generator configured to generate a hash value based on the data unit, the hash value generator including;

a depolarized key generator configured to generate a depolarized initial key based on a depolarizing function applied to an initial key, the initial key based on at least a portion of information included in the data unit, and the depolarizing function defined so that the depolarized initial key is generated for different data units of a same traffic flow; and

a hash function configured to generate the hash value based on the depolarized initial key and the data unit;

a link selector configured to select, based on the hash value, a communication link; and

a second network interface to egress the data unit from the network device via the communication link.

12. The network device of claim 11, wherein the depolarized key generator is configured to generate the depolarized initial key based on an additive function that applies, to the initial key, a randomly generated sequence of bits;

and wherein the randomly generated sequence of bits is unique, within the communication network, to the network device.

13. The network device of claim 11, wherein the depolarized key generator is configured to generate the depolarized initial key based on an essentially bijective remapping function.

14. The network device of claim 11, further comprising a client to receive the hash value;

and wherein;

the hash value is a first hash value;

the network device further comprises a hash value modifier configured to generate a modified hash value based on one of a plurality of mutually exclusive subsets of bits of the first hash value and further based on the client; and

the link selector is further configured to select the communication link based on the modified hash value.

15. The network device of claim 14, wherein:

a type of the client is included in a plurality of types of clients; and

a different mutually exclusive subset of bits corresponds to each type of client in the plurality of types of clients.

16. The network device of claim 11, wherein the hash function is configured to generate a hash value having a length sufficient to provide distribution of data unit traffic having a desired level of uniformity.

17. A system for avoiding polarization in a communication network, comprising:

a plurality of network devices in the communication network, wherein each network device of the plurality of network devices includes;

a network interface to receive a data unit;

a hash value generator to generate a hash value based on the data unit, the hash value generator including;

a depolarized key generator to generate a depolarized initial key based on a depolarizing function applied to an initial key, the initial key based on at least a portion of information included in the data unit, and the depolarizing function being unique, within the communication network, to the each network device, and

a hash function to generate the hash value based on the depolarized initial key and the data unit; and

a link selector to select, based on the hash value, a communication link to egress the data unit from the each network device.

18. The system of claim 17, wherein the depolarizing function is an essentially bijective function, that is unique, within the communication network, to the each network device;

and wherein the hash function is common across the plurality of network devices.

19. The system of claim 17, wherein the depolarizing function is selectable.

20. The system of claim 17, wherein:

the hash value is a first hash value;

the each network device further includes a hash value modifier configured to generate a modified hash value based on one of a plurality of mutually exclusive subsets of bits of the first hash value, the one of the plurality of mutually exclusive subsets of bits of the first hash value corresponding to a type of a client of the modified hash value, and the client of the modified hash value included on the each network device and configured to perform a function used in forwarding the data unit; and

the link selector is further configured to select the communication link based on the modified hash value instead of based on the first hash value.

21-60. -60. (canceled)