A Meta-Heuristic Load Balancer for Cloud Computing Systems

I. INTRODUCTION

• Cloud systems’ heterogeneous hardware and rapidly provisioned resources make resource sharing and management necessary.Cloud services can draw on multiple servers and are provisioned to meet user requirements.Source: §I · p. 1
• Most proposed strategies focus on optimal utilization of one resource, while cloud environments need to accommodate rapid changes in available resource configurations.Virtual machines can be booted up or shut down on demand.Source: §I · p. 1
• The paper specifies a cloud-resource utilization model covering multiple resource types and service migration costs, then presents a prototype meta-heuristic load balancer.The prototype is intended for medium-size cloud systems.Source: §I · p. 1

II. MODEL OF CLOUD RESOURCES UTILIZATION

• Services consume resources supplied by nodes, and both service requirements and node availability are represented as integer-valued resource vectors.The model considers renewable, continuous resources and uses CPU, memory, maximum network bandwidth, and I/O operations speed in the experiment.Source: §II · p. 2
• Resource availability can change as nodes become idle or overloaded, resources are added, demand falls, or part of the network goes offline.The paper identifies automatic migration to alternative nodes as critical in this dynamic setting.Source: §II · p. 2
• Each service has an integer migration-cost value representing the impact of moving it, and the model treats that cost as constant across destination nodes.The model describes migration as carrying service state along with the service.Source: §II · p. 2, Figure 1 · p. 2

III. PROBLEM FORMULATION

• The formulation treats services as mobile and nodes as fixed, with service assignments mapping services to nodes.It considers sets of resource types and available resources on nodes.Source: §III · p. 2
• A stable system keeps the total assigned service demand within each node’s available resources; otherwise, the system is overloaded.The formulation defines an optimal assignment as a stable one with no greater transformation cost than any other stable assignment.Source: §III · p. 3
• The d-resource system optimization problem is a variant of RCPSP and is NP-hard.Simple heuristics can produce low-quality results, while exact methods are limited by problem size or focus on lower bounds.Source: §III · p. 3

Decision-making module

• Because each assignment decision adds computation overhead and badly assigned services can destabilize the system, algorithm choice must balance speed and quality.The design considers several promising strategies for that decision-making task.Source: §IV · pp. 3–4

A. Greedy

• Greedy quickly makes locally optimal choices, though it usually does not produce an optimal solution.It chooses the locally optimal option at each stage in the hope of finding a global optimum.Source: §IV · p. 4

B. Tabu Search (TS)

• Tabu Search explores neighboring solutions and avoids repeatedly considering visited solutions by maintaining a list.Neighbors differ in one or two minor details.Source: §IV · p. 4

C. Simulated Annealing

• Simulated Annealing gradually lowers the probability of accepting worse solutions as it explores the solution space.Source: §IV · p. 4

D. Genetic Algorithm (GA)

• The genetic algorithm uses selection, inheritance, mutation, and crossover; the paper deploys a variant with a Genetic Drift step.The paper describes Genetic Drift as detailed in.Source: §IV · p. 4

E. Seeded Genetic Algorithm (SGA)

• Seeded Genetic Algorithm (SGA) replaces Genetic Drift [33] with locally optimal solutions from Greedy, Tabu Search, and Simulated Annealing, aiming to reduce population size.The paper creates SGA-Greedy, SGA-TS, and SGA-SA variations.Source: §IV · p. 4

F. Full Scan (FS)

• Full Scan searches all available configurations and can find a global optimum in finite time under appropriate modeling assumptions, but requires many computations.The search also uses shaving, path cuts, and largest-migration-cost-first ordering.Source: §IV · p. 4

Workload and evaluation context

• Publicly available cloud workload traces are limited, often anonymous, and stripped of useful details, while experimental studies commonly rely on simulations and models.Source: §V · p. 4

Experimental configuration

• The experiment's system configuration uses selected services and nodes informed by prior research and experience with Amazon EC2 instances.The authors describe the proposed configuration as valid for this experiment.Source: §V · p. 4
• Tables 2 and 3 present the experiment's node and service configurations, respectively.Source: Table 2 · p. 5, Table 3 · p. 5

VI. EXPERIMENTAL RESULTS

• Run counts varied substantially by strategy, especially in smaller solution spaces; Greedy, Tabu Search, and Simulated Annealing were rerun when they finished before the allotted time.The experiments also tracked average unique candidate solutions created in each scenario; testing stability was computationally expensive and implementations cached solutions.Source: §VI · pp. 5–6, Figure 4 · p. 6
• Five scenarios increased problem complexity by adding two nodes and ten services per test, and each strategy returned its best-found solution after an arbitrary computation time.New nodes were assumed to be added when services were deployed and resource demand increased.Source: §VI · pp. 6–7, Table 4 · p. 7
• The Full Scan strategy served as a global-optimum benchmark only when an optimum was found, and could not finish Tests IV and V in reasonable time.The reported limits were 24 hours for Test IV and 5 days for Test V; other strategies’ results appear in Figure 5.Source: §VI · p. 7

A–B. Greedy and Tabu Search

• Greedy ran quickly but found stable solutions in few runs, while Tabu Search worked well on small instances despite a bottleneck in marking same-value solutions as Tabu.The TS strategy used a limit on non-improving moves before returning its current solution.Source: §VII · p. 7

C. Simulated Annealing

• Simulated Annealing required many more computations than Greedy or Tabu Search, but avoided costly generation of all solution neighbors and benefited most from solution caching..Source: §VII · p. 7

D. Genetic Algorithm

• The conventional genetic algorithm performed poorly with four resource types, and solution quality declined as problem size grew, especially with ten or more nodes.Its costly random-solution generation was identified as a drawback as the solution space grew.Source: §VII · pp. 7–8

E. Seeded Genetic Algorithm

• The seeded genetic algorithm returned the best results within the set time frame, reducing the population to 25% and computation time by around 50–70% without reducing quality.It generally examined fewer candidates; the TS-seeded variant returned the best results in this experiment.Source: §VII · p. 8

F. Full Scan

• Full Scan guarantees a global optimum but remains computationally inefficient and was used to find optima only in minor problem instances.The search traverses about 9% of the solution tree after optimization, prioritizing services with the highest migration costs and pruning unstable partial solutions.Source: §VII · p. 8

• Meta-heuristics’ small-step search may benefit from prioritizing already-migrated services and services with lower migration costs, but this requires problem-specific knowledge.Source: §VIII · p. 8
• Random candidate generation is expensive, and the number of tested solutions does not correlate with solution quality; precomputed starting pools may yield better results.Source: §VIII · p. 8
• Some strategies plateau, especially Tabu Search; this implementation returns its current solution after an arbitrary limit of steps without quality gains.The authors suggest handling stagnation more intelligently.Source: §VIII · p. 8
• 6012 possible combinations formed the solution search space on a medium-sized networked system; adding tested resources did not hinder the examined strategies.Source: §VIII · p. 8