Method and apparatus for simulating central queue for distributing call in distributed arrangement of automatic call distributors

• US 6,263,065 B1
• Filed: 03/12/1998
• Issued: 07/17/2001
• Est. Priority Date: 03/18/1997
• Status: Expired due to Term

• Current Assignee: ShoreTel Incorporated (Mitel Networks Corporation)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Durinovic-Johri, Sanja, Levy, Yonatan A., Sabinas, Suhasini V.
• Primary Examiner(s): Matar, Ahmad
• Assistant Examiner(s): Bui, Bing Q.
• Application Number:
  US09/040,223
• Time in Patent Office: 1,223 Days
• Field of Search: 379/265, 379/266, 379/268, 379/269, 379/272, 379/273, 379/309, 379/210
• US Class Current: 379/266.03
• CPC Class Codes: H04M 3/323 for the arrangements providing the connection (test connection, test call, call simulation)
• CPC Class Codes: H04M 3/5125 with remote located operators
• CPC Class Codes: H04M 3/5237 Interconnection arrangements between ACD systems

Abstract

Calls may be distributed and load balancing maintained for a distributed automatic call distributor (ACD) system by simulating a central FIFO queue at the central routing point of the system. The simulated FIFO queue either requires that the number of calls in queue and the oldest call waiting time of calls at each automatic call distributor be periodically provided to the central routing point or event-based data be provided on each call answered in the system or not routed by the central routing point. Deviations from FIFO order of service recorded at the simulated FIFO queue may signal the need for requiring a call at another automatic call distributor. With additional information on agents available, the call removal rate may be estimated. Also, delay estimates may be updated based on comparing actual and estimated delays over time. The routing point may be updated with traffic data through, for example, a known telemarketing operations performance management system (TOPMS) or directly from the automatic call distributors via the toll telecommunications network.

Claims

1. A method for load balancing calls in a distributed automatic call distributor system having a plurality of automatic call distributors, the method comprising steps of:

creating a virtual queue at a routing point in the distributed automatic call distributor system, the virtual queue including a list of individual records, each record containing information relating a call waiting in a queue that is associated with an automatic call distributor of the plurality of automatic call distributors; and

simulating how each call corresponding to a record in the virtual queue is handled in the queue in which the call is waiting based on an update message received from the automatic call distributor associated with the queue in which the call is waiting, the update message containing information relating to a number of calls in the queue associated with the automatic call distributor and information relating to a longest call waiting time in the queue associated with the automatic call distributor.

2. A method as recited in claim 1, wherein the update message further includes information relating to an arrival time for a call waiting in the queue associated with the automatic call distributor,

the method further comprising a step of estimating an expected call waiting delay for each call having a record in the virtual queue based on a number of calls having a record in the virtual queue and the longest call waiting time.

3. A method as recited in claim 2, further comprising a step of periodically receiving the update message from an automatic call distributor.

4. A method as recited in claim 3, wherein the periodically-received update message contains information relating to a number of available agents at the automatic call distributor.

5. A method as recited in claim 2, further comprising a step of estimating a call removal rate for each automatic call distributor based on a call completion rate.

6. A method as recited in claim 5, wherein the call completion rate is based on a number of calls having a record in the virtual queue that are answered.

7. A method as recited in claim 5, wherein the update message includes information relating to a number of available agents at the automatic call distributor, and

wherein the call completion rate is based on the number of available agents at the automatic call distributor and on a number of calls in the virtual queue that are answered.

8. A method as recited in claim 5, wherein the step of estimating the call removal rate includes a step of determining the call completion rate based on an average number of available agents.

9. A method as recited in claim 8, wherein the step of determining the call completion rate is further based on an inflating factor, the inflating factor being based upon call the call completion rate, the average number of available agents and an average call handling time.

10. A method as recited in claim 9, further comprising a step of determining an expected wait time for a call based on a number of calls in the queues associated with each of the automatic call distributors of the plurality of call distributors and the estimated call removal rate.

11. A method as recited in claim 9, further comprising a step of determining a routing decision for a call having a record in the virtual queue when at least one agent is available to take a call, the routing decision being further based on a number of available agents and the estimated call removal rate.

12. A method as recited in claim 1, wherein the step of creating the virtual queue includes steps of:

creating a record in the virtual queue containing information relating to each new call waiting in a queue associated with an automatic call distributor of the plurality of automatic call distributors; and

adding the record to a tail of the virtual queue.

13. A method as recited in claim 12, further comprising a step of periodically receiving the update message from each automatic call distributor, each update message further including information relating to an arrival time for each new call.

14. A method as recited in claim 13, further comprising a step of determining which records in the virtual queue are for calls that are not routed through the routing point.

