Method and apparatus for efficient call routing

• US 6,115,462 A
• Filed: 01/09/1998
• Issued: 09/05/2000
• Est. Priority Date: 01/09/1998
• Status: Expired due to Term

• Current Assignee: Verizon Laboratories Incorporated (Verizon Communications Inc.)
• Original Assignee: GTE Laboratories Incorporated (Lumen Technologies, Inc.)
• Inventors: Servi, Leslie David, Humair, Salal
• Primary Examiner(s): Zele, Krista
• Assistant Examiner(s): TIEU, BENNY QUOC
• Application Number:
  US09/005,039
• Time in Patent Office: 970 Days
• Field of Search: 379/219, 379/220, 379/221, 379/207, 379/139, 379/265, 379/266, 379/309, 379/93.17, 370/252, 370/468, 370/229, 370/230, 370/235, 370/238, 370/351, 455/445
• US Class Current: 379/221.06
• CPC Class Codes: H04Q 3/66 Traffic distributors

Abstract

A method and apparatus to calculate probabilistic routing parameters to more efficiently route telephone calls from an origin to one of a plurality of call centers. In particular, the rate of calls routed to each gate of each call center is measured for a previous time frame and used to estimate the rate of calls routed to input nodes of a routing network from an origin for a next time frame. Using these estimated rates of calls routed to the input nodes, a quadratic programming technique is used to calculate probabilistic routing parameters. These parameters are modified either automatically or by a network manager to improve the routing efficiency.

Claims

1. A method for modifying probabilistic routing parameters in a routing network for a next time frame, comprising the steps, performed on a processor, of:

receiving information regarding a measured number of calls routed to each of a plurality of output nodes for a previous time frame;

estimating a number of calls routed to each of a first plurality of input nodes origins for the next time frame based on the measured number;

calculating a first plurality of probabilistic routing parameters for the next time frame based on the estimated number; and

displaying the first plurality of probabilistic routing parameters to a network manager, wherein the network manager modifies the first plurality of probabilistic routing parameters.

2. The method according to claim 1, wherein the estimating step further comprises the substep of:

approximating a number of calls routed to each of the plurality of output nodes for the next time frame; and

estimating a number of calls routed to each of a first plurality of input nodes origins for the next time frame based on the approximated number.

3. The method according to claim 1, wherein the calculating step includes using quadratic programming.

4. The method of claim 3, wherein the quadratic programming includes linear constraints.

5. The method of claim 3, wherein the calculating step includes constraining a second plurality of calculated probabilistic routing parameters to be equal, said second plurality of calculated probabilistic routing parameters being a subset of the first plurality of calculated probabilistic routing parameters.

6. The method of claim 1, wherein the step of receiving information includes measuring a number of calls routed to each of a plurality of output nodes.

8. The method of claim 6, wherein the selecting step includes inputting the desired cardinality of the second plurality of input nodes.

7. A method for modifying probabilistic routing parameters in a routine network for a next time frame, comprising the steps, performed on a processor, of:

receiving information regarding a measured number of calls routed to each of a plurality o output nodes for a previous time frame;

estimating a number of calls routed to each of a first of a plurality of input nodes origins for the next time frame based on the measured number;

calculating the first plurality of probabilistic routing parameters for the next time frame based on the estimated number wherein the calculating step includes constraining a second plurality of calculated probabilistic routine, parameters to be equal, said second plurality of calculated probabilistic routine parameters being a subset of the first plurality of calculated probabilistic routing parameters, and wherein the calculating step further comprises the steps of;

determining a first efficiency increase associated with a first node;

storing the first efficiency increase in a location associated with the first input node;

determining the next efficiency increase associated with a next input node;

storing the next efficiency increase in a location associated with the next input node;

repeating the determining and steps for each next input node;

selecting a second plurality of input nodes that provide higher efficiency increases than the other input nodes, the second plurality of input nodes being subset of the first plurality of input nodes; and

calculating a third plurality of probabilistic routing parameters for only the selected second plurality of input nodes and constraining the remaining probabilistic routing parameters to be unchanged from the previous time frame; and

displaying the first plurality of probabilistic routing parameters to a network manager, wherein the network manager modifies the first plurality of probabilistic routing parameters.

9. A method for modifying probabilistic routing parameters in a routing network for a next time frame, comprising the steps, performed on a processor, of:

receiving information regarding a measured number of calls routed to each of a plurality of output nodes for a previous time frame;

