Load balancing and overload control in a distributed processing telecommunications system

Claim 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; and responsive to said received measurements, adjusting an allocation of new calls to each processor to equalize the occupancies of each of said processors.

Claim 3

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.

Claim 4

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.

Claim 5

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.

Claim 6

The method of claim 2 wherein said shed fraction is determined periodically by an algorithm: ##EQU4## wherein D 1 represents said shed fraction for a next period, P 0 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 2 represents a predetermined gain factor.

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

Claim 8

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.

Claim 9

The method of claim 5 wherein said allocated fraction for an i'th one of said plurality of processors is determined by an algorithm: 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 1 represents a predetermined gain factor.

Claim 10

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.

Claim 11

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.

Claim 12

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

Claim 15

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.

Claim 16

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.

Claim 17

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.

Claim 18

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 1 represents said shed fraction for a next period, P 0 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 2 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: 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 1 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.

Claim 19

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 1 represents said shed fraction for a next period, P 0 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 2 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: 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 1 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.

Claim 20

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.

Claim 21

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.

Claim 22

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.

Claim 23

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.