Load balancing hash computation for network switches

Patent metadata

Field	Value
Publication number	US-9503435-B2
Application number	US-201414178974-A
Country	US
Kind code	B2
Filing date	Feb 12, 2014
Priority date	Nov 30, 2010
Publication date	Nov 22, 2016
Grant date	Nov 22, 2016

Abstract

Techniques to load balance traffic in a network device or switch include a network device or switch having a first interface to receive a data unit or packet, a second interface to transmit the packet, and a mapper to map between virtual ports and physical ports. The network device includes hash value generator configured to generate a hash value based on information included in the packet and based on at least one virtual port. The hash value may be optionally modified to load balance egress traffic of the network device. The network device selects a particular virtual port for egress of the packet, such as by determining an index into an egress table based on the (modified) hash value. The packet is transmitted from the network device using a physical port mapped to the particular virtual port.

First claim

What is claimed is:

1. A method for load balancing traffic in a network device, comprising:
receiving a data unit at the network device via a first port;
determining, at the network device, an initial key based on information included in the data unit;
generating a depolarized key from the initial key based on combining the initial key with a depolarizing value, the depolarizing value corresponding to the network device and unique with respect to other depolarizing values utilized in a communication network including the network device;
performing a hash function on the depolarized key to determine a hash value for the data unit; and
forwarding the data unit to an egress port that is selected at least partly based on the hash value.

2. The method of claim 1 , wherein that the depolarizing value uniquely corresponds to the network device within the communication network.

3. The method of claim 1 , wherein combining the initial key with the depolarizing value comprises combining the initial key with a configured depolarizing value unique to the network device.

4. The method of claim 1 , wherein combining the initial key with the depolarizing value comprises combining the initial key with a randomly or pseudo-randomly generated depolarizing value unique to the network device.

5. The method of claim 1 , wherein combining the initial key with the depolarizing value comprises at least one of:
appending the depolarizing value to the initial key;
pre-pending the depolarizing value to the initial key; or
interleaving portions of the depolarizing value within portions of the initial key.

6. The method of claim 1 , wherein generating the depolarized key comprises generating a depolarized key having a majority of bits that is bijective.

7. The method of claim 1 , wherein performing the hash function comprises performing a hash function that is common across a plurality of network devices included in the communication network.

8. The method of claim 1 , further comprising:
modifying the hash value; and
selecting the egress port based on the modified hash value.

9. The method of claim 8 , wherein modifying the hash value comprises modifying the hash value based on a number of links of a link aggregate group corresponding to the data unit.

10. The method of claim 1 , wherein receiving the data unit via the first port comprises receiving the data unit via a first physical port mapped to a first virtual port.

11. The method of claim 1 , further comprising:
selecting a virtual egress port at least partly based on the hash value,
wherein the virtual egress port is mapped to a physical egress port.

12. A load-balancing network device, comprising:
a plurality of ports;
a depolarization unit configured to combine a depolarizing value with an initial key to generate a depolarized key, the initial key generated based on information included in a data unit received by the load-balancing network device, and the depolarizing value corresponding to the load-balancing network device and being unique with respect to other depolarizing values utilized in a communication network including the load-balancing network device;
a hash value determiner configured to perform a hash function on the depolarized key to determine a hash value for the data unit; and
a network interface configured to egress the data unit via an egress port selected at least partly based on the hash value.

13. The load-balancing network device of claim 12 , wherein the depolarizing value is a configured value.

14. The load-balancing network device of claim 12 , wherein the depolarizing value is randomly or pseudo-randomly generated.

15. The load-balancing network device of claim 12 , wherein the depolarization unit is configured to combine the depolarizing value with the initial key by at least one of:
appending the depolarizing value to the initial key;
pre-pending the depolarizing value to the initial key; or
interleaving a portion of the depolarizing value between portions of the initial key.

16. The load-balancing network device of claim 12 , wherein a number of bytes of the depolarizing value is equal to a number of bytes of the initial key.

17. The load-balancing network device of claim 12 , wherein:
the data unit corresponds to a particular flow,
the hash value is a common hash value for all data units corresponding to the particular flow, and
the depolarization unit is configured to cause the common hash value to be generated by the hash value determiner for the all data units corresponding to the particular flow.

18. The load-balancing network device of claim 17 , wherein the common hash value generated by the load-balancing network device for the all data units corresponding to the particular flow is different from a common hash value generated by another load-balancing network device corresponding to the communication network for the all data units included in the particular flow.

19. The load-balancing network device of claim 17 ,
wherein the particular flow is a first particular flow and the common hash value is a first common hash value; and
wherein the depolarization unit is further configured to cause a second common hash value to be generated by the hash value determiner for all data units corresponding to a second particular flow.

20. The load-balancing network device of claim 12 , wherein a majority of bits included in the combination of the depolarizing value and the initial key is bijective.

Assignees

• Marvell Israel (M I S L) Ltd

Inventors

• Roitshtein Amir
• Mizrahi Tal

Classifications

• H04L47/70

  Admission control; Resource allocation · CPC title

• H04L47/125

  by balancing the load, e.g. traffic engineering · CPC title

• H04L9/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 title

• H04L63/061 Primary

  for key exchange, e.g. in peer-to-peer networks (cryptographic mechanisms or cryptographic arrangements for key agreement H04L9/0838) · CPC title

• H04L47/41

  by acting on aggregated flows or links · CPC title