A Survey on Economic based Resource Allocation Algorithms on Distributed Systems

Amin Nezarat

Abstract


Due to the widespread use of cloud services, the need for proper and dynamic distribution will redouble the resources. One of the most complex problems in cloud environments is resource allocation such that on one hand the resource provider should obtain maximum utilization and on the other hand users want to lease best resources based on his time and budget constraints. Many studies which presented new methods for solving this NP-complete problem have used heuristic algorithm. Based on economic aspects of cloud environments, using market oriented model for solving allocation problem can decrease the complexity and converge it to the best solution in minimum time. In this paper, we explore the state-of-the-art models and paper for resource allocation and scheduling in grid and cloud computing.


References


J. Bredin, D. Kotz, D. Rus, R. T. Maheswaran, C. Imer and a. T. Basar, "Computational markets toregulate mobile-agent systems," Autonomous Agents and Multi-Agent Systems, vol. 6, p. 235–263, 2003.

A. Galstyan, S. Kolar and a. K. Lerman, "Resource allocation games with changing resource ca-pacities," in In Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems, 2003.

R. Gibbons, A Primer in Game Theory, Pearson Higher Education, 1992.

M. Armbrust, A. Fox and a. R. Griffith., "Above the clouds: A berkeley view of cloud computing," University of California, Berkeley, 2009.

Q. Fan, Q. Wu, F. M. es, N. Xiong, A. V. Vasilakos and a. Y. He, "Game and balance multicast architecture algorithms for sensor grid," Sensors, vol. 9, no. 9, p. 7177–7202, 2009.

R. Buyya, D. Abramson, J. Giddy and a. H. Stockinger, "Economic models for resource management and scheduling in grid computing," Concurrency and Computation: Practice and Experience, vol. 14, p. 1507–1542, 2002.

Sandholm and T. W., "Multiagent systems: a modern approach to distributed artificial intelligence," Distributed rational decision making, vol. 37, p. 201–258, 1999.

Y. k. Kwok, S. Song and a. K. Hwang, "Selfish grid computing: Game-theoretic modeling and nash performance results," in In Proceedings of International Symposium on Cluster Computing and the Grid, 2005.

R. T. Maheswaran and T. Basar, "Nash equilibrium and decentralized negotiation in auctioning divisible resources," Group Decision and Negotiation, vol. 12, p. 361–395, 2003.

S. Khan and I. Ahmad, "Non-cooperative, semi-cooperative, and cooperative games-based grid resource allocation," in Parallel and Distributed Processing Symposium, 2006.

B. An, C. Miao and Z. Shen, "Market based resource allocation with incomplete information," in In Proceedings of the 20th International Joint Conference on Artifical Intelligence, 2007.

S. Garg and R. Buyya, "Market-Orient ed Resource Management and Scheduling: A Taxonomy and Survey," Cooperative Networking, pp. 277-306, 2011.

I. E. Sutherland, "A futures market in computer time," Communications of the ACM, vol. 11, no. 6, p. 449–451, 1968.

R. A. Gagliano, M. D. Fraser and M. E. Schaefer, "Auction allocation of computing resources," Communications of the ACM, vol. 38, no. 6, p. 88–102, 1995.

M. A. Gibney, N. R. Jennings, N. J. Vriend and J.-M.Griffiths, "Market-based call routing in telecommunications networks using adaptive pricing and real bidding," in In Proceedings of the Third International Workshop on Intelligent Agents for Telecommunication Applications, 1999.

L. Joita, O. F. Rana, F. Freitag, I. Chao, P. Chacin, L. Navarro and O. Ardaiz, "A catallactic market for data mining services," Future Generation Computer Systems, vol. 23, no. 1, p. 146–153, 2007.

B. N. Chun and D. E. Culler, "User-centric performance analysis of market-based cluster batch schedulers," in In Proceedings of the 2nd IEEE/ACM International Symposium on Cluster Computing and the Grid, Washington, DC, USA, 2002.

G. Stuer, K. Vanmechelen and J. Broeckhove, "A commodity market algorithm for pricing substitutable grid resources," Future Generation Computer Systems, vol. 23, no. 5, p. 688–701, 2007.

