gistfile1.txt

#!/usr/bin/perl
use strict;
use warnings;
use List::Util qw(sum max min);
use Data::Dumper;

# Implementation of the TOPSIS algorithm for load balancing VMs across hypervisors
# with support for migrations from an initial placement

# Class representing a Virtual Machine
package VM;
sub new {
    my ($class, $id, $cpu_req, $mem_req, $io_req, $initial_host) = @_;
    return bless {
        id => $id,
        cpu_req => $cpu_req,
        mem_req => $mem_req,
        io_req => $io_req,
        host => $initial_host,
        initial_host => $initial_host
    }, $class;
}
sub get_id { return $_[0]->{id}; }
sub get_cpu_req { return $_[0]->{cpu_req}; }
sub get_mem_req { return $_[0]->{mem_req}; }
sub get_io_req { return $_[0]->{io_req}; }
sub set_host { $_[0]->{host} = $_[1]; }
sub get_host { return $_[0]->{host}; }
sub get_initial_host { return $_[0]->{initial_host}; }

# Class representing a Hypervisor
package Hypervisor;
sub new {
    my ($class, $id, $cpu_total, $mem_total, $io_capacity, $current_load) = @_;
    return bless {
        id => $id,
        cpu_total => $cpu_total,
        mem_total => $mem_total,
        io_capacity => $io_capacity,
        current_load => $current_load || 0,
        vms => []
    }, $class;
}
sub get_id { return $_[0]->{id}; }
sub get_cpu_total { return $_[0]->{cpu_total}; }
sub get_mem_total { return $_[0]->{mem_total}; }
sub get_io_capacity { return $_[0]->{io_capacity}; }
sub get_current_load { return $_[0]->{current_load}; }
sub get_cpu_avail { return $_[0]->{cpu_total} - $_[0]->{current_load}; }

# Add a VM to the hypervisor (for new placements)
sub add_vm {
    my ($self, $vm) = @_;
    push @{$self->{vms}}, $vm;
    $self->{current_load} += $vm->get_cpu_req();
    $vm->set_host($self->get_id());
}

# Add a VM to the hypervisor (for initial placements)
sub add_initial_vm {
    my ($self, $vm) = @_;
    # Just add the VM without setting its host as it should already be set
    push @{$self->{vms}}, $vm;
    $self->{current_load} += $vm->get_cpu_req();
}

sub get_vms { return @{$_[0]->{vms}}; }
sub has_vm_with_id {
    my ($self, $vm_id) = @_;
    foreach my $vm ($self->get_vms()) {
        return 1 if $vm->get_id() eq $vm_id;
    }
    return 0;
}
sub calc_cpu_usage { return $_[0]->{current_load} / $_[0]->{cpu_total}; }
sub calc_mem_usage {
    my $self = shift;
    my $mem_used = 0;
    foreach my $vm ($self->get_vms()) {
        $mem_used += $vm->get_mem_req();
    }
    return $mem_used / $self->{mem_total};
}
sub calc_io_usage {
    my $self = shift;
    my $io_used = 0;
    foreach my $vm ($self->get_vms()) {
        $io_used += $vm->get_io_req();
    }
    return $io_used / $self->{io_capacity};
}

# Class for the load balancer using TOPSIS with soft constraints and migration support
package TOPSISLoadBalancer;
use List::Util qw(sum max min);

sub new {
    my ($class, $hypervisors) = @_;
    return bless {
        hypervisors => $hypervisors,
        weights => { 
            cpu => 0.3, 
            mem => 0.3, 
            io => 0.2, 
            constraints => 0.2  # Weight for soft constraints in TOPSIS
        },
        criteria_benefit => { 
            cpu => 0, 
            mem => 0, 
            io => 0, 
            constraints => 0  # 0 = cost (lower is better)
        },
        anti_affinity_constraints => {},  # VMs that should not be on the same hypervisor
        affinity_constraints => {},       # VMs that should be on the same hypervisor
        placement_constraints => {},      # VMs that should be placed on specific hypervisors
        constraint_weights => {
            anti_affinity => 5.0,  # Default weight for anti-affinity constraints
            affinity => 5.0,       # Default weight for affinity constraints
            placement => 10.0      # Default weight for placement constraints
        },
        strict_mode => 0  # If 1, constraints become hard constraints
    }, $class;
}

