A game-theoretic method of fair resource allocation for cloud computing services
Tóm tắt
As cloud-based services become more numerous and dynamic, resource provisioning becomes more and more challenging. A QoS constrained resource allocation problem is considered in this paper, in which service demanders intend to solve sophisticated parallel computing problem by requesting the usage of resources across a cloud-based network, and a cost of each computational service depends on the amount of computation. Game theory is used to solve the problem of resource allocation. A practical approximated solution with the following two steps is proposed. First, each participant solves its optimal problem independently, without consideration of the multiplexing of resource assignments. A Binary Integer Programming method is proposed to solve the independent optimization. Second, an evolutionary mechanism is designed, which changes multiplexed strategies of the initial optimal solutions of different participants with minimizing their efficiency losses. The algorithms in the evolutionary mechanism take both optimization and fairness into account. It is demonstrated that Nash equilibrium always exists if the resource allocation game has feasible solutions.
Tài liệu tham khảo
Al-Ali R, Amin K, von Laszewski G, Rana O, Walker D, Hategan M, Zaluzec N (2004) Analysis and provision of QoS for distributed grid applications. J Grid Comput 2(2):163–182
Amoura AK, Bampis E, Kenyon C, Manoussakis Y (2002) Scheduling independent multiprocessor tasks. Algorithmica 32:247–261
An B, Douglis F, Ye F (2008) Heuristics for negotiation schedules in multi-plan optimization. In: Proc of the seventh international joint conference on autonomous agents and multi-agent systems, 2008, pp 551–558
An B, Vasilakos AV, Lesser V (2009) Evolutionary stable resource pricing strategies. In: ACM SIGCOMM 2009, Barcelona, Spain, August 17–21, 2009
Andelman N, Azar Y, Sorani M (2005) Truthful approximation mechanisms for scheduling selfish related machines. In: STOC 2005, pp 69–82
Borst S, Boxma O, Groote JF, Mauw S (2003) Task allocation in a multi-server system. J Sched 6:423–436
Boyera WF, Hura GS (2005) Non-evolutionary algorithm for scheduling dependent tasks in distributed heterogeneous computing environments. J Parallel Distrib Comput 65:1035–1046
Briest P, Krysta P, Vöcking B (2205) Approximation techniques for utilitarian mechanism design. In: STOC 2005, pp 39–48
Buyya R, Abramson D, Giddy J, Stockinger H (2002) Economic models for resource management and scheduling in grid computing. Special issue on grid computing environments. J Concurr Comput: Pract Exp (CCPE) 14:13–15
Christodoulou G, Koutsoupias E, Kovacs A (2007) Mechanism design for fractional scheduling on unrelated machines. In: ICALP 2007
Christodoulou G, Koutsoupias E, Vidali A (2007) A lower bound for scheduling mechanisms. In: SODA 2007, pp 1163–1169
Collins DE, George AD (2001) Parallel and sequential job scheduling in heterogeneous clusters: a simulation study using software in the loop. Simulation 77:169–184
Dobzinski S, Nisan N, Schapira M (2005) Approximation algorithms for combinatorial auctions with complement-free bidders. In: STOC 2005, pp 610–618
Dogan A, Özgüner F (2002) Scheduling independent tasks with QoS requirements in grid computing with time-varying resource prices. In: CCGRID 2002, pp 58–69
Doulamis N, Doulamis A, Litke A, Panagakis A, Varvarigou T, Varvarigos E (2007) Adjusted fair scheduling and non-linear workload prediction for QoS guarantees in grid computing. Comput Commun 30:499–515
Hochbaum DS (1996) Approximation algorithms for NP-hard problems. PWS Publishing, Boston
Iverson MA, Ozguner F, Potter L (1999) Statistical prediction of task execution times through analytic benchmarking for scheduling in a heterogeneous environment. IEEE Trans Comput 48(12):1374–1379
Karatza HD, Hilzer RC (2003) Parallel job scheduling in homogeneous distributed systems. Simulation 79(5–6):287–298
Koole G, Righter R (2008) Resource allocation in grid computing. J Sched 11:163–173
Korkhov VV, Krzhizhanovskaya VV, Sloot PMA (2008) A grid-based virtual reactor: parallel performance and adaptive load balancing. J Parallel Distrib Comput 68:596–608
Korkhova VV, Moscicki JT, Krzhizhanovskaya VV (2009) Dynamic workload balancing of parallel applications with user-level scheduling on the grid. Future Gener Comput Syst 25:28–34
Lavi R, Swamy C (2007) Truthful mechanism design for multi-dimensional scheduling via cycle-monotonicity. In: EC 2007
Lenstra JK, Shmoys DB, Tardos E (1990) Approximation algorithms for scheduling unrelated parallel machines. Math Program 46(1):259–271
Li K (2004) Experimental performance evaluation of job scheduling and processor allocation algorithms for grid computing on metacomputers. In: IPDPS 2004, pp 170–177
Mualem A, Schapira M (2007) Setting lower bounds on truthfulness. In: SODA 2007, pp 1143–1152
Nisan N, Ronen A (1999) Algorithmic mechanism design (extended abstract). In: STOC 1999, pp 129–140
Nisan N, Ronen A (2001) Algorithmic mechanism design. Games Econ Behav 35:166–196
Ranganathan K, Ripeanu M, Sarin A, Foster I (2004) Incentive mechanisms for large collaborative resource sharing. In: CCGrid 2004, pp 1-8
Schoneveld A, de Ronde JF, Sloot PMA (1997) On the complexity of task allocation. Complexity 3:52–60
Schopf JM (2003) Ten actions when grid scheduling. In: Nabrzyski J, Schopf JM, Weglarz J (eds) Grid resource management: state of the art and future trends. Kluwer, Dordrecht (Chap 2)
Sonmez OO, Gursoy A (2007) A novel economic-based scheduling heuristic for computational grids. Int J High Perform Comput Appl 21(1):21–29
Wolski R, Plank JS, Brevik J, Bryan T (2001) G-commerce: Market formulations controlling resource allocation on the computational grid. In: Proceeding of IPDPS 2001, p 46