15. A method as recited in claim 13, further comprising a step of determining a deviation from a first-in, first-out order of service for a call having a record in the virtual queue.

16. A method as recited in claim 15, further comprising a step of requeuing the call at another automatic call distributor based on the determined deviation from the first-in, first-out order of service for the call.

17. A method as recited in claim 1, further comprising a step of routing a call having a record in the virtual queue based on an expected wait time for the call.

18. A method as recited in claim 17, further comprising steps of:

measuring an actual wait time for a call having a record in the virtual queue based on the virtual queue;

determining a difference between the measured wait time for the call and an estimated expected wait time for the call; and

correcting an expected wait time estimate based on the calculated difference between the measured wait time for the call and an estimated expected wait time for the call.

19. A method as recited in claim 1, wherein the update message further including event-based information for the call.

20. A method as recited in claim 19, further comprising a step of updating of the virtual queue based on each received update message.

21. A method as recited in claim 20, further comprising a step of estimating a call removal rate for each respective automatic call distributor based on a call completion rate for each automatic call distributor.

22. A method as recited in claim 21, wherein the call completion rate at an automatic call distributor is based on a calculated number of calls answered at the automatic call distributor.

23. A method as recited in claim 21, wherein the event-based information includes information relating to a number of available agents,

the method further comprising a step of periodically determining the call completion rate based on the available agents and on the number of calls answered having a record in the virtual queue.

24. A method as recited in claim 21, wherein the event-based data includes information relating to available agents, and

wherein the step of estimating the call removal rate includes a step of inflating the call completion rate based on an average number of available agents.

25. A method as recited in claim 24, wherein the step of inflating the call completion rate is based on an inflating factor, the inflating factor being based upon the call completion rate, the average number of available agents and an average call handling time.

26. A method as recited in claim 20, further comprising a step of determining calls having records in the virtual queue that were not routed through the routing point.

27. A routing point in a distributed automatic call distributor system having a plurality of automatic call distributors, the routing point comprising:

a memory storing a virtual queue, the virtual queue being arranged as a first-in, first-out queue and including a list of individual records, each record containing information relating a call waiting in a queue associated with an automatic call distributor of the plurality of automatic call distributors; and

a processor routing calls having records in the virtual queue, the processor receiving an update message from each automatic call distributor, each update message containing information relating to a number of calls in the queue associated with the automatic call distributor and information relating to a longest call waiting time in the queue associated with the automatic call distributor, the processor routing calls based on the number of calls in queues associated with each respective automatic call distributor of the plurality of automatic call distributors, the longest call waiting time and a total number of available agents for each automatic call distributor of the plurality of automatic call distributors.

28. The routing point as recited in claim 27, wherein the update

messages further include information relating to calls in a queues associated with an automatic call distributor of the plurality of automatic call distributors.

29. A routing point in a distributed automatic call distributor system having a plurality of automatic call distributors, the routing point comprising:

a memory storing a virtual queue, the virtual queue being arranged as a first-in, first-out queue and including a list of individual records, each record containing information relating a call waiting in a queue associated with an automatic call distributor of the plurality of automatic call distributors; and

a processor routing calls according to the virtual queue, the routing point receiving an update message from an automatic call distributor containing update event-based information relating to a number of calls in queue associated with the automatic call distributor and information relating to a longest call waiting time in the queue associated with the automatic call distributor.

30. The routing point according to claim 29, wherein the update message further includes information relating to a number of calls in the queue associated with the automatic call distributor and information relating to a longest call waiting time in the queue associated with the automatic call distributor.

31. A method for simulating a queue at a routing point in a distributed automatic call distributor system having a plurality of automatic call distributors, the method comprising steps of:

receiving at the routing point from each automatic call distributor information relating to a longest call waiting time for calls in each queue associated with an automatic call distributor, and

creating a virtual queue at the routing point, the queue containing information representing calls the plurality of queues at each of the distributed automatic call distributors.

32. A method as recited in claim 31, further comprising steps of:

receiving at the routing point information relating to a number of calls in each queue associated with an automatic call distributor and a total number of available agents associated with the automatic call distributor;

determining a call completion rate; and

estimating a call removal rate at each automatic call distributor based on the determined call completion rate.

33. A method as recited in claim 32, wherein the step of determining the call completion rate includes a step of determining a number of calls answered having a record in the virtual queue.

34. A method as recited in claim 32, wherein the step of determining the call completion rate includes a step of determining a number of calls completed based on information relating to available agents and based on a number of calls answered having a record in the virtual queue.

35. A method as recited in claim 32, wherein the step of estimating the call removal rate includes a step of inflating the call completion rate based on an average number of available agents.

36. A method as recited in claim 35, wherein the step of inflating the call completion rate is based on an inflating factor, the inflating factor being related to the call completion rate, the average number of available agents and an average call handling time.

