Methods and apparatus for selecting a server to process a request

• US 7,320,131 B1
• Filed: 06/06/2001
• Issued: 01/15/2008
• Est. Priority Date: 06/06/2001
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: O'Toole, James W. Jr.
• Primary Examiner(s): An; Meng-Al T.
• Assistant Examiner(s): Tang; Kenneth
• Application Number:
  US09/875,521
• Time in Patent Office: 2,414 Days
• Field of Search: 718/1, 718100-108, 709200-253, 705/52
• US Class Current: 718/104
• CPC Class Codes: G06F 2209/5019 Workload prediction
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06Q 20/102 Bill distribution or payments
• CPC Class Codes: H04L 67/61 taking into account QoS or priority requirements

Abstract

The invention is directed to techniques for selecting a resource from several resources to process a request from a client. A client sends the request to a data communications device (e.g., network device or switch), which measures usage information from usage meters associated with each resource (e.g., server). The data communications device then makes a usage estimate for each server of the increase in usage required for that server to process the request from the client. Then the data communications device selects one of the servers depending on the usage estimates required to respond to the client'"'"'s request. The data communications device can consider other factors such as the current level of usage, past usage, and the increased cost of responding to the request. In addition, the data communications device can consider the peak usage level of each resource already established in a current billing period.

Claims

1. A method in a data communications device for directing a request to process data, comprising the steps of:

maintaining cost information for a plurality of resources available to satisfy client requests via a plurality of resource providers, the cost information for each resource specifying a relationship between levels of usage of the resource in a billing interval and corresponding levels of prices charged by the respective resource provider in the billing interval;

maintaining usage information for the plurality of resources, the usage information for each resource specifying a level of usage of the resource that has been experienced during the billing interval;

receiving the request from a client;

generating, based on the usage information and an estimated request usage of the request, an estimated response usage for each resource of the plurality of resources that reflects a potential usage if responding to the request, each estimated response usage being associated, via the cost information, with a corresponding cost estimate for processing the request, a first cost estimate being a first cost increase for a first resource of the plurality of resources if the first resource responds to the request, and a second cost estimate being a second cost increase for a second resource of the plurality of resources if the second resource responds to the request;

selecting a resource from said plurality of resources to process the request based on the respective cost estimate associated with said estimated response usage of each of said resources, the selecting including (1) comparing the first cost increase and the second cost increase to determine one of the first and second cost increases that has a lower cost increment, and (2) selecting one of the first resource and the second resource to respond to the request from the client based on the lower cost increment; and

forwarding the request to the selected resource.

2. The method of claim 1, wherein the step of selecting a resource comprises:

generating an estimated available usage for each resource based on the request and usage information received from a usage meter for each resource; and

selecting the resource based on a highest estimated available usage for each resource.

3. The method of claim 1 wherein the data communications device is in communication with multiple servers, and wherein the method further comprises the step of:

receiving server data from the servers to make cost estimates based on a marginal cost increase for each server to handle the request, where past usage is a relevant factor when considering a peak usage level already established for a resource in a billing period.

4. A data communications device for directing a request to process data, comprising:

a memory that stores a cost modeler application;

an interconnection mechanism; and

a processor coupled to the memory by the interconnection mechanism, wherein the processor operates in accordance with instructions of the cost modeler application stored in the memory to direct the request, the instructions of the cost modeler application configuring the processor to;

maintain cost information for a plurality of resources available to satisfy client requests via a plurality of resource providers, the cost information for each resource specifying a relationship between levels of usage of the resource in a billing interval and corresponding levels of prices charged by the respective resource provider in the billing interval;

maintain usage information for the plurality of resources, the usage information for each resource specifying a level of usage of the resource that has been experienced during the billing interval;

receive the request from a client;

