Rules-based queuing of calls to call-handling resources

• US 6,434,230 B1
• Filed: 02/02/1999
• Issued: 08/13/2002
• Est. Priority Date: 02/02/1999
• Status: Expired due to Fees

• Current Assignee: Avaya Incorporated, ViRexx Medical Corp. (Endo International PLC)
• Original Assignee: Avaya Technology Corporation Miami Lakes FLA US
• Inventors: Gabriel, Camille
• Primary Examiner(s): Matar, Ahmad F.
• Assistant Examiner(s): BUI, BING Q
• Application Number:
  US09/241,717
• Time in Patent Office: 1,288 Days
• Field of Search: 379/265.01, 379/265.02, 379/265.11, 379/265.12, 379/265.13, 379/266.01, 379/266.02, 379/309
• US Class Current: 379/265.01
• CPC Class Codes: H04M 3/523 with call distribution or queueing
• CPC Class Codes: H04M 3/5232 Call distribution algorithms

Abstract

Resolution of contention over resources (102-105) in an automatic call distribution (ACD) system (101). Call (201) attributes (202) and resource (221) attributes (222) are defined (140,130). Rules (211) match calls'"'"' attributes with resources'"'"' attributes, Rules have priorities (212) comprising an initial value (213) and a function (214) that changes the value over time. Rules preferably define call coverage paths (215). Each resource has its own call queue (121-129). Rules are matched (230) to arriving call'"'"'s attributes, to determine (240) resources that can handle the call. A token (250) for every matching rule is placed in the queues of all resources that can handle the call, at a position determined by the rule'"'"'s priority. The priority and queue position changes over time according to the rule'"'"'s time function. When a resource dequeues the call'"'"'s token to process the call, tokens for the call are removed from all queues.

Claims

1. A method of distributing requests among resources for processing the requests, comprising:

in response to a request to be processed, determining request attributes of the request;

in response to the determining, finding among a plurality of resources each comprising a different one and only one entity capable of processing a request at least one resource that corresponds to the determined request attributes, by searching a plurality of rule definitions each defining a correspondence between at least one request attribute and at least one resource that is needed for processing a request having the at least one request attributes; and

in response to the finding of at least one resource, enqueuing the request in a request queue of each one of the found resources, each one of the plurality of resources having its own request queue, and for processing only requests enqueued in its own request queue, wherein;

each rule definition further defines a priority of the corresponding rule, and

at least one rule definition further defines a function for changing the priority of the corresponding rule over time; and

enqueuing comprises

enqueuing the request in the request queue of each one of the found resources at the priority of the rule that led to the finding of the one resource,

over time changing the priority of the request in the request queue of each one of the resources found by the at least one rule according to the function of the rule definition of the at least one rule, and

requeuing the request in the request queue of each one of the resources found by the at least one rule according to the changed priority of the request in that request queue.

2. The method of claim 1 wherein:

finding comprises

finding at least one resource attribute that corresponds to the determined request attributes by searching the plurality of rule definitions each defining a correspondence between at least one request attribute and at least one resource attribute that is needed for processing a request having the at least one request attribute; and

in response to finding at least one resource attribute, finding at least one resource among the plurality of the resources that has the found at least one resource attribute, by searching a plurality of resource definitions each defining a correspondence between one of a plurality of resources and at least one resource attribute possessed by the one resource.

4. The method of claim 1 wherein the request comprises a call.

5. The method of claim 1 wherein:

the plurality of resources each comprise one of (a) a different single one agent, (b) a different single one service circuit, and (c) a different single one function.

11. An apparatus that performs the method of claims 2 or 3 or 8 or 1 or 6 or 7 or 9 or 10 or 4 or 5.

12. A computer readable medium containing software which, when executed in a computer, causes the computer to perform the method of claim 2 or 3 or 8 or 1 or 6 or 7 or 9 or 10 or 4 or 5.

3. The method of claim further comprising:

in response to one of the found resources processing the request, removing the request from all of the request queues.

6. A method of distributing requests among resources for processing the requests, comprising:

in response to a request to be processed, determining request attributes of the request;

in response to the determining, finding among a plurality of resources each comprising a different one and only one entity capable of processing a request at least one resource that corresponds to the determined request attributes, by searching a plurality of rule definitions each defining a correspondence between at least one request attribute and at least one resource that is needed for processing a request having the at least one request attribute; and