37. A method as recited in claim 31, wherein the step of receiving information relating to the number of calls in each queue associated with an automatic call distributor and the longest call waiting time for calls in each queue associated with an automatic call distributor includes a step of receiving periodic update messages from each automatic call distributor.

38. A method as recited in claim 31, wherein the step of creating the virtual queue at the routing point includes steps of:

creating an entry for the virtual queue for each new call that is in a queue associated with an automatic call distributor; and

adding the entry to a tail of the virtual queue.

39. A method as recited in claim 31, wherein the step of receiving information relating to the number of calls in each queue associated with an automatic call distributor and the longest call waiting time for calls in each queue associated with an automatic call distributor includes a step of receiving periodic update messages from each automatic call distributor.

40. A method as recited in claim 39, further comprising a step of determining which calls having a record in the virtual queue have been answered.

41. A method as recited in claim 40, further comprising a step of determining a deviation from first in, first out order of service for a call having a record in the virtual queue.

42. A method as recited in claim 31, further comprising steps of:

determining a deviation from a first-in, first-out order of service for a call having a record in the virtual queue; and

requeuing the call at another automatic call distributor.

43. A method as recited in claim 31, further comprising steps of:

measuring an actual wait time for a call having a record in the virtual queue based on the virtual queue;

determining a difference between the measured wait time for the call and an estimated expected wait time for the call; and

correcting the estimated expected wait time for the call based on the determined difference between the measured wait time for the call and the estimated expected wait time for the call.

44. A method as recited in claim 31, further comprising a step of forming a list of entries for each call that is to be routed at the routing point.

45. A method for simulating a queue at a routing point in a distributed automatic call distributor system having a plurality of automatic call distributors, the method comprising steps of:

receiving update event-based data contained on an update message for calls to the automatic call distributor system, the update event-based data including information relating to a number of calls and a longest waiting time for calls in each queue associated with an automatic call distributor; and

creating a virtual queue at the routing point, the virtual queue including a list of individual records, each record containing information relating a call waiting in a queue associated with an automatic call distributor of the plurality of automatic call distributor system.

46. A method as recited in claim 45, wherein the step of receiving event-based data includes a step updating records in the virtual queue waiting in a queue associated with each automatic call distributor.

47. A method as recited in claim 45, further comprising a step of determining calls in the virtual queue that are not routed through a routing point.

48. A method as recited in claim 45, wherein the virtual queue is updated with data for each call that is answered.

49. A method as recited in claim 45, further comprising steps of:

receiving event-based data from an automatic call distributor, the event-based data relating to a count of a total number of available agents associated with the automatic call distributor; and

estimating a call removal rate at the automatic call distributor based on a call completion rate.

50. A method as recited in claim 49, wherein the call completion rate is based on a determined number of answered calls having a record in the virtual queue.

51. A method as recited in claim 49, wherein the call completion rate is based on a number of calls completed to available agents and on a number of answered calls having a record in the virtual queue.

52. A method as recited in claim 49, wherein the step of estimating the call removal rate includes a step of inflating the call completion rate based on an average number of available agents.

53. A method as recited in claim 52, wherein the step of inflating the call completion rate is based on an inflating factor, the inflating factor being based on the call completion rate, an average number of available agents and an average call handling time.

54. A method as recited in claim 52, wherein the step of creating the virtual queue includes steps of:

receiving periodic data update from an automatic call distributor, the periodic data update containing information relating to a new call received at the automatic call distributor;

creating a new entry for the virtual queue for each new call that is received at the automatic call distributor based on the periodic data update; and

adding each new entry to a tail of the virtual queue.

55. A routing point in a distributed automatic call distributor system having a plurality of automatic call distributors, the routing point comprising:

a processor forming a virtual first-in, first-out queue, the virtual queue including a list of individual records, each record containing information relating a call waiting in a queue associated with an automatic call distributor of the plurality of automatic call distributors, the processor receiving an update message containing information relating to a number of calls and a longest call waiting time for each automatic call distributor; and

memory storing the records as the virtual queue.

56. The routing point as recited in claim 55, wherein the routing point receives periodic update messages from a data collection system.

57. A routing point in a distributed automatic call distributor system having a plurality of automatic call distributors, the routing point comprising:

a processor forming a virtual first-in, first-out queue, the virtual queue including a list of individual records, each record containing information relating a call waiting in a queue associated with an automatic call distributor of the plurality of automatic call distributors, the routing point receiving update event-based data for calls waiting in queues associated with the automatic call distributors, the update event-based data including information relating to a number of calls and a longest call waiting time for calls in each queue associated with an automatic call distributor of the plurality of automatic call distributors; and

a memory storing the records as the virtual queue.