PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey on Load Balancing Algorithms for VM Placement in Cloud Computing

Minxian Xu, Wenhong Tian, Rajkumar Buyya

arXiv:1607.06269v3cs.DC

TL;DR

Cloud data centers must place heterogeneous VMs under fluctuating workloads without causing resource imbalance, performance degradation, or SLA violations. This survey classifies and compares VM load balancing algorithms across multiple design and evaluation dimensions. It concludes that the literature has diverse multi-objective methods and that realistic validation, adaptive algorithms, heterogeneous-resource support, and coordinated objectives remain open directions.

  • Problem

    Heterogeneous servers hosting VMs with varying specifications and fluctuating usage can cause imbalanced resource utilization, performance degradation, and SLA violations.

  • Method

    The survey analyzes and classifies VM load balancing algorithms across scheduling scenarios, management approaches, resource types, VM uniformity, allocation dynamicity, metrics, and evaluation approaches.

  • Results

    The survey presents comparative strengths and weaknesses of existing algorithms and identifies patterns across their objectives, platforms, and evaluation methods.

  • Takeaways & Limitations

    Future work should validate meta-heuristics on realistic platforms, support dynamic heterogeneous multi-resource environments, coordinate multiple objectives, and investigate hybrid strategies.

  • Takeaways & Limitations

    Most meta-heuristic evaluations use simulation toolkits, and the diversity of surveyed studies prevents a definitive choice of the best algorithm for each situation.

Abstract

from arXiv · show

The emergence of cloud computing based on virtualization technologies brings huge opportunities to host virtual resource at low cost without the need of owning any infrastructure. Virtualization technologies enable users to acquire, configure and be charged on pay-per-use basis. However, Cloud data centers mostly comprise heterogeneous commodity servers hosting multiple virtual machines (VMs) with potential various specifications and fluctuating resource usages, which may cause imbalanced resource utilization within servers that may lead to performance degradation and service level agreements (SLAs) violations. To achieve efficient scheduling, these challenges should be addressed and solved by using load balancing strategies, which have been proved to be NP-hard problem. From multiple perspectives, this work identifies the challenges and analyzes existing algorithms for allocating VMs to PMs in infrastructure Clouds, especially focuses on load balancing. A detailed classification targeting load balancing algorithms for VM placement in cloud data centers is investigated and the surveyed algorithms are classified according to the classification. The goal of this paper is to provide a comprehensive and comparative understanding of existing literature and aid researchers by providing an insight for potential future enhancements.

1. INTRODUCTION

Virtualization improves flexibility and utilization in cloud data centers, but heterogeneous VMs and fluctuating workloads can imbalance resources, degrade performance, and violate SLAs. The survey classifies and compares VM load balancing algorithms, metrics, and evaluation approaches.

  • Motivation: Virtualization enables on-demand allocation, hides server heterogeneity, supports server consolidation, and improves utilization compared with overprovisioned traditional data centers.Traditional configurations waste energy and floor space while incurring management overhead.
  • Motivation: Heterogeneous VMs and unpredictable workloads can create resource imbalances that degrade performance and violate SLAs.Examples include computation-intensive applications with low memory requirements and changing host load behavior.
  • Load balancing objective: Load balancing assigns VMs to suitable hosts while balancing resource utilization across hosts.It can also support fail-over, scalability, bottleneck avoidance, and lower response time.
  • Evaluation challenges: VM load balancing is evaluated using dimensions including scalability, response time, overhead, performance, and resource utilization.Overhead includes VM migration and communication costs, while resource utilization indicates overloaded or underutilized hosts.
  • Survey contribution: The survey extends prior classifications across scheduling scenario, management approach, resource type, VM uniformity, and allocation dynamicity.It also summarizes scheduling metrics, evaluation platforms and toolkits, and algorithm strengths and weaknesses.

2. VM LOAD BALANCING SCENARIO AND MANAGEMENT

