Dynamic link load balancing

• US 8,259,585 B1
• Filed: 04/17/2009
• Issued: 09/04/2012
• Est. Priority Date: 04/17/2009
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: S P, Arun Kumar, Golash, Mukul
• Primary Examiner(s): Ly, Anh-Vu
• Assistant Examiner(s): Crompton, Christopher R
• Application Number:
  US12/425,517
• Time in Patent Office: 1,236 Days
• Field of Search: 370/237
• US Class Current: 370/237
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering

Abstract

Techniques are described for load balancing packet flows across parallel data paths. For example, a network device includes a plurality of parallel network interfaces and a control unit that applies each of a first set of hash functions to a packet and one of a second set of hash functions to the packet. Bins of each of the first set of hash functions are mapped to bits of a bit vector. Bins of each of the second set of hash functions are mapped to the plurality of parallel network interfaces. The control unit selects the one of the second set of hash functions to apply to the packet based on values of the bits of the bit vector. The control unit forwards the packet through the network interface that is identified by applying the selected one of the second set of hash functions to the packet.

Claims

1. A method comprising:

receiving, with a network device, a packet of a packet flow, wherein the network device is coupled to a plurality of parallel data paths;

determining whether the packet is a request to establish a network connection;

when the packet is a request to establish a network connection, querying a Bloom filter of the network device with packet flow information of the packet to determine whether the packet flow is a member of the Bloom filter;

when the packet flow is not a member of the Bloom filter, selecting a first one of the plurality of parallel data paths with a first hash function and determining whether the first one of the parallel data paths is congested; and

when the first one of the parallel data paths is congested, adding the packet flow to the Bloom filter, selecting a second one of the plurality of parallel data paths with a second hash function and forwarding the packet through the selected second one of the parallel data paths.

2. The method of claim 1, wherein determining whether the packet is a request to establish a network connection comprises determining whether the packet is a synchronization (SYN) packet.

3. The method of claim 1, wherein querying a Bloom filter to determine whether the packet flow is a member of the Bloom filter comprises querying the Bloom filter to determine whether application of the Bloom filter to the flow information of the packet produces a bit vector signature currently stored in the Bloom filter in response to one or more previous packet flows.

4. The method of claim 1, wherein querying a Bloom filter comprises:

applying each of a set of Bloom filter hash functions to the flow information of the packet to select a subset of bits of a bit vector of the Bloom filter, wherein bins of the Bloom filter hash functions are mapped to the bits of the bit vector;

when at least one of the selected subset of bits is not currently set, determining that the packet is not a member of the Bloom filter; and

when each of the selected subset of bits is currently set, determining that the packet is a member of the Bloom filter.

5. The method of claim 1, wherein selecting the first one of the plurality of parallel data paths with a first hash function comprises executing the first hash function on a portion of the packet.

6. The method of claim 5, wherein executing the first hash function on a portion of the packet comprises executing the first hash function on a packet header of the packet.

7. The method of claim 1, wherein adding the packet flow to the Bloom filter comprises:

applying each of a set of Bloom filter hash functions to the flow information of the packet to select a subset of bits of a bit vector of the Bloom filter, wherein bins of the Bloom filter hash functions are mapped to the bits of the bit vector; and

setting each of the selected subset of bits of the bit vector to a value of 1.

8. The method of claim 1, wherein when the first one of the parallel data paths selected with the first hash function is not congested, the method further comprises forwarding the packet through the selected first one of the parallel data paths.

9. The method of claim 1, wherein when the packet is a request to establish a network connection and when the packet is a member of the Bloom filter, the method further comprises:

selecting a third one of the plurality of parallel data paths with the second hash function; and

forwarding the packet through the selected third one of the parallel data paths.

10. The method of claim 1, wherein when the packet is not a request to establish a network connection, the method further comprises querying the Bloom filter with the packet to determine whether the packet is a member of the Bloom filter.

11. The method of claim 10, wherein when the packet is not a request to establish a network connection and the packet is not a member of the Bloom filter, the method further comprises:

selecting the first one of the plurality of parallel data paths with the first hash function; and

forwarding the packet through the selected first one of the parallel data paths.

12. The method of claim 10, wherein when the packet is not a request to establish a network connection and the packet is a member of the Bloom filter, the method further comprises:

selecting the second one of the plurality of parallel data paths with the second hash function; and

forwarding the packet through the selected second one of the parallel data paths.

13. A network device comprising:

an input network interface that receives a packet of a packet flow;

a plurality of parallel output network interfaces;

a link monitoring module that identifies each of the plurality of parallel output network interfaces that is congested;