generate, based on the usage information and an estimated request usage of the request, an estimated response usage for each resource of the plurality of resources that reflects a potential usage if responding to the request, each estimated response usage being associated, via the cost information, with a corresponding cost estimate for processing the request, a first cost estimate being a first cost increase for a first resource of the plurality of resources if the first resource responds to the request, and a second cost estimate being a second cost increase for a second resource of the plurality of resources if the second resource responds to the request;

select a resource from said plurality of resources to process the request based on the respective cost estimate associated with said estimated response usage of each of said resources, by (1) comparing the first cost increase and the second cost increase to determine one of the first and second cost increases that has a lower cost increment, and (2) selecting one of the first resource and the second resource to respond to the request from the client based on the lower cost increment; and

forward the request to the selected resource.

5. The data communications device of claim 4, wherein the cost modeler application comprises further instructions that configure the processor to:

generate an estimated available usage for each resource based on the request and usage information received from a usage meter for each resource; and

select the resource based on a highest estimated available usage for each resource.

6. A data communications device for directing a request to process data, comprising:

means for maintaining cost information for a plurality of resources available to satisfy client requests via a plurality of resource providers, the cost information for each resource specifying a relationship between levels of usage of the resource in a billing interval and corresponding levels of prices charged by the respective resource provider in the billing interval;

means for maintaining usage information for the plurality of resources, the usage information for each resource specifying a level of usage of the resource that has been experienced during the billing interval;

means for receiving the request from a client;

means for generating, based on the usage information and an estimated request usage of the request, an estimated response usage for each resource of the plurality of resources that reflects a potential usage if responding to the request, each estimated response usage being associated, via the cost information, with a corresponding cost estimate for processing the request, a first cost estimate being a first cost increase for a first resource of the plurality of resources if the first resource responds to the request, and a second cost estimate being a second cost increase for a second resource of the plurality of resources if the second resource responds to the request;

means for selecting a resource from said plurality of resources to process the request based on the respective cost estimate associated with said estimated response usage of each of said resources, the selecting including (1) comparing the first cost increase and the second cost increase to determine one of the first and second cost increases that has a lower cost increment, and (2) selecting one of the first resource and the second resource to respond to the request from the client based on the lower cost increment; and

means for forwarding the request to the selected resource.

7. A computer program product that includes a computer readable medium having instructions stored thereon for directing a request to process data, such that the instructions, when carried out by a data communications device, cause the data communications device to perform the steps of:

maintaining cost information for a plurality of resources available to satisfy client requests via a plurality of resource providers, the cost information for each resource specifying a relationship between levels of usage of the resource in a billing interval and corresponding levels of prices charged by the respective resource provider in the billing interval;

maintaining usage information for the plurality of resources, the usage information for each resource specifying a level of usage of the resource that has been experienced during the billing interval;

receiving the request from a client;

generating, based on the usage information and an estimated request usage of the request, an estimated response usage for each resource of the plurality of resources that reflects a potential usage if responding to the request, each estimated response usage being associated, via the cost information, with a corresponding cost estimate for processing the request, a first cost estimate being a first cost increase for a first resource of the plurality of resources if the first resource responds to the request, and a second cost estimate being a second cost increase for a second resource of the plurality of resources if the second resource responds to the request;

selecting a resource from said plurality of resources to process the request based on the respective cost estimate associated with said estimated response usage of each of said resources, the selecting including (1) comparing the first cost increase and the second cost increase to determine one of the first and second cost increases that has a lower cost increment, and (2) selecting one of the first resource and the second resource to respond to the request from the client based on the lower cost increment; and

forwarding the request to the one of the plurality of resources selected in the step of selecting.

8. A method for selecting with a data communication device a resource from a plurality of resources to process a request from a client, comprising the steps of:

maintaining cost information for a plurality of resources available to satisfy client requests via a plurality of resource providers, the cost information for each resource specifying a relationship between levels of usage of the resource in a billing interval and corresponding levels of prices charged by the respective resource provider in the billing interval;

maintaining usage information for the plurality of resources, the usage information for each resource specifying a level of usage of the resource that has been experienced during the billing interval;