VM load balancing varies across public, private, and hybrid cloud scenarios and can be managed centrally or distributively. The survey relates these settings to their operational constraints, scheduling architectures, and trade-offs.

  • Cloud scenarios: Public, private, and hybrid clouds impose different constraints on VM load balancing algorithms.Public clouds face changing APIs and unpredictable loads, private clouds offer more control, and hybrid clouds combine both models.
  • Public Cloud: Public clouds use pay-as-you-go infrastructure but complicate VM and host information collection because APIs vary and change frequently.Historic data may be used to predict future load under unpredictable or periodic demand.
  • Private Cloud: Private clouds provide greater control for deploying complex load balancing algorithms and imposing constraints such as migration limits.Their loads are comparatively predictable and controlled.
  • Centralized management: Centralized schedulers collect global host information and make VM allocation decisions through a central controller.They are simpler to implement and manage but depend on a single controller.
  • Distributed management: Distributed schedulers make decisions through local schedulers, distributing computation overhead across nodes.They reduce central bottleneck pressure and improve reliability and scalability, but require cooperation and control-plane overhead.

3. VM LOAD BALANCING ALGORITHM MODELING IN CLOUDS

The survey models VM load balancing through resource dimensions, VM uniformity, allocation dynamicity, optimization strategy, and scheduling process. Because placement is NP-hard, surveyed methods primarily use approximate heuristic, meta-heuristic, or hybrid strategies across initial placement and live migration.

  • Resource type: Algorithms may balance a single resource, commonly CPU, or multiple resources such as CPU, memory, and I/O.Multi-resource methods use weights or priorities to represent resource importance.
  • VM type uniformity: VMs are modeled as homogeneous or heterogeneous, with heterogeneous models selecting host types according to task characteristics and scheduling objectives.Homogeneous assumptions simplify scheduling but are rarely adopted in real cloud environments.
  • Allocation dynamicity: Static allocation uses VM information known in advance, whereas dynamic allocation responds to loads at each time interval and can combine placement with migration.Static methods generally perform better overall, while changing real-cloud demands can make them unsuitable.
  • Optimization strategy: Since VM load balancing is NP-hard, most surveyed algorithms seek approximate solutions using heuristic, meta-heuristic, or hybrid strategies.Heuristics target problem-specific solutions, meta-heuristics use general procedures, and hybrids combine both approaches.
  • Scheduling process: The scheduling process consists mainly of VM initial placement and VM live migration.Migration involves trigger, VM selection, and VM acceptance policies for moving workloads from overloaded hosts.

4. LOAD BALANCING SCHEDULING METRICS COMPARISON

The survey compares metrics used to evaluate VM load balancing, emphasizing that each captures different aspects of utilization, time, distribution, or performance. Several metrics have explicit scope conditions or should be interpreted jointly rather than alone.

  • Utilization Metrics: Utilization standard deviation and load variance measure deviation from mean utilization but may not suit algorithms emphasizing time constraints.They are popular because they are easy to measure.
  • Time-Based Metrics: Makespan measures the longest host processing time and is better suited to real-time scheduling than utilization-deviation metrics.A shorter makespan can be the primary scheduling objective.
  • Host-Level Metrics: Number of overloaded hosts gives a system-level view of overload, but depends on the configured threshold and reveals few load-distribution details.Load balancing algorithms aim to reduce this number.
  • Network Metrics: Standard deviation of connections suits network-intensive systems but does not represent resource usage because connections can consume different resources.It is a load measure focused on connections.
  • Multi-Resource Metrics: Average imbalance level combines weighted deviations across multiple resources, such as CPU, memory, and bandwidth.This extends single-resource utilization metrics to multi-resource evaluation.
  • Performance Metrics: Migration count and SLA violations are auxiliary metrics that should be evaluated with other measures rather than individually.Migrations trade load balance against performance, while SLA violations indicate insufficient resources for VMs.

5. PERFORMANCE EVALUATION APPROACHES

The survey reviews realistic cloud platforms and simulation toolkits for evaluating VM load balancing algorithms. It contrasts practical testing environments with simulation-based evaluation and summarizes reported environments, scales, baselines, and improvements.

  • Evaluation Approaches: Realistic platforms are presented as persuasive environments for performance testing, while simulations support large-scale experiments when network conditions or laboratory resources are constrained.The survey discusses both categories as approaches for VM load balancing evaluation.
  • Realistic Platforms: OpenNebula supports implementation and testing of VM load balancing algorithms through virtual platforms, cloud APIs, and resource-information collection.The platform manages heterogeneous and distributed infrastructures.
  • Realistic Platforms: The surveyed realistic platforms include OpenNebula, ElasticHosts, and Amazon EC2, while Eucalyptus, CloudStack, and OpenStack were not used in the surveyed evaluations.The survey therefore does not introduce the latter platforms in detail.
  • Simulation Toolkits: CloudSim, CloudSched, and FlexCloud provide simulation capabilities for extensible policies, resource-scheduling comparisons, and VM-allocation performance evaluation.These tools support experiments involving cloud data-center and workload configurations.
  • Comparative Evaluation: The survey’s comparison summarizes evaluation approaches, experimental scenarios, environments, scales, baselines, and reported performance improvements.It notes that realistic tests typically use fewer than 10 machines, whereas simulations scale to hundreds or thousands of hosts and VMs.

