A coral-reefs and Game Theory-based approach for optimizing elastic cloud resource allocation

https://doi.org/10.1016/j.future.2016.05.025Get rights and content

Highlights

  • Bio-inspired coral-reefs optimization paradigm to model cloud elasticity.

  • Game theory-based approach to identify the best cloud resource reallocation schema.

  • Fuzzy linguistic SLA formalization.

Abstract

Elasticity is a key feature in cloud computing, which distinguishes this paradigm from other ones, such as cluster and grid computing. On the other hand, dynamic resource reallocation is one of the most important and complex issues in cloud scenarios, which can be expressed as a multi-objective optimization problem with the opposing objectives of maximizing demand satisfaction and minimizing costs and resource consumptions. In this paper, we propose a meta-heuristic approach for cloud resource allocation based on the bio-inspired coral-reefs optimization paradigm to model cloud elasticity in a cloud-data center, and on the classic Game Theory to optimize the resource reallocation schema with respect to cloud provider’s optimization objectives, as well as customer requirements, expressed through Service Level Agreements formalized by using a fuzzy linguistic method.

Introduction

In recent years, cloud computing has attracted attention from industry, government and academic worlds. An increasing amount of applications make extensive usage of cloud resources, according to an on-demand, self-service, and pay-by-use business model, with the progressive adoption of cloud-based services by many sectors of modern society. One of the main reasons of this success is the possibility of acquiring virtual resources in a dynamic and elastic way. In particular, the emerging virtualization technologies allow multiple virtual machines (VMs) to run concurrently on a single physical host, called host machine (HM). Each VM, in turn, hosts its operating system, middleware and applications, by using a partition of the underlying hardware resources capacity (CPU power, memory, store capability and network bandwidth)  [1]. Cloud elasticity is the key feature for implementing server consolidation strategies. It allows for on-demand migration and dynamic reallocation of VMs  [2]. NIST defines elasticity as the ability for customers to quickly purchase on-demand and automatically release as many resources as needed, ideally giving to the user the feeling that the cloud resource capabilities are unlimited  [3]. Specific elasticity control mechanisms are implemented to decide when and how to scale-up or scale-down virtual resources, in accordance with the provider’s own optimization objectives, as well as with user-defined settings and requirements formalized within the context of a specific Service Level Agreement (SLA) between the cloud provider and the customer. In order to do this, resource usage information, such as CPU load, free memory and network traffic volumes, for all the available HMs, has to be continuously collected and analyzed on-line. Three different techniques are used in the implementation of cloud elasticity solutions: replication, migration and resizing  [4], resulting in different strategies and approaches for handling resource allocation within a cloud infrastructure.

The dynamic resource allocation problem describes the decision of how many HMs are required overall to cope with the current demand, and how VMs are (re-)allocated to each HM in the individual time intervals. The optimization of resource allocation consists in minimizing the number of HMs necessary to host all the VMs associated to users’ demands. This is a typical multi-objective optimization task, where the most important goals are the minimization of the needed hardware resources and the satisfaction of SLAs contracted with the customers. This problem, widely simplified, is closely related to a commonly known NP-hard combinatorial optimization problem, the “bin packing” problem  [5], where the items to be packed can be viewed as the VMs and the bins as the HM nodes with their multi-dimensional capacity represented by the available computing power, free memory, storage capability and network bandwidth. Consequently, our elastic cloud resource allocation problem, that is inherently more complex, will be NP-hard, and thus, a reasonable heuristic solution, achieving near-optimal results is strongly desirable.

In such a complex multi-objective scenario, traditional optimization methods are not able to efficiently provide good results, due to their inherent difficulties in exploring huge solution spaces. Hence, novel approaches based on bio-inspired meta-heuristic schemes, seem to be the most promising options to achieve a better trade-off between the complexity of the search process and the optimization of the solutions found. Such schemes rely on models and strategies borrowed from the observation of behaviors, and evolution mechanisms available in nature, where only the fittest individuals are able to survive in organizations characterized by a high degree of competition. In this direction, to model the elastic resource reallocation dynamics of a typical cloud environment, we adopted a Coral-Reefs Optimization (CRO) approach, which artificially simulates the reefs evolution processes, including corals’ reproduction and competition for the space in the reefs  [6], which, by analogy, model the continuous demands for resource re-sizing, migration and replication, characterizing the operational life-cycle of VMs hosted within a cloud data center. This approach presents extremely interesting and promising features in achieving convergence towards global optima.

