Method and apparatus for load balancing work on a network of servers based on the probability of being serviced within a service time goal

• US 7,770,175 B2
• Filed: 09/26/2003
• Issued: 08/03/2010
• Est. Priority Date: 09/26/2003
• Status: Active Grant

• Current Assignee: Avaya Incorporated
• Original Assignee: Avaya Incorporated
• Inventors: Roybal, Larry John, Flockhart, Andrew D., Steiner, Robert C.
• Primary Examiner(s): An; Meng-Ai
• Assistant Examiner(s): WAI, ERIC CHARLES
• Application Number:
  US10/673,118
• Publication Number:
  US 20050071844A1
• Time in Patent Office: 2,503 Days
• Field of Search: 718104-105, 379/265, 379/266, 370/429
• US Class Current: 718/105
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/10015 Access to distributed or replicated servers, e.g. using brokers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

The present invention is directed to balancing resource loads. In particular, the present invention is directed to assigning work to service locations having the greatest probability of servicing the work within a target time. Because an average wait time is not necessarily equal to a probability of servicing work within a target time, the present invention is useful in meeting service target goals. Because the present invention operates by comparing the probability of a defined set of service locations to one another, absolute probabilities need not be calculated. Instead, relative probabilities may be used in assigning work.

Claims

1. A computer-implemented method for balancing resource loads, comprising:

receiving a work request;

determining for each of a plurality of service locations a probability of servicing said work request within a target time, wherein said determined probability includes determining a relative probability for each service location included in the plurality of service locations by calculating a number of opportunities to service said work request within said target time by each service location included in the plurality of service locations, wherein said number of opportunities is calculated as a function of a weighted advance time (WAT), where WAT is a weighted advance time for a work request assigned to said service location;

selecting at least a first service location having at least one of a greatest determined probability of servicing said work request within said target time and a sufficient determined probability of servicing said work request within said target time; and

assigning said work request to said selected service location.

2. The method of claim 1, wherein said step of selecting at least a first service location comprises selecting a first service location having a sufficient determined probability of servicing said work request within said target time.

3. The method of claim 1, wherein said step of selecting at least a first service location comprises selecting a first service location having a greatest determined probability of servicing said work request within said target time.

4. The method of claim 1, wherein selecting at least a first service location comprises selecting a first service location having at least a selected minimum number of opportunities to service said work request within said target time.

5. The method of claim 1, wherein said step of selecting at least a first service location comprises selecting a first service location having a greatest number of opportunities to service said work request within said target time.

