Allocating computing resources based on user intent

• US 9,495,211 B1
• Filed: 03/04/2014
• Issued: 11/15/2016
• Est. Priority Date: 03/04/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Helstroom, David J., Weir, Patricia, Smith, Cameron Cody, Hirsch, Zachary A., Longyear, Ulric B.
• Primary Examiner(s): Swift, Charles
• Application Number:
  US14/196,518
• Time in Patent Office: 987 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/5005 to service a request
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: G06F 9/5022 Mechanisms to release resources
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/5033 considering data affinity
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/5044 considering hardware capabilities
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/5055 considering software capabilities, i.e. software resources associated or available to the machine
• CPC Class Codes: G06F 9/5061 Partitioning or combining of resources
• CPC Class Codes: G06F 9/5072 Grid computing
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for allocating computing resources. In one aspect, a method includes receiving intent data specifying one or more computing services to be hosted by a computing network, requested characteristics of computing resources for use in hosting the computing service, and a priority value for each requested characteristic. A budget constraint is identified for each computing service. Available resources data is identified that specifies a set of available computing resources. A resource allocation problem for allocating computing resources for the one or more computing resources is generated based on the intent data, each budget constraint, and the available resources data. At least a portion of the set of computing resources is allocated for the one or more computing services based on results of evaluating the resource allocation problem to meet a particular resource allocation objective.

Claims

1. A method performed by data processing apparatus, the method comprising:

receiving intent data specifying;

one or more computing services to be hosted by a computing network;

one or more requested characteristics of underlying computing resources for use in hosting the computing service on the computing network; and

for each requested characteristic, a priority value that indicates a priority of the requested characteristic relative to a priority of each other requested characteristic;

identifying a budget constraint for each of the one or more computing services;

identifying available resources data that specifies a set of available computing resources and, for each available computing resource;

characteristics of the available computing resource;

pricing data for the available computing resource; and

forecasted demand data for the available computing resource;

generating a resource allocation problem for allocating computing resources for the one or more computing services based on the received intent data, each budget constraint, and the available resources data;

allocating at least a portion of the set of computing resources for the one or more computing services based on results of evaluating the resource allocation problem to meet a particular resource allocation objective, the allocating comprising;

determining that the budget constraint is not satisfied by a first allocation of computing resources resulting from solving the resource allocation problem to meet the particular resource allocation objective;

generating an adjusted resource allocation problem by removing at least one requested characteristic from the resource allocation problem, the at least one requested characteristic being selected for removal based on the priority value for the at least one requested characteristic; and

identifying a second allocation of computing resources based on results of solving the adjusted resource allocation problem to meet the particular resource allocation objective; and

providing, for the one or more computing services, access to the allocated computing resources.

2. The method of claim 1, wherein the resource allocation problem comprises one of a linear programming problem and a mixed integer programming problem.

3. The method of claim 1, wherein generating the resource allocation problem includes identifying, for each of the one or more computing services, one or more underlying computing services and one or more underlying computing resources that will be used to provide the computing service using a translation function for the computing service.

4. The method of claim 3, wherein generating a resource allocation problem includes:

generating a graph based on (a) the one or more underlying computing services and the one or more underlying computing resources for each of the one or more computing services specified by the intent data and (b) the available resources data, the graph comprising;

a node of each underlying computing service;

a node for each underlying computing resource; and

edges between two or more pairs of nodes, a particular edge between a particular pair of nodes representing a dependency of a first node of the particular pair of nodes on a second node of the particular pair of node; and

generating the resource allocation problem based on the generated graph.

5. The method of claim 4, wherein the graph further comprises, for each edge, data identifying a requested performance characteristic of a relationship between a pair of nodes connected by the edge.

6. The method of claim 4, wherein the graph comprises a directed acyclic graph.

7. The method of claim 1, wherein allocating the at least a portion of the set of computing resources for the one or more services comprises:

identifying a third allocation of computing resources based on results of solving the resource allocation problem to meet the particular objective;

determining that a cluster of computing resources is over-allocated based on the third allocation of computing resources;

increasing a price of at least one computing resource of the cluster in the resource allocation problem to generate a second adjusted resource allocation problem; and

identifying a fourth allocation of computing resources based on results of solving the second adjusted resource allocation problem to meet the particular resource allocation objective.

8. The method of claim 1, wherein the particular resource allocation objective comprises reducing a total cost for implementing the one or more computing services.

9. The method of claim 1, wherein allocating at least a portion of the set of computing resources for the one or more computing services based on results of solving the resource allocation problem comprises:

to determine a first forecasted resource allocation, solving the resource allocation problem to identify a forecasted resource allocation that maximizes a number of the requested performance characteristics provided for each of the one or more computing services based on an infinite amount of available computing resources; and

to determine a second forecasted resource allocation, solving the resource allocation problem to identify a forecasted allocation that minimizes a total cost of computing resources for each of the one or more computing services based on a finite amount of available computing resources.