# Additional method to output summary statistics only (for large datasets)
sub summarize_placement {
    my ($self) = @_;
    
    # Count VMs per hypervisor
    my %vm_counts;
    my %resource_usage;
    
    foreach my $hyp (@{$self->{hypervisors}}) {
        my $hyp_id = $hyp->get_id();
        $vm_counts{$hyp_id} = scalar $hyp->get_vms();
        
        my $cpu_usage = $hyp->calc_cpu_usage();
        my $mem_usage = $hyp->calc_mem_usage();
        my $io_usage = $hyp->calc_io_usage();
        
        # Highlight if exceeding 80% threshold
        my $cpu_str = sprintf("%.2f%%", $cpu_usage * 100);
        my $mem_str = sprintf("%.2f%%", $mem_usage * 100);
        my $io_str = sprintf("%.2f%%", $io_usage * 100);
        
        if ($cpu_usage > 0.8) {
            $cpu_str .= " [OVER]";
        }
        if ($mem_usage > 0.8) {
            $mem_str .= " [OVER]";
        }
        
        $resource_usage{$hyp_id} = {
            'cpu' => $cpu_str,
            'mem' => $mem_str,
            'io' => $io_str,
        };
    }
    
    # Print summary
    print "\nHypervisor Summary (${\scalar(keys %vm_counts)} hypervisors):\n";
    print "ID\t| VMs\t| CPU\t\t| Memory\t\t| IO\n";
    print "-" x 60 . "\n";
    
    foreach my $hyp_id (sort keys %vm_counts) {
        printf "%s\t| %d\t| %s\t| %s\t| %s\n", 
            $hyp_id, 
            $vm_counts{$hyp_id},
            $resource_usage{$hyp_id}{'cpu'},
            $resource_usage{$hyp_id}{'mem'},
            $resource_usage{$hyp_id}{'io'};
    }
    
    # Check for capacity violations
    my $over_capacity = 0;
    foreach my $hyp (@{$self->{hypervisors}}) {
        if ($hyp->calc_cpu_usage() > 0.8 || $hyp->calc_mem_usage() > 0.8) {
            $over_capacity++;
        }
    }
    
    if ($over_capacity > 0) {
        print "\n⚠️  WARNING: $over_capacity hypervisors exceed 80% CPU or memory capacity\n";
    } else {
        print "\n✓ All hypervisors are within 80% CPU and memory capacity\n";
    }
    
    # Print constraint summary
    my $vm_count = 0;
    foreach my $hyp (@{$self->{hypervisors}}) {
        $vm_count += scalar $hyp->get_vms();
    }
    
    print "\nConstraint Summary:\n";
    printf "Total VMs: %d\n", $vm_count;
    printf "Anti-affinity constraints: %d\n", scalar(keys %{$self->{anti_affinity_constraints}});
    printf "Affinity constraints: %d\n", scalar(keys %{$self->{affinity_constraints}});
    printf "Placement constraints: %d\n", scalar(keys %{$self->{placement_constraints}});
}

sub set_weights {
    my ($self, $cpu_weight, $mem_weight, $io_weight, $constraints_weight) = @_;
    $self->{weights} = {
        cpu => $cpu_weight,
        mem => $mem_weight,
        io => $io_weight,
        constraints => $constraints_weight
    };
}

sub set_constraint_weights {
    my ($self, $anti_affinity_weight, $affinity_weight, $placement_weight) = @_;
    $self->{constraint_weights} = {
        anti_affinity => $anti_affinity_weight,
        affinity => $affinity_weight,
        placement => defined $placement_weight ? $placement_weight : 10.0
    };
}

sub set_strict_mode {
    my ($self, $strict) = @_;
    $self->{strict_mode} = $strict ? 1 : 0;
}

# Initialize the load balancer with VMs already assigned to hypervisors
sub initialize_with_placement {
    my ($self, $vms) = @_;
    
    # First, map each VM to its initial hypervisor
    my %vm_map;
    foreach my $vm (@$vms) {
        my $initial_host = $vm->get_initial_host();
        next unless defined $initial_host;
        
        $vm_map{$initial_host} ||= [];
        push @{$vm_map{$initial_host}}, $vm;
    }
    
    # Then assign each VM to its initial hypervisor
    foreach my $hyp (@{$self->{hypervisors}}) {
        my $hyp_id = $hyp->get_id();
        if (exists $vm_map{$hyp_id}) {
            foreach my $vm (@{$vm_map{$hyp_id}}) {
                $hyp->add_initial_vm($vm);
                print "VM " . $vm->get_id() . " initially placed on hypervisor $hyp_id\n";
            }
        }
    }
}

# Add an anti-affinity constraint between two VMs (soft constraint with weight)
sub add_anti_affinity_constraint {
    my ($self, $vm_id1, $vm_id2, $weight) = @_;
    $weight = $self->{constraint_weights}->{anti_affinity} unless defined $weight;
    
    if (!exists $self->{anti_affinity_constraints}->{$vm_id1}) {
        $self->{anti_affinity_constraints}->{$vm_id1} = [];
    }
    push @{$self->{anti_affinity_constraints}->{$vm_id1}}, { vm_id => $vm_id2, weight => $weight };
    
    # Add the constraint in the other direction as well
    if (!exists $self->{anti_affinity_constraints}->{$vm_id2}) {
        $self->{anti_affinity_constraints}->{$vm_id2} = [];
    }
    push @{$self->{anti_affinity_constraints}->{$vm_id2}}, { vm_id => $vm_id1, weight => $weight };
}

