Load balancing system, apparatus and method

• US 6,768,716 B1
• Filed: 04/18/2000
• Issued: 07/27/2004
• Est. Priority Date: 04/10/2000
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Buchmann, Peter, Webb, David J., Abel, François G., Engbersen, Antonius, Luijten, Ronald P., Herkersdorf, Andreas
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): LEE, CHI HO A
• Application Number:
  US09/551,049
• Time in Patent Office: 1,561 Days
• Field of Search: 709/105, 370/230, 370/235, 370/389, 370/392, 370/532-536, 370/542-544, 370/468
• US Class Current: 370/230
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: H04L 69/12 Protocol engines
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A real-time load-balancing system for distributing a sequence of incoming data packets emanating from a high speed communication line to a plurality of processing means, each operating at a capacity that is lower than the capacity of the high speed communication line; the system according to the invention comprises: a parser capable of extracting a configurable set of classifier bits from the incoming packets for feeding into a compression means; the compression means is capable of reducing a bit pattern of length K to a bit pattern having a length L which is a fraction of K; a pipeline block for delaying incoming packets until a load balancing decision is found, and an inverse demultiplexer for receiving a port identifier output from said compression means as selector and for directing pipelined packets to the appropriate output port.

Claims

1. A real-time load-balancing system for distributing a sequence of incoming data packets emanating from a high speed communication line to a plurality of processing means, each operating at a capacity that is lower than the capacity of the high speed communication line, said system comprising:

a parser means capable of extracting a configurable set of classifier bits from the incoming packets for feeding into a compression means;

said compression means being capable of reducing a bit pattern of length K to a bit pattern having a length L which is a fraction of K;

a pipeline block for delaying incoming packets until a load balancing decision is found, and

an inverse demultiplexer for receiving a port identifier output from said compression means as selector and for directing pipelined packets to the appropriate output port.

2. The system of claim 1 additionally comprising a lookup memory for outputting a port identifier based on an index computed by said compression means, wherein each entry into said lookup memory is capable of dynamic coordination to any output port of said system so as to populate a large number of consumer unit requests per lookup memory entry and to collect lookup memory locations that are no longer in use for providing flexibility to perform a load balancing by providing a timeout per memory entry.

3. The system of claim 1 additionally comprising an extended classifier means.

4. The system of claim 1 additionally comprising a feedback loop for controlling load distribution and for allocating data packets to said data processing means.

5. The system of claim 1 wherein said compression means is a nonlinear hashing function.

6. A method for distributing a sequence of incoming data packets emanating from a high speed communication line to a plurality of processing means, each processing means operating at a capacity that is lower than the capacity of the high speed communication line, said method comprising:

providing a parser means for extracting a configurable set of classifier bits from the incoming packets for feeding into a compression means;

said compression means reducing a bit pattern of length K to a bit pattern having a length L which is a fraction of K;

a pipeline block for delaying incoming packets until a load balancing decision is found, and

an inverse demultiplexer for receiving a port identifier output from said compression means as selector and for directing pipelined packets to the appropriate output port.

7. The method of claim 6 comprising additionally providing a lookup memory for outputting a port identifier based on an index computed by said compression means, wherein each entry into said lookup memory is coordinated dynamically to any output port and to populate a large number of consumer unit requests per lookup memory entry while collecting lookup memory locations that are no longer in use for providing flexibility to perform a load balancing by providing a timeout per memory entry.

8. The method of claim 6 comprising additionally providing an extended classifier means.

9. The method of claim 6 additionally comprising providing a feedback loop for controlling load distribution and for allocating data packets to said data processing means.

10. The method of claim 8 wherein a nonlinear hashing function said is used as said compression means.

11. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing distribution of a sequence of incoming data packets emanating from a high speed communication line to a plurality of processing means, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 6.

12. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for distributing a sequence of incoming data packets emanating from a high speed communication line to a plurality of processing means, said method comprising the steps of claim 6.

13. An real-time load-balancing apparatus for distributing a sequence of incoming data packets emanating from a high speed communication line to a plurality of processing means, each operating at a capacity that is lower than the capacity of the high speed communication line, said apparatus comprising:

a parser, the parser capable of extracting a configurable set of classifier bits from the incoming packets for feeding into a compressing module, said compressing module being capable of reducing a bit pattern of length K to a bit pattern having a length L which is a fraction of K;

a pipeline blocker for delaying incoming packets until a load balancing decision is found, and

an inverse demultiplexer for receiving a port identifier output from said compressing module as selector and for directing pipelined packets to an appropriate output port.

14. The apparatus of claim 13 additionally comprising a lookup memory for outputting a port identifier based on an index computed by said compressing module, wherein each entry into said lookup memory is capable of dynamic coordination to any output port of said apparatus so as to populate a large number of consumer unit requests per lookup memory entry and to collect lookup memory locations that are no longer in use for providing flexibility to perform a load balancing by providing a timeout per memory entry.

15. The apparatus of claim 13 additionally comprising an extended classifier module.

16. The apparatus of claim 13 additionally comprising a feedback loop for controlling load distribution and for allocating data packets to said data processing means.

17. The apparatus of claim 13 wherein said compressing module uses a nonlinear hashing function.