On the other hand, cloud customers can be seen as non-cooperative entities, whose fundamental interest is not the optimization of the overall system performance, but rather the maximization of their individual benefit. Therefore, a natural hint for carefully driving the VM allocation process comes from classic game theory. Accordingly, we used a game theory-based approach to identify the best VM reallocation schema with respect to the critical requirements specified by the cloud customers in their SLAs, formalized by using fuzzy linguistic label sets, and typically characterized by different and even conflicting performance objectives and optimization criteria. This approach is able to drive the complex interactions between the customers and the cloud provider towards a social optimum (i.e., an equilibrium point between their own demands and goals), by optimizing a global objective function that takes into account the individual interests of all the involved entities.

The rest of the paper is organized as follows. In Section  2, the strategies and methods currently adopted to implement cloud elasticity capabilities are presented. Section  3 defines the problem of interest. The proposed approach for elastic resource reallocation is presented in Section  4. The related experimental performance evaluation results are shown in Section  5. Finally, Section  6 presents some concluding considerations and remarks.

Section snippets

Background and related work

Elasticity represents a dynamic property of the cloud paradigm, which allows the system to scale on-demand within an operational system context  [7]. It enables applications to evolve, by following the users’ demand, without needing traditional “fork-lift” upgrades, and hence, introduces the degree of adaptiveness that is fundamental for modern big data-centric environments.

Generally, Infrastructure as a Service (IaaS) architectures provide an elasticity controller, which is responsible for

Definition of the resource allocation optimization problem

In order to describe and evaluate the proposed approach, we defined a simplified model for resource management in the cloud computing environment. We consider a scenario, in which a cloud data-center is composed by several computing nodes, characterized by a set of parameters, such as CPU, memory, and storage capacity. Specifically, we denote H=(h1,,hn) as the set of HMs in the data-center, and respectively, C=(c1,,cn) their available (free) resource capacity, where cj is described in terms

The meta-heuristic approach

This section, first, introduces a fuzzy linguistic model for formalizing a generic SLA  [28], established between the cloud customer and the cloud provider (Section  4.1). Then, the CRO algorithm, based on the coral-reefs behavior, is adopted to simulate the continuous requests of new cloud resources needed to trigger the resize, replication and migration processes characterizing cloud data center activities (Section  4.2). Last, in Section  4.3, we describe how to use a game theory-based

Experimental results

According to the proposed Coral Reefs-based ecosystem approach, each grid element (x,y) of the reef (modeled in our context as a vector A={ax,y,i}) represents a HM hx,y. We assume that, the space available (resource capacity cx,y) within each element hx,y is different, i.e., the HMs are heterogeneous. Moreover, the HM hx,y can host a set of VM instances (micro-colony), such that Eq. (2) is verified.

Thus, at each step of the simulation process, the CRO-algorithm computes which VM instances

Conclusions

In this work, a new bio-inspired and game theoretic-based meta-heuristic scheme for managing elastic resources reallocation in cloud infrastructures has been presented.

Specifically, the proposed solution leverages an evolutionary algorithm based on the observation of the reefs structure and coral reproduction, showing a very interesting behavior to simulate the continuous requests of new cloud resources, which trigger the resize, replication and migration processes characterizing cloud

Massimo Ficco received the degree in computer engineering from the University of Naples Federico II (IT) in 2000 and the Ph.D. degree in information engineering from the University of Parthenope in 2010. He is an assistant professor in the Department of “Ingegneria Industriale e dell’Informazione” at the Second University of Naples (SUN). From 2000 to 2010, he was a senior researcher at the Italian University Consortium for Computer Science (CINI). His current research interests include

