[pve-devel] [PATCH pve-ha-manager 1/8] add AHP && Topsis Math Helpers

[Alexandre Derumier <aderumier@odiso.com>]

Topis
https://www.youtube.com/watch?v=kfcN7MuYVeI

AHP:
https://www.youtube.com/watch?v=J4T70o8gjlk

AHP-Topis implementation in vm balancing:
https://arxiv.org/pdf/1002.3329.pdf
https://meral.edu.mm/record/4285/files/9069.pdf

Topsis (Technique for Order Preference by Similarity to Ideal Solution)
is a Multi-criteria decision making method, to find best solution (with a score),
when we need to order multiple values.

simple example: order nodes with by lower higher cpu and higher memory, where memory factor is more important

$nodes->{node1}->{cpu} = 80;
$nodes->{node1}->{mem} = 100;

$nodes->{node2}->{cpu} = 79;
$nodes->{node2}->{mem} = 99;

$nodes->{node3}->{cpu} = 90;
$nodes->{node3}->{mem} = 102;

The score results are
node1 score: 0.745400652669653
node2 score: 0.688707427881571
node3 score: 0.311292572118429

Node1 will be choose as it have the bigger score

We can of course add more parameters for more complex ranking.

Topis need a priority weight between differents parameters.
As it can be very complex to have good weights, the AHP (Analytic Hierarchy Process)
method is used to compute weights with doing a pair-wise compare of priority between all parameters

simple example : mem is twice more important than cpu

my $preferences = {
	mem => {
	    mem => 1,
	    cpu => 2,
        },
        cpu => {
	    cpu => 1,
	},
};

weights results:

cpu : 0.333333333333333
mem : 0.666666666666667
---
 debian/pve-ha-manager.install |   2 +
 src/PVE/HA/Balancer/AHP.pm    | 120 ++++++++++++++++++++++++++++++++++
 src/PVE/HA/Balancer/Makefile  |   6 ++
 src/PVE/HA/Balancer/Topsis.pm | 115 ++++++++++++++++++++++++++++++++
 src/PVE/HA/Makefile           |   2 +
 5 files changed, 245 insertions(+)
 create mode 100644 src/PVE/HA/Balancer/AHP.pm
 create mode 100644 src/PVE/HA/Balancer/Makefile
 create mode 100644 src/PVE/HA/Balancer/Topsis.pm

diff --git a/debian/pve-ha-manager.install b/debian/pve-ha-manager.install
index 33a5c58..d6979c4 100644
--- a/debian/pve-ha-manager.install
+++ b/debian/pve-ha-manager.install
@@ -19,6 +19,8 @@
 /usr/share/perl5/PVE/API2/HA/Status.pm
 /usr/share/perl5/PVE/CLI/ha_manager.pm
 /usr/share/perl5/PVE/HA/CRM.pm
+/usr/share/perl5/PVE/HA/Balancer/AHP.pm
+/usr/share/perl5/PVE/HA/Balancer/Topsis.pm
 /usr/share/perl5/PVE/HA/Config.pm
 /usr/share/perl5/PVE/HA/Config.pm
 /usr/share/perl5/PVE/HA/Env.pm
