OPTIMAL MULTI-FACTOR EVALUATION IN COMPUTING SYSTEMS

• US 20120303571A1
• Filed: 05/26/2011
• Published: 11/29/2012
• Est. Priority Date: 05/26/2011
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Faynberg, Igor, Lu, Hui-Lan
• Granted Patent: US 8,498,957 B2
• Time in Patent Office: Days
• US Class Current: 706/52
• CPC Class Codes: G06F 21/31 User authentication
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

Techniques are disclosed for optimally scheduling computations that involve multiple factors, the cost of evaluations and probabilities of success of which are known. For example, a methodology is provided for determining an optimal schedule of a multi-factor test in sub-quadratic time. While the methodology has wide ranging application, we illustrate a particular applicability to a security application involving multi-factor authentication in a cloud computing environment, as well as applicability to the contact center agent scheduling.

Claims

1. A method, comprising:

determining, via at least one computing device, an optimal schedule for evaluating a multi-factor test, wherein the multi-factor test comprises two or more factors to be tested, with two or more respective costs associated with evaluating the two or more factors and with two or more respective probabilities associated with a given evaluation result for the two or more factors and the optimal schedule minimizing an expectation of an overall cost to evaluate the multi-factor test;

wherein the determination of the optimal schedule comprises sorting the factors whereby a first factor is determined to precede a second factor in an ordering of factors when a relation exists whereby a sum of the cost associated with the first factor and a product of the cost of a second factor and the probability associated with the first factor is less than a sum of the cost associated with the second factor and a product of the cost of the first factor and the probability associated with the second factor.

2. The method of claim 1, wherein the optimal schedule determination step is performed in sub-quadratic time.

3. The method of claim 1, further comprising the step of performing the multi-factor test based on the optimal schedule.

4. The method of claim 3, wherein the multi-factor test is performed based on the optimal schedule by the at least one computing device.

5. The method of claim 3, wherein the multi-factor test is performed based on the optimal schedule by one or more other computing devices.

6. The method of claim 1, wherein the optimal schedule is determined by the at least computing device and at least one other computing device.

7. The method of claim 1, wherein the first factor and the second factor form a factor pair when the first factor is determined to precede the second factor in accordance with the given relation.

8. The method of claim 1, wherein the expectation of the overall cost to evaluate the multi-factor test is determined by comparing expectations for given factor pairs.

9. The method of claim 1, wherein the optimal schedule determination step further comprises splitting the two or more factors into two sub-lists, and recursively performing ordering on each of these sub-lists according to the precedence relation.

10. The method of claim 9, wherein the optimal schedule determination step further comprises merging the two ordered sub-lists into a final factor list which represents the optimal schedule for evaluating the factors.

11. The method of claim 1, wherein the optimal schedule represents an order of agents that a caller is to pass through in a contact center to resolve an issue.

12. The method of claim 11, wherein the two or more factors to be evaluated represent two or more characteristics associated with the agents of the contact center.

13. The method of claim 1, wherein the optimal schedule represents an order associated with one or more requests to authenticate objects submitted to an authentication process by nodes in a computing system.

14. The method of claim 13, wherein the two or more factors to be evaluated represent two or more relationships associated with the object to be authenticated.

15. The method of claim 13, wherein the computing system is a cloud computing system.

16. Apparatus, comprising:

one or more memories; and

one or more processor devices operatively coupled to the one or more memories and configured to determine an optimal schedule for evaluating a multi-factor test, wherein the multi-factor test comprises two or more factors to be tested, with two or more respective costs associated with evaluating the two or more factors and with two or more respective probabilities associated with a given evaluation result for the two or more factors and the optimal schedule minimizing an expectation of an overall cost to evaluate the multi-factor test;

wherein the determination of the optimal schedule comprises sorting the factors whereby a first factor is determined to precede a second factor in an ordering of factors when a relation exists whereby a sum of the cost associated with the first factor and a product of the cost of a second factor and the probability associated with the first factor is less than a sum of the cost associated with the second factor and a product of the cost of the first factor and the probability associated with the second factor.

17. The apparatus of claim 16, wherein the optimal schedule determination is performed in sub-quadratic time.

18. The apparatus of claim 16, wherein the one or more processor devices are further configured to perform the multi-factor test based on the optimal schedule.

19. The apparatus of claim 16, wherein the optimal schedule represents an order of agents that a caller is to pass through in a contact center to resolve an issue, and the two or more factors to be evaluated represent two or more characteristics associated with the agents of the contact center.

20. The apparatus of claim 16, wherein the optimal schedule represents an order associated with one or more requests to authenticate objects submitted to an authentication process by nodes in a cloud computing system, and the two or more factors to be evaluated represent two or more relationships associated with the object to be authenticated.