Optimization problems on virtual machines allocation for cloud computing

• Grant number: 15/08438-0
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: June 01, 2015
• End date: August 01, 2016
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Cid Carvalho de Souza
• Grantee: Matheus de Souza Ataide
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Associated scholarship(s): 15/23270-9 - GRASP heuristics for assignment problems in cloud computing, BE.EP.IC

Abstract

Cloud computing is becoming more present in our daily life, not only for domestic users, but in the business, commercial and academic areas as well. By sharing resources and adopting a pay-as-you-go pricing model, cloud computing promise a better use of the computational infrastructure and to reduce costs. However, to achieve a high level of resource use, it is inevitable that the components of a given application are assigned to non-contiguously virtual machines. In this way, those components can end up in physically distant machines in the cloud. These differences in distance can cause big average latency variations between the components. For many applications this discrepancy in latency has a big impact in the computational performance, which depends fundamentally on the way that the application components are mapped to the cloud. Optimization problems related to this mapping were discussed in recent scientific articles by Zou et al. (2012). Besides showing that those problems are NP-hard, the authors also proposed and tested some greedy heuristics to solve them, comparing the results with solutions generated in a purely random way. Analysing these results, we noticed the potential of using heuristics that combined those two characteristics to achieve solutions better than the ones found until now. One heuristic that naturally appears as a candidate in this situation is GRASP (Greedy Randomized Adaptive Search Procedure). In this way, the objective of this scientific initiation project is to investigate the use of GRASP in the solution of the problems treated in Zou et al. (2012).