Method for load balancing in a multi-processor system where arising jobs are processed by a plurality of processors under real-time conditions

• US 5,655,120 A
• Filed: 11/06/1996
• Issued: 08/05/1997
• Est. Priority Date: 09/24/1993
• Status: Expired due to Fees

• Current Assignee: Nokia Siemens Networks GmbH & Company KG (Nokia Corporation)
• Original Assignee: Siemens AG
• Inventors: Witte, Martin, Oehlerich, Joerg, Held, Walter
• Primary Examiner(s): Kriess, Kevin A.
• Assistant Examiner(s): Toplu, Lucien
• Application Number:
  US08/743,673
• Time in Patent Office: 272 Days
• Field of Search: 395/675, 379/309
• US Class Current: 718/105
• CPC Class Codes: G06F 2209/5022 Workload threshold
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/5088 involving task migration
• CPC Class Codes: H04M 3/365 Load metering of control unit
• CPC Class Codes: H04Q 3/5455 Multi-processor, parallelism, distributed systems

Abstract

Method for load handling in a multiprocessor system, particularly a multiprocessor system of a communication system, whereby arising jobs can be processed by a plurality of processors under real-time conditions. When individual processors proceed into overload due to locally heavy load situations, then a discharge of the local overload is achieved in that further requests arriving at the processor in this load situation are forwarded insofar as possible or necessary to other processors that are not overloaded.

Claims

1. A method for lead balancing in a multi-processor system of a communication system, comprising the steps of:

processing arising jobs by a plurality of processors under real-time conditions;

calculating with each processor a load state thereof so as to evaluate an actual load state by direct recognition of a processing time being given to each processor in order to deal with tasks of the respective processor;

informing each of all of the plurality of processors of the load states of all of the other processors within a time grid;

dependent on an upward crossing of a specific value of a load state of a particular processor and dependent on the load states of the other processors, transferring from the particular processor at least a part of the jobs arising at it to the other processors;

determining a value indicative of a number of the jobs to be distributed away to the other processors, and making a decision as to whether a specific pending job is to be distributed by forming a quotient of jobs previously distributed in a time interval with a plurality of all incoming jobs, comparing that quotient to said value indicative of the number of jobs to be distributed away, and when the quotient is greater than the value indicating the number of jobs to be distributed away, the specific pending job is distributed;

distributing the transferred jobs onto the other processors in conformity with the load states of said other processors; and

transferring from said particular processor only so many jobs until the load state of said particular processor again falls below said specific value.

2. A method according to claim 1 including the step of defining the load state of each processor as a quantified value.

3. A method according to claim 2 including the step of providing said quantified value defining said load states with a hysteresis value for avoiding overshoots upon entry into overload defined by said crossing of said specific value.

4. A method according to claim 1 including the step of informing each processor of the load states of the other processors with an "each-informs-each" communication from individual control managers of the respective processors to all other control managers of the other processors in the communication system.

5. A method according to claim 1 including the step of utilizing a load control manager in each processor to receive and process the load states sent to the particular processor from the other processors.

6. A method according to claim 5 including the step of storing in the particular processor in tables corresponding to said time grid the load states received from the other processors.

7. A method according to claim 1 including the step of determining which processors are to receive the transfer jobs from the particular processor dependent on the respective load states of the other processors.

8. A method according to claim 1 including the step of raising or lowering a number of jobs which are transferred from said particular processor dependent on the respective load states of the other processors.

9. A method according to claim 1 including the step of determining how many jobs are to be transferred away from said particular processor in case of an overload based on an aggregate result from numbers of jobs which can be additionally assumed by the other processors.

10. A method according to claim 1 wherein one of the group of processors is a specifically defined processor which has a centralized load control master, and wherein the said load control master collects the load states of the other processors and then transmits collected information to all processors.

11. A method for load balancing in a multi-processor system of a communication system which is receiving calls, comprising the steps of:

calculating with each processor a load state thereof so as to evaluate an actual load state by direct recognition of a processing time being given to each processor in order to deal with tasks of the respective processor;

informing each of all of the plurality of processors of the load states of all of the other processors;

dependent on an upward crossing of a specific value of a load state of a particular processor and dependent on the load states of the other processors, transferring from the particular processor at least a part of the calls arising at it to the other processors;

determining a value indicative of a number of the calls to be distributed away to the other processors, and making a decision as to whether a specific pending call is to be distributed by forming a quotient of calls previously distributed in a time interval with a plurality of all incoming calls, comparing that quotient to said value indicative of the number of calls to be distributed away, and based on the comparison, deciding whether the specific pending call is distributed;

distributing the transferred jobs onto the other processors in conformity with the load states of said other processors; and

transferring from said particular processor only so many calls until the load state of said particular processor again falls below said specific value.