Apparatus and method for performing traffic redirection in a distributed system using a portion metric

• US 6,205,477 B1
• Filed: 10/20/1998
• Issued: 03/20/2001
• Est. Priority Date: 10/20/1998
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Johnson, Richard A., Shah, Dhaval N., Bosteder, Dalen D.
• Primary Examiner(s): Coulter, Kenneth R.
• Application Number:
  US09/175,195
• Time in Patent Office: 882 Days
• Field of Search: 709/203, 709/223, 709/220
• US Class Current: 709/220
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• 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/1021 based on client or server locations
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs

Abstract

A method and system for distributing a service request among a plurality of servers is disclosed. A portion metric is assigned to each one of the plurality of servers, the portion metric designating a portion of total server requests to be allocated to the one of the plurality of servers. A server request may then be received. A total number of server requests processed by the plurality of servers is incremented and a number of server requests distributed to each one of the plurality of servers is maintained. The server request is then distributed to one of the plurality of servers using the portion metric assigned to each one of the plurality of servers, the number of server requests distributed to each one of the plurality of servers, and the total number of server requests.

Claims

1. A method for distributing a service request, the method comprising:

assigning a portion metric to each one of a plurality of servers, the portion metric designating a portion of total server requests to be allocated to the one of the plurality of servers;

accepting an HTTP connection;

incrementing a total number of server requests processed by the plurality of servers;

maintaining a number of server requests distributed to each one of the plurality of servers;

selecting one of the plurality of servers using the portion metric assigned to each one of the plurality of servers, the number of server requests distributed to each one of the plurality of servers, and the total number of server requests; and

sending an HTTP code redirect.

2. A method for distributing a service request, the method comprising:

determining a metric value associated with each one of a plurality of servers;

configuring a tolerance range used in comparing the metric value for each one of the plurality of servers;

comparing the metric value for each one of the plurality of servers to obtain a set of the plurality of servers, each one of the set of the plurality of servers having a metric value within the tolerance range;

applying an alternate metric to the set of the plurality of servers to obtain a selected server when the set of the plurality of servers includes more than one server, and otherwise establishing that the selected server is the obtained set of the plurality of servers; and

providing the selected server.

3. A method for distributing a service request, the method comprising:

associating each one of a plurality of servers with a Domain Name System host name, each one of the plurality of servers having a unique IP address;

assigning a portion metric to each one of the plurality of servers, the portion metric designating a portion of total server requests to be allocated to the one of the plurality of servers;

receiving a server request, the server request being a Domain Name System host name query including the Domain Name System host name;

incrementing a total number of server requests processed by the plurality of servers;

maintaining a number of server requests distributed to each one of the plurality of servers;

selecting one of the plurality of servers using the portion metric assigned to each one of the plurality of servers, the number of server requests distributed to each one of the plurality of servers, and the total number of server requests; and

providing an IP address associated with the selected one of the plurality of servers.

4. The method as recited in claim 3, wherein selecting one of the plurality of servers further includes:

computing a metric value for each one of the plurality of servers using the number of server requests distributed to each one of the plurality of servers, the portion metric assigned to each one of the plurality of servers, and the total number of server requests processed; and

comparing the metric value for each one of the plurality of servers to determine a selected server.

5. The method as recited in claim 4, wherein maintaining the number of server requests distributed to each one of the plurality of servers further includes:

increasing the number of server requests distributed for the selected server.

6. The method as recited in claim 4, wherein the selected server has a lowest metric value.

7. The method as recited in claim 4, wherein the selected server has a highest metric value.

8. The method as recited in claim 5, wherein increasing the number of server requests distributed is performed in response to distributing the server request.

9. The method as recited in claim 3, wherein incrementing the total number of server requests further includes:

incrementing the total number of server requests in response to receiving the server request.

10. The method as recited in claim 3, wherein incrementing the total number of server requests further includes:

incrementing the total number of server requests in response to distributing the server request.

11. The method as recited in claim 3, further including:

if more than one server is selected, applying an alternate metric to a set of the plurality of servers to obtain a selected server.

