Load sharing across flows

• US 6,603,765 B1
• Filed: 07/21/2000
• Issued: 08/05/2003
• Est. Priority Date: 12/31/1997
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Dejanovic, Thomas, Wilford, Bruce A.
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): LY, ANH VU H
• Application Number:
  US09/621,415
• Time in Patent Office: 1,110 Days
• Field of Search: 370/230.1, 370/235, 370/392, 370/396, 370/398, 370/395.31, 370/422, 370/395.32, 370/395.3, 370/395.42
• US Class Current: 370/395.32
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/10015 Access to distributed or replicated servers, e.g. using brokers
• CPC Class Codes: H04L 9/40 Network security protocols

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.

Claims

1. 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.

2. A method as in claim 1, wherein said steps for associating include associating a single distribution value for substantially all packets in a respective one of said flows.

3. A method as in claim 1, wherein said distribution value for each said packet is based upon, at least in part, a respective packet source address and a respective packet destination address.

4. A method as in claim 1, wherein said distribution value for each said packet is based upon, at least in part, a respective packet source port and a respective packet destination port.

5. A method as in claim 1, wherein said distribution value for each said packet is based upon, at least in part, a respective packet protocol type.

44. A computer readable media, comprising:

the computer readable media having instructions for execution on a processor for the practice of the method of claim 1 or claim 26 or claim 41.

45. Electromagnetic signals propagating on a computer network, comprising:

the electromagnetic signals carrying information containing instructions for execution on a processor for the practice of the method of claim 1 or claim 26 or claim 41.

6. 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.

7. A system as in claim 6, wherein:

said distribution value generator is operative to assign a single distribution value for substantially all packets in a respective one of said flows.

8. A system as in claim 6, wherein said distribution value is based upon, at least in part, a respective packet source address and a respective packet destination address.

9. A system as in claim 6, wherein said distribution value is based, at least in part, upon a respective packet source port and a respective packet destination port.

10. A system as in claim 6, wherein said distribution value is based upon, at least in part, a respective packet protocol type.

11. 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.

12. A system as in claim 11, wherein the means for generating includes means for associating a single distribution value for substantially all packets in a respective one of said flows.

13. A system as in claim 11, wherein the distribution value is based upon, at least in part, packet source and destination addresses.

14. A system as in claim 11, wherein the distribution value is based upon, at least in part, packet source and destination ports.

15. A system as in claim 11, wherein the distribution value is based upon, at least in part, packet protocol information.

16. 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.

17. Memory as in claim 16, wherein the generation of the respective distribution value includes associating a single distribution value with substantially all packets in a respective one of said flows.

18. Memory as in claim 16, wherein the distribution value is based upon, at least in part, packet source and destination addresses.

19. Memory as in claim 16, wherein the distribution value is based upon, at least in part, packet source and destination ports.

20. Memory as in claim 16, wherein the distribution value is based upon, at least in part, packet protocol information.

21. 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.

22. A device as in claim 21 wherein the step of generating includes associating a single distribution value for substantially all packets in a respective one of said flows.

23. A device as in claim 21, wherein the distribution value is based upon, at least in part, packet source and destination addresses.

24. A device as in claim 21, wherein the distribution value is based upon, at least in part, packet source and destination ports.

25. A device as in claim 21, wherein the distribution value is based upon, at least in part, packet protocol information.

26. 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.

27. The method as in claim 26, further comprising:

determining the modulus value by dividing the hash value by a divisor to obtain a remainder, and using the remainder as the modulus value.

28. The method as in claim 27 further comprising:

using as the divisor the number of outgoing data paths.

29. The method as in claim 27 further comprising:

using as a divisor a number which yields a desired range for the remainder, the range being comparable to the number of outgoing data paths.

30. The method as in claim 26 further comprising:

indexing into a load sharing table by the modulus.

31. 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.

32. The system as in claim 31, further comprising:

a division circuit to determine the modulus value by dividing the hash value by a divisor to obtain a remainder, and using the remainder as the modulus value.

33. The system as in claim 31 further comprising:

the number of outgoing data paths used as the divisor.

34. The system as in claim 31 further comprising:

a number used as the divisor to yield a desired range for the remainder, the range being comparable to the number of outgoing data paths.

35. The system as in claim 31 further comprising:

a load sharing table indexed by the modulus.

36. 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.

37. The system as in claim 36, further comprising:

means for determining the modulus value by dividing the hash value by a divisor to obtain a remainder, and using the remainder as the modulus value.

38. The system as in claim 36, further comprising:

means for using as the divisor the number of outgoing data paths.

39. The system as in claim 36 further comprising:

means for using as a divisor a number which yields a desired range for the remainder, the range being comparable to the number of outgoing data paths.

40. The system as in claim 37 further comprising:

means for indexing into a load sharing table by the modulus.

41. 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.

42. 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.

43. 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.