HEART: Heterogeneous-Aware Traffic Allocation in Multi-Replica Deployments on Kubernetes

Traffic scheduling for microservices in emerging edge-cloud environments is challenged by heterogeneous node performance and varying inter-node latencies. Inefficient scheduling among replicas may lead to replica overload and excessive communication overhead, ultimately degrading Quality of Service (QoS) metrics-specifically, the 99th percentile tail latency(P99 latency). To address these challenges, we introduce HEART, a novel two-stage traffic scheduler that jointly accounts for node heterogeneity and network latency. In Stage 1, HEART computes per-replica traffic proportions using a sliding window and an exponentially weighted moving average of CPU usage and request rates, thereby capturing recent load trends. In Stage 2, HEART applies k-means clustering to inter-node latency measurements to identify and prune high-latency links, which in turn reduces communication delays. A Maximum Flow algorithm is subsequently employed to verify whether the pruned network supports the required traffic flow; if the reduced network proves insufficient, additional links are incrementally reinstated until a feasible configuration is achieved. Finally, a Minimum-Cost Flow algorithm-selected for its proven optimality in network flow allocation-is applied to distribute traffic cost-effectively across the network. Experimental results demonstrate that HEART significantly reduces the P99 latency compared to existing approaches such as the default Kubernetes scheduler, the Least- Request algorithm of Istio, OptTraffic, and LATA, thereby enhancing overall QoS.