Load balancing and overload control in a distributed processing telecommunications system

• US 4,974,256 A
• Filed: 06/30/1989
• Issued: 11/27/1990
• Est. Priority Date: 06/30/1989
• Status: Expired due to Term

• Current Assignee: American Telephone & Telegraph Company (AT&T, Inc.), Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: AT&T, Inc.
• Inventors: Cyr, Bernard L., Lee, Tzongyu P., Kaufman, Joseph S.
• Primary Examiner(s): Brown, Thomas W.
• Application Number:
  US07/375,102
• Time in Patent Office: 515 Days
• Field of Search: 379/113, 379/269, 379/59
• US Class Current: 379/112.04
• CPC Class Codes: H04M 3/365 Load metering of control unit
• CPC Class Codes: H04Q 3/54591 Supervision, e.g. fault localisation, traffic measurements, avoiding errors, failure recovery, monitoring, statistical analysis
• CPC Class Codes: H04W 28/088 among core entities

Abstract

This invention relates to a method of allocating new telecommunications cells to one of a plurality of processors, and to control acceptance of new calls when in overload. The method is based on measuring the real time occupancy of each processor periodically, and allocating new calls for the following period in such a way as to attempt to make each processor'"'"'s occupancy approach the average occupancy of all the processors. An overload state is detected when the average occupancy of the processors in one period exceeds a predetermined threshold, e.g., 90%. When this happens, load is shed in an amount calculated to restore the average occupancy to the threshold value over a number of periods of time. Advantageously, this method optimizes the call processing capacity of the processors.

Claims

1. In a distributed multiprocessing telecommunications control system comprising a plurality of processors each for processing calls, a method of allocating new calls to ones of said plurality of processors comprising the steps of:

receiving a measurement of real time work occupancy of each of said plurality of processors; and

responsive to said received measurements, adjusting an allocation of new calls to each processor to equalize the occupancies of each of said processors.

2. In a distributed multiprocessing telecommunications control system comprising a plurality of processors each for processing calls, a method of allocating new calls to ones of said plurality of processors comprising the steps of:

receiving a measurement of real time work occupancy of each of said plurality of processors;

responsive to said received measurements, adjusting an allocation of new calls to each processor to equalize the occupancies of each of said processors;

detecting that an average of said measured occupancies of said processors exceeds a predetermined threshold; and

shedding a fraction of new calls, said fraction determined to change an average occupancy of said processors to approximately equal said threshold.

3. The method of claim 2 wherein said shedding comprises adjusting said shed fraction by a multiple of a difference between a predetermined threshold value and said average of said measured occupancies of said plurality of processors.

4. The method of claim 2 wherein said shed fraction is determined periodically by an algorithm:

##EQU4## wherein D₁ represents said shed fraction for a next period, P₀ represents a fraction of calls accepted during a period immediately prior to said next period, T represents a predefined constant representing an average occupancy of said plurality of processors at a threshold of overload of said telecommunications control system, A represents average measured occupancy of said plurality of processors during said prior period and G₂ represents a predetermined gain factor.

5. In a distributed multiprocessing telecommunications control system comprising a plurality of processors each for processing calls, a method of allocating new calls to ones of said plurality of processors comprising the steps of:

receiving a measurement of real time work occupancy of each of said plurality of processors; and

responsive to said received measurements, adjusting an allocation of new calls to each processor to equalize the occupancies of each of said processors;

wherein said adjusting is performed periodically and comprises adding to an allocated fraction for each processor for a prior period a predetermined multiple of a difference between an occupancy of said each processor during said prior period and an average occupancy of said plurality of processors during said prior period.

6. The method of claim 5 wherein said allocated fraction for an i'"'"'th one of said plurality of processors is determined by an algorithm:

space="preserve" listing-type="equation">S.sub.1i =S.sub.0i +(A-a.sub.i)G.sub.1,

wherein S_1i, S_0i represent an allocated fraction for said i'"'"'th processor for a next and said prior period, respectively, A represents an average occupancy of said plurality of processors during said prior period, a_i represents an occupancy of said i'"'"'th processor during said prior period, and G₁ represents a predetermined gain factor.

7. In a distributed multiprocessing telecommunications control system comprising a plurality of processors each for processing calls, a method of allocating new calls to ones of said plurality of processors comprising the steps of:

receiving a measurement of real time work occupancy of each of said plurality of processors; and

responsive to said received measurements, adjusting an allocation of new calls to each processor to equalize the occupancies of each of said processors;

wherein said occupancy of each of said processors is measured periodically over the same period, and said adjusting is performed at a beginning of each period.

8. The method of claim 7 wherein each of said processors is polled periodically to transmit said measurement.

9. A method of assigning work to a plurality of processors comprising:

determining a work occupancy for each of said processors;

responsive to said occupancy determining, adjusting allocation fractions of new work for each of said processors toward work occupancy equalization among said processors; and

thereafter allocating new work to said processors based on said adjusted allocation fractions.

10. In a distributed multiprocessing system comprising a plurality of processors each for performing data processing operations in response to requests, a method of allocating new requests to ones of said plurality of processors comprising the steps of:

measuring a work occupancy of each of said plurality of processors;

responsive to said measuring, periodically adjusting allocation fractions of new work requests for each processor toward work occupancy equalization among said processors; and

thereafter, allocating new work to said processors based on said adjusted allocation fractions.

11. The method of claim 10 wherein said adjusting comprises adding to an allocation fraction for each processor for a prior period a predetermined multiple of a difference between an occupancy of said each processor during said prior period and an average occupancy of said plurality of processors during said prior period.

12. In a distributed multiprocessing telecommunications control system comprising a plurality of processors each for processing calls, a method of allocating new calls to ones of said plurality of processors comprising the steps of:

measuring a work occupancy of each of said plurality of processors;

periodically adjusting a fraction of new calls to be allocated to each processor in such manner that the occupancies of each of said plurality of processors are adjusted toward equalization;

detecting that an average of said measured occupancies of said processors exceeds a predetermined threshold; and

shedding a fraction of new calls, said fraction determined to attempt to achieve an average occupancy of said processors approximately equal to said threshold;

wherein said shedding comprises adjusting said shed fraction by a multiple of a difference between a predetermined threshold value and a measured average occupancy of said plurality of processors;

wherein said shed fraction is determined periodically by an algorithm;

##EQU5## wherein D₁ represents said shed fraction for a next period, P₀ represents a fraction of calls accepted during a period immediately prior to said next period, T represents a predefined constant representing an average occupancy of said plurality of processors at a threshold of overload of said telecommunications control system, A represents average measured occupancy of said plurality of processors during said prior period and G₂ represents a predetermined gain factor;

wherein said adjusting comprises adding to an allocated fraction for each processor for a prior period a predetermined multiple of a difference between an occupancy of said each processor during said prior period and an average occupancy of said plurality of processors during said prior period;

wherein said allocated fraction for an i'"'"'th one of said plurality of processors is calculated by a formula;

space="preserve" listing-type="equation">S.sub.1i =S.sub.0i +(A-a.sub.i)G.sub.1,

wherein S_1i, S_0i represent an allocated fraction for said i'"'"'th processor for a next and said prior period, respectively, A represents an average occupancy of said plurality of processors during said prior period, a_i represents an occupancy of said i'"'"'th processor during said prior period, and G₁ represents a predetermined gain factor; and

wherein said occupancy of each of said processors is measured periodically over the same period, and said adjusting is performed at a beginning of each period.

13. In a distributed multiprocessing telecommunications control system, means for allocating new calls to ones of a plurality of call control processors, comprising:

a plurality of call control processors, each operative under the control of a first program, for measuring its own real time work occupancy; and

processor means, operative under the control of a second program and responsive to said measuring real time work occupancy of each of said call control processors, for adjusting an allocation of new calls to each of said call control processors to equalize said real time work occupancies of each of said call control processors.

14. The means for allocating new calls of claim 13 wherein said call control processors are further operative under the control of said first program for measuring said occupancies periodically and for reporting said measurements to said processor means periodically.

15. The means for allocating new calls of claim 13 wherein said processor means is further operative under the control of said second program to determine whether an average of said measured occupancies exceeds a predetermined threshold, and, responsive to said determination, for controlling the shedding of a fraction of new calls, said fraction determined to change an average occupancy of said call control processors to approximately equal said threshold.