in response to the finding of at least one resource, enqueuing the request in a request queue of each one of the found resources, each one of the plurality of resources having its own request queue, and for processing only requests enqueued in its own request queue, wherein;

each rule definition further defines a priority of the corresponding rule, and

the rule definition that led to the finding of the found resources further defines a preemption threshold;

enqueuing comprises

enqueuing the request in the request queue of each one of the found resources at the priority of the rule that led to the finding of the one resource; and

the method further comprises

one of the found resources removing the request from its request queue and processing the request, and

in response to another request being enqueued in the request queue of the one of the found resources at a priority that exceeds by the preemption threshold the priority at which the request that is being processed was enqueued, preempting the processing of the request that is being processed by processing of the other request.

7. A method of distributing requests among resources for processing the requests, comprising:

in response to a request to be processed, determining request attributes of the request;

in response to me determining, finding among a plurality of resources each comprising a different one and only one entity capable of processing a request at least one resource that corresponds to the determined request attributes, by searching a plurality of rule definitions each defining a correspondence between at least one request attribute and at least one resource that is needed for processing a request having the at least one request attribute; and

in response to the finding of at least one resource, enqueuing the request in a request queue of each one of the found resources, each one of the plurality of resources having its own request queue, and for processing only requests enqueued in its own request queue, wherein;

the rule definition of at least one of the rules further defines a coverage path of the one rule; and

enqueuing comprises

estimating a minimum in-queue waiting time for the request in the request queues of the resources found by the one rule,

in response to an estimated minimum in-queue waiting time not exceeding a threshold, enqueuing the request in the request queues of the resources found by the one rule, and

in response to the estimated minimum in-queue waiting time exceeding the threshold, enqueuing the request in the request queues of at least one resource, other than the found resources, identified by the coverage path of the one rule.

8. The method of claim 7 wherein:

each rule definition further defines a priority of the corresponding rules; and

enqueuing comprises

enqueuing the request in the request queue of each one of the found resources at the priority of the rule that led to the finding of the one resource.

9. A method of distributing requests among resources for processing the requests, comprising:

in response to a request to be processed, determining request attributes of the request;

in response to the determining, finding among a plurality of resources each comprising a different one and only one entity capable of processing a request at least one resource attribute that corresponds to the determined request attributes, by searching a plurality of rule definitions each defining a correspondence between at least one request attribute and at least one resource attribute that is needed for processing a request having the at least one request attribute;

in response to finding at least one resource attribute, finding at least one resource among the plurality of the resources that has the found at least one resource attribute, by searching a plurality of resource definitions each defining a correspondence between one of a plurality of resources and at least one resource attribute possessed by the one resource; and

in response to the finding of at least one resource, enqueuing the request in a request queue of each one of the found resources, each one of the plurality of resources having its own request queue, and for processing only requests enqueued in its own request queue, wherein;

each rule definition further defines an initial priority of the corresponding rule, a function for changing the priority of the corresponding rule over time, and a coverage path of the corresponding rule; and

enqueuing comprises

estimating a minimum in-queue waiting time for the request in the request queues of the resources found by a rule,

in response to the estimated minimum in-queue waiting time not exceeding a threshold, enqueuing the request in the request queue of a resource found by the rule at the initial priority of the rule,

in response to the estimated minimum in-queue waiting time exceeding the threshold, enqueuing the request in the request queue of a resource identified by the coverage path of the rule,

over time changing the priority of the request in the request queue in which it is enqueued according to the function of the rule definition of the rule, and

re-queuing the request in the request queue in which it is enqueued according to the changed priority of the request in the request queue in which it is enqueued; and

the method further comprising

in response to one of the found resources processing the request, removing the request from all of the request queues.

10. A method of distributing requests among resources for processing the requests, comprising:

in response to a request to be processed, determining request attributes of the request;

in response to the determining, finding among a plurality of resources each comprising a different one and only one entity capable of processing a request at least one resource attribute that corresponds to the determined request attributes, by searching a plurality of rule definitions each defining a correspondence between at least one request attribute and at least one resource attribute that is needed for processing a request having the at least one request attribute;

in response to finding at least one resource attribute, finding at least one resource among the plurality of the resources that has the found at least one resource attribute, by searching a plurality of resource is definitions each defining a correspondence between one of a plurality of resources and at least one resource attribute possessed by the one resource; and

