Dynamic link load balancing
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
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. - View Dependent Claims (14, 15, 16, 17, 18, 19)
-
-
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.
-
Specification