6. ALGORITHMS COMPARISON

The surveyed algorithms address VM load balancing through migration, multi-resource placement, and communication-aware strategies. Their reported benefits are paired with scope limitations involving load dimensions and scheduling stages.

  • Migration-Based Balancing: Migration Management Agent dynamically balances VM loads across HLA federations while modeling communication costs between migrated and remaining VMs.It targets systems whose computation and communication loads vary during execution.
  • Migration-Based Balancing: MMA neglects stochastic VM-host interactions and models host load using CPU utilization only.These design choices constrain the resources and interactions represented by the algorithm.
  • Multi-Resource Mapping: Ni et al.’s probability-based VM mapping considers weighted multiple resources to reduce load crowding when concurrent users request the same host resources.Concurrent requests can rapidly increase target-host load and degrade performance.
  • Multi-Resource Mapping: A realistic homogeneous-VM experiment found that Ni et al.’s approach efficiently reduced utilization standard deviation across nodes.The approach mainly addresses initial VM placement rather than the running stage.

6.3. Scheme for optimizing virtual machines in multi-cloud environment

The surveyed schemes span multi-objective placement in heterogeneous multi-clouds, distributed intra-cloud balancing, and prediction-based adaptive migration. Their scope and assumptions differ across static scheduling, resource modeling, and evaluation scale.

  • Multi-Cloud Placement: Tordsson et al.’s cloud-broker algorithms jointly optimize load balancing, performance, and cost across heterogeneous resources and VM types in multi-cloud environments.The broker manages VM placement across providers with different infrastructures and offerings.
  • Multi-Cloud Placement: Tordsson et al.’s comprehensive experiments mainly evaluate static VM scheduling, limiting scalability when applied to dynamic scenarios.The limitation follows from the mismatch between static evaluation and dynamic use.
  • Intra-Cloud Balancing: DLBA-CAB uses adaptive live migration and distributed comparison-and-balance to equilibrate processor and I/O usage within a cloud.Its cost function weights CPU and I/O usage, and the algorithm was designed to enhance Eucalyptus.
  • Intra-Cloud Balancing: DLBA-CAB reaches Nash equilibrium quickly but assumes host memory usage is always sufficient.The memory assumption limits the completeness of its resource model.
  • Adaptive Prediction-Based Balancing: Yang et al.’s prediction-based multi-strategy assigns different strategies to light-load, optimal, warning, and overload host states.The method uses weighted multiple-resource information and aims to reduce overloaded hosts and unnecessary migration.
  • Adaptive Prediction-Based Balancing: Yang et al.’s algorithm was evaluated only with small-scale hosts and not on realistic platforms.Its reported adaptivity therefore has a limited evaluation scope.

6.6. Central Load Balancing Policy for VM

CLBVM uses periodic global load information with distributed collection and centralized reallocation to balance VM loads. Its feasibility is reported in XEN, but constant network-load assumptions and limited resource coverage constrain applicability.

  • CLBVM targets shorter response time and higher throughput in distributed Clouds while requiring low overhead, periodic updates, and minimal live-migration downtime.The policy combines several operational requirements to support its stated objectives.
  • Each host continuously classifies CPU load as Heavy, Moderate, or Light and exchanges information with a master server.The master periodically reallocates load from heavily loaded hosts to lightly loaded hosts.
  • XEN practice indicates that CLBVM can improve throughput in a distributed environment.
  • The policy assumes nearly constant network loads and rarely considers memory or I/O resources.These assumptions reduce its applicability to current Cloud environments and limit resource-model coverage.
  • A distributed P2P load balancer cooperates across hosts without centralized control to improve scalability and place VMs on hosts with more or specialized resources.Its dynamic scheduling reflects the difficulty of precisely predicting VM behavior.
  • Communication cost may increase rapidly as the number of hosts grows, and this cost is not considered.

6.8. Dynamic and Integrated Resource Scheduling Algorithm

