VM-Orchestrator: MILP-based Data Center Resource Management

A high-performance Virtual Machine (VM) orchestration system that solves the VM Placement Problem (VMPP) using Mixed Integer Linear Programming (MILP). The system is validated via a custom Discrete Event Simulator modeling data center dynamics as an M/G/c/c queueing system.

📖 Overview

This project, developed as part of an Engineering Thesis at Warsaw University of Technology, moves beyond iterative "First-Fit" heuristics. It implements a holistic orchestrator capable of processing batches of VM requests simultaneously to achieve global optimality across multiple conflicting objectives.

Key Optimization Objectives:

1. Energy Efficiency: Minimizing the number of active physical hosts.
2. Load Balancing: Equalizing resource utilization across servers to prevent hotspots.
3. Migration Awareness: Balancing placement optimality with the cost of moving existing workloads.
4. Time-Constrained Solving: Hybrid strategies for real-time responsiveness.

🛠 Tech Stack

• Optimization: MiniZinc, HiGHS (primary MILP solver), COIN-OR.
  • Note: HiGHS was selected as the primary solver after comparative testing, demonstrating the fastest convergence times for complex VM placement scenarios.
• Simulation: Python 3.12+ (NumPy, Matplotlib)
• Modeling: Mixed Integer Linear Programming (MILP)

🏗 System Architecture

The system consists of three main layers: the User Interface (API), the Orchestration Core (Logic), and the Simulated Data Center Environment.

graph TD
    User((User/Client)) -->|Deployment Request| API[Orchestration API]
    subgraph Core [Orchestration Core]
        API -->|Batch Requests| Solver[MiniZinc MILP Solver]
        Solver -->|Constraint Satisfaction| Logic{Placement Logic}
    end
    subgraph Environment [Simulated Data Center]
        Logic -->|Allocate/Migrate| DC[Physical Hosts]
        DC -->|Telemetry/State| Solver
    end
    DC -.->|M/G/c/c Dynamics| Stats[Performance Metrics]

Loading

Orchestrator Algorithm Flow

The core decision-making loop of the Orchestrator evaluates the optimal placement while accounting for migration costs and deployment failures.

flowchart TD
    Start((START)) --> ReadState[1. Read Current DC State & VM Request]
    ReadState --> CheckOpt{2. Termination<br>Condition Met?}
    CheckOpt -->|Optimum Proven OR Timeout| Allocate[5. Allocate VMs according<br>to the best solution found]
    Allocate --> End((END))
    CheckOpt -->|No| FindIntermediate[3. Find next intermediate<br>feasible solution]
    FindIntermediate --> CalcCost[4. Calculate Total Cost<br>incl. migrations & rejections]
    CalcCost --> CheckOpt

Loading

🔢 Mathematical Formulation

The orchestrator solves a multi-resource (vCPU, RAM) bin-packing problem. The system evaluates the state based on dynamically generated objective functions.

Objective Function 1 & 2 (Energy Minimization):

$$\min \left( \text{UsedServers} + \text{Migrations} \cdot \text{MigrationCost} + \text{UnassignedVMs} \cdot \text{AllocationPenalty} \right)$$

Objective Function 3 & 4 (Load Balancing): Instead of minimizing the active server count, this function minimizes the sum of maximum deviations from the average load across all resource types ($r \in \text{ResourceTypes}$).

$$\min \left( \sum_{r \in R} \text{MaxDeviation}(r) + \text{Migrations} \cdot \text{MigrationCost} + \text{UnassignedVMs} \cdot \text{AllocationPenalty} \right)$$

Key Constraints:

• Resource Capacity: For each server and resource type, total allocated resources cannot exceed capacity ($\sum \text{Placement}{s,v} \cdot \text{VMResources}{v,r} \le \text{Resources}_{s,r}$).
• Assignment Integrity: Each VM must be placed on exactly one server or marked as unassigned.
• Symmetry Breaking: Lexicographical ordering of servers to significantly reduce the solver's search space.

🚀 Performance Comparison

The system implements 5 distinct strategies (Objective Functions):

Strategy	Goal	Description
OF1	Energy Minimization	Maximize host density, enabling idle nodes to be shut down.
OF2	Fast Energy Min	OF1 with strict computation time limits for dynamic environments.
OF3	Load Balancing	Distribute load evenly across nodes to increase hardware lifespan.
OF4	Fast Load Balancing	OF3 optimized for rapid, sub-second decision-making.
OF5	Feasible Solution	Immediate allocation without cost optimization (Baseline benchmark).

📊 Scientific Validation

The custom Python event-driven simulator's accuracy was rigorously verified against the Erlang B formula for M/G/c/c queueing systems. In stress tests handling $10^6$ requests, the experimental rejection probability matched the theoretical values with a difference of < 0.1%, proving the simulator's absolute reliability for data center research.

🚦 Getting Started

Prerequisites

• MiniZinc Bundle: Download here (ensure minizinc is in your PATH).
• Python Environment: Ensure you have Python 3.12 or higher.

Installation

git clone https://github.com/your-username/VM-Orchestrator.git
cd VM-Orchestrator
pip install -r requirements.txt

Running Experiments

To run the primary orchestration simulations:

python src/sequence_orchestration.py

Or to run detailed performance analyses:

python src/performance_tests.py

Detailed performance plots and raw data can be found in the experiments/ and validation/ directories.

---

Author: Adam Staciwa | Warsaw University of Technology (2025)