# Add an affinity constraint between two VMs (soft constraint with weight)
sub add_affinity_constraint {
    my ($self, $vm_id1, $vm_id2, $weight) = @_;
    $weight = $self->{constraint_weights}->{affinity} unless defined $weight;
    
    if (!exists $self->{affinity_constraints}->{$vm_id1}) {
        $self->{affinity_constraints}->{$vm_id1} = [];
    }
    push @{$self->{affinity_constraints}->{$vm_id1}}, { vm_id => $vm_id2, weight => $weight };
    
    # Add the constraint in the other direction as well
    if (!exists $self->{affinity_constraints}->{$vm_id2}) {
        $self->{affinity_constraints}->{$vm_id2} = [];
    }
    push @{$self->{affinity_constraints}->{$vm_id2}}, { vm_id => $vm_id1, weight => $weight };
}

# Add a placement constraint for a VM (must be placed on one of the specified hypervisors)
sub add_placement_constraint {
    my ($self, $vm_id, $allowed_hypervisors, $weight) = @_;
    $weight = $self->{constraint_weights}->{placement} unless defined $weight;
    
    $self->{placement_constraints}->{$vm_id} = {
        allowed_hypervisors => $allowed_hypervisors,  # Array of hypervisor IDs
        weight => $weight
    };
}

# Calculate constraint score for a potential placement
sub calculate_constraint_score {
    my ($self, $vm, $hypervisor) = @_;
    my $vm_id = $vm->get_id();
    my $score = 0;
    
    # Simulate adding the VM to calculate projected resource usage
    my $projected_cpu = $hypervisor->calc_cpu_usage() + 
                        ($vm->get_cpu_req() / $hypervisor->get_cpu_total());
    
    my $mem_used = 0;
    foreach my $existing_vm ($hypervisor->get_vms()) {
        $mem_used += $existing_vm->get_mem_req();
    }
    my $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 $self->{strict_mode} ? -1000 : -10;  # Larger penalty in strict mode
    }
    
    # Check maximum capacity constraint of 80% for CPU and memory
    my $max_capacity = 0.8; # 80%
    if ($projected_cpu > $max_capacity || $projected_mem > $max_capacity) {
        if ($self->{strict_mode}) {
            return -1000;  # Very large penalty in strict mode (hard constraint)
        }
        # Add significant penalty for exceeding 80% threshold
        my $penalty = 0;
        if ($projected_cpu > $max_capacity) {
            $penalty += ($projected_cpu - $max_capacity) * 100;  # More penalty for higher excess
        }
        if ($projected_mem > $max_capacity) {
            $penalty += ($projected_mem - $max_capacity) * 100;
        }
        $score -= $penalty;
    }
    
    # Check placement constraints (which hypervisors are allowed)
    if (exists $self->{placement_constraints}->{$vm_id}) {
        my $constraint = $self->{placement_constraints}->{$vm_id};
        my $hyp_id = $hypervisor->get_id();
        my $allowed = 0;
        
        foreach my $allowed_hyp_id (@{$constraint->{allowed_hypervisors}}) {
            if ($hyp_id eq $allowed_hyp_id) {
                $allowed = 1;
                last;
            }
        }
        
        if (!$allowed) {
            if ($self->{strict_mode}) {
                return -1000;  # 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 (exists $self->{anti_affinity_constraints}->{$vm_id}) {
        foreach my $constraint (@{$self->{anti_affinity_constraints}->{$vm_id}}) {
            my $conflicting_vm_id = $constraint->{vm_id};
            my $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;  # Very large penalty in strict mode (hard constraint)
                }
                $score -= $weight;  # Subtract the penalty weight in soft mode
            }
        }
    }
    
    # Affinity rewards (soft constraints)
    if (exists $self->{affinity_constraints}->{$vm_id}) {
        foreach my $constraint (@{$self->{affinity_constraints}->{$vm_id}}) {
            my $affinity_vm_id = $constraint->{vm_id};
            my $weight = $constraint->{weight};
            
            # Check if the affinity VM is already placed
            my $found_on_another_hypervisor = 0;
            foreach my $hyp (@{$self->{hypervisors}}) {
                if ($hyp->has_vm_with_id($affinity_vm_id)) {
                    if ($hyp->get_id() eq $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;  # Very large penalty in strict mode (hard constraint)
                        }
                        $score -= $weight;  # Penalty in soft mode
                    }
                    $found_on_another_hypervisor = 1;
                    last;
                }
            }
            
            # If the affinity VM is not yet placed, no effect on score
        }
    }
    
    return $score;
}