The surveyed approaches address VM placement through integrated multi-resource scheduling, offline partitioning, and hybrid heuristic optimization. Their reported benefits include improved load balance and lower makespan, alongside migration-cost or implementation-complexity limitations.

  • DAIRS integrates CPU, memory, and network bandwidth using weights and evaluates multi-resource scheduling with average imbalance level across hosts.VM requests are processed in a pipeline with different request statuses.
  • DAIRS ignores the communication cost of migrations.
  • Prepartition uses known reservation-model VM information to divide multi-resource VM requests into smaller parts for better resource use and reduced overloads.
  • Its approximation ratio can approach the optimal solution, while offline no-migration load balancing has a best stated ratio of 4/3.
  • A hybrid genetic approach combines heuristic initial packing with iterative placement optimization to reduce migrations under variable host loads and dynamic VM allocations.Its fitness function aims to minimize placement standard deviation.
  • Coordinating heuristic and meta-heuristic methods improves scheduling objectives but increases implementation complexity in realistic environments.

6.11. VM Scheduling Strategy based on Genetic Algorithm

The surveyed genetic and ant-colony approaches optimize VM placement or migration under changing loads, using historical, current, or pheromone-based information. Reported results include better balancing and balanced multi-objective performance, with complexity and static-information constraints.

  • Hu et al.’s genetic algorithm seeks effective VM mappings while minimizing migration times through a spanning-tree solution structure.Less-loaded nodes are placed as leaves with higher probability of accepting VMs.
  • The algorithm requires a centralized controller to collect host information.
  • Using both historical and current data lets the algorithm account for reallocation influence in advance.Experiments report better load-balancing performance than least-loaded scheduling, although complexity remains open for discussion.
  • The distributed ACO migration strategy targets load balancing, resource utilization, and fewer migrations through autonomous local migration agents.Agents monitor host utilization and use positive and negative pheromone strategies.
  • CloudSim simulations with heterogeneous VMs show balanced performance across SLA violations, migration count, and load variation.Because of computation and time costs, the strategy schedules with all VM information known in advance.

6.13. Ant Colony Optimization and Particle Swarm Optimization

ACOPS combines ant colony and particle swarm optimization for dynamic VM placement, targeting resource-utilization balance and request acceptance. Its reported effectiveness is paired with a pre-rejection trade-off that can reduce provider revenue.

  • ACOPS combines ant colony and particle swarm optimization to maximize resource-utilization balance and accept as many VM requests as possible.It considers both CPU and memory resources.
  • Unlike comparable static meta-heuristics, ACOPS optimizes VM placement dynamically.
  • Table III classifies surveyed algorithms according to their VM model.
  • Results demonstrate effectiveness in balancing loads, while the authors derive ACOPS time complexity.
  • The Pre-reject step accelerates solution finding but rejects some VMs, causing revenue loss for Cloud service providers.

7. CHALLENGES AND FUTURE DIRECTIONS

The paper identifies open challenges for VM load-balancing research across evaluation, VM modeling, and scheduling models. Key needs include realistic validation, multi-objective coordination, adaptive heterogeneous-resource support, and common comparative evaluation.

  • Experiment platform and performance evaluation: Future evaluations should validate meta-heuristics on realistic cloud platforms rather than relying mainly on simulation toolkits.The survey reports that most meta-heuristics outperform traditional heuristics, but their experiments are mostly simulation-based.
  • Experiment platform and performance evaluation: VM load-balancing studies increasingly require coordinated optimization of load balancing, cost, and downtime objectives.The paper characterizes these goals as multi-objective and identifies their coordination and consistency as an open challenge.
  • Experiment platform and performance evaluation: A common-platform comparative study is still needed to determine which algorithm performs best or when each algorithm should be used.The survey attributes this unresolved question to heterogeneous problem formulations and the lack of experiments under identical configurations.
  • Classification of VM model: Self-adaptive algorithms are needed because dynamic VM load makes static allocation unsuitable.The survey also calls for support for heterogeneous VMs and multiple resource types because CPU may not be the only bottleneck.
  • Classification of VM model: Hybrid heuristic and meta-heuristic strategies are promising, but balancing placement speed against optimization quality remains unresolved.A heuristic can place VMs quickly, while a meta-heuristic can optimize placement through migrations.
  • Classification of scheduling model: Scheduling research should account for future loads, communication costs, and correlated physical and virtual networks during cross-cloud migration.Current studies often use current or historical utilization, while these additional effects remain insufficiently analyzed.
Loading 1607.06269v3…