Selection of a resource in a distributed computer system
View Patent ↗A method for selecting a resource from a plurality of resources includes determining a score for that resource on the basis of a stochastic property of that resource. An interval corrsesponding to that resource is then defined to have an extent that depends on the score. A particular resource is then selected by generating a random number and selecting that resource when the random number falls within the interval.
1. A method for selecting a resource from a plurality of resources, said method comprising:
determining a score for said resource on the basis of a stochastic property of said resource;
defining an interval corresponding to said resource, said interval having an extent that depends on said score;
generating a random number; and
selecting said resource if said random number is within said interval.
2. The method of claim 1 , wherein defining an interval corresponding to said resource comprises
determining a normalized score for said resource; and
defining an extent of said interval on the basis of said normalized score.
3. The method of claim 2 , wherein determining a normalized score comprises
evaluating a sum of scores assigned to each resource in said plurality of resources; and
normalizing said score assigned to said resource by said sum of scores.
4. The method of claim 1 , wherein generating a random number comprises generating a uniformly distributed random number.
5. The method of claim 1 , further comprising polling a selected resource to update a prior measurement of said stochastic property associated with said resource.
6. The method of claim 1 , wherein determining said score comprises estimating a present value of said stochastic property on the basis of a prior measurement of said stochastic property.
7. The method of claim 6 , further comprising selecting said prior measurement to be a most-recently known value of said stochastic property.
8. The method of claim 1 , further comprising selecting said resource to be a processor having a variable workload.
9. The method of claim 8 , wherein determining a score for said resource comprises obtaining an estimate of a present workload of said processor.
10. The method of claim 9 , wherein determining a score for said resource further comprises evaluating an inverse of said estimate of said present workload of said processor.
11. The method of claim 9 , wherein obtaining an estimate of a present workload of said processor comprises retrieving, from memory, a last-known workload of said processor.
12. The method of claim 1 , further comprising selecting said resource to be a queue having a variable queue-length.
13. A method for selecting a queue from a plurality of queues, said method comprising:
assigning a score to said queue;
defining an interval corresponding to said queue, said interval having an extent that depends on said score;
generating a random number; and
selecting said queue if said random number is within said interval.
14. The method of claim 13 , wherein assigning said score comprises determining an effective queue-length of said queue.
15. The method of claim 14 , wherein determining said effective queue-length comprises estimating a queue-length of said queue.
16. The method of claim 15 , wherein determining said effective queue-length comprises determining a priority of said queue.
17. The method of claim 16 , wherein assigning said score comprises weighting said queue-length with said priority.
18. The method of claim 13 , wherein defining an interval comprises selecting said extent on the basis of a normalized score.
19. The method of claim 18 , wherein selecting said extent on the basis of a normalized score comprises:
evaluating a sum of scores of all queues in said plurality of queues; and
normalizing said score for said queue by said sum of scores.
20. The method of claim 13 , wherein generating a random number comprises generating a uniformly distributed random number.
21. The method of claim 15 , wherein estimating the number of waiting elements in said queue comprises determining a last-known queue-length for said queue.
22. The method of claim 21 , further comprising:
polling said selected queue to determine a queue-length of said selected queue; and
updating said last-known queue-length for said selected queue.
23. The method of claim 22 , wherein updating said last-known queue length comprises polling said selected queue to determining a number of waiting elements in said selected queue.
24. The method of claim 23 , further comprising caching said number of waiting elements for use in estimating a length of said queue.
25. A computer-readable medium having encoded thereon software for selecting a resource from a plurality of resources, said software comprising instructions for:
determining a score for said resource on the basis of a stochastic property of said resource;
defining an interval corresponding to said resource, said interval having an extent that depends on said score;
generating a random number; and
selecting said resource if said random number is within said interval.
26. A computer-readable medium having encoded thereon software for selecting a queue from a plurality of queues, said software comprising instructions for:
assigning a score to said queue;
defining an interval corresponding to said queue, said interval having an extent that depends on said score;
generating a random number; and
selecting said queue if said random number is within said interval.