sub find_best_hypervisor_for_vm {
    my ($self, $vm) = @_;
    my @hypervisors = @{$self->{hypervisors}};
    
    # Build the decision matrix including constraint scores
    my @decision_matrix;
    
    for (my $i = 0; $i < @hypervisors; $i++) {
        my $hyp = $hypervisors[$i];
        
        # Calculate constraint score
        my $constraint_score = $self->calculate_constraint_score($vm, $hyp);
        
        # In strict mode, skip hypervisors with very negative constraint scores
        next if $self->{strict_mode} && $constraint_score <= -1000;
        
        # Add to decision matrix
        push @decision_matrix, {
            hypervisor_idx => $i,
            criteria => {
                cpu => $hyp->calc_cpu_usage(),
                mem => $hyp->calc_mem_usage(),
                io => $hyp->calc_io_usage(),
                constraints => -$constraint_score  # Negative because lower is better in TOPSIS
            }
        };
    }
    
    # If no suitable hypervisor found
    if (@decision_matrix == 0) {
        print "No suitable hypervisor for VM ".$vm->get_id()." (resources or constraints)\n";
        return undef;
    }
    
    # If only one suitable hypervisor found
    if (@decision_matrix == 1) {
        return $decision_matrix[0]->{hypervisor_idx};
    }
    
    # Normalize the decision matrix
    my $norm_matrix = $self->normalize_matrix(\@decision_matrix);
    
    # Apply weights
    my $weighted_matrix = $self->apply_weights($norm_matrix);
    
    # Determine the positive and negative ideal solutions
    my ($positive_ideal, $negative_ideal) = $self->find_ideal_solutions($weighted_matrix);
    
    # Calculate distances for each hypervisor
    my @distances;
    foreach my $entry (@$weighted_matrix) {
        my $d_positive = $self->calculate_distance($entry->{criteria}, $positive_ideal);
        my $d_negative = $self->calculate_distance($entry->{criteria}, $negative_ideal);
        my $closeness = $d_negative / ($d_positive + $d_negative);
        
        push @distances, {
            hypervisor_idx => $entry->{hypervisor_idx},
            closeness => $closeness
        };
    }
    
    # Sort by closeness score (highest to lowest)
    @distances = sort { $b->{closeness} <=> $a->{closeness} } @distances;
    
    # Return the hypervisor with the best score
    return @distances ? $distances[0]->{hypervisor_idx} : undef;
}

sub normalize_matrix {
    my ($self, $matrix) = @_;
    my @normalized;
    
    # Calculate the square roots of the sums of squares for each criterion
    my %denominators;
    foreach my $criterion (keys %{$self->{weights}}) {
        my $sum_of_squares = 0;
        foreach my $entry (@$matrix) {
            $sum_of_squares += ($entry->{criteria}->{$criterion} || 0) ** 2;
        }
        $denominators{$criterion} = sqrt($sum_of_squares);
    }
    
    # Normalize
    foreach my $entry (@$matrix) {
        my %normalized_criteria;
        foreach my $criterion (keys %{$self->{weights}}) {
            if ($denominators{$criterion} > 0) {
                $normalized_criteria{$criterion} = ($entry->{criteria}->{$criterion} || 0) / $denominators{$criterion};
            } else {
                $normalized_criteria{$criterion} = 0;
            }
        }
        
        push @normalized, {
            hypervisor_idx => $entry->{hypervisor_idx},
            criteria => \%normalized_criteria
        };
    }
    
    return \@normalized;
}

sub apply_weights {
    my ($self, $norm_matrix) = @_;
    my @weighted;
    
    foreach my $entry (@$norm_matrix) {
        my %weighted_criteria;
        foreach my $criterion (keys %{$self->{weights}}) {
            $weighted_criteria{$criterion} = ($entry->{criteria}->{$criterion} || 0) * $self->{weights}->{$criterion};
        }
        
        push @weighted, {
            hypervisor_idx => $entry->{hypervisor_idx},
            criteria => \%weighted_criteria
        };
    }
    
    return \@weighted;
}

