Load sharing across flows
AssigneeCisco Technology, Inc.
InventorsBruce A. Wilford, Thomas Dejanovic
Life of this patent
Estimating the term…
Abstract
The invention provides a system and method for sharing packet traffic load among a plurality of possible paths. Each packet is associated with a flow, and a hash value is determined for each flow, so as to distribute the sequence of packets into a set of hash buckets. The hash value has a relatively large number of bits, but is divided by the number of possible paths so as to achieve a relatively small modulus value; the modulus value is used to index into a relatively small table associating one selected path with each entry. The modulus value is determined by a relatively small amount of circuitry, simultaneously for a plurality of moduli, and one such modulus value is selected in response to the number of possible paths.
Claims45
A method for distributing respective pluralities of packets belonging to respective flows among a number N of outgoing data paths, said method comprising the following steps:
- for each packet, associating a respective distribution value therewith, said respective distribution value being based, at least in part, upon a respective hash value generated from packet network layer information;
- determining a modulus value of the distribution value, the distribution value having a first plurality of bits and the modulus value having a second plurality of bits, the first plurality of bits being greater in number of bits than the second plurality of bits, so that the modulus value has a maximum value comparable to N;
- and
- sharing packet traffic load among the N outgoing data paths in response to the modulus value.
A system for distributing respective pluralities of packets belonging to respective flows among a number N of outgoing data paths, said system comprising:
- a distribution value generator for associating with each packet a respective distribution value, the value being generated based, at least in part, upon a respective hash value generated from packet network layer information;
- determining a modulus value of the distribution value, the distribution value having a first plurality of bits and the modulus value having a second plurality of bits, the first plurality of bits being greater in number of bits than the second plurality of bits, so that the modulus value has a maximum value comparable to N;
- and
- a load-sharing element that shares packet traffic load among the outgoing data paths in response to the modulus value.
A system for distributing respective pluralities of packets belonging to respective flows among a number N of outgoing data paths, the system comprising:
- means for generating for each packet a respective distribution value, the value being generated based, at least in part, upon a respective hash value generated from packet network layer information;
- means for determining a modulus value of the distribution value, the distribution value having a first plurality of bits and the modulus value having a second plurality of bits, the first plurality of bits being greater in number of bits than the second plurality of bits, so that the modulus value has a maximum value comparable to N;
- and
- means for sharing packet traffic load among the paths in response to the modulus value.
Computer-readable memory comprising computer-executable program instructions that when executed distribute respective pluralities of packets belonging to respective flows among a number N of outgoing data paths, the instructions when executed also causing:
- generating for each packet a respective distribution value, the value being generated based, at least in part, upon a respective hash value generated from packet network layer information;
- determining a modulus value of the distribution value, the distribution value having a first plurality of bits and the modulus value having a second plurality of bits, the first plurality of bits being greater in number of bits than the second plurality of bits, so that the modulus value has a maximum value comparable to N;
- and
- sharing of packet traffic load among the paths in response to the modulus value.
A network device for distributing respective pluralities of packets belonging to respective flows among a number N of outgoing data paths, comprising a network interface and a processor configured to perform the steps of:
- generating for each packet a respective distribution value, the value being generated based, at least in part, upon a respective hash value generated from packet network layer information;
- determining a modulus value of the distribution value, the distribution value having a first plurality of bits and the modulus value having a second plurality of bits, the first plurality of bits being greater in number of bits than the second plurality of bits, so that the modulus value has a maximum value comparable to N;
- and
- sharing packet traffic load among the paths in response to the modulus value.
A method for distributing packets belonging to different flows among a number N of outgoing data paths, comprising:
- for each packet determining a hash value generated from packet network layer information;
- determining a modulus value of the hash value, the hash value having a first plurality of bits and the modulus value having a second plurality of bits, the first plurality of bits being greater in number of bits than the second plurality of bits, so that the modulus value has a maximum value comparable to N;
- and
- sharing packet traffic load among the N outgoing data paths in response to the modulus value.
A system for distributing packets belonging to different flows among a number N of outgoing data paths, comprising:
- a hash value generator for associating with each packet a hash value generated from packet network layer information;
- a modulus element to determine a modulus value of the hash value, the hash value having a first plurality of bits and the modulus value having a second plurality of bits, the first plurality of bits being greater in number of bits than the second plurality of bits, so that the modulus value has a maximum value comparable to N;
- and
- a load-sharing element that shares packet traffic load among the outgoing data paths in response to the modulus value.
A system for distributing packets belonging to different flows among a number N of outgoing data paths, comprising:
- means for determining for each packet a hash value generated from packet network layer information;
- means for determining a modulus value of the hash value, the hash value having a first plurality of bits and the modulus value having a second plurality of bits, the first plurality of bits being greater in number of bits than the second plurality of bits, so that the modulus value has a maximum value comparable to N;
- and
- means for sharing packet traffic load among the N outgoing data paths in response to the modulus value.
A method for distributing packets belonging to different flows among a number N of outgoing data paths, comprising:
- for each packet determining a hash value generated from packet network layer information;
- determining a modulus value of the hash value by dividing the hash value by a divisor to obtain a remainder, and using the remainder as the modulus value;
- indexing into a load sharing table by the modulus value;
- and
- sharing packet traffic load among the N outgoing data paths in response to an entry in the load sharing table indexed by the modulus value.
A system for distributing packets belonging to different flows among a number N of outgoing data paths, comprising:
- a hash value generator for associating with each packet a hash value generated from packet network layer information;
- a modulus element to determine a modulus value of the hash value by dividing the hash value by a divisor to obtain a remainder, and using the remainder as the modulus value;
- a load sharing table indexed by the modulus value;
- a load-sharing element that shares packet traffic load among the outgoing data paths in response to an entry in the load sharing table indexed by the modulus value.
A system for distributing packets belonging to different flows among a number N of outgoing data paths, comprising:
- means for determining a hash value for each packet, the hash value generated from a packet network layer information;
- means for determining a modulus value of the hash value by dividing the hash value by a divisor to obtain a remainder, and using the remainder as the modulus value;
- means for indexing into a load sharing table by the modulus value;
- and
- means for sharing packet traffic load among the N outgoing data paths in response to an entry in the load sharing table indexed by the modulus value.
Dependencies are inferred from the claim text.