Resource Allocation with a Budget Constraint for Computing Independent Tasks in the Cloud

We consider the problem of running a large amount of independent equal-sized tasks in the cloud with a budget constraint. We model the cloud infrastructure by a node-weighted edge-weighted star-shaped graph which captures the different computing power and communication capacity of the computing resources in the cloud. Instead of trying to minimize the make span or the total-completion-time of the system, our study focuses on the maximization of the steady-state throughput of the system. We show that the specific budget-constrained steady-state throughput maximization problem can be formulated and solved as a linear programming problem. We identify two modes of the system, i.e., the budget-bound mode and the communication-bound mode where the closed-form solutions exist for the formulated problem. The best allocation scheme is benefit-first when the system is budget-bound, where the preference should be given to the nodes in the order of increasing cost, and is bandwidth-first when the system is communication-bound, where the preference should be given to compute nodes in the order of decreasing bandwidth.