References (43)

  • D. Agrawal et al.

    Database scalability, elasticity, and autonomy in the cloud

  • L.M. Vaquero et al.

    Dynamically scaling applications in the cloud

    SIGCOMM Comput. Commun. Rev.

    (2011)
  • R.N. Calheiros et al.

    The aneka platform and qos-driven resource provisioning for elastic applications on hybrid clouds

    Future Gener. Comput. Syst.

    (2011)
  • Z. Shen et al.

    Cloudscale: elastic resource scaling for multi-tenant cloud systems

  • Z. Gong et al.

    Press: Predictive elastic resource scaling for cloud systems

  • W. Dawoud et al.

    Elastic vm for cloud resources provisioning optimization

  • J.O. Fito et al.

    Sla-driven elastic cloud hosting provider

  • N. Roy et al.

    Efficient autoscaling in the cloud using predictive models for workload forecasting

  • N. Vasic et al.

    Dejavu: accelerating resource allocation in virtualized environments

  • T. Knauth, C. Fetzer, Scaling non-elastic applications using virtual machines, in: Proc. of the 4th Int. Conf. on Cloud...
  • K. Lazri, S. Laniepce, J. Ben-Othman, When dynamic VM migration falls under the control of vm users, in: Proc. of the...
  • Cited by (72)

    • A hybrid constrained coral reefs optimization algorithm with machine learning for optimizing multi-reservoir systems operation

      2021, Journal of Environmental Management
      Citation Excerpt :

      Most of them have focused on CRO-SL as a co-evolutionary algorithm (Camacho-Gómez et al., 2018; Jiménez-Fernández et al., 2019; Salcedo-Sanz et al., 2019; Tsai et al., 2019). Some others have combined CRO with: game theory (Ficco et al., 2018), statistical approaches (Durán-Rosal et al., 2018), simulated annealing (Yan et al., 2019), and memetic strategy (Durán-Rosal et al., 2019), while some are still using the original version of CRO (Agrawal et al., 2018; Azgomi and Sohrabi, 2019; Garcia-Hernandez et al., 2019). An expanding list of the CRO algorithm applications on top of generating reliable results in various fields reveals its potential capability in water resources optimization problems.

    View all citing articles on Scopus

    Massimo Ficco received the degree in computer engineering from the University of Naples Federico II (IT) in 2000 and the Ph.D. degree in information engineering from the University of Parthenope in 2010. He is an assistant professor in the Department of “Ingegneria Industriale e dell’Informazione” at the Second University of Naples (SUN). From 2000 to 2010, he was a senior researcher at the Italian University Consortium for Computer Science (CINI). His current research interests include software engineering architecture, cloud computing, security aspects of critical infrastructure, and mobile computing.

    Christian Esposito received the graduate-degree in computer engineering in 2006, and the Ph.D. degree in 2009 from the University of Naples Federico II. Currently, he is a postdoc researcher in the Institute of High Performance Computing and Networking (ICAR) at the National Research Council (CNR). His main interests include mobile computing, benchmarking, aspects of publish/subscribe services, and reliability strategies for data dissemination in large-scale critical systems.

    Francesco Palmieri received the M.S. degree and the Ph.D. degree in computer science from the University of Salerno. He was an Assistant Professor at the Second University of Napoli. Currently he is an Associate Professor at the University of Salerno. His research interests include advanced networking protocols and architectures and network security. He has been the director of the Networking Division of the Federico II University of Napoli and contributed to the development of the Internet in Italy as a senior member of the Technical-Scientific Advisory Committee and of the CSIRT of the Italian NREN GARR. He serves as the editor-in-chief of an international journal and participates to the editorial board of other ones.

    Aniello Castiglione received a Ph.D. in Computer Science from the University of Salerno, Italy. Actually he is an adjunct professor at the University of Salerno (Italy) and at the University of Naples “Federico II” (Italy). He received the Italian National Academic Qualification (ASN) as Associate Professor in Computer Science. He serves as a reviewer for several international journals and is Managing Editor of two international journals. He also acts as a reviewer in around 50 international journals. He served as Program Chair and TPC member in around 90 international conferences. He acted as a Guest Editor in several journals and serves as Editor in several editorial boards of international journals. He published more than 100 papers in international journals and conferences. One of his papers has been selected as “Featured Article” in the IEEE Cybersecurity initiative. He has been involved in forensic investigations, collaborating with several Law Enforcement Agencies as a consultant. He is a member of several associations, including ACM, IEEE. His current research interests include Information Forensics, Digital Forensics, Security and Privacy on Cloud, Communication Networks and Applied Cryptography.

    View full text