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

Equal traffic shares produced unequal load

Microservices run multiple replicas of a component. Equal traffic shares can overload replicas on slower nodes, while different inter-node delays send some requests through slower paths. HEART accounts for both differences to reduce P99 latency.

Even with sub-1ms inter-node delays, default routing reached 4,010ms P99 at 100 RPS. Istio Least Request lowered it to 293ms, but replicas on slower nodes still exceeded 100% CPU briefly. Their per-request CPU utilization also varied by about 12.3%, motivating the use of load trends alongside current measurements.

Our earlier LATA method could still retain slow links. Removing one link reduced the critical-path delay from 100ms to 80ms, suggesting that slow links should be filtered before traffic shares were optimized. Computation also needed attention: scheduling time rose from 8.8ms to 98.1ms as the replica count increased from 100 to 400.

Separating processing capacity from network cost

HEART updates routing every 30 seconds in two stages. ATPM determines group-level traffic shares from processing capacity. NTAM then assigns those shares to links while accounting for network delay. This separates node-capacity estimation from path allocation.

The Metric Collector gathers replica CPU usage, request counts, inter-node delays, and component call relationships through Prometheus exporters. Both stages use these measurements without collecting the same information separately.

ATPM: estimating load and group shares

Replicas of the same component are grouped by node, reducing the number of links considered in the next stage. Load is calculated as CPU usage per request; replicas that have served no requests are excluded from that calculation.

A fixed EWMA weight can respond too slowly or react too strongly to a short fluctuation. The weight is adjusted each cycle from recent volatility and constrained to a range selected by comparing candidate settings.

Groups with higher estimated load receive smaller traffic shares. When measurements are missing, existing groups reuse their previous EWMA and new groups use the mean of valid groups. If all values are zero, traffic is divided equally. Computation runs in parallel by component.

NTAM: filtering slow links and checking feasibility

NTAM assigns the ATPM proportions to actual links. Minimizing total flow cost alone still left slow links that raised P99, so the design removes slow links before optimizing the remaining paths.

K-means separates links into high- and low-delay groups. When high-delay links are few, they are removed together; otherwise, removal proceeds from the slowest link. A Maximum Flow check verifies that the remaining graph can satisfy each group’s required traffic. If not, links are restored or the last feasible configuration is retained.

Once the required traffic can be carried, Minimum-Cost Flow minimizes total traffic × latency. Each group’s allocation is divided equally among its replicas. Enabling the slow-link filter alone reduced P99 by about 7.5% on average.

Results — P99 and overhead together

On the pairwise application, HEART reduced P99 by about 95.2% versus default routing and from 293ms to 194ms versus Least Request. It remained stable from 50 to 200 RPS, with a more even CPU load across replicas on slower nodes. At 50 RPS in high-latency Scenario B, P99 was 502ms for OptTraffic, 440ms for LATA, and 357ms for HEART.

At 400 RPS with sub-1ms links, the DAG application had P99 values of 30,620ms with default routing, 768ms with Least Request, 1,580ms with OptTraffic, 1,450ms with LATA, and 82ms with HEART. From 200 to 400 RPS, HEART increased from 60ms to 82ms, while default routing increased about 61-fold. HEART also limited the max–min CPU-utilization difference to about 3 percentage points.

Ablation experiments tested load-trend analysis. Including it reduced P99 from 366ms to 176ms in Scenario A, about 51.9%, and from 528ms to 241ms in Scenario B, about 54.4%. Under a complex workload, the max–min CPU-utilization gap was about 15 percentage points with the trend and 75 without it.

As replica count grew from 100 to 400, scheduling computation rose from 8.8ms to 98.1ms for LATA and from 6ms to 9.4ms for HEART. Group-level computation and parallel processing across components and component pairs limited that overhead. HEART was implemented in Go 1.22.6 and evaluated on Kubernetes 1.27.5 with one master and five heterogeneous workers. I participated in its joint design and implementation as the follow-up to LATA; it was published at IEEE CLOUD 2025.

Evaluation covered up to 400 replicas on stable nodes. The 30-second update cycle cannot respond immediately to failures between updates. Event-driven failure handling and integration with autoscaling remain follow-up work.