Method and apparatus for metric based server selection

• US 6,795,858 B1
• Filed: 12/29/2000
• Issued: 09/21/2004
• Est. Priority Date: 12/29/2000
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Jain, Bijendra N., Mccloghrie, Keith
• Primary Examiner(s): Lim, Krisna
• Application Number:
  US09/750,661
• Time in Patent Office: 1,362 Days
• Field of Search: 709/226, 709/238, 709/244, 709/102, 709/105
• US Class Current: 709/226
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• 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/101 based on network conditions
• CPC Class Codes: H04L 67/1038 Load balancing arrangements to avoid a single path through a load balancer

Abstract

Methods and apparatus are provided for selecting a server that can provider content to a client in an optimal manner. A server selection system is coupled to a network node that can identify servers that can provide client reqeusted content. Performance metrics of the servers and their associated priorities are obtained. Servers with metrics that are worse than all the metrics of any other server are optionally eliminated from consideration for best server. Priorities for the metrics are obtained. The metric with the highest priority is applied to analyze the group of servers. The server with the best value for the metric and all servers with metric values falling within a significance window are retained. All others are eliminated from consideration. The other metrics are applied until no metrics remain or only one server remains. If no metrics remain, a best server is identified from the remaining group.

Claims

1. A method for selecting a server from a group of servers to provide content to a client in an optimal manner, the method comprising:

for each server in the group of servers, obtaining values of at least a first performance metric and a second performance metric, wherein the performance metrics correspond with the characteristics of transmission between the servers and network nodes associated with the client;

applying a first significance window defining a range of acceptable values of the first performance metric and removing from consideration those servers in the group having poor values of the first performance metric, which fall outside the significance window;

applying a second significance window to the servers remaining after applying the first significance window, the second significance window defining a range of acceptable values of the second performance metric; and

identifying the best server from among any remaining servers lying within the second significance window.

2. The method of claim 1, further comprising:

obtaining values of a third performance metric for each server in the group of servers;

applying a third significance window to any remaining servers lying within the second significance window, the third significance window defining a range of acceptable values of the third performance metric; and

identifying the best server from among any remaining servers lying within the third significance window.

3. The method of claim 1, further comprising identifying the group of servers that can each serve the same content.

4. The method of claim 1, further comprising:

removing from consideration one or more poor servers from having poorer values of all performance metrics under consideration than at least one other server in the group of servers.

5. The method of claim 4, wherein the poor server is removed prior to applying the first significance window.

6. The method of claim 1, wherein the first performance metric is selected from the group consisting of round trip time, drop rate, server load, available bandwidth, administrative distance, monetary cost, number of hops, and use of third party systems.

7. The method of claim 1, wherein the first performance metric is a measure of round trip time and the second performance metric is selected from the group consisting of available bandwidth, server load, and drop rate.

8. The method of claim 1, further comprising calculating at least one of the first significance window and the second significance window.

9. The method of claim 8, wherein calculating the at least one of the first and second significance windows comprises:

calculating the difference between the best and worst metric values for available servers; and

identifying a multiplier, wherein the product of the multiplier and the difference between the best and worst metric values yields the significance window.

10. The method of claim 8, wherein calculating the at least one of the first and second significance windows comprises:

providing an upper and lower bound for a significance window;

calculating the difference between the best and worst metric values for available servers;

identifying a multiplier; and

calculating the product of the multiplier and the difference, wherein the significance window is the median of the upper bound, lower bound, and the product of the multiplier and the difference.

11. The method of claim 8, wherein at least one of the first and second significance windows has a constant size.

12. The method of claim 8, wherein calculating the at least one of the first and second significance windows comprises:

identifying a percentage of servers with metric values closest to an identified optimal value.

13. A computer program product comprising a machine readable medium on which is provided program instructions for selecting a server from a group of servers to provide content to a client in an optimal manner, the instructions encoding a method comprising:

for each server in the group of servers, obtaining values of at least a first performance metric and a second performance metric, wherein the performance metrics correspond with the characteristics of transmission between the servers and network nodes associated with the client;

applying a first significance window defining a range of acceptable values of the first performance metric and removing from consideration those servers in the group having poor values of the first performance metric, which fall outside the significance window;

applying a second significance window to the servers remaining after applying the first significance window, the second significance window defining a range of acceptable values of the second performance metric; and

identifying the best server from among any remaining servers lying within the second significance window.

14. The computer program product of claim 13, wherein instructions further comprise calculating at least one of the first significance window and the second significance window.

15. The computer program product of claim 14, wherein instructions for calculating the at least one of the first and second significance windows comprises:

calculating the difference between the best and worst metric values for available servers; and

identifying a multiplier, wherein the product of the multiplier and the difference between the best and worst metric values yields the significance window.

16. The computer program product of claim 14, wherein instructions for calculating the at least one of the first and second significance windows comprises:

providing an upper and lower bound for a significance window;

calculating the difference between the best and worst metric values for available servers;

identifying a multiplier; and

