VM Placement via Linear Relaxation — CloudSim Simulation

A CloudSim-based research simulator comparing VM allocation algorithms in cloud datacenters. The project implements and evaluates a Linear Relaxation (LR)-based two-phase VM placement algorithm against traditional heuristics (First Fit, Most-Full, Least-Full) using realistic datacenter parameters.

Research context: AUB CS Research Project supervised by Dr. Mohamad Zalghout.

---

Table of Contents

• Overview
• Project Structure
• Prerequisites
• Setup
• Running the Simulation
• Generating Graphs
• Simulation Parameters
• Algorithms
• Output Files
• Troubleshooting

---

Overview

The simulator compares the following VM placement strategies:

Algorithm	Description
LR + Modified Most-Full	Phase 1: LP relaxation rounding. Phase 2: normalized 4-resource Most-Full. (Proposed)
LR only	Phase 1 only — no Phase 2 heuristic.
First Fit	CloudSim native: first host with enough resources.
Most-Full	CloudSim native: most utilized host.
Least-Full	CloudSim native: least utilized host.

Key metrics: allocation rate, CPU/RAM/network/disk utilization rates.

---

Project Structure

cloudsim/                               # Root
├── cloudsim/                           # CloudSim core (do not modify)
│   └── modules/
│       ├── cloudsim/                   # CloudSim library source
│       └── cloudsim-examples/
│           └── src/main/java/
│               └── org.cloudbus.cloudsim.examples/
│                   ├── AlgorithmsComparison.java            # Main entry point
│                   └── algorithms/
│                       ├── LinearRelaxationAlgorithmHelper.java
│                       ├── LinearRelaxationAlgorithm.java
│                       ├── LinearRelaxationAlgorithmModifiedMostFull.java
│                       └── BranchAndBoundAlgorithm.java     # See note below (in Step 3)
├── results/
│   ├── CSV/                # Auto-generated simulation output
│   ├── images/             # Auto-generated graphs
│   ├── scripts/            # Python scripts for visualization
│   │   ├── graph.py        # Graph chart
│   │   ├── bar.py          # Bar chart
│   │   └── migrate.py      # Migration analysis script
│   ├── extra/              # Helper scripts
│   └── requirements.txt    # Python dependencies
├── SCPSolver/              # External JARs 
│   ├── SCPSolver.jar
│   ├── GLPKSolverPack.jar
│   └── LPSOLVESolverPack.jar
└── README.md

---

Prerequisites

Tool	Version	Notes
Java (Corretto or OpenJDK)	17+	Corretto 24 tested
IntelliJ IDEA	Any recent	Community edition works
Maven	Bundled with IntelliJ	For dependency management
Python	3.8+	For graph generation only

---

Setup

Step 1 — Clone the repository

git clone https://github.com/mariamelwirish/cloudsim
cd cloudsim

Step 2 — Open in IntelliJ IDEA

1. Open IntelliJ IDEA
2. Click Open and select the inner cloudsim/ directory (the one containing modules/)
3. Wait for Maven to finish indexing — may take a few minutes on first run

Step 3 — Add SCPSolver JARs

The SCPSolver JARs are already included in the SCPSolver/ folder in the repo. You just need to register them in IntelliJ:

1. In IntelliJ: File → Project Structure → Libraries → + → Java
2. Navigate to the SCPSolver/ folder and add all three JARs: SCPSolver.jar, GLPKSolverPack.jar, and LPSOLVESolverPack.jar
3. In File → Project Structure → Modules → cloudsim-examples → Dependencies, confirm all three appear

Note on Branch & Bound: BranchAndBoundAlgorithm.java uses SCPSolver (GLPK/LPSolve) which requires the JARs above. SCPSolver ships prebuilt x86_64 binaries and crashes on Apple Silicon. A future improvement would be replacing SCPSolver with a pure Java ILP solver (e.g. ojAlgo) for full cross-platform support. All other algorithms use Commons Math3 (pure Java) and work on all platforms.

Step 4 — Verify Maven dependencies

Commons Math3 (used by all LR algorithms) resolves automatically via Maven. No action needed — just confirm it appears in pom.xml:

<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-math3</artifactId>
    <version>3.6.1</version>
</dependency>

Step 5 — Set up Python environment

From the results/ directory:

macOS / Linux:

python3 -m venv .venv
source .venv/bin/activate
pip install -r requirements.txt

Windows:

py -m venv .venv
.\.venv\Scripts\activate
pip install -r requirements.txt

---

Running the Simulation

Standard run

1. Open AlgorithmsComparison.java in IntelliJ
2. Adjust parameters if needed (see Simulation Parameters)
3. Right-click → Run 'AlgorithmsComparison.main()'
4. CSV results are saved to results/CSV/ automatically

---

Generating Graphs

1. Ensure CSV files exist in results/CSV/
2. Activate your Python virtual environment
3. From the results/ directory:

python scripts/graph.py

Graphs are saved to results/images/ as .png (600 DPI) and .pdf.

To change which algorithms appear, edit the FILES dict at the top of graph.py:

FILES = {
    "LR + Modified Most-Full": "CSV/LinearRelaxationAlgorithmModifiedMostFull.csv",
    "MostFull":                "CSV/SelectionPolicyMostFull.csv",
    # add or remove entries as needed
}

---

Simulation Parameters

All in AlgorithmsComparison.java:

Parameter	Default	Description
NUM_HOSTS	70	Number of hosts
NUM_VMS	400	Number of VMs

Host resource ranges (randomizeSpecs()):

Resource	Range
CPU	16–64 cores
RAM	32–128 GB
Network BW	10–40 Gbps
Disk	10–40 TB

VM resource ranges:

Resource	Range
CPU	2–8 cores
RAM	4–16 GB
Network BW	1–4 Gbps
Disk	1–4 TB

---

Algorithms

Two-Phase LR Approach

Phase 1 (identical for all LR variants):

1. Formulate VM placement as ILP — maximize allocated VMs subject to 4-resource host constraints
2. Solve LP relaxation using Commons Math3 SimplexSolver
3. Sort solution values descending; round x_ij > 0.5 to 1 if host capacity allows

Phase 2 (heuristic for remaining unplaced VMs):

Variant	Host ordering metric
Modified Most-Full	(cpu/C + ram/M + bw/N + disk/D) / 4 descending

The Modified variants are our contribution — normalizing across all 4 resources prevents mis-classifying hosts that are CPU-heavy but have ample RAM/disk/network.

---

Output Files

File	Location	Description
LinearRelaxationAlgorithmModifiedMostFull.csv	results/CSV/	Proposed algorithm
LinearRelaxationAlgorithm.csv	results/CSV/	Phase 1 only
SelectionPolicyMostFull.csv	results/CSV/	CloudSim Most-Full
SelectionPolicyLeastFull.csv	results/CSV/	CloudSim Least-Full
SelectionPolicyFirstFit.csv	results/CSV/	CloudSim First-Fit
*.png / *.pdf	results/images/	Bar charts at 600 DPI

CSV columns: placedVMs, numVMs, allocRate, cpuUtilRate, ramUtilRate, netUtilRate, diskUtilRate

---

Troubleshooting

NoClassDefFoundError for SCPSolver: Re-check Setup Step 3. If B&B is commented out in main(), you can safely ignore this error.

LP solver very slow: Complexity scales with numHosts × numVMs. At 100×400 = 40,000 variables expect ~5–10s. Avoid going above 100×600.

Apple Silicon — SCPSolver crashes: Expected behavior. Will be resolved in the future.

Graphs not generating: Check that the virtual environment is activated, CSV files exist in results/CSV/, and algorithm names in FILES exactly match CSV filenames.

Results not saving to correct folder: Check Run → Edit Configurations → Working Directory in IntelliJ. It should point to the cloudsim module directory so that ../results/ resolves correctly.