10. A system comprising:

a data store for storing data related to available computing resources; and

one or more processors configured to interact with the data store, the one or more processors being further configured to perform operations comprising;

receiving intent data specifying;

one or more computing services to be hosted by a computing network;

one or more requested characteristics of underlying computing resources for use in hosting the computing service on the computing network; and

for each requested characteristic, a priority value that indicates a priority of the requested characteristic relative to a priority of each other requested characteristic;

identifying a budget constraint for each of the one or more computing services;

identifying available resources data that specifies a set of available computing resources and, for each available computing resource;

characteristics of the available computing resource;

pricing data for the available computing resource; and

forecasted demand data for the available computing resource;

generating a resource allocation problem for allocating computing resources for the one or more computing services based on the received intent data, each budget constraint, and the available resources data;

allocating at least a portion of the set of computing resources for the one or more computing services based on results of evaluating the resource allocation problem to meet a particular resource allocation objective, the allocating comprising;

determining that the budget constraint is not satisfied by a first allocation of computing resources resulting from solving the resource allocation problem to meet the particular resource allocation objective;

generating an adjusted resource allocation problem by removing at least one requested characteristic from the resource allocation problem, the at least one requested characteristic being selected for removal based on the priority value for the at least one requested characteristic; and

identifying a second allocation of computing resources based on results of solving the adjusted resource allocation problem to meet the particular resource allocation objective; and

providing, for the one or more computing services, access to the allocated computing resources.

11. The system of claim 10, wherein the resource allocation problem comprises one of a linear programming problem and a mixed integer programming problem.

12. The system of claim 10, wherein generating the resource allocation problem includes identifying, for each of the one or more computing services, one or more underlying computing services and one or more underlying computing resources that will be used to provide the computing service using a translation function for the computing service.

13. The system of claim 12, wherein generating a resource allocation problem includes:

generating a graph based on (a) the one or more underlying computing services and the one or more underlying computing resources for each of the one or more computing services specified by the intent data and (b) the available resources data, the graph comprising;

a node of each underlying computing service;

a node for each underlying computing resource; and

edges between two or more pairs of nodes, a particular edge between a particular pair of nodes representing a dependency of a first node of the particular pair of nodes on a second node of the particular pair of node; and

generating the resource allocation problem based on the generated graph.

14. The system of claim 13, wherein the graph further comprises, for each edge, data identifying a requested performance characteristic of a relationship between a pair of nodes connected by the edge.

15. The system of claim 10, wherein allocating the at least a portion of the set of computing resources for the one or more services comprises:

identifying a third allocation of computing resources based on results of solving the resource allocation problem to meet the particular objective;

determining that a cluster of computing resources is over-allocated based on the third allocation of computing resources;

increasing a price of at least one computing resource of the cluster in the resource allocation problem to generate a second adjusted resource allocation problem; and

identifying a fourth allocation of computing resources based on results of solving the second adjusted resource allocation problem to meet the particular resource allocation objective.

16. The system of claim 10, wherein the particular resource allocation objective comprises reducing a total cost for implementing the one or more computing services.

17. The system of claim 10, wherein allocating at least a portion of the set of computing resources for the one or more services based on results of solving the resource allocation problem comprises:

to determine a first forecasted resource allocation, solving the resource allocation problem to identify a forecasted resource allocation that maximizes a number of the requested performance characteristics provided for each of the one or more computing services based on an infinite amount of available computing resources; and

to determine a second forecasted resource allocation, solving the resource allocation problem to identify a forecasted allocation that minimizes a total cost of computing resources for each of the one or more computing services based on a finite amount of available computing resources.

18. A computer storage medium encoded with a computer program, the program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

receiving intent data specifying;

one or more computing services to be hosted by a computing network;

one or more requested characteristics of underlying computing resources for use in hosting the computing service on the computing network; and

for each requested characteristic, a priority value that indicates a priority of the requested characteristic relative to a priority of each other requested characteristic;

identifying a budget constraint for each of the one or more computing services;

identifying available resources data that specifies a set of available computing resources and, for each available computing resource;

characteristics of the available computing resource;

pricing data for the available computing resource; and

forecasted demand data for the available computing resource;

generating a resource allocation problem for allocating computing resources for the one or more computing services based on the received intent data, each budget constraint, and the available resources data;

allocating at least a portion of the set of computing resources for the one or more computing services based on results of evaluating the resource allocation problem to meet a particular resource allocation objective, the allocating comprising;

determining that the budget constraint is not satisfied by a first allocation of computing resources resulting from solving the resource allocation problem to meet the particular resource allocation objective;

generating an adjusted resource allocation problem by removing at least one requested characteristic from the resource allocation problem, the at least one requested characteristic being selected for removal based on the priority value for the at least one requested characteristic; and

identifying a second allocation of computing resources based on results of solving the adjusted resource allocation problem to meet the particular resource allocation objective; and

providing, for the one or more computing services, access to the allocated computing resources.