generating, based on the usage information and an estimated request usage of the request, a usage metric for each resource of the plurality of resources;

generating an economic metric for each resource based on the cost information, the usage metric for each resource, and the request, a first economic metric being a first cost increase for a first resource of the plurality of resources if the first resource responds to the request, and a second economic metric being a second cost increase for a second resource of the plurality of resources if the second resource responds to the request; and

choosing with the data communication device one of the plurality of the resources to respond to the request for data based on a comparison of the economic metric for each resource, the choosing including (1) comparing the first cost increase and the second cost increase to determine one of the first and second cost increases that has a lower cost increment, and (2) selecting one of the first resource and the second resource to respond to the request from the client based on the lower cost increment.

9. The method of claim 8, wherein the step of generating the usage metric comprises the steps of:

receiving usage information from a usage meter for each resource that measures the amount of usage of each resource over time;

generating an estimated base usage of each resource based on the usage information; and

generating a peak usage metric for each resource that represents a measurement of the highest level of usage attained for each resource over a current billing period based on the usage information.

10. The method of claim 8, wherein the step of generating the economic metric comprises the steps of:

generating an estimated request usage for each resource that reflects an estimate of the projected usage of each resource over a current time based on the request for data; and

generating an estimated available usage for each resource based on the usage metric for each resource and the estimated request usage for each resource.

11. The method of claim 10, wherein:

the step of generating the estimated available usage comprises generating the estimated available usage based on the estimated request usage for each resource, an estimated base usage for each resource based on usage information received for each resource, and a peak usage metric for each resource that represents a measurement of the highest level of usage attained for each resource over a current billing period based on the usage information.

12. The method of claim 11, wherein the step of generating the estimated available usage comprises the steps of:

identifying a subset of the plurality of resources wherein the estimated request usage is higher than a predetermined usage limit defined relative to the peak usage metric for each resource; and

assigning a predetermined marginal cost to an incremental usage of each resource in the subset.

13. The method of claim 8, wherein the step of generating the economic metric comprises generating a bandwidth metric that represents the bandwidth requirements for each resource based on (i) the request and (ii) the network address of a client providing the request and the network address of each resource.

14. The method of claim 8, wherein the step of generating the economic metric comprises generating the economic metric based on a category of the request that indicates an estimated request usage for each resource.

15. The method of claim 8, wherein the step of choosing one of the plurality of resources comprises the step of:

comparing an estimated available usage for each resource generated based on the request and the usage metric for each resource.

16. A data communication device for selecting a resource from a plurality of resources to process a request from a client, the data communication device comprising:

a memory that stores a cost modeler application;

an interconnection mechanism; and

a processor coupled to the memory by the interconnection mechanism, wherein the processor operates in accordance with instructions of the cost modeler application stored in the memory to select the resource, the instructions of the cost modeler application configuring the processor to;

maintain cost information for a plurality of resources available to satisfy client requests via a plurality of resource providers, the cost information for each resource specifying a relationship between levels of usage of the resource in a billing interval and corresponding levels of prices charged by the respective resource provider in the billing interval;

maintain usage information for the plurality of resources, the usage information for each resource specifying a level of usage of the resource that has been experienced during the billing interval;

generate, based on the usage information and an estimated request usage of the request, a usage metric for each resource of the plurality of resources;

generate an economic metric for each resource based on the cost information, the usage metric for each resource, and the request, a first economic metric being a first cost increase for a first resource of the plurality of resources if the first resource responds to the request, and a second economic metric being a second cost increase for a second resource of the plurality of resources if the second resource responds to the request; and

choose one of the plurality of the resources to respond to the request for data based on a comparison of the economic metric for each resource, by (1) comparing the first cost increase and the second cost increase to determine one of the first and second cost increases that has a lower cost increment, and (2) selecting one of the first resource and the second resource to respond to the request from the client based on the lower cost increment.

17. The data communications device of claim 16, wherein the cost modeler application comprises further instructions that configure the processor to:

receive usage information from a usage meter for each resource that measures the amount of usage of each resource over time;

generate an estimated base usage of each resource based on the usage information; and

generate a peak usage metric for each resource that represents a measurement of the highest level of usage attained for each resource over a current billing period based on the usage information.

18. The data communications device of claim 16, wherein the cost modeler application comprises further instructions that configure the processor to:

generate an estimated request usage for each resource that reflects an estimate of the projected usage of each resource over a current time based on the request for data; and

generate an estimated available usage for each resource based on the usage metric for each resource and the estimated request usage for each resource.

19. The data communications device of claim 18, wherein the cost modeler application comprises further instructions that configure the processor to generate the estimated available usage based on the estimated request usage for each resource, an estimated base usage for each resource based on usage information received for each resource, and a peak usage metric for each resource that represents a measurement of the highest level of usage attained for each resource over a current billing period based on the usage information.

20. The data communications device of claim 19, wherein the cost modeler application comprises further instructions that configure the processor to:

identify a subset of the plurality of resources wherein the estimated request usage is higher than a predetermined usage limit defined relative to the peak usage metric for each resource; and

assign a predetermined marginal cost to an incremental usage of each resource in the subset.

21. The data communications device of claim 16, wherein the cost modeler application comprises further instructions that configure the processor to generate a bandwidth metric that represents the bandwidth requirements for each resource based on (i) the request and (ii) the network address of a client providing the request and the network address of each resource.

22. The data communications device of claim 16, wherein the cost modeler application comprises further instructions that configure the processor to generate the economic metric based on a category of the request that indicates an estimated request usage for each resource.

23. The data communications device of claim 16, wherein the cost modeler application comprises further instructions that configure the processor to compare an estimated available usage for each resource generated based on the request and the usage metric for each resource.

24. A data communications device for selecting a resource from a plurality of resources to process a request from a client, the data communications device comprising:

means for maintaining cost information for a plurality of resources available to satisfy client requests via a plurality of resource providers, the cost information for each resource specifying a relationship between levels of usage of the resource in a billing interval and corresponding levels of prices charged by the respective resource provider in the billing interval;

means for maintaining usage information for the plurality of resources, the usage information for each resource specifying a level of usage of the resource that has been experienced during the billing interval;

means for generating, based on the usage information and an estimated request usage of the request, a usage metric for each resource of the plurality of resources;

means for generating an economic metric for each resource based on the cost information, the usage metric for each resource, and the request, a first economic metric being a first cost increase for a first resource of the plurality of resources if the first resource responds to the request, and a second economic metric being a second cost increase for a second resource of the plurality of resources if the second resource responds to the request; and

means for choosing one of the plurality of the resources to respond to the request for data based on a comparison of the economic metric for each resource, by (1) comparing the first cost increase and the second cost increase to determine one of the first and second cost increases that has a lower cost increment, and (2) selecting one of the first resource and the second resource to respond to the request from the client based on the lower cost increment.

25. A computer program product that includes a computer readable medium having instructions stored thereon for selecting a resource from a plurality of resources to process a request from a client, such that the instructions, when carried out by a data communications device, cause the data communications device to perform the steps of:

maintaining cost information for a plurality of resources available to satisfy client requests via a plurality of resource providers, the cost information for each resource specifying a relationship between levels of usage of the resource in a billing interval and corresponding levels of prices charged by the respective resource provider in the billing interval;

maintaining usage information for the plurality of resources, the usage information for each resource specifying a level of usage of the resource that has been experienced during the billing interval;

generating, based on the usage information and an estimated request usage of the request, a usage metric for each resource of the plurality of resources;

generating an economic metric for each resource based on the cost information, the usage metric for each resource, and the request, a first economic metric being a first cost increase for a first resource of the plurality of resources if the first resource responds to the request, and a second economic metric being a second cost increase for a second resource of the plurality of resources if the second resource responds to the request; and

