Load sharing across flows

• US 6,111,877 A
• Filed: 12/31/1997
• Issued: 08/29/2000
• 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): SLAVITT, MITCHELL R
• Application Number:
  US09/002,210
• Time in Patent Office: 972 Days
• Field of Search: 370/389, 370/392, 370/394, 370/235, 370/238
• US Class Current: 370/392
• 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 system 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 a sequence of packets among a number N of data paths, said method including steps for

for each packet in said sequence, associating a distribution value therewith, said distribution value having a number of possible values well in excess of said number N;

for each said distribution value, determining a modulus of said distribution value with regard to said number N; and

sharing packet traffic load among a plurality of outgoing data paths in response to said modulus.

2. A method as in claim 1, including steps for partitioning said sequence of packets into a plurality of flows;

wherein said steps for associating include steps for associating a single distribution value for substantially all packets in one of said flows.

3. A method as in claim 1, wherein said distribution value for each said packet is responsive to an address for a sender for said packet and an address for a destination for said packet.

4. A method as in claim 1, wherein said distribution value for each said packet is responsive to a port for a sender for said packet and a port for a destination for said packet.

5. A method as in claim 1, wherein said distribution value for each said packet is responsive to a protocol type for said packet.

6. A method as in claim 1, wherein said distribution value includes a hash function value.

7. A method as in claim 1, wherein said distribution value includes a pseudo-random value.

8. A method as in claim 1, wherein said distribution value includes at least twice as many bits as needed to enumerate said number N.

9. A method as in claim 1, wherein said steps for determining a modulus include steps for

determining a first modulus of a first portion of said distribution value;

determining a second modulus of a combination of said first modulus and a second portion of said distribution value.

10. A method as in claim 1, wherein said steps for determining a modulus include steps for

determining a first modulus of said distribution value with regard to a first divisor;

determining a second modulus of said distribution value with regard to a second divisor; and

selecting between said first modulus and said second modulus in response to said number N.

11. A method as in claim 1, wherein said steps for determining a modulus include steps for

simultaneously determining a plurality of modulus values for said distribution value;

and

selecting among said plurality of modulus values in response to said number N.

12. A method as in claim 1, wherein said steps for sharing packet traffic load include steps for indexing into a table in response to said modulus.

13. A method as in claim 1, wherein said steps for sharing packet traffic load include steps for indexing into a table in response to said modulus, said table having fewer entries than twice said number N.

14. A system for distributing a sequence of packets among a number N of data paths, said system including

a distribution value element coupled to each packet in said sequence, an output of said distribution value element having a number of possible values well in excess of said number N;

a modulus element coupled to said distribution value element; and

a load-sharing element responsive to an output of said modulus element.

15. A system as in claim 14, wherein

said sequence of packets forms a plurality of flows;

and

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

16. A system as in claim 14, wherein said distribution value element is responsive to an address for a sender for each said packet and an address for a destination for each said packet.

17. A system as in claim 14, wherein said distribution value element is responsive to a port for a sender for each said packet and a port for a destination for each said packet.

18. A system as in claim 14, wherein said distribution value element is responsive to a protocol type for each said packet.

19. A system as in claim 14, wherein said distribution value element includes a hash function.

20. A system as in claim 14, wherein said distribution value element includes a uniform distribution element.

21. A system as in claim 14, wherein an output of said distribution value element includes at least twice as many bits as needed to enumerate said number N.

22. A system as in claim 14, wherein said modulus element includes

a first modulus element coupled to a first portion of said distribution value;

a second modulus element coupled an output of said first modulus element and to a second portion of said distribution value.

23. A system as in claim 14, wherein said modulus element includes

a first modulus element coupled to said distribution value and to a first divisor;

a second modulus element coupled to said distribution value and to a second divisor; and

a selector coupled to said first modulus element and to said second modulus element.

24. A system as in claim 14, wherein modulus element includes

a plurality of modulus elements each coupled to said distribution value;

and

a selector coupled to said plurality of modulus elements and to said number N.

25. A system as in claim 14, wherein said load-sharing element includes an indexed table.

26. A system as in claim 14, wherein said load-sharing element includes an indexed table, said table having fewer entries than twice said number N.