sub find_ideal_solutions {
    my ($self, $weighted_matrix) = @_;
    
    my %positive_ideal;
    my %negative_ideal;
    
    # Initialize with extreme values
    foreach my $criterion (keys %{$self->{weights}}) {
        $positive_ideal{$criterion} = $self->{criteria_benefit}->{$criterion} ? -9999 : 9999;
        $negative_ideal{$criterion} = $self->{criteria_benefit}->{$criterion} ? 9999 : -9999;
    }
    
    # Find the ideal values
    foreach my $entry (@$weighted_matrix) {
        foreach my $criterion (keys %{$self->{weights}}) {
            my $value = $entry->{criteria}->{$criterion} || 0;
            
            if ($self->{criteria_benefit}->{$criterion}) {
                # For benefit (larger = better)
                $positive_ideal{$criterion} = max($positive_ideal{$criterion}, $value);
                $negative_ideal{$criterion} = min($negative_ideal{$criterion}, $value);
            } else {
                # For cost (smaller = better)
                $positive_ideal{$criterion} = min($positive_ideal{$criterion}, $value);
                $negative_ideal{$criterion} = max($negative_ideal{$criterion}, $value);
            }
        }
    }
    
    return (\%positive_ideal, \%negative_ideal);
}

sub calculate_distance {
    my ($self, $point, $reference) = @_;
    my $sum_of_squares = 0;
    
    foreach my $criterion (keys %{$self->{weights}}) {
        $sum_of_squares += (($point->{$criterion} || 0) - ($reference->{$criterion} || 0)) ** 2;
    }
    
    return sqrt($sum_of_squares);
}

# Optimize the order of VM placement
sub optimize_vm_order {
    my ($self, $vms) = @_;
    
    # Calculate the total constraint weights for each VM
    my %constraint_weight_sum;
    foreach my $vm (@$vms) {
        my $vm_id = $vm->get_id();
        my $total_weight = 0;
        
        # Sum anti-affinity constraint weights
        if (exists $self->{anti_affinity_constraints}->{$vm_id}) {
            foreach my $constraint (@{$self->{anti_affinity_constraints}->{$vm_id}}) {
                $total_weight += $constraint->{weight};
            }
        }
        
        # Sum affinity constraint weights
        if (exists $self->{affinity_constraints}->{$vm_id}) {
            foreach my $constraint (@{$self->{affinity_constraints}->{$vm_id}}) {
                $total_weight += $constraint->{weight};
            }
        }
        
        # Add placement constraint weight
        if (exists $self->{placement_constraints}->{$vm_id}) {
            $total_weight += $self->{placement_constraints}->{$vm_id}->{weight};
        }
        
        $constraint_weight_sum{$vm_id} = $total_weight;
    }
    
    # With soft constraints, we sort VMs by their constraint importance and resource requirements
    my @sorted_vms = sort {
        $constraint_weight_sum{$b->get_id()} <=> $constraint_weight_sum{$a->get_id()} ||
        $b->get_cpu_req() <=> $a->get_cpu_req() ||
        $b->get_mem_req() <=> $a->get_mem_req()
    } @$vms;
    
    return \@sorted_vms;
}

sub distribute_vms {
    my ($self, $vms) = @_;
    
    # Start timing
    my $start_time = time();
    
    # Optimize the order of VM placement
    my $ordered_vms = $self->optimize_vm_order($vms);
    
    # Statistics for reporting
    my $placed_count = 0;
    my $migrated_count = 0;
    my $newly_placed_count = 0;
    my $failed_count = 0;
    
    # For large datasets, don't print details for every VM
    my $is_large_dataset = @$ordered_vms > 100;
    my $last_progress = 0;
    
    for (my $i = 0; $i < @$ordered_vms; $i++) {
        my $vm = $ordered_vms->[$i];
        
        # Show progress for large datasets
        if ($is_large_dataset) {
            my $progress = int(($i / @$ordered_vms) * 100);
            if ($progress >= $last_progress + 5) {  # Update every 5%
                print "Processing VMs: $progress% complete...\r";
                $last_progress = $progress;
            }
        }
        
        # Check if this VM has an initial placement
        my $has_initial_placement = defined $vm->get_initial_host();
        
        # Skip VMs that are already optimally placed
        if (defined $vm->get_host()) {
            my $current_host = $vm->get_host();
            my $current_host_idx = -1;
            
            for (my $i = 0; $i < @{$self->{hypervisors}}; $i++) {
                if ($self->{hypervisors}->[$i]->get_id() eq $current_host) {
                    $current_host_idx = $i;
                    last;
                }
            }
            
            my $best_hyp_idx = $self->find_best_hypervisor_for_vm($vm);
            if (defined $best_hyp_idx && $current_host_idx == $best_hyp_idx) {
                unless ($is_large_dataset) {
                    print "VM " . $vm->get_id() . " is already optimally placed on hypervisor " . 
                          $self->{hypervisors}->[$best_hyp_idx]->get_id() . "\n";
                }
                $placed_count++;
                next;
            }
        }
        
        my $best_hyp_idx = $self->find_best_hypervisor_for_vm($vm);
        if (defined $best_hyp_idx) {
            # Check if this is a migration or a new placement
            if (defined $vm->get_initial_host()) {
                my $initial_host = $vm->get_initial_host();
                my $best_host = $self->{hypervisors}->[$best_hyp_idx]->get_id();
                
                if ($initial_host ne $best_host) {
                    unless ($is_large_dataset) {
                        print "MIGRATION: VM " . $vm->get_id() . " from $initial_host to $best_host\n";
                    }
                    $migrated_count++;
                } else {
                    unless ($is_large_dataset) {
                        print "VM " . $vm->get_id() . " stays on hypervisor $best_host\n";
                    }
                }
            } else {
                unless ($is_large_dataset) {
                    print "NEW PLACEMENT: VM " . $vm->get_id() . " assigned to hypervisor " . 
                          $self->{hypervisors}->[$best_hyp_idx]->get_id() . "\n";
                }
                $newly_placed_count++;
            }
            
            $self->{hypervisors}->[$best_hyp_idx]->add_vm($vm);
            $placed_count++;
        } else {
            unless ($is_large_dataset) {
                print "FAILURE: Unable to place VM " . $vm->get_id() . "\n";
            }
            $failed_count++;
        }
    }
    
    if ($is_large_dataset) {
        print "Processing VMs: 100% complete!                    \n";
    }
    
    # End timing
    my $end_time = time();
    my $duration = $end_time - $start_time;
    
    print "\nPlacement completed in " . sprintf("%.2f", $duration) . " seconds:\n";
    print "  - $placed_count VMs placed successfully\n";
    print "  - $migrated_count VMs migrated\n";
    print "  - $newly_placed_count VMs newly placed\n";
    print "  - $failed_count VMs failed to place\n";
}