diff --git a/src/PVE/HA/Balancer/AHP.pm b/src/PVE/HA/Balancer/AHP.pm
new file mode 100644
index 0000000..a10c8fc
--- /dev/null
+++ b/src/PVE/HA/Balancer/AHP.pm
@@ -0,0 +1,120 @@
+package PVE::HA::Balancer::AHP;
+
+use strict;
+use warnings;
+
+##maths
+my $bitwise_matrix = sub {
+    my ($hash) = @_;
+
+    my $bitwise_matrix = {};
+    foreach my $rowkey (keys %$hash) {
+	my $row = $hash->{$rowkey};
+	foreach my $columnkey (keys %$row) {
+	    $bitwise_matrix->{$rowkey}->{$columnkey} = $row->{$columnkey};
+	    $bitwise_matrix->{$columnkey}->{$rowkey} = 1 / $row->{$columnkey};
+	}
+    }
+    return $bitwise_matrix;
+};
+
+my $compute_colum_sum = sub {
+    my ($bitwise_matrix) = @_;
+
+    my $matrix_column_sum = {};
+    foreach my $rowkey (keys %$bitwise_matrix) {
+	my $row = $bitwise_matrix->{$rowkey};
+	foreach my $columnkey (keys %$row) {
+	    $matrix_column_sum->{$columnkey} = 0 if !defined($matrix_column_sum->{$columnkey});
+	    $matrix_column_sum->{$columnkey} += $row->{$columnkey};
+	}
+    }
+    return $matrix_column_sum;
+};
+
+my $preference_vector = sub {
+    my ($bitwise_matrix) = @_;
+
+    my $matrix_column_sum = &$compute_colum_sum($bitwise_matrix);
+
+    my $preference_vector = {};
+    foreach my $rowkey (keys %$bitwise_matrix) {
+	my $row = $bitwise_matrix->{$rowkey};
+	my $row_sum = 0;
+	foreach my $columnkey (keys %$row) {
+	    $row_sum += $row->{$columnkey} / $matrix_column_sum->{$columnkey};
+	}
+	$preference_vector->{$rowkey} += $row_sum/ (keys %$row);
+    }
+    $preference_vector;
+};
+
+my $compute_ci = sub {
+    my ($bitwise_matrix, $preference_vector) = @_;
+
+    my $sum = 0;
+    foreach my $rowkey (keys %$bitwise_matrix) {
+	my $row = $bitwise_matrix->{$rowkey};
+	my $weighted_row_sum = 0;
+	foreach my $columnkey (keys %$row) {
+	    $weighted_row_sum += ($row->{$columnkey} * $preference_vector->{$columnkey});
+	}
+	$sum += $weighted_row_sum / $preference_vector->{$rowkey};
+    }
+
+    my $criteria_numbers = keys %$bitwise_matrix;
+    my $avg = $sum / $criteria_numbers;
+    my $ci = ($avg - $criteria_numbers) / ($criteria_numbers - 1);
+    return $ci;
+};
+
+my $compute_ri = sub {
+    my ($bitwise_matrix) = @_;
+
+    my $criteria_numbers = keys %$bitwise_matrix;
+
+    my $ri = {
+		1 => 0,
+		2 => 0,
+		3 => 0.58,
+		4 => 0.9,
+		5 => 1.12,
+		6 => 1.24,
+		7 => 1.32,
+		8 => 1.41,
+		9 => 1.45,
+		10 => 1.49,
+		11 => 1.51,
+		12 => 1.53,
+		13 => 1.56,
+		14 => 1.57,
+		15 => 1.59
+    };
+    die "too much criterias" if $criteria_numbers > 15;
+    return $ri->{$criteria_numbers};
+};
+
+my $verify_ci_index = sub {
+    my ($bitwise_matrix, $preference_vector) = @_;
+
+    die "empty matrix" if !$bitwise_matrix || !keys %$bitwise_matrix;
+
+    my $ri = &$compute_ri($bitwise_matrix);
+    return if $ri == 0;
+
+    my $ci = &$compute_ci($bitwise_matrix, $preference_vector);
+    my $ci_index = $ci/$ri;
+
+    warn "bad ahp ci index:$ci_index. please review your preferences" if $ci_index >= 0.1;
+};
+
+sub compute_weights {
+    my ($preferences) = @_;
+
+    my $bitwise_matrix = &$bitwise_matrix($preferences);
+    my $preference_vector = &$preference_vector($bitwise_matrix);
+    &$verify_ci_index($bitwise_matrix, $preference_vector); #optionnal to verify
+
+    return $preference_vector;
+}
+1;
diff --git a/src/PVE/HA/Balancer/Makefile b/src/PVE/HA/Balancer/Makefile
new file mode 100644
index 0000000..de4b1b2
--- /dev/null
+++ b/src/PVE/HA/Balancer/Makefile
@@ -0,0 +1,6 @@
+SOURCES=Topsis.pm AHP.pm
+
+.PHONY: install
+install:
+	install -d -m 0755 ${DESTDIR}${PERLDIR}/PVE/HA/Balancer
+	for i in ${SOURCES}; do install -D -m 0644 $$i ${DESTDIR}${PERLDIR}/PVE/HA/Balancer/$$i; done
diff --git a/src/PVE/HA/Balancer/Topsis.pm b/src/PVE/HA/Balancer/Topsis.pm
new file mode 100644
index 0000000..e59e9da
--- /dev/null
+++ b/src/PVE/HA/Balancer/Topsis.pm
@@ -0,0 +1,115 @@
+package PVE::HA::Balancer::Topsis;
+
+use strict;
+use warnings;
+
+#topsis best ordering score
+#https://en.wikipedia.org/wiki/TOPSIS
+#https://www.youtube.com/watch?v=kfcN7MuYVeI
+my $normalize = sub {
+    my ($hash, $weights) = @_;
+
+    my $norms = {};
+    foreach my $key (keys %$hash) {
+        my $row = $hash->{$key};
+        foreach my $column (keys %$row) {
+	    next if !defined($weights->{$column});
+            $norms->{$column} = 0 if !defined($norms->{$column});
+            $norms->{$column} += $row->{$column} * $row->{$column};
+        }
+    }
+
+    my $result = {};
+
+    foreach my $key (keys %$hash) {
+        my $row = $hash->{$key};
+        foreach my $column (keys %$row) {
+	    next if !defined($weights->{$column});
+	    if ($norms->{$column} == 0) {
+		$result->{$key}->{$column} = 0;
+	    } else {
+		$result->{$key}->{$column} = $row->{$column} / sqrt($norms->{$column});
+		$result->{$key}->{$column} *= $weights->{$column};
+	    }
+        }
+    }
+
+    return $result;
+};
+
+my $best_worst_values = sub {
+    my ($hash, $order) = @_;
+
+    my $result = {};
+
+    foreach my $key (keys %$hash) {
+        my $row = $hash->{$key};
+        foreach my $column (keys %$row) {
+
+            if ($order->{$column} eq '+') {
+                $result->{$column}->{best} = $row->{$column} if !defined($result->{$column}->{best}) || $row->{$column} > $result->{$column}->{best};
+                $result->{$column}->{worst} = $row->{$column} if !defined($result->{$column}->{worst}) || $row->{$column} < $result->{$column}->{worst};
+            } elsif ($order->{$column} eq '-') {
+                $result->{$column}->{best} = $row->{$column} if !defined($result->{$column}->{best}) || $row->{$column} < $result->{$column}->{best};
+                $result->{$column}->{worst} = $row->{$column} if !defined($result->{$column}->{worst}) || $row->{$column} > $result->{$column}->{worst};
+            }
+        }
+    }
+    return $result;
+
+};
+
+my $euclidean_distance = sub {
+    my ($hash, $best_worst_hash, $type) = @_;
+
+    my $result = {};
+
+    foreach my $type ('best', 'worst') {
+
+        foreach my $key (keys %$hash) {
+            my $row = $hash->{$key};
+            foreach my $column (keys %$row) {
+                my $diff = ($row->{$column} - $best_worst_hash->{$column}->{$type});
+                $diff *= $diff;
+                $result->{$key}->{$type} = 0 if !defined($result->{$key}->{$type});
+                $result->{$key}->{$type} += $diff;
+            }
+            $result->{$key}->{$type} = sqrt($result->{$key}->{$type});
+        }
+    }
+
+    return $result;
+};
+
+my $compute_score = sub {
+    my ($hash) = @_;
+
+    my $result = {};
+
+    foreach my $key (keys %$hash) {
+        my $row = $hash->{$key};
+        foreach my $column (keys %$row) {
+	    if($hash->{$key}->{worst} == 0 && $hash->{$key}->{best} == 0) {
+		$result->{$key}->{score} = 0;
+	    } else {
+		$result->{$key}->{score} = $hash->{$key}->{worst} / ($hash->{$key}->{worst} + $hash->{$key}->{best});
+	    }
+        }
+    }
+    return $result;
+};
+
+sub score {
+    my ($hash, $weights, $bestorder) = @_;
+
+    die "topsis_score : empty hash" if !$hash || !keys %$hash;
+
+    my $normalized_hash = &$normalize($hash, $weights);
+    my $best_worst_hash = &$best_worst_values($normalized_hash, $bestorder);
+    my $euclidean_distances = &$euclidean_distance($normalized_hash, $best_worst_hash);
+    my $scores = &$compute_score($euclidean_distances);
+
+    return $scores;
+}
+
+1;
diff --git a/src/PVE/HA/Makefile b/src/PVE/HA/Makefile
index c366f6c..a548c86 100644
--- a/src/PVE/HA/Makefile
+++ b/src/PVE/HA/Makefile
@@ -9,9 +9,11 @@ install:
 	for i in ${SOURCES}; do install -D -m 0644 $$i ${DESTDIR}${PERLDIR}/PVE/HA/$$i; done
 	make -C Resources install
 	make -C Env install
+	make -C Balancer install
 
 .PHONY: installsim
 installsim:
 	install -d -m 0755 ${DESTDIR}${PERLDIR}/PVE/HA
 	for i in ${SIM_SOURCES}; do install -D -m 0644 $$i ${DESTDIR}${PERLDIR}/PVE/HA/$$i; done
 	make -C Sim install
+	make -C Balancer install
-- 
2.30.2