System and method for integrated overload control and message distribution

• US 5,754,786 A
• Filed: 09/13/1996
• Issued: 05/19/1998
• Est. Priority Date: 09/13/1996
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Diaz, Alvaro H., Milito, Rodolfo Alberto
• Primary Examiner(s): Treat, William M.
• Application Number:
  US08/713,565
• Time in Patent Office: 613 Days
• Field of Search: 395/200.53, 395/675, 379/112, 379/309
• US Class Current: 709/223
• CPC Class Codes: H04Q 2213/13107 Control equipment for a part of the connection, distributed control, co-processing
• CPC Class Codes: H04Q 2213/13274 Call rejection, call barring
• CPC Class Codes: H04Q 2213/13336 Store & forward, messaging systems
• CPC Class Codes: H04Q 2213/13344 Overflow
• CPC Class Codes: H04Q 2213/13352 Self-routing networks, real-time routing
• CPC Class Codes: H04Q 3/66 Traffic distributors

Abstract

A message distribution system having multiple message processors provides integrated overload control and message distribution. An additional "dummy" message processor is established by the system, to which a certain fraction of messages is assigned as though it were a real processor, thereby accomplishing rejection of that fraction of messages. The fraction to be rejected is determined in real time based on the states of the various processors, which also is the basis for the allocation among the processors of those messages that are not rejected.

Claims

1. A method for controlling overload and distributing messages among message processors in a system, said system having a plurality of message processors and at least one distribution node for receiving messages and distributing said messages to said message processors, wherein different ones of said messages occupy respective ones of said message processors for different durations, said method comprising the steps of:

providing a virtual message processor in addition to said plurality of message processors, whereby messages arriving at said virtual message processor are denied processing by said system;

monitoring operation of said system to determine a respective level of activity for each of said message processors and for said system;

calculating from said respective levels of activity a desired distribution of messages among said message processors and said virtual message processor; and

distributing messages from said distribution node to said message processors and said virtual message processor in accordance with said calculated desired distribution.

2. The method of claim 1 wherein:

said monitoring and calculating steps occur at regular intervals; and

said calculated desired distribution is used in said distributing step between said regular intervals.

3. The method of claim 2 wherein said monitoring and calculating steps are performed by said at least one distribution node.

4. The method of claim 3 wherein:

when said system comprises a plurality of said distribution nodes, said monitoring and calculating steps are performed independently by each of said distribution nodes; and

each of said distribution nodes distributes said messages to said message processors in accordance with a respective independently calculated desired distribution.

5. The method of claim 4 wherein said regular intervals are identical for all of said distribution nodes.

6. The method of claim 5 wherein said regular intervals occur at staggered times among said distribution nodes.

7. The method of claim 4 wherein said regular intervals are different for different ones of said distribution nodes.

8. The method of claim 2 further comprising establishing a respective credit bank corresponding to each said message processor and said virtual message processor;

wherein;

said monitoring and calculating steps comprise;

whenever a message arrives at a distribution node, deriving from said desired distribution a respective fractional credit to be deposited in each respective credit bank, said respective fractional credits summing to one credit unit; and

said distributing step comprises;

identifying one of said credit banks having a higher credit balance than any other one of said credit banks,

distributing said message to one of said message processors corresponding to said one of said banks having said higher credit balance, and

subtracting a unit of credit from said one of said banks having said higher credit balance.

9. The method of claim 1 wherein:

when said system comprises a plurality of said distribution nodes, said monitoring and calculating steps are performed independently by each of said distribution nodes; and

each of said distribution nodes distributes said messages to said message processors in accordance with a respective independently calculated desired distribution.

10. The method of claim 1 wherein, when said system comprises at least one system processor associated with said message processors, said monitoring step comprises monitoring activity of said at least one system processor as part of said level of activity for said system.

11. The method of claim 1 wherein said calculating step comprises calculating a desired distribution in which a fraction of arriving messages is directed to said virtual message processor, and all messages not directed to said virtual message processor are distributed uniformly among said message processors.

12. The method of claim 1 wherein said calculating step comprises calculating a desired distribution in which a fraction of arriving messages is directed to said virtual message processor, and all messages not directed to said virtual message processor are distributed among said message processors according to said levels of activity of said message processors.

13. The method of claim 12 wherein:

said monitoring step comprises determining said levels of activity as a function of number of messages being serviced by each of said message processors; and

said calculating step comprises calculating a desired distribution in which a fraction of arriving messages is directed to said virtual message processor, and all messages not directed to said virtual message processor are distributed among said message processors in inverse proportion to said numbers of messages being serviced by each of said message processors.

14. The method of claim 12 wherein:

said monitoring step comprises determining said levels of activity as a function of utilization of each of said message processors; and

said calculating step comprises calculating a desired distribution in which a fraction of arriving messages is directed to said virtual message processor, and all messages not directed to said virtual message processor are distributed among said message processors in inverse proportion to said utilization of each of said message processors.