6. The method of claim 1, wherein said number of opportunities (#OPPS) is calculated as #OPPS=((Target time-EWT)/WAT)+1, where EWT is an estimated wait time for a work request assigned to said service location, and where WAT is a weighted advance time for a work request assigned to said service location.

7. The method of claim 1, further comprising, in response to more than one service location having a greatest calculated number of opportunities to service said work request within said target time, calculating an advance time metric.

8. The method of claim 7, wherein said advance time metric comprises an expected wait time, wherein said step of selecting comprises selecting a location having a lowest expected wait time.

9. The method of claim 7, wherein said advance time metric comprises a weighted advance time trend, wherein said step of selecting comprises selecting a location having a lowest weighted advance time trend.

10. The method of claim 9, wherein said weighted advance time trend (WAT_Trend) is calculated as WAT_Trendn=(x*WAT_Trendn−

1)+((1−

x)*WAT_Change), where x is a constant, and where the WAT_Change is calculated as WAT_Change=(WATn-WATn−

1)/WATn−

1.

11. The method of claim 1, wherein each of said service locations is associated with a queue capable of containing a plurality of work requests.

12. The method of claim 1, wherein said selected service location comprise at least one split.

13. A load-balancing apparatus, including a hardware processor and memory, comprising:

means for receiving a work request;

means for calculating a probability that a service location is capable of servicing said work request within a target time, wherein said means for calculating a probability includes means for calculating a number of opportunities to service said work request within said target time with respect to a service location, wherein said number of opportunities is calculated as a weighted advance time (WAT), where WAT is a weighted advance time for a work request assigned to said service location;

means for selecting a service location having at least one of a highest probability of servicing said work request within said target time and a sufficient probability of servicing said work request within said target time; and

means for allocating said work request to said selected service location.

14. The apparatus of claim 13, wherein said service location is associated with a queue and comprises at least one associated resource.

15. The apparatus of claim 13, wherein said service location comprises a split.

16. The apparatus of claim 13, further comprising means for calculating an advance time metric.

30. The apparatus of claim 13, wherein said number of opportunities (#OPPS) is calculated as #OPPS=((Target time-EWT)/WAT)+1, where EWT is an estimated wait time for a work request assigned to said service location, and where WAT is a weighted advance time for a work request assigned to said service location.

17. A work allocation apparatus, comprising:

a plurality of service locations;

a plurality of service resources, wherein at least a one of said service resources is associated with each of said service locations;

a communication network interface, operable to receive work requests; and

a hardware processor implementing a controller, wherein said controller operates to calculate a relative probability that a work request will be serviced within a target time for each service location included in the plurality of service locations, wherein said relative probability is determined for a service location by calculating a number of opportunities to service said work request within a predetermined target time, wherein said number of opportunities is calculated as a function of a weighted advance time (WAT), where WAT is a weighted advance time for a work request assigned to said service location, wherein a work request received at said communication network interface is assigned to a service location having at least one of a highest probability of servicing said work request within said predetermined target time and a sufficient probability of servicing said work request within said predetermined target time.

18. The apparatus of claim 17, wherein said service resources comprise service agents.

19. The apparatus of claim 17, wherein said service resources are organized into splits.

20. The apparatus of claim 17, wherein said work request is associated with a request for assistance.

21. The apparatus of claim 17, wherein said communication network interface is interconnected to at least one of an Internet protocol network and a public switched telephone network.

22. The apparatus of claim 17, wherein said service locations each comprise a server.

31. The apparatus of claim 17, wherein said number of opportunities (#OPPS) is calculated as #OPPS=((Target time-EWT)/WAT)+1, where EWT is an estimated wait time for a work request assigned to said service location, and where WAT is a weighted advance time for a work request assigned to said service location.

23. A computer storage medium containing instructions, when executed by a processor, to perform the method comprising:

receiving a work request;

calculating for each of a plurality of service locations a relative probability that said work request will receive service within a target time period, wherein said calculated probability comprises a calculated number of opportunities that a service location will have to service said work request within said target time period, wherein said number of opportunities is calculated as a function of an expected wait time (EWT) for said service location;

selecting at least one a one of said plurality of service locations having at least one of a greatest probability of servicing said work request within said target time period and a sufficient probability of servicing said work request within said target time period; and

assigning said work request to one of said selected service locations.

24. The method of claim 23, wherein said number of opportunities (#OPP) is given by:

#OPP=((Target time-EWT)/WAT)+1, where EWT is an expected wait time for said service location, and where WAT is a weighted advance time for said service location.

25. The method of claim 23, further comprising:

in response to a number of service locations having an equal calculated probability, calculating an advance time metric for each of said number of service locations.

26. The method of claim 25, wherein said calculating an advance time metric comprises:

calculating a weighted advance time;

calculating a weighted advance time change;

calculating a weighted advance time trend; and

wherein said step of selecting a one of said plurality of service locations comprises selecting a service location with a lowest calculated weighted advance time trend.

27. The method of claim 26, wherein said weighted advance time change (WAT_Change) is given by WAT_Change=(WATn-WATn−

1)/WATn−

1, where WATn is the weighted advance time most recently calculated, and where WATn−

1 is a previously calculated weighted advance time, wherein said weighted advance time trend (WAT_Trend) is given by WAT_Trendn=(x*WAT_Trendn−

1)+((1−

x)*WAT_Change), where x is a constant.

28. The method of claim 25, wherein said calculating an advance time metric comprises calculating an estimated waiting time.

29. The method of claim 23, further comprising:

selecting a target time for servicing a work request.

32. The method of claim 23, wherein said number of opportunities (#OPP) is given by:

#OPP=((Target time-EWT)/WAT)+1, where EWT is an estimated wait time for a work request assigned to said service location, and where WAT is a weighted advance time for a work request assigned to said service location.