choosing one of the plurality of the resources to respond to the request for data based on a comparison of the economic metric for each resource, by (1) comparing the first cost increase and the second cost increase to determine one of the first and second cost increases that has a lower cost increment, and (2) selecting one of the first resource and the second resource to respond to the request from the client based on the lower cost increment.

26. A method for selecting with a data communication device a resource from a plurality of resources to process a request from a client, comprising the steps of:

generating a usage metric for each resource of the plurality of resources;

generating an economic metric for each resource based on the usage metric for each resource and the request, the economic metric being based on a resource usage amount relating to the client; and

choosing with the data communication device one of the plurality of the resources to respond to the request for data based on a comparison of the economic metric for each resource,

wherein the step of generating the usage metric comprises the steps of;

receiving usage information from a usage meter for each resource that measures the amount of usage of each resource over time;

generating an estimated base usage of each resource based on the usage information; and

generating a peak usage metric for each resource that represents a measurement of the highest level of usage attained for each resource over a current billing period based on the usage information;

wherein the step of generating the economic metric comprises the steps of;

generating an estimated request usage for each resource that reflects an estimate of the projected usage of each resource over a current time based on the request for data; and

generating an estimated available usage for each resource based on the usage metric for each resource and the estimated request usage for each resource;

wherein the step of generating the estimated available usage comprises generating the estimated available usage based on the estimated request usage for each resource, an estimated base usage for each resource based on usage information received for each resource, and a peak usage metric for each resource that represents a measurement of the highest level of usage attained for each resource over a current billing period based on the usage information;

wherein the step of generating the estimated available usage comprises the steps of;

identifying a subset of the plurality of resources wherein the estimated request usage is higher than a predetermined usage limit defined relative to the peak usage metric for each resource; and

assigning a predetermined marginal cost to an incremental usage of each resource in the subset; and

wherein the step of choosing one of the plurality of resources comprises the step of comparing an estimated available usage for each resource generated based on the request and the usage metric for each resource.

27. A data communication device for selecting a resource from a plurality of resources to process a request from a client, the data communication device comprising:

a memory that stores a cost modeler application;

an interconnection mechanism; and

a processor coupled to the memory by the interconnection mechanism, wherein the processor operates in accordance with instructions of the cost modeler application stored in the memory to select the resource, the instructions of the cost modeler application configuring the processor to;

generate a usage metric for each resource of the plurality of resources;

generate an economic metric for each resource based on the usage metric for each resource and the request, the economic metric being based on a resource usage amount relating to the client; and

choose one of the plurality of the resources to respond to the request for data based on a comparison of the economic metric for each resource,

wherein the cost modeler application comprises further instructions that configure the processor to;

receive usage information from a usage meter for each resource that measures the amount of usage of each resource over time;

generate an estimated base usage of each resource based on the usage information; and

generate a peak usage metric for each resource that represents a measurement of the highest level of usage attained for each resource over a current billing period based on the usage information;

wherein the cost modeler application comprises further instructions that configure the processor to;

generate an estimated request usage for each resource that reflects an estimate of the projected usage of each resource over a current time based on the request for data; and

generate an estimated available usage for each resource based on the usage metric for each resource and the estimated request usage for each resource;

wherein the cost modeler application comprises further instructions that configure the processor to generate the estimated available usage based on the estimated request usage for each resource, an estimated base usage for each resource based on usage information received for each resource, and a peak usage metric for each resource that represents a measurement of the highest level of usage attained for each resource over a current billing period based on the usage information;

wherein the cost modeler application comprises further instructions that configure the processor to;

identify a subset of the plurality of resources wherein the estimated request usage is higher than a predetermined usage limit defined relative to the peak usage metric for each resource; and

assign a predetermined marginal cost to an incremental usage of each resource in the subset; and

wherein the cost modeler application comprises further instructions that configure the processor to compare an estimated available usage for each resource generated based on the request and the usage metric for each resource.