15. A message processing system comprising:

a plurality of message processors;

at least one distribution node for receiving messages and distributing said messages to said message processors, wherein different ones of said messages occupy respective ones of said message processors for different durations;

a virtual message processor in addition to said plurality of message processors, whereby messages arriving at said virtual message processor are denied processing by said system;

a monitor of said system to determine a respective level of activity for each of said message processors and for said system; and

a distribution calculator for calculating from said respective levels of activity a desired distribution of messages among said message processors and said virtual message processor;

wherein;

messages are distributed from said distribution node to said message processors and said virtual message processor in accordance with said calculated desired distribution.

16. The system of claim 15 wherein:

said monitor and said distribution calculator operate at regular intervals; and

said calculated desired distribution is used to distribute said messages between said regular intervals.

17. The system of claim 16 wherein each said at least one distribution node functions as said monitor and said distribution calculator.

18. The system of claim 17 comprising a plurality of said distribution nodes;

wherein;

each of said distribution nodes operates independently as said monitor and said distribution calculator; and

each of said distribution nodes distributes said messages to said message processors in accordance with a respective independently calculated desired distribution.

19. The system of claim 18 wherein said regular intervals are identical for all of said distribution nodes.

20. The system of claim 19 wherein said regular intervals occur at staggered times among said distribution nodes.

21. The system of claim 18 wherein said regular intervals are different for different ones of said distribution nodes.

22. The system of claim 16 further comprising a respective credit bank corresponding to each said message processor and said virtual message processor;

wherein;

whenever a message arrives at a distribution node, said distribution calculator derives from said desired distribution a respective fractional credit to be deposited in each respective credit bank, said respective fractional credits summing to one credit unit; and

messages are distributed from said distribution node to one of said message processors and said virtual message processor by;

identifying one of said credit banks having a higher credit balance than any other one of said credit banks,

distributing said message to one of said message processors corresponding to said one of said banks having said higher credit balance, and

subtracting a unit of credit from said one of said banks having said higher credit balance.

23. The system of claim 15 comprising a plurality of said distribution nodes;

wherein;

each of said distribution nodes operates independently as said monitor and said distribution calculator; and

each of said distribution nodes distributes said messages to said message processors in accordance with a respective independently calculated desired distribution.

24. The system of claim 15 further comprising at least one system processor associated with said message processors;

wherein;

said monitor monitors activity of said at least one system processor as part of said level of activity for said system.

25. The system of claim 15 wherein said distribution calculator calculates a desired distribution in which a fraction of arriving messages is directed to said virtual message processor, and all messages not directed to said virtual message processor are distributed uniformly among said message processors.

26. The system of claim 15 wherein said distribution calculator calculates a desired distribution in which a fraction of arriving messages is directed to said virtual message processor, and all messages not directed to said virtual message processor are distributed among said message processors according to said levels of activity of said message processors.

27. The system of claim 26 wherein:

said monitor determines said levels of activity as a function of number of messages being serviced by each of said message processors; and

said distribution calculator calculates a desired distribution in which a fraction of arriving messages is directed to said virtual message processor, and all messages not directed to said virtual message processor are distributed among said message processors in inverse proportion to said numbers of messages being serviced by each of said message processors.

28. The system of claim 26 wherein:

said monitor determines said levels of activity as a function of utilization of each of said message processors; and

said distribution calculator calculates a desired distribution in which a fraction of arriving messages is directed to said virtual message processor, and all messages not directed to said virtual message processor are distributed among said message processors in inverse proportion to said utilization of each of said message processors.

29. A method for controlling overload in a distributed message processing system, said system having a plurality of at least one type of processor, one of said at least one type being message processor, wherein each message to be processed is routed to one of said message processors as said message arrives, said method being for maintaining performance targets for said system, said method comprising the steps of:

measuring, at regular intervals, performance of processors in said system to obtain performance measurements;

filtering said performance measurements to minimize random fluctuations in performance to obtain consistent filtered performance values;

establishing a respective bank for each respective message processor, and a virtual bank for determining a rate of rejection of arriving messages;

adjusting a throttling parameter in response to said filtered performance values, said throttling parameter functioning as credit to said virtual bank for determining a rate of rejection of arriving messages;

as each said message arrives, allocating credits to each said respective bank, other than said virtual bank, in inverse proportion to at least one of (a) utilization, (b) buffer occupancy, and (c) delay, of said respective message processor;

as each said message arrives, finding that one of said respective banks and virtual bank having a maximum credit, and routing said arriving message to said respective message processor when said one of said respective banks and virtual bank having a maximum credit is one of said banks, and rejecting said message when said one of said respective banks and virtual bank having a maximum credit is said virtual bank; and

subtracting a unit of credit from said one of said respective banks and virtual bank upon said routing or rejection.