A Resource Leasing Policy for on-Demand Computing

Abstract

Leasing computational resources for on-demand computing is now a viable option for providers of network services. Temporary spikes or lulls in demand for a service can be accommodated by flexible leasing arrangements. From the service provider's perspective, the problem is how many resources to lease and for how long. In this paper we formulate and solve the resource leasing problem for the case of a single service. The objective is to minimize the cost of leasing resources while still maintaining an adequate quality of service, which we measure by the average wait time of requests. Demand for the service and execution times of service requests are modeled as random variables. The problem is formulated as a continuous-time, infinite-horizon Markov decision problem. We use the dynamic programming method of value iteration for its solution and we characterize the resulting optimal cost function. We find that the cost of providing a service is convex-like in the number of resources leased and nondecreasing in the number of requests in the system. Close examination of the optimal cost function shows that the cost of providing a service is more sensitive to underdeployment than to overdeployment. Thus, when demand for the service is known to exist, but is unpredictable, it is better to lease more resources than fewer resources.

Keywords

Network services On-demand computing Grid computing Dynamic programming

Get full access to this article

View all access options for this article.

References

Arnold, D. et al. 2002. Users’ Guide to NetSolve V1.4.1. Innovative Computing Department Technical Report ICL-UT-02-05, University of Tennessee, Knoxville, TN, June.

Bertsekas, D. P. 2000. Dynamic Programming and Optimal Control, 2nd edition, Vol. 1, Athena Scientific, Nashua .

Bertsekas, D. P. 2001. Dynamic Programming and Optimal Control, 2nd edition, Vol. 2, Athena Scientific, Nashua .

Bertsekas, D. P. and Tsitsiklis, J. N. 1996. Neuro-Dynamic Programming, Athena Scientific, Nashua .

Bolch, G. et al. 1998. Queuing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications, Wiley, New York .

Buyya, R. et al. 2002. Economic models for resource management and scheduling in grid computing . Concurrency and Computation: Practice and Experience 14(13–15): 1507–1542 .

England, D. and Weissman, J. 2004. A stochastic control model for deployment of dynamic grid services. Proceedings of the 5th IEEE/ACM International Workshop on Grid Computing (GRID 2004), Pittsburgh, PA , November 8, pp. 192–199.

Foster, I. and Kesselman, C. , editors. 2004. The Grid: Blueprint for a New Computing Infrastructure, Vol. 2, Elsevier, Amsterdam .

Foster, I. , Kesselman, C. , and Tuecke, S. 2001. The anatomy of the grid: enabling scalable virtual organizations . International Journal of Supercomputer Applications 15(3): 200–222 .

10.

Foster, I. et al. 2002. Grid services for distributed system integration . Computer 35(6): 37–46 .

11.

Fox, A. et al. 1997. Cluster-based scalable network services. Proceedings of the 16th ACM Symposium on Operating Systems Principles (SOSP’97) Saint-Malo, France , October 5–8.

12.

Gross, D. M. and Harris, C. M. 1985. Fundamentals of Queueing Theory, 2nd edition, Wiley, New York .

13.

Marbach, P. , Mihatsch, O. , and Tsitsiklis, J. N. 2000. Call admission control and routing in integrated services networks using neuro-dynamic programming . IEEE Journal on Selected Areas in Communications 18(2): 197–208 .

14.

Resnick, S. I. 1992. Adventures in Stochastic Processes, Birkhäuser, Boston .

15.

Ross, S. M. 1989. Introduction to Probability Models, 4th edition, Academic Press, New York .

16.

Tanaka, Y. et al. 2003. Ninf-g: a reference implementation of rpc-based programming middleware for grid computing . Journal of Grid Computing 1(1): 41–51 .

17.

von Behren, R. et al. 2002. Ninja: a framework for network services. Proceedings of the 2002 USENIX Annual Technical Conference, Monterey, CA .

18.

Weissman, J. B. and Lee, B-D. 2001. The service grid: supporting scalable heterogeneous services in wide-area networks. Proceedings of the IEEE Symposium on Applications and the Internet, San Diego, CA .

19.

Weissman, J. B. and Lee, B-D. 2002. The virtual service grid: an architecture for delivering high-end network services . Concurrency: Practice and Experience 14(4): 287–319 .

20.

Weissman, J. B. , Kim, S. H. , and England, D. 2005. Supporting the dynamic grid service life cycle. Proceedings of the IEEE International Symposium on Cluster Computing and the Grid (CCGrid2005), Cardiff, UK , May.

21.

Welsh, M. , Culler, D. , and Brewer, E. 2001. Seda: an architecture for well-conditioned, scalable internet services. Proceedings of the 18th ACM Symposium on Operating Systems Principles (SOSP’01), Banff, Canada , October 21–24.

22.

Wolski, R. et al. 2001. G-commerce: market formulations controlling resource allocation on the computational grid. Proceedings of the International Parallel and Distributed Processing Symposium, San Francisco, CA , April 23–27.

23.

Wolski, R. et al. 2003. Grid resource allocation and control using computational economies. Grid Computing: Making the Global Infrastructure a Reality, F. Berman , G. Fox , and A. Hey , editors, Wiley, New York , Chapter 32, pp. 747–769.