[PATCH proxmox 1/7] resource-scheduling: clamp imbalance value to unit interval

[Dominik Rusovac <d.rusovac@proxmox.com>]

The currently used load imbalance value is given as the so-called
coefficient of variation (CV), a value that may exceed 1. As such, the
CV value alone lacks meaning. A CV value of 0.0 means no imbalance, but
what does a value of, say, 1.7 mean?

Relative to the number of nodes in a cluster, it is possible to
determine the upper bound of the CV value [0][1]. By dividing the CV
value by its upper bound, the load imbalance can be represented as a
value that varies between 0 and 1. Expressing the CV as a percentage
makes the concept of load imbalance easier to interpret.

[0] https://repositorio.ipbeja.pt/server/api/core/bitstreams/8ed9a444-dbe0-402f-9d2f-90c5bf6e418c/content
[1] https://stats.stackexchange.com/questions/18621/maximum-value-of-coefficient-of-variation-for-bounded-data-set

Signed-off-by: Dominik Rusovac <d.rusovac@proxmox.com>
---
 proxmox-resource-scheduling/src/scheduler.rs | 33 +++++++++++++-------
 1 file changed, 21 insertions(+), 12 deletions(-)

diff --git a/proxmox-resource-scheduling/src/scheduler.rs b/proxmox-resource-scheduling/src/scheduler.rs
index 49d16f9f..4eacbff9 100644
--- a/proxmox-resource-scheduling/src/scheduler.rs
+++ b/proxmox-resource-scheduling/src/scheduler.rs
@@ -17,17 +17,23 @@ pub struct NodeUsage {
     pub stats: NodeStats,
 }
 
-/// Returns the load imbalance among the nodes.
+/// Returns the load imbalance among the nodes, which is a value between 0 and 1 that describes the
+/// statistical dispersion of the individual node loads around the mean node load. The lower the
+/// value, the better.
 ///
-/// The load balance is measured as the statistical dispersion of the individual node loads.
-///
-/// The current implementation uses the dimensionless coefficient of variation, which expresses the
-/// standard deviation in relation to the average mean of the node loads.
-///
-/// The coefficient of variation is not robust, which is a desired property here, because outliers
-/// should be detected as much as possible.
+/// In more detail, the current implementation computes the so-called coefficient of variation (CV),
+/// which is the ratio of the standard deviation to the mean of the given node loads. The lower
+/// bound of the CV is reached if all node loads are equal. The upper bound is reached if all nodes
+/// except one are idle. To present the CV as a value between 0 and 1, it's being divided by the
+/// upper bound of the CV for the given number of nodes.
 fn calculate_node_imbalance(nodes: &[NodeUsage], to_load: impl Fn(&NodeUsage) -> f64) -> f64 {
-    let node_count = nodes.len();
+    let node_count = nodes.len() as f64;
+
+    // imbalance is perfect for less than 2 nodes
+    if node_count < 2.0 {
+        return 0.0;
+    }
+
     let node_loads = nodes.iter().map(to_load).collect::<Vec<_>>();
 
     let load_sum = node_loads.iter().sum::<f64>();
@@ -36,14 +42,17 @@ fn calculate_node_imbalance(nodes: &[NodeUsage], to_load: impl Fn(&NodeUsage) ->
     if load_sum == 0.0 {
         0.0
     } else {
-        let load_mean = load_sum / node_count as f64;
+        let load_mean = load_sum / node_count;
 
         let squared_diff_sum = node_loads
             .iter()
             .fold(0.0, |sum, node_load| sum + (node_load - load_mean).powi(2));
-        let load_sd = (squared_diff_sum / node_count as f64).sqrt();
+        let load_sd = (squared_diff_sum / node_count).sqrt();
+
+        let max_cv = (node_count - 1.0).sqrt();
+        let cv = load_sd / load_mean;
 
-        load_sd / load_mean
+        cv / max_cv
     }
 }
 
-- 
2.47.3