calculating the product of the multiplier and the difference, wherein the significance window is the median of the upper bound, lower bound, and the product of the multiplier and the difference.

17. The computer program product of claim 14, wherein instructions for calculating the at least one of the first and second significance windows comprises:

identifying a percentage of servers with metric values closest to an identified optimal value.

18. An apparatus for selecting a server from a group of servers to provide content to a client in an optimal manner, the apparatus comprising:

memory configured to store, at least temporarily, values of at least a first performance metric and a second performance metric, wherein the metrics are associated with the characteristics of transmission between the servers and network nodes associated with the client;

one or more processors coupled with the memory, wherein the processors are configured or designed to apply a second significance window to a list of servers falling inside a first significance window and to identify the best server from among any remaining servers lying within the second significance window, wherein the first significance window is defined by a range of acceptable values of the first performance metric for removing from consideration those servers which fall outside the first significance window and the second significance window is defined by a range of acceptable values of a second performance metric for removing from consideration those servers which fall outside the second significance window.

19. The apparatus of claim 18 further comprising:

memory further configured to store values of a third performance metric for each server in the group of servers, wherein the one or more processors are further configured or designed to apply the third significance window to a list of servers falling inside both the first and second significance windows and to identify the best server from among any remaining servers lying within the third significance window and wherein the third significance window is defined by a range of acceptable values of a third performance metric for removing from consideration those servers which fall outside the third significance window.

20. The apparatus of claim 18, wherein the processors are further configured or designed calculate at least one of the first significance window and the second significance window.

21. The apparatus of claim 20, wherein the processors are configured or designed to calculate the difference between the best and worst metric values for available servers, and identify a multiplier, wherein the product of the multiplier and the difference between the best and worst metric values yields the significance window.

22. An apparatus for selecting a server from a group of servers to provide content to a client in an optimal manner, the apparatus comprising:

memory containing values of at least a first performance metric and a second performance metric, wherein the metrics are associated with the characteristics of transmission between the servers and network nodes associated with the client;

one or more processors coupled with the memory, wherein the processors are configured or designed to perform the following operations;

applying a first significance window defining a range of acceptable values of the first performance metric and removing from consideration those servers which fall outside the significance window;

applying a second significance window to the servers remaining after applying the first significance window, the second significance window defining a range of acceptable values of the second performance metric; and

identifying the best server from among any remaining servers lying within the second significance window.

23. The apparatus of claim 22, wherein the processors are configured or designed to perform the following additional operations:

obtaining values of a third performance metric for each server in the group of servers;

applying a third significance window to any remaining servers lying within the second significance window, the third significance window defining a range of acceptable values of the third performance metric; and

identifying the best server from among any remaining servers lying within the third significance window.

24. The apparatus of claim 22, wherein the processors are configured or designed to perform the following additional operations:

calculating at least one of the first significance window and the second significance window.

25. The apparatus of claim 24, wherein the processors are configured or designed to perform the following additional operations:

calculating the difference between the best and worst metric values for available servers; and

identifying a multiplier, wherein the product of the multiplier and the difference between the best and worst metric values yields the significance window.

26. An apparatus for selecting a server from a group of servers to provide content to a client in an optimal manner, the apparatus comprising:

means for obtaining values of at least a first performance metric and a second performance metric for each server in the group of servers, wherein the performance metrics correspond with the characteristics of transmission between the servers and network nodes associated with the client;

means for applying a first significance window defining a range of acceptable values of the first performance metric and removing from consideration those servers in the group having poor values of the first performance metric, which fall outside the significance window;

means for applying a second significance window to the servers remaining after applying the first significance window, the second significance window defining a range of acceptable values of the second performance metric; and

means for identifying the best server from among any remaining servers lying within the second significance window.

27. The apparatus of claim 26, further comprising:

means for obtaining values of a third performance metric for each server in the group of servers;

means for applying a third significance window to any remaining servers lying within the second significance window, the third significance window defining a range of acceptable values of the third performance metric; and

means for identifying the best server from among any remaining servers lying within the third significance window.

28. The apparatus of claim 26, further comprising means for calculating at least one of the first significance window and the second significance window.

29. The apparatus of claim 28, wherein means for calculating the at least one of the first and second significance windows comprises:

means for calculating the difference between the best and worst metric values for available servers; and

means for identifying a multiplier, wherein the product of the multiplier and the difference between the best and worst metric values yields the significance window.

30. The apparatus of claim 28, wherein means for calculating the at least one of the first and second significance windows comprises:

means for providing an upper and lower bound for a significance window;

means for calculating the difference between the best and worst metric values for available servers;

means for identifying a multiplier; and

means for calculating the product of the multiplier and the difference, wherein the significance window is the median of the upper bound, lower bound, and the product of the multiplier and the difference.

31. The apparatus of claim 28, wherein means for calculating the at least one of the first and second significance windows comprises:

means for providing a significance window of constant size.

32. The apparatus of claim 28, wherein means for calculating the at least one of the first and second significance windows comprises:

means for identifying a percentage of servers with metric values closest to an identified optimal value.