From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from firstgate.proxmox.com (firstgate.proxmox.com [212.224.123.68]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits)) (No client certificate requested) by lists.proxmox.com (Postfix) with ESMTPS id F2F0EA770 for ; Wed, 27 Apr 2022 17:33:58 +0200 (CEST) Received: from firstgate.proxmox.com (localhost [127.0.0.1]) by firstgate.proxmox.com (Proxmox) with ESMTP id E80EF2881C for ; Wed, 27 Apr 2022 17:33:58 +0200 (CEST) Received: from bastionodiso.odiso.net (bastionodiso.odiso.net [IPv6:2a0a:1580:2000::2d]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits)) (No client certificate requested) by firstgate.proxmox.com (Proxmox) with ESMTPS id 0CF7B287C5 for ; Wed, 27 Apr 2022 17:33:53 +0200 (CEST) Received: from kvmformation3.odiso.net (formationkvm3.odiso.net [10.3.94.12]) by bastionodiso.odiso.net (Postfix) with ESMTP id B8100159B7; Wed, 27 Apr 2022 17:33:52 +0200 (CEST) Received: by kvmformation3.odiso.net (Postfix, from userid 0) id AAA83F94BB; Wed, 27 Apr 2022 17:33:52 +0200 (CEST) From: Alexandre Derumier To: pve-devel@lists.proxmox.com Date: Wed, 27 Apr 2022 17:33:44 +0200 Message-Id: <20220427153351.1773666-2-aderumier@odiso.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20220427153351.1773666-1-aderumier@odiso.com> References: <20220427153351.1773666-1-aderumier@odiso.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-SPAM-LEVEL: Spam detection results: 0 AWL -0.003 Adjusted score from AWL reputation of From: address BAYES_00 -1.9 Bayes spam probability is 0 to 1% HEADER_FROM_DIFFERENT_DOMAINS 0.248 From and EnvelopeFrom 2nd level mail domains are different KAM_DMARC_STATUS 0.01 Test Rule for DKIM or SPF Failure with Strict Alignment KAM_LAZY_DOMAIN_SECURITY 1 Sending domain does not have any anti-forgery methods NO_DNS_FOR_FROM 0.001 Envelope sender has no MX or A DNS records SPF_HELO_NONE 0.001 SPF: HELO does not publish an SPF Record SPF_NONE 0.001 SPF: sender does not publish an SPF Record Subject: [pve-devel] [PATCH pve-ha-manager 1/8] add AHP && Topsis Math Helpers X-BeenThere: pve-devel@lists.proxmox.com X-Mailman-Version: 2.1.29 Precedence: list List-Id: Proxmox VE development discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 27 Apr 2022 15:33:59 -0000 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