System for load balancing between message processors by routing all queued messages to a particular processor selected by a deterministic rule

• US 5,592,672 A
• Filed: 01/18/1996
• Issued: 01/07/1997
• Est. Priority Date: 11/02/1993
• Status: Expired due to Term

• Current Assignee: Intellectual Ventures II LLC (Intellectual Ventures LLC)
• Original Assignee: Bell Communications Research, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Grewal, Kalwant S., Patel, Jagdish A., Wang, Tzyh-Jong
• Primary Examiner(s): Ellis, Richard L.
• Application Number:
  US08/588,279
• Time in Patent Office: 355 Days
• Field of Search: 395/250, 395/650, 370/58.2, 370/60
• US Class Current: 718/105
• CPC Class Codes: H04Q 3/0025 Provisions for signalling

Abstract

A service control point having multiple independent control processor and multiple front end communication processors incorporates a deterministic rule message distribution process for balancing the traffic load among the front end processors from all the independent control processors. The deterministic rule method is applied independently in each control processor and queues all outgoing messages in one of three queues; those that must be transmitted on Linkset-0, those that must be transmitted on Linkset-1, and those that can be transmitted on either linkset. Our message distribution process keeps all messages in queue until message number or timer threshold is reached. The traffic is routed to a front end processor such that the resulting distribution is closest to the expected distribution.

Claims

1. A service controller comprising:

a plurality of front end communication processors each connected to a signalling link in each of two linksets;

at least two independent control processors each connected to each of said front end processors with each said control processor comprising;

a memory for queuing outgoing messages addressed to a signalling link;

counter means for keeping track of the number of messages in queue;

timer means for keeping track of the time messages are in queue; and

message distribution means for using a deterministic rule for routing the messages in said memory to a one of said front end communication processors to control the load on the front and processors as identified by said rule when one of said counter means or said timer means reaches its predetermined threshold value.

2. The service controller of claim 1 wherein said message distribution means comprises:

memory for storing the expected traffic for each of said front end communication processors;

memory for storing the actual number of messages sent to each said front end communication processors;

memory for storing the total number of messages sent to all of said front end communication processors;

means for adding the number of messages in queue obtained from said counter means to the number of messages actually sent to each one of said front end communication processors;

means for calculating the differences between said sums of messages sent and said messages in queue and said expected traffic to be sent to said each front end communication processor; and

means for sending all of said messages in queue as a block to said front end communication processor which has said smallest calculated difference.

3. The service controller of claim 1 wherein said memory comprises three queues, one for queuing messages to be transmitted over a first of said linksets, one for queuing messages to be transmitted over a second of said linksets, and one queue for queuing messages to be transmitted over either of said linksets.

4. The service controller of claim 3 wherein said counter means keeps track of the total number of messages in all of said three queues.

5. The service controller of claim 4 wherein said predetermined threshold value for said counter means equals 12.

6. The service controller of claim 4 wherein said predetermined threshold value for said timer means equals 200 milliseconds.

7. A method for deterministically routing traffic in a service controller from each of a plurality of independent control processors to each of a plurality of front end processors, said method comprising the steps of:

queuing outgoing messages from said control processor;

counting the number of messages in queue;

timing how long the queue contains messages;

tracking the total number of messages sent to each of said front end communication processors;

storing the expected number of messages to be sent to each of said front end communication processors;

determining the difference between the total of the actual traffic sent to each of said front end communication processors and said messages in queue compared to the expected traffic for each of said front end processors; and

sending all the messages in queue to said front end processor with the lowest difference in said determining step when the value determined in said counting step or when the value determined in said timing step equals its predetermined threshold.

8. The method as recited in claim 7 wherein said queuing step further comprises the steps of:

queuing in one queue messages that are to be transmitted over a first linkset;

queuing in a second queue messages that are to be transmitted over a second linkset;

queuing in a third queue messages that can be transmitted over either of said linksets;

wherein said counting step comprises the steps of counting the total messages in all of said three queues; and

wherein said timing step comprises the step of timing the period a message is in any of said three queues.

9. The method as recited in claim 8 wherein said predetermined threshold for said value determined in said counting step equal 12.

10. The method as recited in claim 8 wherein said predetermined threshold for said value determined in said timing step equal 200 milliseconds.

11. The method as recited in claim 7 wherein the difference determined in said determining step for the traffic sent from one control processor to the first front end processor is calculated according the formula ##EQU2## where P_i is the expected ratio of traffic to be sent to each front end processor over all traffic sent, where N_i is the number of messages sent to each front end processor i, where T is the total number of messages processed by said control processor, where n is the number of messages in said queue, and where z is the total number of front end processors.

12. The method as recited in claim 11 wherein the difference determined in said determining step for the traffic sent from one control processor to the X^th front end processor is calculated according the formula ##EQU3## where P_i is the expected ratio of traffic to be sent to each front end processor over all traffic sent, where N_i is the number of messages sent to each front end processor i, where T is the total number of messages processed by said control processor, where n is the number of messages in said queue, and where z is the total number of front end processors.

13. A method for minimizing traffic congestion from multiple independent control processors routing incoming message traffic arriving randomly to multiple front end communication processors for distribution as outgoing messages to alternate linksets, said method comprising:

queuing said outgoing messages in one of three queues depending on whether such outgoing messages are to be distributed over one or the other of said linksets or may be distributed over either of said linksets;

counting the number of messages in each queue;

timing how long said queues contain messages, and

upon either said counting step or said timing step reaching its predetermined threshold value transmitting said blocks of messages to the one front end communication processor which has the lowest difference of messages sent and in queue to the number of messages expected to be received at said one front end communication processor.