in response to the finding of at least one resource, enqueuing the request in a request queue of each one of the found resources, each one of the plurality of resources having its own request queue, and for processing only requests enqueued in its own request queue, wherein;

each rule definition further defines an initial priority of the corresponding rule, a function for changing the priority of the corresponding rule over time, and a coverage path of the corresponding rule, and

the rule definition that led to the finding of the found resources further defines a preemption threshold;

enqueuing comprises

estimating a minimum in-queue waiting time for the request in the request queues of the resources found by a rule,

in response to the estimated minimum in-queue waiting time not exceeding a threshold, enqueuing the request in the request queue of a resource found by the rule at the initial priority of the rule,

in response to the estimated minimum in-queue waiting time exceeding the threshold, enqueuing the request in the request queue of a resource identified by the coverage path of the rule,

over time changing the priority of the request in the request queue in which it is enqueued according to the function of the rule definition of the rule, and

re-queuing the request in the request queue in which it is enqueued according to the changed priority of the request in the request queue in which it is enqueued; and

the method further comprising

in response to one of the found resources processing the request, removing the request from all of the request queues, and

in response to another request being enqueued in the request queue of the one of the found resources at a priority that exceeds by the preemption threshold the priority at which the request that is being processed was enqueued when it was removed from the request queues, preempting the processing of the request that is being processed by processing of the other request.

13. An apparatus for distributing requests among resources for processing the requests, comprising:

means for determining attributes of an individual request;

means for defining a plurality of request queues each corresponding to a different one of a plurality of resources each comprising a different one and only one entity capable of processing a request, for enqueuing requests, each one of the plurality of resources having its own request queue for processing only requests enqueued by its own request queue;

means for storing a plurality of rule definitions each defining a correspondence between at least one request attribute and at least one resource that is needed for processing a request having the at least one request attribute;

means responsive to the individual request having at least one determined request attribute, for finding from the rules definitions at least one resource that corresponds to the at least one determined request attribute; and

means responsive to the finding of the at least one resource, for enqueuing the individual request in the request queue of each of the found resources, wherein;

each rule definition further defines a priority of the corresponding rule, and

at last one rule definition further defines a function for changing the priority of the corresponding rule over time; and

the enqueuing means comprise

means for enqueuing the request in the request queue of each one of the found resources at the priority of the rule that led to the finding of the one resource,

means for changing over time the priority of the request in the request queue of each one of the resources found by the at least one rule according to the function of the rule definition of the at least one rule, and

means for requeuing the request in the request queue of each one of the resources found by the at least one rule according to the changed priority of the request in that request queue.

14. An apparatus for distributing requests among resources for processing the requests, comprising:

means for determining attributes of an individual request;

means for defining a plurality of request queues each corresponding to a different one of a plurality of resources each comprising a different one and only one entity capable of processing a request, for enqueuing requests, each one of the plurality of resources having its own request queue for processing only requests enqueued by its own request queue;

means for storing a plurality of rule definitions each defining a correspondence between at least one request attribute and at least one resource that is needed for processing a request having the at least one request attribute;

means responsive to the individual request having at least one determined request attribute, for finding from the rules definitions at least one resource that corresponds to the at least one determined request attribute; and

means responsive to the finding of the at least one resource, for enqueuing the individual request in the request queue of each of the found resources, wherein;

each rule definition further defines a priority of the corresponding rule, and

the rule definition that led to the finding of the found resources further defines a preemption threshold;

the enqueuing means comprise

means for enqueuing the request in the request queue of each one of the found resources at the priority of the rule that led to the finding of the one resource; and

the apparatus further comprises

means responsive to another request being enqueued, in the request queue of one of the found resources that has removed the individual request from its request queue and is processing the individual request, at a priority that exceeds by the preemption threshold the priority at which the individual request that is being processed was enqueued, for preempting the processing of the individual request that is being processed by processing of the other request.

15. The apparatus of claim 14 further comprising:

means responsive to one of the found resources processing the request, for removing the request from all of the request queues.

16. The apparatus of claim 15 further comprising:

means for receiving the requests for processing;

the plurality of resources for processing the requests; and

means for connecting the received requests to the resources.

17. The apparatus of claim 16 wherein the requests comprise calls.