T.-M.-H. Nguyen and F. Magoul`es, "Autonomic data management system in grid environment," Journal of Algorithms & Computational Technology, vol. 3, p. 155–177, 2009.

N. Stratford and R. Mortier, "An economic approach to adaptive resource management," in In Proceedings of the 7th Workshop on Hot Topics in Operating Systems, 1999.

C. Ozturan, "Resource bartering in data grids," Science of Computer Programming, vol. 12, no. 3, p. 155–168, 2004.

R. Wolski, J. S. Plank, J. Brevik and T. Bryan, "Analyzing market-based resource allocation strategies for the computational grid," Intl. J. of High Performance Comp Appl., vol. 15, no. 3, p. 258–281, 2001.

J. Gomoluch and M. Schroeder, "Market-based resource allocation for grid computing:A model and simulation," in In Proc. 1st International Workshop on Middleware for Grid Computing, 2003.

S. K. Garg, S. Venugopal, J. Broberg and R. Buyya, "Double auction-inspired meta-scheduling of parallel applications on global grids," Journal of Parallel and Distributed Computing, 2013.

A. Das and D. Grosu, "Combinatorial auction-based protocols for resource allocation in grids," in In Proc. 19th International Parallel and Distributed Processing Symposium, 6th Workshop on Parallel and Distributed Scientific and Engineering Computing, 2005.

R. K. Dash, P. Vytelingum, A. Rogers, E. David and N. R. Jennings, "Market-based task allocation mechanisms for limited-capacity suppliers," IEEE Transactions on Systems, Man and Cybernetics–Part A: Systems and Humans, vol. 37, no. 3, p. 391–405, 2007.

D. Grosu., "AGORA: An architecture for strategyproof computing in grids," in In Proc. 3rd International Symposium on Parallel and Distributed Computing, 2004.

H. Wang, Q. Jing, R. Chen, B. He, Z. Qian and L. Zhou, "Distributed systems meet economics: Pricing in the cloud," in In Proc. 2nd USENIX Workshop on Hot Topics in Cloud Computing, 2010.

E. Walker, W. Brisken and J. Romney, "To lease or not to lease from storage clouds," IEEE Computer, vol. 43, no. 4, p. 44–50, 2010.

A. Li, X. Yang, S. Kandula and M. Zhang, "CloudCmp: Shopping for a cloud made easy," in In Proc. 2nd USENIX Workshop on Hot Topics in Cloud Computing, 2010.

R. Buyya, R. Ranjan and R. N. Calheiros, "InterCloud: Utility-oriented federation of cloud computing environments for scaling of application services," in In Proc. 10th International Conference on Algorithms and Architectures for Parallel Processing, 2010.

J. Altmann, C. Courcoubetis, G. D. Stamoulis, M. Dramitinos, T. Rayna, M. Risch and C. Bannink, "GridEcon: A market place for computing resources," in In Proc. Workshop on Grid Economics and Business Models, 2008.

M. Risch, J. Altmann, L. Guo, A. Fleming and C. Courcoubetis, "The GridEcon platform: A business scenario testbed for commercial cloud services," in In Proc. Workshop on Grid Economics and Business Models, 2009.

W.-Y. Lin, G.-Y.Lin and H.-Y. Wei, "Dynamic auction mechanism for cloud resource allocation," in In Proc. 2010 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing, 2010.

N. Chohan, C. Castillo, M. Spreitzer, M. Steinder, A. Tantawi and C. Krintz, "See spot run: Using spot instances for MapReduce workflows," in In Proc. 2nd USENIX Workshop on Hot Topics in Cloud Computing, 2010.

E. Campos-Nanez, N. Fabra and A. Garcia, "Dynamic auctions for on-demand services," IEEE Transactions on Systems, Man and Cybernetics–Part A: Systems and Humans, vol. 37, no. 6, p. 878–886, 2007.

A. Quiroz, H. Kim, M. Parashar, N. Gnanasambandam and N. Sharma, "Towards autonomic workload provisioning for enterprise grids and clouds," in In Proc. 10th IEEE/ACM International Conference on Grid Computing, 2009.

H. N. Van, F. D. Tran and J.-M. Menaud, "Autonomic virtual resource management for service hosting platforms," in In Proc. ICSE Workshop on Software Engineering Challenges in Cloud Computing, 2009.

C. Vecchiola, R. N. Calheiros, D. Karunamoorthy and R. Buyya, "Deadline-driven provisioning of resources fro scientific applications in hybrid clouds with aneka," Future Generation Computer Systems, vol. 28, p. 58–65, 2012.

A. Kansal, F. Zhao, J. Liu, N. Kothari and A. A. Bhattacharya, "Virtual machine power metering and provisioning," in In Proc. 1st ACM Symposium on Cloud computing, 2010.

X. Meng, C. Isci, J. Kephart, L. Zhang, E. Bouillet and D. Pendarakis, "Efficient resource provisioning in compute clouds via vm multiplexing," in In Proc. 7th international conference on Autonomic computing, 2010.

W. Chen, X. Qiao, J. Wei and T. Huang, "A profit-aware virtual machine deployment optimization framework for cloud platform providers," in In Proc. 5th IEEE International Conference on Cloud Computing, 2012.

R. Ghosh and V. K. Naik, "Biting of safely more than you can chew: Predictive analytics for resource over-commit in IaaS cloud," in In Proc. 5th IEEE International Conference on Cloud Computing, 2012.

T. M. Lynar, R. D. Herbert and S. Simon, "Auction resource allocation mechanisms in grids of heterogeneous computers," WSEAS Transactions on Computers, vol. 8, no. 10, p. 1671–1680, 2009.

R. Wolski, J. S. Plank, J. Brevik and T. Bryan, "G-commerce: Market formulations controlling resource allocation on the computational grid," in In Proceedings of International Parallel and Distributed Processing Symposium, 2001.

K. Stanoevska-Slabeva, D. M. Parrilli and G. Thanos, "Beingrid: Development of business models for the grid industry," in In Proceedings of International Workshop on Grid Economics and Business Models, 2008.

M. Risch, J. Altmann, L. Guo, A. Fleming and C. Courcoubetis, "The gridecon platform: A business scenario testbed for commercial cloud services," Seoul National University, Technology Management, Economics and Policy Program, 2009.

R. Buyya, R. Ranjan and R. N. Calheiros, "Modeling and simulation of scalable cloud computing environments and the cloudsim toolkit: Challenges and opportunities," in In Proceedings of the 7th High Performance Computing and Simulation Conference, 2009.

G. Wei, A. Vasilakos, Y. Zheng and N. Xiong, "A game-theoretic method of fair resource allocation forcloud computing services," The Journal of Supercomputing, vol. 54, pp. 1-18, 2009.

S. R. and K. P., "A survey on auction based resource allocation in cloud computing," International Journal of Research in Computer Applications ans Robotics, vol. 1, no. 9, pp. 96-102, 2013.

A. J, A. D and P. M, "Generalized Nash equilibria for SaaS/PaaS clouds," Eur J Oper Res.

A. D., P. B. and P. M., "Generalized Nash Equilibria for the Service Provisioning Problem in Cloud Systems," IEEE Transactions on Services Computing, vol. 6, no. 4, pp. 429-442, 2013.

G. Khanna, K. Beaty, G. Kar and A. Kochut, "Application performance management in virtualized server environments," in in Proc. of the IEEE Network Ops.and Mgmt, 2006.

M. Steinder, I. Whalley, D. Carrera, I. Gaweda and D. Chess, "Server virtualization in autonomic management of heterogeneous workloads," in in Proc. of the IEEE Sym. on Integrated Network Management, 2007.

J. Kephart, H. Chan, D. Levine, G. Tesauro, F. Rawson and C. Le-furgy, "Coordinating multiple autonomic managers to achieve specified power-performance tradeoffs," in in Proc. IEEE Intl. Conf. on Autonomic Computing (ICAC), 2007.

P. Ranganathan, P. Leech, D. Irwin and J. Chase, "Ensemble-level power management for dense blade servers," in in Proc. of the IEEE Sym. on Computer Architecture, 2006.

E. Pinheiro, R. Bianchini and T. Heath, Dynamic Cluster Reconfigura-tion for Power and Performance, Kluwer Academic Publishers, 2003.

T. Abdelzaher, K. Shin and N. Bhatti, "Performance Guarantees for Web Server End-Systems: A Control-Theoretical Approach," IEEE Trans. Parallel and Distributed Systems, vol. 13, no. 1, pp. 80-96, 2002.

D. Kusic and N. Kandasamy, "isk-Aware Limited Lookahead Control for Dynamic Resource Provisioning in Enterprise Computing Systems," in Int’l Conf. Autonomic Computing, 2006.

D. Kusic, J. Kephart, N. Kandasamy and G. Jiang, "Power and Performance Management of Virtualized Computing Environments via Lookahead Control," in Int’l Conf. Autonomic Computing, 2008.

W. Qin and Q. Wang, "Modeling and Control Design for Performance Management of Web Servers via an LPV Approach," IEEE Trans. Control Systems Technology, vol. 15, no. 2, pp. 259-275, 2007.

R. Raghavendra, P. Ranganathan, V. Talwar, Z.Wang and X. Zhu, "No ‘Power’ Struggles: Coordinated Multi-Level Power Management for the Data Center," SIGARCH Computer Architecture News, vol. 36, no. 1, pp. 48-59, 2013.

F. Teng and F. Magoulès, "A new game theoretical resource allocation algorithm for cloud computing," in In Proceedings of the 5th international conference on Advances in Grid and Pervasive Computing (GPC'10), 2010.

S. Zaman and D. Grosu, "A Combinatorial Auction-Based Mechanism for Dynamic VM Provisioning and Allocation in Clouds," Cloud Computing, IEEE Transactions on, vol. 1, no. 2, pp. 129-141, 2013.

D. Feitelson, "Parallel Workloads Archives: Logs.," [Online]. Available: http://www.cs.huji.ac.il/labs/parallel/workload/logs.html..

D. Feitelson, "Parallel Workloads Archives: Standard Workload Format.," [Online]. Available: http://www.cs.huji.ac.il/labs/parallel/workload/swf.html.




DOI: http://dx.doi.org/10.7613/hccaj.v1i1.8

Refbacks

  • There are currently no refbacks.



The Official Journal of Nanostructured Coatings Institute of Payame Noor University and HPCLab Company.