sub verify_constraints {
    my ($self) = @_;
    print "Verifying constraints:\n";
    
    # Create a mapping of VM IDs to their hypervisors and initial hosts
    my %vm_hosts;
    my %vm_initial_hosts;
    
    foreach my $hyp (@{$self->{hypervisors}}) {
        foreach my $vm ($hyp->get_vms()) {
            $vm_hosts{$vm->get_id()} = $hyp->get_id();
            if (defined $vm->get_initial_host()) {
                $vm_initial_hosts{$vm->get_id()} = $vm->get_initial_host();
            }
        }
    }
    
    # Check capacity constraints (80% max)
    print "\nCapacity constraints (80% max):\n";
    my $capacity_violations = 0;
    
    foreach my $hyp (@{$self->{hypervisors}}) {
        my $hyp_id = $hyp->get_id();
        my $cpu_usage = $hyp->calc_cpu_usage();
        my $mem_usage = $hyp->calc_mem_usage();
        
        if ($cpu_usage > 0.8 || $mem_usage > 0.8) {
            print "  VIOLATED: Hypervisor $hyp_id exceeds 80% limit - ";
            print "CPU: " . sprintf("%.2f%%", $cpu_usage * 100) . ", ";
            print "Memory: " . sprintf("%.2f%%", $mem_usage * 100) . "\n";
            $capacity_violations++;
        }
    }
    
    if ($capacity_violations == 0) {
        print "  All hypervisors are within 80% capacity limits\n";
    } else {
        print "  Found $capacity_violations hypervisors exceeding capacity limits\n";
    }
    
    # Print migration summary
    print "\nMigration summary:\n";
    foreach my $vm_id (keys %vm_hosts) {
        my $current_host = $vm_hosts{$vm_id};
        
        if (exists $vm_initial_hosts{$vm_id}) {
            my $initial_host = $vm_initial_hosts{$vm_id};
            if ($current_host ne $initial_host) {
                print "  VM $vm_id migrated from $initial_host to $current_host\n";
            } else {
                print "  VM $vm_id stayed on $current_host\n";
            }
        } else {
            print "  VM $vm_id newly placed on $current_host\n";
        }
    }
    
    # Verify placement constraints
    print "\nPlacement constraints:\n";
    foreach my $vm_id (keys %{$self->{placement_constraints}}) {
        my $constraint = $self->{placement_constraints}->{$vm_id};
        my $allowed_hyps = join(", ", @{$constraint->{allowed_hypervisors}});
        
        if (exists $vm_hosts{$vm_id}) {
            my $current_hyp = $vm_hosts{$vm_id};
            my $allowed = 0;
            
            foreach my $allowed_hyp (@{$constraint->{allowed_hypervisors}}) {
                if ($current_hyp eq $allowed_hyp) {
                    $allowed = 1;
                    last;
                }
            }
            
            if ($allowed) {
                print "  RESPECTED: $vm_id is on $current_hyp (allowed hypervisors: $allowed_hyps)\n";
            } else {
                print "  VIOLATED: $vm_id is on $current_hyp but should be on one of: $allowed_hyps\n";
            }
        } else {
            print "  NOT PLACED: $vm_id should be on one of: $allowed_hyps\n";
        }
    }
    
    # Verify anti-affinity constraints
    print "\nAnti-affinity constraints:\n";
    foreach my $vm_id1 (keys %{$self->{anti_affinity_constraints}}) {
        foreach my $constraint (@{$self->{anti_affinity_constraints}->{$vm_id1}}) {
            my $vm_id2 = $constraint->{vm_id};
            my $weight = $constraint->{weight};
            
            if (exists $vm_hosts{$vm_id1} && exists $vm_hosts{$vm_id2}) {
                if ($vm_hosts{$vm_id1} eq $vm_hosts{$vm_id2}) {
                    print "  VIOLATED: $vm_id1 and $vm_id2 are on the same hypervisor " . 
                          $vm_hosts{$vm_id1} . " (weight: $weight)\n";
                } else {
                    print "  RESPECTED: $vm_id1 and $vm_id2 are on different hypervisors (weight: $weight)\n";
                }
            }
        }
    }
    
    # Verify affinity constraints
    print "\nAffinity constraints:\n";
    foreach my $vm_id1 (keys %{$self->{affinity_constraints}}) {
        foreach my $constraint (@{$self->{affinity_constraints}->{$vm_id1}}) {
            my $vm_id2 = $constraint->{vm_id};
            my $weight = $constraint->{weight};
            
            if (exists $vm_hosts{$vm_id1} && exists $vm_hosts{$vm_id2}) {
                if ($vm_hosts{$vm_id1} ne $vm_hosts{$vm_id2}) {
                    print "  VIOLATED: $vm_id1 and $vm_id2 are on different hypervisors (weight: $weight)\n";
                } else {
                    print "  RESPECTED: $vm_id1 and $vm_id2 are on the same hypervisor " . 
                          $vm_hosts{$vm_id1} . " (weight: $weight)\n";
                }
            }
        }
    }
}

sub print_hypervisor_status {
    my ($self) = @_;
    
    print "\nHypervisor Status:\n";
    foreach my $hyp (@{$self->{hypervisors}}) {
        print "Hypervisor " . $hyp->get_id() . ":\n";
        print "  - CPU usage: " . sprintf("%.2f%%", $hyp->calc_cpu_usage() * 100) . "\n";
        print "  - Memory usage: " . sprintf("%.2f%%", $hyp->calc_mem_usage() * 100) . "\n";
        print "  - IO usage: " . sprintf("%.2f%%", $hyp->calc_io_usage() * 100) . "\n";
        print "  - Hosted VMs: ";
        my @vm_ids = map { $_->get_id() } $hyp->get_vms();
        print join(", ", @vm_ids) . "\n\n";
    }
}

# Main package for the script
package main;
use List::Util qw(shuffle);
use Time::HiRes qw(time);

# Function to generate random hypervisors
sub generate_hypervisors {
    my ($count) = @_;
    my @hypervisors;
    
    for my $i (1..$count) {
        # Create hypervisors with varying capacities
        my $cpu_total = 100 + int(rand(200));  # 100-300 CPU units
        my $mem_total = 128 + int(rand(384));  # 128-512 memory units
        my $io_capacity = 1000 + int(rand(2000));  # 1000-3000 IO units
        my $current_load = int(rand(20));  # 0-20% initial load
        
        push @hypervisors, Hypervisor->new("hyp$i", $cpu_total, $mem_total, $io_capacity, $current_load);
    }
    
    return @hypervisors;
}

# Function to generate random VMs with optional initial placement
sub generate_vms {
    my ($count, $hypervisors, $initial_placement_ratio) = @_;
    $initial_placement_ratio //= 0.8;  # Default 80% of VMs have initial placement
    my @vms;
    
    my @hyp_ids = map { $_->get_id() } @$hypervisors;
    
    for my $i (1..$count) {
        # Create VMs with varying resource requirements
        my $cpu_req = 2 + int(rand(18));     # 2-20 CPU units
        my $mem_req = 4 + int(rand(60));     # 4-64 memory units
        my $io_req = 50 + int(rand(150));    # 50-200 IO units
        
        # Decide if this VM has an initial placement
        my $initial_host;
        if (rand() < $initial_placement_ratio) {
            $initial_host = $hyp_ids[int(rand(@hyp_ids))];
        }
        
        push @vms, VM->new("vm$i", $cpu_req, $mem_req, $io_req, $initial_host);
    }
    
    return @vms;
}