12. The method as recited in claim 4, further including:

configuring a tolerance range used in comparing the metric value for each one of the plurality of servers.

13. The method as recited in claim 12, wherein comparing the metric value for each one of the plurality of servers further includes:

defining a set of the plurality of servers having metric values within the tolerance range and including the selected one of the plurality of servers; and

applying an alternate metric to the set of the plurality of servers to obtain a selected one of the plurality of servers when the set of the plurality of servers includes more than one server, and otherwise establishing that the selected one of the plurality of servers is the set of the plurality of servers.

14. The method as recited in claim 12, wherein comparing the metric value for each one of the plurality of servers further includes:

obtaining a set of the plurality of servers, each one of the set of the plurality of servers having a metric value within the tolerance range; and

applying an alternate metric to the set of the plurality of servers to obtain a selected one of the plurality of servers when the set of the plurality of servers includes more than one server, and otherwise establishing that the selected one of the plurality of servers is the set of the plurality of servers.

15. The method as recited in claim 4, wherein computing the metric value for each one of the plurality of servers further includes:

adding the portion metric for each one of the plurality of servers to obtain a total portion metric;

calculating a server request percentage for each one of the plurality of servers using the number of server requests distributed to each one of the plurality of servers, the total portion metric, and the total number of server requests received; and

determining a metric value for each one of the plurality of servers using the server request percentage distributed to each one of the plurality of servers and the portion metric assigned to each one of the plurality of servers.

16. The method as recited in claim 15, wherein calculating the server request percentage for each one of the plurality of servers further includes:

calculating a server request percentage for one of the plurality of servers using the number of server requests for the one of the plurality of servers, the total portion metric, and the total number of server requests received.

17. The method as recited in claim 16, wherein calculating the server request percentage for the one of the plurality of servers includes:

multiplying the number of server requests distributed to the one of the plurality of servers and the total portion metric to obtain a product; and

dividing the product by the total number of server requests received to obtain a server request percentage for the one of the plurality of servers.

18. The method as recited in claim 15, wherein determining the metric value for each one of the plurality of servers further includes:

determining a metric value for one of the plurality of servers using the server request percentage for the one of the plurality of servers and the portion metric for the one of the plurality of servers.

19. The method as recited in claim 18, wherein determining the metric value for the one of the plurality of servers further includes:

subtracting the portion metric for the one of the plurality of servers from the server request percentage for the one of the plurality of servers to obtain a metric value for the one of the plurality of servers.

20. The method as recited in claim 18, wherein determining the metric value for the one of the plurality of servers further includes:

subtracting the server request percentage for the one of the plurality of servers from the portion metric for one of the plurality of servers to obtain a metric value for the one of the plurality of servers.

21. The method as recited in claim 17, wherein dividing the product by the total number of server requests further includes:

if the total number of server requests is equal to zero, initializing the server request percentage for the one of the plurality of servers to a value of zero; and

if the total number of server requests is greater than zero, dividing the product by the total number of server requests received to obtain the server request percentage for the one of the plurality of servers.

22. The method as recited in claim 15, wherein calculating the server request percentage for each one of the plurality of servers further includes:

assigning a value of zero to the server request percentage for each one of the plurality of servers when the total number of server requests is equal to zero.

23. The method as recited in claim 3, further including:

initializing the total number of server requests and the number of server requests distributed to each one of the plurality of servers to a constant.

24. The method as recited in claim 23, wherein the constant is zero.

25. The method as recited in claim 3, wherein incrementing the total number of server requests further includes:

adding the number of server requests distributed to each one of the plurality of servers to obtain the total number of server requests.

26. A method for distributing a service request, the method comprising:

assigning a portion metric to each one of a plurality of servers, the portion metric designating a portion of total server requests to be allocated to the one of the plurality of servers;

adding the portion metric for each one of the plurality of servers to obtain a total portion metric;

maintaining a number of server requests distributed to each one of the plurality of servers;

receiving a server request;

incrementing a total number of server requests processed by the plurality of servers;

