[pve-devel] [PATCH pve-ha-manager 1/8] add AHP && Topsis Math Helpers
Alexandre Derumier
aderumier at odiso.com
Wed Apr 27 17:33:44 CEST 2022
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
More information about the pve-devel
mailing list