a Bloom filter that stores bit vector signatures of packet flows and determines whether a bit vector signature for a queried packet matches one of the stored bit vector signatures;

a load balancing module that selects one of the plurality of parallel output network interfaces for the packet flow, wherein the load balancing module queries the Bloom filter to select one of a plurality of hash functions to apply to the packet, wherein the load balancing module applies the selected hash function to the packet to select the one of the plurality of parallel output network interfaces, and wherein the load balancing module queries the link monitoring module to determine whether the selected parallel output network interface is congested for packets that are requests to establish a network connection, wherein when the packet is a request to establish a network connection, the load balancing module queries the Bloom filter to determine whether a bit vector signature for the packet matches one of the stored bit vector signatures, wherein when the bit vector signature for the packet does not match one of the stored bit vector signatures the Bloom filter, the load balancing module executes a first hash function to select a first one of the plurality of parallel output network interfaces and queries the link monitoring module to determine whether the first one of the parallel data paths selected with the first hash function is congested, and wherein when the link monitoring module determines that the first one of the parallel output network interfaces is congested, the load balancing module adds the packet flow to the Bloom filter and executes a second hash function on the packet to select a second one of the plurality of parallel output network interfaces; and

a control unit that determines whether the packet is a request to establish a network connection and that forwards the packet along the selected one of the plurality of parallel output network interfaces.

14. The network device of claim 13, wherein the Bloom filter stores a bit vector signature for the packet.

15. The network device of claim 13, wherein when the link monitoring module determines that the first one of the parallel output network interfaces selected with the first hash function is not congested, the control unit forwards the packet through the first one of the parallel output network interfaces.

16. The network device of claim 13, wherein when the bit vector signature for the packet matches one of the stored bit vector signatures, the load balancing module applies a second hash function to select a second one of the plurality of parallel output network interface, and wherein the control unit forwards the packet through the second one of the plurality of parallel output network interfaces.

17. The network device of claim 13, wherein when the packet is not a request to establish a network connection, the load balancing module queries the Bloom filter to determine whether a bit vector signature for the packet matches one of the stored bit vector signatures of the Bloom filter, wherein when the bit vector signature for the packet does not match one of the stored bit vector signatures, the load balancing module executes a first hash function to select a first one of the plurality of parallel output network interfaces, but when the bit vector signature for the packet matches one of the stored bit vector signatures, the load balancing module executes a second hash function to select a second one of the plurality of parallel output network interfaces and queries the link monitoring module to determine whether the second one of the parallel data paths is congested.

18. The network device of claim 13, wherein the Bloom filter comprises a set of Bloom filter hash functions and a bit vector, wherein bins of each of the Bloom filter hash functions are mapped to bits of the bit vector.

19. The network device of claim 18, further comprising a timer that determines at least one of the bits of the bit vector that is a least recently used bit, wherein the control unit clears the least recently used bit when the timer expires.

20. A non-transitory computer-readable medium comprising instructions for causing a programmable processor of a network device comprising a plurality of parallel data paths to:

receive a packet of a packet flow;

determine whether the packet is a request to establish a network connection;

when the packet is a request to establish a network connection, query a Bloom filter with the packet to determine whether a bit vector signature of the packet matches one of a plurality of bit vector signatures stored by the Bloom filter;

when the bit vector signature matches one of the plurality of bit vector signatures stored by the Bloom filter, select a first one of the plurality of parallel data paths with a first hash function and forward the packet through the selected first one of the plurality of parallel data paths;

when the bit vector signature does not match one of the plurality of bit vector signatures stored by the Bloom filter, select a second one of the plurality of parallel data paths with a second hash function and determine whether the selected second one of the parallel data paths is congested;

when the selected second one of the parallel data paths is not congested, forward the packet through the selected second one of the parallel data paths;

when the selected second one of the parallel data paths is congested, store the bit vector signature of the packet with the Bloom filter to add the packet flow to the Bloom filter, select the first one of the parallel data paths with the first hash function, and forward the packet through the selected first one of the parallel data paths; and

when the packet is not a request to establish a network connection, query the Bloom filter with the packet to determine whether a bit vector signature of the packet matches one of a plurality of bit vector signatures stored by the Bloom filter;

when the bit vector signature matches one of the plurality of bit vector signatures stored by the Bloom filter, select the first one of the plurality of parallel data paths with the first hash function and forward the packet through the selected first one of the parallel data paths; and

when the bit vector signature does not match one of the plurality of bit vector signatures stored by the Bloom filter, select the second one of the plurality of parallel data paths with a second hash function and forward the packet through the selected second one of the parallel data paths.