Skip to content

Instantly share code, notes, and snippets.

@aderumier

aderumier/gist:ecfd441540f8528fe667f5361afda5c3

Created March 25, 2025 17:00
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save aderumier/ecfd441540f8528fe667f5361afda5c3 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save aderumier/ecfd441540f8528fe667f5361afda5c3 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
gistfile1.txt
use std::collections::{HashMap, HashSet};
use std::fmt;
use std::io::Write;
use rand::Rng;
use rand::seq::SliceRandom;
use std::time::Instant;
// Structure representing a Virtual Machine
#[derive(Debug, Clone)]
struct VM {
id: String,
cpu_req: f64,
mem_req: f64,
io_req: f64,
host: Option<String>,
initial_host: Option<String>, // Keep track of the initial host for migration purposes
}
impl VM {
fn new(id: &str, cpu_req: f64, mem_req: f64, io_req: f64) -> Self {
VM {
id: id.to_string(),
cpu_req,
mem_req,
io_req,
host: None,
initial_host: None,
}
}
fn new_with_host(id: &str, cpu_req: f64, mem_req: f64, io_req: f64, host: &str) -> Self {
VM {
id: id.to_string(),
cpu_req,
mem_req,
io_req,
host: Some(host.to_string()),
initial_host: Some(host.to_string()),
}
}
fn get_id(&self) -> &str {
&self.id
}
fn get_cpu_req(&self) -> f64 {
self.cpu_req
}
fn get_mem_req(&self) -> f64 {
self.mem_req
}
fn get_io_req(&self) -> f64 {
self.io_req
}
fn set_host(&mut self, host: &str) {
self.host = Some(host.to_string());
}
fn get_host(&self) -> Option<&String> {
self.host.as_ref()
}
fn get_initial_host(&self) -> Option<&String> {
self.initial_host.as_ref()
}
}
// Structure representing a Hypervisor
#[derive(Debug)]
struct Hypervisor {
id: String,
cpu_total: f64,
mem_total: f64,
io_capacity: f64,
current_load: f64,
vms: Vec<VM>,
}
impl Hypervisor {
fn new(id: &str, cpu_total: f64, mem_total: f64, io_capacity: f64, current_load: f64) -> Self {
Hypervisor {
id: id.to_string(),
cpu_total,
mem_total,
io_capacity,
current_load,
vms: Vec::new(),
}
}
fn get_id(&self) -> &str {
&self.id
}
fn get_cpu_total(&self) -> f64 {
self.cpu_total
}
fn get_mem_total(&self) -> f64 {
self.mem_total
}
fn get_io_capacity(&self) -> f64 {
self.io_capacity
}
fn get_current_load(&self) -> f64 {
self.current_load
}
fn get_cpu_avail(&self) -> f64 {
self.cpu_total - self.current_load
}
fn add_vm(&mut self, mut vm: VM) {
self.current_load += vm.get_cpu_req();
vm.set_host(&self.id);
self.vms.push(vm);
}
// Initialize the hypervisor with a VM that's already assigned to it
fn add_initial_vm(&mut self, mut vm: VM) {
if vm.get_host().is_none() {
vm.set_host(&self.id);
}
self.current_load += vm.get_cpu_req();
self.vms.push(vm);
}
fn get_vms(&self) -> &Vec<VM> {
&self.vms
}
fn has_vm_with_id(&self, vm_id: &str) -> bool {
self.vms.iter().any(|vm| vm.get_id() == vm_id)
}
fn calc_cpu_usage(&self) -> f64 {
self.current_load / self.cpu_total
}
fn calc_mem_usage(&self) -> f64 {
let mem_used: f64 = self.vms.iter().map(|vm| vm.get_mem_req()).sum();
mem_used / self.mem_total
}
fn calc_io_usage(&self) -> f64 {
let io_used: f64 = self.vms.iter().map(|vm| vm.get_io_req()).sum();
io_used / self.io_capacity
}
}
// Structure for constraint with weight
#[derive(Debug, Clone)]
struct WeightedConstraint {
vm_id: String,
weight: f64,
}
impl WeightedConstraint {
fn new(vm_id: &str, weight: f64) -> Self {
WeightedConstraint {
vm_id: vm_id.to_string(),
weight,
}
}
}
// Structure for placement constraint
#[derive(Debug, Clone)]
struct PlacementConstraint {
allowed_hypervisors: Vec<String>,
weight: f64,
}
impl PlacementConstraint {
fn new(allowed_hypervisors: Vec<&str>, weight: f64) -> Self {
PlacementConstraint {
allowed_hypervisors: allowed_hypervisors.into_iter().map(|s| s.to_string()).collect(),
weight,
}
}
}
// TOPSIS Load Balancer with soft constraints
#[derive(Debug)]
struct TOPSISLoadBalancer {
hypervisors: Vec<Hypervisor>,
weights: HashMap<String, f64>,
criteria_benefit: HashMap<String, bool>,
anti_affinity_constraints: HashMap<String, Vec<WeightedConstraint>>,
affinity_constraints: HashMap<String, Vec<WeightedConstraint>>,
placement_constraints: HashMap<String, PlacementConstraint>,
constraint_weights: HashMap<String, f64>,
strict_mode: bool,
}
impl TOPSISLoadBalancer {
fn new(hypervisors: Vec<Hypervisor>) -> Self {
let mut weights = HashMap::new();
weights.insert("cpu".to_string(), 0.3);
weights.insert("mem".to_string(), 0.3);
weights.insert("io".to_string(), 0.2);
weights.insert("constraints".to_string(), 0.2);
let mut criteria_benefit = HashMap::new();
criteria_benefit.insert("cpu".to_string(), false);
criteria_benefit.insert("mem".to_string(), false);
criteria_benefit.insert("io".to_string(), false);
criteria_benefit.insert("constraints".to_string(), false);
let mut constraint_weights = HashMap::new();
constraint_weights.insert("anti_affinity".to_string(), 5.0);
constraint_weights.insert("affinity".to_string(), 5.0);
constraint_weights.insert("placement".to_string(), 10.0);
TOPSISLoadBalancer {
hypervisors,
weights,
criteria_benefit,
anti_affinity_constraints: HashMap::new(),
affinity_constraints: HashMap::new(),
placement_constraints: HashMap::new(),
constraint_weights,
strict_mode: false,
}
}
fn set_weights(&mut self, cpu_weight: f64, mem_weight: f64, io_weight: f64, constraints_weight: f64) {
self.weights.insert("cpu".to_string(), cpu_weight);
self.weights.insert("mem".to_string(), mem_weight);
self.weights.insert("io".to_string(), io_weight);
self.weights.insert("constraints".to_string(), constraints_weight);
}
fn set_constraint_weights(&mut self, anti_affinity_weight: f64, affinity_weight: f64, placement_weight: f64) {
self.constraint_weights.insert("anti_affinity".to_string(), anti_affinity_weight);
self.constraint_weights.insert("affinity".to_string(), affinity_weight);
self.constraint_weights.insert("placement".to_string(), placement_weight);
}
fn set_strict_mode(&mut self, strict: bool) {
self.strict_mode = strict;
}
// Initialize the load balancer with VMs already assigned to hypervisors
fn initialize_with_placement(&mut self, vms: &[VM]) {
// First, we need to map each VM to its initial hypervisor
let mut vm_map: HashMap<&str, Vec<VM>> = HashMap::new();
for vm in vms {
if let Some(initial_host) = vm.get_initial_host() {
vm_map.entry(initial_host).or_insert_with(Vec::new).push(vm.clone());
}
}
// Then assign each VM to its initial hypervisor
for hyp in &mut self.hypervisors {
let hyp_id = hyp.get_id();
if let Some(assigned_vms) = vm_map.get(hyp_id) {
for vm in assigned_vms {
hyp.add_initial_vm(vm.clone());
println!("VM {} initially placed on hypervisor {}", vm.get_id(), hyp_id);
}
}
}
}
fn add_anti_affinity_constraint(&mut self, vm_id1: &str, vm_id2: &str, weight: Option<f64>) {
let weight_value = weight.unwrap_or_else(|| *self.constraint_weights.get("anti_affinity").unwrap());
// Add constraint in first direction
self.anti_affinity_constraints
.entry(vm_id1.to_string())
.or_insert_with(Vec::new)
.push(WeightedConstraint::new(vm_id2, weight_value));
// Add constraint in the other direction
self.anti_affinity_constraints
.entry(vm_id2.to_string())
.or_insert_with(Vec::new)
.push(WeightedConstraint::new(vm_id1, weight_value));
}
fn add_affinity_constraint(&mut self, vm_id1: &str, vm_id2: &str, weight: Option<f64>) {
let weight_value = weight.unwrap_or_else(|| *self.constraint_weights.get("affinity").unwrap());
// Add constraint in first direction
self.affinity_constraints
.entry(vm_id1.to_string())
.or_insert_with(Vec::new)
.push(WeightedConstraint::new(vm_id2, weight_value));
// Add constraint in the other direction
self.affinity_constraints
.entry(vm_id2.to_string())
.or_insert_with(Vec::new)
.push(WeightedConstraint::new(vm_id1, weight_value));
}
fn add_placement_constraint(&mut self, vm_id: &str, allowed_hypervisors: Vec<&str>, weight: Option<f64>) {
let weight_value = weight.unwrap_or_else(|| *self.constraint_weights.get("placement").unwrap());
self.placement_constraints.insert(
vm_id.to_string(),
PlacementConstraint::new(allowed_hypervisors, weight_value)
);
}
fn calculate_constraint_score(&self, vm: &VM, hypervisor: &Hypervisor) -> f64 {
let vm_id = vm.get_id();
let mut score = 0.0;
// Simulate adding the VM to calculate projected resource usage
let projected_cpu = hypervisor.calc_cpu_usage() +
(vm.get_cpu_req() / hypervisor.get_cpu_total());
let mut mem_used = 0.0;
for existing_vm in hypervisor.get_vms() {
mem_used += existing_vm.get_mem_req();
}
let projected_mem = (mem_used + vm.get_mem_req()) / hypervisor.get_mem_total();
// Check hard resource constraints first
if hypervisor.get_cpu_avail() < vm.get_cpu_req() {
return if self.strict_mode { -1000.0 } else { -10.0 };
}
// Check maximum capacity constraint of 80% for CPU and memory
let max_capacity = 0.8; // 80%
if projected_cpu > max_capacity || projected_mem > max_capacity {
if self.strict_mode {
return -1000.0; // Very large penalty in strict mode (hard constraint)
}
// Add significant penalty for exceeding 80% threshold
let mut penalty = 0.0;
if projected_cpu > max_capacity {
penalty += (projected_cpu - max_capacity) * 100.0; // More penalty for higher excess
}
if projected_mem > max_capacity {
penalty += (projected_mem - max_capacity) * 100.0;
}
score -= penalty;
}
// Check placement constraints (which hypervisors are allowed)
if let Some(constraint) = self.placement_constraints.get(vm_id) {
let hyp_id = hypervisor.get_id();
let allowed = constraint.allowed_hypervisors.iter().any(|allowed_hyp_id| allowed_hyp_id == hyp_id);
if !allowed {
if self.strict_mode {
return -1000.0; // Very large penalty in strict mode (hard constraint)
}
score -= constraint.weight; // Penalty in soft mode
} else {
score += constraint.weight * 0.5; // Reward for allowed hypervisor
}
}
// Anti-affinity penalties (soft constraints)
if let Some(constraints) = self.anti_affinity_constraints.get(vm_id) {
for constraint in constraints {
let conflicting_vm_id = &constraint.vm_id;
let weight = constraint.weight;
// Apply penalty if the conflicting VM is already on this hypervisor
if hypervisor.has_vm_with_id(conflicting_vm_id) {
if self.strict_mode {
return -1000.0; // Very large penalty in strict mode (hard constraint)
}
score -= weight; // Subtract the penalty weight in soft mode
}
}
}
// Affinity rewards (soft constraints)
if let Some(constraints) = self.affinity_constraints.get(vm_id) {
for constraint in constraints {
let affinity_vm_id = &constraint.vm_id;
let weight = constraint.weight;
// Check if the affinity VM is already placed
for hyp in &self.hypervisors {
if hyp.has_vm_with_id(affinity_vm_id) {
if hyp.get_id() == hypervisor.get_id() {
// The affinity VM is already on this hypervisor, add reward
score += weight;
} else {
// The affinity VM is on a different hypervisor, add penalty
if self.strict_mode {
return -1000.0; // Very large penalty in strict mode (hard constraint)
}
score -= weight; // Penalty in soft mode
}
break;
}
}
}
}
score
}
fn find_best_hypervisor_for_vm(&self, vm: &VM) -> Option<usize> {
// Build the decision matrix including constraint scores
let mut decision_matrix = Vec::new();
for (i, hyp) in self.hypervisors.iter().enumerate() {
// Calculate constraint score
let constraint_score = self.calculate_constraint_score(vm, hyp);
// In strict mode, skip hypervisors with very negative constraint scores
if self.strict_mode && constraint_score <= -1000.0 {
continue;
}
// Add to decision matrix
decision_matrix.push((
i, // hypervisor index
[
("cpu".to_string(), hyp.calc_cpu_usage()),
("mem".to_string(), hyp.calc_mem_usage()),
("io".to_string(), hyp.calc_io_usage()),
("constraints".to_string(), -constraint_score), // Negative because lower is better in TOPSIS
].iter().cloned().collect::<HashMap<String, f64>>()
));
}
// If no suitable hypervisor found
if decision_matrix.is_empty() {
println!("No suitable hypervisor for VM {} (resources or constraints)", vm.get_id());
return None;
}
// If only one suitable hypervisor found
if decision_matrix.len() == 1 {
return Some(decision_matrix[0].0);
}
// Normalize the decision matrix
let norm_matrix = self.normalize_matrix(&decision_matrix);
// Apply weights
let weighted_matrix = self.apply_weights(&norm_matrix);
// Determine the positive and negative ideal solutions
let (positive_ideal, negative_ideal) = self.find_ideal_solutions(&weighted_matrix);
// Calculate distances for each hypervisor
let mut distances = Vec::new();
for (hyp_idx, criteria) in &weighted_matrix {
let d_positive = self.calculate_distance(criteria, &positive_ideal);
let d_negative = self.calculate_distance(criteria, &negative_ideal);
let closeness = d_negative / (d_positive + d_negative);
distances.push((*hyp_idx, closeness));
}
// Sort by closeness score (highest to lowest)
distances.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap());
// Return the hypervisor with the best score
if !distances.is_empty() {
Some(distances[0].0)
} else {
None
}
}
fn normalize_matrix(&self, matrix: &[(usize, HashMap<String, f64>)]) -> Vec<(usize, HashMap<String, f64>)> {
let mut denominators = HashMap::new();
// Calculate the square roots of the sums of squares for each criterion
for criterion in self.weights.keys() {
let sum_of_squares: f64 = matrix.iter()
.map(|(_, criteria)| criteria.get(criterion).unwrap_or(&0.0).powi(2))
.sum();
denominators.insert(criterion.clone(), sum_of_squares.sqrt());
}
// Normalize
let mut normalized = Vec::new();
for (hyp_idx, criteria) in matrix {
let mut normalized_criteria = HashMap::new();
for (criterion, value) in criteria {
let denominator = denominators.get(criterion).unwrap_or(&1.0);
if *denominator > 0.0 {
normalized_criteria.insert(criterion.clone(), value / denominator);
} else {
normalized_criteria.insert(criterion.clone(), 0.0);
}
}
normalized.push((*hyp_idx, normalized_criteria));
}
normalized
}
fn apply_weights(&self, norm_matrix: &[(usize, HashMap<String, f64>)]) -> Vec<(usize, HashMap<String, f64>)> {
let mut weighted = Vec::new();
for (hyp_idx, criteria) in norm_matrix {
let mut weighted_criteria = HashMap::new();
for (criterion, value) in criteria {
if let Some(weight) = self.weights.get(criterion) {
weighted_criteria.insert(criterion.clone(), value * weight);
}
}
weighted.push((*hyp_idx, weighted_criteria));
}
weighted
}
fn find_ideal_solutions(&self, weighted_matrix: &[(usize, HashMap<String, f64>)]) -> (HashMap<String, f64>, HashMap<String, f64>) {
let mut positive_ideal = HashMap::new();
let mut negative_ideal = HashMap::new();
// Initialize with extreme values
for criterion in self.weights.keys() {
let is_benefit = *self.criteria_benefit.get(criterion).unwrap_or(&false);
positive_ideal.insert(criterion.clone(), if is_benefit { f64::MIN } else { f64::MAX });
negative_ideal.insert(criterion.clone(), if is_benefit { f64::MAX } else { f64::MIN });
}
// Find the ideal values
for (_, criteria) in weighted_matrix {
for (criterion, value) in criteria {
let is_benefit = *self.criteria_benefit.get(criterion).unwrap_or(&false);
if is_benefit {
// For benefit (larger = better)
if let Some(current) = positive_ideal.get_mut(criterion) {
*current = current.max(*value);
}
if let Some(current) = negative_ideal.get_mut(criterion) {
*current = current.min(*value);
}
} else {
// For cost (smaller = better)
if let Some(current) = positive_ideal.get_mut(criterion) {
*current = current.min(*value);
}
if let Some(current) = negative_ideal.get_mut(criterion) {
*current = current.max(*value);
}
}
}
}
(positive_ideal, negative_ideal)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment