LowNodeUtilization plugin does not honor MaxSkew constraints, causing inefficient Pod redistribution

[qeesung]

Issue Description

In a Kubernetes cluster with multiple nodes distributed across different zones, using the Descheduler's LowNodeUtilization plugin may result in inefficient Pod redistribution when MaxSkew constraints are in place. Specifically, the issue occurs when nodes with high utilization and low utilization exist in separate zones, and a MaxSkew=1 topology spread constraint is configured. This constraint can lead to Pods being scheduled to other high utilization nodes instead of balancing the overall load of the cluster.

Example

Consider a cluster with four nodes distributed across two zones (ZoneA and ZoneB). Nodes in ZoneA are under low utilization, while nodes in ZoneB are highly utilized. The configuration includes a topology spread constraint of MaxSkew=1. When the LowNodeUtilization plugin is used to drive Pod eviction, it attempts to redistribute the Pods from the high utilization nodes in ZoneB. However, due to the MaxSkew constraint, the redistributed Pods may only be allowed to reschedule on other nodes within ZoneB, which are also highly utilized.

The result is that Pods may end up rescheduling to the same or another highly utilized node, failing to balance the overall load of the cluster.

=========== Before Descheduler ===========

+------------------+------------------+
|      N1 (ZoneA)  |      N2 (ZoneA)  |
| Low Utilization  | Low Utilization  |
+------------------+------------------+

+------------------+------------------+
|      N3 (ZoneB)  |      N4 (ZoneB)  |
| High Utilization | High Utilization |
+------------------+------------------+

=========== After Descheduler ============

+------------------+------------------+
|      N1 (ZoneA)  |      N2 (ZoneA)  |
| Low Utilization  | Low Utilization  |
+------------------+------------------+

+------------------+------------------+
|      N3 (ZoneB)  |      N4 (ZoneB)  |
| High Utilization | High Utilization |
|       (Pod Evicted from N3)         |
|       (Pod Rescheduled to N4)       |
+------------------+------------------+

Problem

• Pods evicted from high utilization nodes in ZoneB can only be rescheduled within ZoneB due to the MaxSkew=1 constraint, despite the availability of under-utilized nodes in ZoneA.
• This behavior causes the LowNodeUtilization plugin to fail in achieving load balancing effectively, as the Pods are merely being shifted between high utilization nodes.
• Leads to a potential cycle of evictions and reschedules without reducing overall utilization imbalances.

Expected Behavior

The LowNodeUtilization plugin should ideally consider topology spread constraints and balance the load effectively across zones, ensuring that Pods are rescheduled to nodes with lower utilization wherever possible, rather than simply adhering to strict MaxSkew limits in scenarios where it results in inefficiencies.