# Function to add random constraints
sub add_random_constraints {
    my ($balancer, $vms, $constraint_density) = @_;
    $constraint_density //= 0.05;  # Default 5% of possible VM pairs have constraints
    
    my $vm_count = @$vms;
    my $max_constraints = int($vm_count * ($vm_count - 1) / 2 * $constraint_density);
    
    # Create a list of VM IDs
    my @vm_ids = map { $_->get_id() } @$vms;
    
    # Add some anti-affinity constraints (VMs that shouldn't be together)
    for (1..int($max_constraints/2)) {
        my $vm1 = $vm_ids[int(rand(@vm_ids))];
        my $vm2 = $vm_ids[int(rand(@vm_ids))];
        next if $vm1 eq $vm2;  # Skip if same VM
        $balancer->add_anti_affinity_constraint($vm1, $vm2);
    }
    
    # Add some affinity constraints (VMs that should be together)
    for (1..int($max_constraints/2)) {
        my $vm1 = $vm_ids[int(rand(@vm_ids))];
        my $vm2 = $vm_ids[int(rand(@vm_ids))];
        next if $vm1 eq $vm2;  # Skip if same VM
        $balancer->add_affinity_constraint($vm1, $vm2);
    }
    
    # Add some placement constraints (VMs that must be on specific hypervisors)
    my @hyp_ids = map { $_->get_id() } @{$balancer->{hypervisors}};
    for (1..int($vm_count * 0.1)) {  # 10% of VMs have placement constraints
        my $vm = $vm_ids[int(rand(@vm_ids))];
        
        # Choose between 1 and 3 allowed hypervisors
        my $num_allowed = 1 + int(rand(3));
        my @allowed = @hyp_ids[0..$num_allowed-1];
        shuffle @allowed;
        
        $balancer->add_placement_constraint($vm, \@allowed);
    }
}

# Create hypervisors and VMs for the example
if ($ENV{SMALL_EXAMPLE}) {
    # Small example with specific placements
    # Create hypervisors
    my @hypervisors = (
        Hypervisor->new("hyp1", 100, 128, 1000, 20),
        Hypervisor->new("hyp2", 80, 96, 800, 10),
        Hypervisor->new("hyp3", 120, 192, 1200, 30)
    );

    # Create VMs with their initial placement:
    # vm1 on hyp1, vm2 on hyp1, vm3 on hyp3, vm4 on hyp2, vm5 has no initial placement
    my @vms = (
        VM->new("vm1", 10, 16, 100, "hyp1"),
        VM->new("vm2", 8, 8, 80, "hyp1"),
        VM->new("vm3", 15, 32, 150, "hyp3"),
        VM->new("vm4", 12, 16, 120, "hyp2"),
        VM->new("vm5", 20, 64, 200, undef),  # No initial placement
    );

    # Create and configure the load balancer
    my $balancer = TOPSISLoadBalancer->new(\@hypervisors);

    # Initialize the load balancer with the current VM placement
    $balancer->initialize_with_placement(\@vms);

    # Add anti-affinity constraint: vm1 and vm4 cannot be on the same hypervisor
    $balancer->add_anti_affinity_constraint("vm1", "vm4");

    # Add affinity constraint: vm2 and vm3 must be on the same hypervisor
    $balancer->add_affinity_constraint("vm2", "vm3");

    # Add placement constraints: vm1 must be on hyp1 or hyp2, vm4 must be on hyp3
    $balancer->add_placement_constraint("vm1", ["hyp1", "hyp2"]);
    $balancer->add_placement_constraint("vm4", ["hyp3"]);

    # Print initial placement
    print "\nInitial placement:\n";
    $balancer->print_hypervisor_status();

    print "\nStarting VM optimization...\n";

    # Optimize the VM placement
    $balancer->distribute_vms(\@vms);

    # Display the results
    print "\nFinal placement:\n";
    $balancer->print_hypervisor_status();

    # Verify if all constraints are respected
    $balancer->verify_constraints();
}
else {
    # Large-scale example with 17 hypervisors and 1000 VMs
    print "Running large-scale example with 17 hypervisors and 1000 VMs\n";
    
    # Generate random hypervisors and VMs
    my @hypervisors = generate_hypervisors(17);
    my @vms = generate_vms(1000, \@hypervisors, 0.8);  # 80% initial placement
    
    # Create the load balancer
    my $balancer = TOPSISLoadBalancer->new(\@hypervisors);
    
    # Initialize with existing placement
    $balancer->initialize_with_placement(\@vms);
    
    # Add random constraints
    add_random_constraints($balancer, \@vms, 0.01);  # 1% density
    
    # Print initial summary
    print "\nInitial placement summary:\n";
    $balancer->summarize_placement();
    
    print "\nStarting optimization of 1000 VMs across 17 hypervisors...\n";
    
    # Optimize VM placement
    $balancer->distribute_vms(\@vms);
    
    # Print final summary
    print "\nFinal placement summary:\n";
    $balancer->summarize_placement();
}