estimating a number of calls routed to each of a plurality of input nodes for the next time frame based on the measured number;

calculating a first plurality of probabilistic routing parameters for the next time frame based on the estimated number; and

automatically modifying the first plurality of probabilistic routing parameters.

10. The method of claim 9, wherein the step of calculating a first plurality of probabilistic routing parameters is limited to calculating probabilistic routing parameters for a second plurality of input nodes, said second plurality of input nodes being s subset of the first plurality of input nodes.

11. An apparatus for modifying probabilistic routing parameters of a routing network for a next time frame, comprising:

means for receiving information regarding a measured number of calls routed to each of a plurality of output nodes for a previous time frame;

means for estimating a number of calls routed to each of a plurality of input nodes for the next time frame based on the measured number;

means for calculating a first plurality of probabilistic routing parameters for the next time frame based on the estimated number; and

means for displaying the first plurality of probabilistic routing parameters to a network manager, wherein the network manager modifies the probabilistic routing parameters.

12. The apparatus of claim 11, wherein the means for estimating further comprises:

means for approximating a number of calls routed to each of the plurality of output nodes for the next time frame; and

means for estimating a number of calls routed to each of a plurality of input nodes for the next time frame based on the approximated number.

13. The apparatus of claim 11, wherein the means for calculating includes means for quadratic programming.

14. The apparatus of claim 11, wherein the means for receiving includes means for measuring a number of calls routed to each of a plurality of output nodes.

15. An apparatus for modifying probabilistic routing parameters of a routing network for a next time frame, comprising:

a measuring device to measure a number of calls routed to each of a plurality of output nodes during a previous time frame;

an estimator to estimate for the next time frame a number of calls routed to each of a plurality input nodes based on the measured number; and

a probability calculator to calculate a plurality of probabilistic routing parameters to route calls.

16. A computer program product comprising:

a computer usable medium having computer readable code embodied therein for processing data for a routing network to route calls along communication paths, the computer usable medium comprising;

a receiving module configured to receive information regarding a measured number of calls routed to each of a plurality of output nodes for a current time frame;

an estimating module configured to estimate, based on the measured number, a number of calls routed to each of a plurality of input nodes for the next time frame;

a calculating module configured to calculate a plurality of probabilistic routing parameters for the next time frame based on the estimated number; and

a displaying module configured to display the probabilistic routing parameters to a network manager based on the calculated plurality of probabilistic routing parameters, wherein the network manager modifies the plurality of probabilistic routing parameters.

17. A method for setting probabilistic routing parameters at a call center for a next time frame, comprising the steps, performed on a processor, of:

measuring for each of a plurality of output nodes a number of calls routed to the output node;

storing each measured number at a first plurality of storage locations in a memory, each one of the first plurality of storage locations being associated with one of the plurality of output nodes;

estimating, for each of a plurality of input nodes, a number of calls routed to each input node from the plurality of numbers stored in the first plurality of storage locations;

storing each estimated number at a second plurality of storage locations in the memory, each one of the second plurality of storage locations being associated with one of the plurality of input nodes;

calculating a plurality of probabilistic routing parameters for the next time frame based on the numbers stored at the second plurality of storage locations; and

modifying the probabilistic routing parameters based on the calculated plurality of probabilistic routing parameters.

18. The method according to claim 17, wherein the calculating step includes using the technique of quadratic programming.

19. The method of claim 17, wherein the first plurality of calculated probabilities includes a second plurality of calculated probabilities constrained to be equal.

20. A computer program product comprising:

a computer usable medium having computer readable code embodied therein for processing data for a routing network to route calls along communication paths, the computer usable medium comprising;

a receiving module configured to receive information regarding a measured number of calls routed to each of a plurality of output nodes;

a first storing module configured to store each measured number at a first plurality of storage locations in a memory, each one of the first plurality of storage locations being associated with one of the plurality of output nodes;

an estimating module configured to estimate from the plurality of numbers stored in the first plurality of storage locations for each of a plurality of input nodes a number of calls routed to each of the plurality of input nodes;

the first storing module further configured to store each estimated number at a second plurality of storage location in the memory, each one of the second plurality of storage locations being associated with one of the plurality of input nodes;

a calculating module configured to calculate a plurality of probabilistic routing parameters for the next time frame based on the plurality of measured numbers stored at the second plurality of storage locations; and

a modifying module configured to set the probabilistic routing parameters based on the calculated plurality of probabilistic routing parameters.