18. An apparatus for distributing requests among resources for processing the requests, comprising:

means for determining attributes of an individual request;

means for defining a plurality of request queues each corresponding to a different one of a plurality of resources each comprising a different one and only one entity capable of processing a request, for enqueuing requests, each one of the plurality of resources having its own request queue for processing only requests enqueued by its own request queue;

means for storing a plurality of rule definitions each defining a correspondence between at least one request an attribute and at least one resource that is needed for processing a request having the at least one request attribute;

means responsive to the individual request having at least one determined request attribute, for finding from the rules definitions at least one resource that corresponds to the at least one determined request attribute; and

means responsive to the finding of the at least one resource, for enqueuing the individual request in the request queue of each of the found resources, wherein;

the rule definition of at least one of the rules further defines a coverage path of the one rule; and

the enqueuing means comprise

means for estimating a minimum in-queue waiting time for the request in the request queues of the resources found by the one rule, and

means responsive to an estimated minimum in-queue waiting time not exceeding a threshold, for enqueuing the request in the request queues of the resources found by the one rule, and responsive to the estimated minimum in-queue waiting time exceeding the threshold, for enqueuing the request in the request queues of at least one resource, other than the found resources, identified by the coverage path of the one rule.

19. The apparatus of claim 18

wherein the means for finding comprise:

means for storing a plurality of resources definitions each defining attributes of a corresponding one of a plurality of request processing resources;

means responsive to a request having at least one determined request attribute, for finding from the rules definitions at least one resource attribute that corresponds to the at least one determined request attribute; and

means responsive to finding at least one resource attribute, for finding from the resources definitions at least one resource among the plurality of the resources that corresponds to the found resource attribute.

20. The apparatus of claim 18 wherein;

the plurality of resources each comprise one of (a) a different single one agent, (b) a different single one service circuit, and (c) a different single one function.

21. The apparatus of claim 18 wherein:

each rule definition further defines a priority of the corresponding rule; and

the enqueuing means comprise

means for enqueuing the request in the request queue of each one of the found resources at the priority of the rule that led to the finding of the one resource.

22. An apparatus for distributing requests among resources for processing the requests, comprising:

means for determining attributes of an individual request;

means for defining a plurality of request queues each corresponding to a different one of a plurality of resources each comprising a different one and only one entity capable of processing a request, for enqueuing requests, each one of the plurality of resources having its own request queue for processing only requests enqueued by its own request queue;

means for storing a plurality of rule definitions each defining a correspondence between at least one request attribute and at least one resource that is needed for processing a request having the at least one request attribute;

means for storing a plurality of resources definitions each defining attributes of a corresponding one of a plurality of request processing resources;

means responsive to the individual request having at least one determined request attribute, for finding from the rules definitions at least one resource attribute that corresponds to the at least one determined request attribute;

means responsive to finding at least one resource attribute, for finding from the resources definitions at least one resource among the plurality of the resources that corresponds to the found resource attribute; and

means responsive to the finding of the at least one resource, for enqueuing the individual request in the request queue of each of the found resources, wherein;

each rule definition further defines an initial priority of the corresponding rule, a function for changing the priority of the corresponding rule overtime, and a coverage path of the corresponding rule; and

the enqueuing means comprise

means for estimating a minimum in-queue waiting time for the request in the request queues of the resources found by a rule,

means responsive to the estimated minimum in-queue waiting time not exceeding a threshold, for enqueuing the request in the request queue of a resource found by the rule at the initial priority of the rule, and responsive to the estimated minimum in-queue waiting time exceeding the threshold, for enqueuing the request in the request queue of a resource identified by the coverage path of the rule, and

means for changing over time the priority of the request in the request queue in which it is enqueued according to the function of the rule definition of the rule, and for re-queuing the request in the request queue in which it is enqueued according to the changed priority of the request in the request queue in which it is enqueued; and

the apparatus further comprising

means responsive to one of the found resources processing the request, for removing the request from all of the request queues.

23. The apparatus of claim 22 wherein:

the rule definition that led to the finding of the found resources further defines a preemption threshold; and

the apparatus further comprising

means responsive to another request being enqueued in the request queue of the one of the found resources at a priority that exceeds by the preemption threshold the priority at which the request that is being processed was enqueued when it was removed from the request queues, for preempting the processing of the request that is being processed by processing of the other request.