computing a server request percentage for each one of the plurality of servers, the server request percentage for one of the plurality of servers being a product of the number of server requests distributed to the one of the plurality of servers and the total portion metric divided by the total number of server requests received;

calculating a metric value for each one of the plurality of servers, the metric value for one of the plurality of servers being defined by the server request percentage for the one of the plurality of servers and the portion metric for the one of the plurality of servers;

comparing the metric value for each one of the plurality of servers to obtain a selected server;

applying an alternate metric to the selected server when the selected server includes more than one server; and

providing the selected server.

27. The method as recited in claim 26, wherein the alternate metric is a distance metric.

28. The method as recited in claim 26, further including:

turning a plurality of metrics on, the plurality of metrics including the alternate metric.

29. The method as recited in claim 26, further including:

specifying an order in which each of the plurality of metrics is considered.

30. The method as recited in claim 26, further including:

specifying a priority for each one of the plurality of metrics.

31. The method as recited in claim 30, wherein specifying a priority further includes:

assigning a weight indicating a metric priority to one of the plurality of metrics.

32. A method for distributing a service request, the method comprising:

assigning a portion metric to each one of a plurality of servers, the portion metric designating a portion of total server requests to be allocated to the one of the plurality of servers;

adding the portion metric for each one of the plurality of servers to obtain a total portion metric;

maintaining a number of server requests distributed to each one of the plurality of servers;

receiving a server request;

incrementing a total number of server requests processed by the plurality of servers;

computing a server request percentage for each one of the plurality of servers, the server request percentage for one of the plurality of servers being a product of the number of server requests distributed to the one of the plurality of servers and the total portion metric divided by the total number of server requests received;

calculating a metric value for each one of the plurality of servers, the metric value for one of the plurality of servers being defined by the server request percentage for the one of the plurality of servers and the portion metric for the one of the plurality of servers;

configuring a tolerance range used in comparing the metric value for each one of the plurality of servers;

comparing the metric value for each one of the plurality of servers to obtain a set of the plurality of servers, each one of the set of the plurality of servers having a metric value within the tolerance range;

applying an alternate metric to the set of the plurality of servers to obtain a selected server when the set of the plurality of servers includes more than one server, and otherwise establishing that the selected server is the obtained set of the plurality of servers; and

providing the selected server.

33. A method for detecting load imbalance within a distributed system, the method comprising:

assigning a portion metric to each one of a plurality of servers, the portion metric designating a portion of total server requests to be allocated to the one of the plurality of servers;

adding the portion metric for each one of the plurality of servers to obtain a total portion metric;

maintaining a number of server requests distributed to each one of the plurality of servers;

receiving a server request;

incrementing a total number of server requests processed by the plurality of servers;

computing a server request percentage for each one of the plurality of servers, the server request percentage for one of the plurality of servers being a product of the number of server requests distributed to the one of the plurality of servers and the total portion metric divided by the total number of server requests received;

calculating a metric value for each one of the plurality of servers, the metric value for one of the plurality of servers being defined by the server request percentage for the one of the plurality of servers and the portion metric for the one of the plurality of servers;

configuring a tolerance range used in comparing the metric value for each one of the plurality of servers;

comparing the metric value for each one of the plurality of servers to obtain a set of the plurality of servers, each one of the set of the plurality of servers having a metric value within the tolerance range;

detecting load imbalance when the set of the plurality of servers includes only one server; and

applying an alternate metric to the set of the plurality of servers to obtain a selected server when the set of the plurality of servers includes more than one server, and otherwise establishing that the selected server is the obtained set of the plurality of servers.

34. The method as recited in claim 33, further including:

generating a report in response to the detection of load imbalance, the report including information designed to assist in correcting load imbalance.

35. The method as recited in claim 34, wherein the report includes the number of server requests distributed to each one of the plurality of servers.

36. The method as recited in claim 33, further including:

reassigning portion metrics for selected ones of the plurality of servers in response to the detection of load imbalance.

37. The method as recited in claim 33, further including:

reconfiguring the tolerance range in response to the detection of load imbalance.