Skip to content
← Publications
IEEE CLOUD 2025 2025

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

Hokun Park, Donggyun Kim, Hyungjun Kim, Gyujeong Lim, Heonchang Yu

2025 IEEE 18th International Conference on Cloud Computing (CLOUD)

Summary

Routing to nearby replicas can cause overload, while equal shares can retain slow paths. HEART calculates processing capacity and network delay separately to adjust both traffic shares and routes.

Role
Second authorjoint design and implementation of the LATA follow-up
Outcome
82ms P99 for the DAG at 400 RPS with sub-1ms links; 9.4ms scheduling overhead at 400 replicas.
HEART system architecture: ATPM and NTAM modules across master and worker nodes
The HEART system architecture (ATPM + NTAM)

Unequal Node Loads Despite Equal Traffic Shares

Microservices run multiple replicas of a component. Even with equal traffic shares, replicas on nodes with relatively lower performance can reach overload sooner. Inter-node delays also vary, so the destination replica affects response time. HEART considers both processing capacity and communication paths 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 nodes with relatively lower performance 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.

Separate Calculations for Capacity and Network Latency

HEART separates how much traffic to send from which paths to use. ATPM first assigns group-level shares according to node processing capacity. NTAM then selects lower-delay paths that satisfy those shares. The two stages repeat every 30 seconds to update routing.

The Metric Collector gathers replica CPU usage, request counts, inter-node delays, and component call relationships through Prometheus exporters. ATPM and NTAM share these observations.

ATPM: Group Traffic Shares Adjusted to Load Trends

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.

Group load is the mean CPU usage per request among valid replicas divided by the group’s total replica count. Replicas on the same node may have similar processing characteristics, but a larger group can share more incoming requests.

The emphasis on recent load can make estimates lag or overreact to temporary changes. EWMA combines new load with the previous estimate in a weighted average. Its coefficient α, the weight given to the new observation, is updated according to recent variation.

The 30 most recent group-load observations provide a mean and an MSE, the mean squared deviation from that mean. An equally sized MSE history is retained; Min-Max normalization of the current MSE within it determines the EWMA coefficient. The experimental comparison selected a 0.2–0.8 range to avoid nearly ignoring new observations or giving them full weight.

Traffic shares are the reciprocals of predicted group loads, normalized by their sum. A lower predicted load gives a group a larger share, while a higher load gives it a smaller one. The shares sum to one and become the sending and receiving constraints for the next stage.

An existing group without a valid observation reuses its previous EWMA; a new group uses the mean of other valid groups. If all values are zero, traffic is distributed uniformly so groups can still receive requests without observations. Group loads and proportions are calculated in parallel for each component.

NTAM: Removing Slow Links While Preserving Required Flow

NTAM finds paths that carry the shares assigned by ATPM. Minimum-Cost Flow (MCF) minimizes total communication cost, but can still send some requests over slow paths. The design therefore removes slow links before calculating traffic shares on the remaining paths.

A bipartite graph uses upstream groups as supply vertices and downstream groups as demand vertices. ATPM fixes each group’s sending and receiving amount, measured inter-node latency supplies the link cost, and the smaller of the associated supply and demand determines link capacity.

K-means divides links into high- and low-latency clusters. If the high-latency cluster is smaller, its links are removed together and restored as needed; otherwise, links are removed one at a time from the slowest. If the required traffic can no longer be delivered, the algorithm returns to the last feasible configuration.

Maximum Flow checks whether the remaining links can carry the full required traffic. MCF then minimizes delay cost on a graph that passes that check. Separating pruning feasibility from cost optimization prevents lower-delay routing from disconnecting required traffic.

MCF minimizes the sum of traffic volume multiplied by latency on the validated graph. Each group-to-group flow is divided equally among its replica pairs to produce deployable traffic proportions. Applying the high-latency link filter alone reduced P99 by an average of 7.5%.

  1. Assign group proportions from processing capacity

    Group replicas on the same node and account for per-request CPU and replica count. Forecast load with EWMA, using prior values, peer initialization, or equal allocation when observations are missing.

  2. Identify slow links for pruning

    Cluster link delays into two groups. Remove the high-delay group first when it is smaller; otherwise prune links one at a time, starting with the slowest.

  3. Verify that all required traffic can flow

    Use MaxFlow to check supply and demand. Restore links or return to the last feasible configuration when the required flow cannot be carried.

  4. Minimize cost on the feasible graph

    Solve Minimum-Cost Flow over the retained links and translate group allocations into routing proportions for individual replicas.

HEART traffic allocation · summary of Algorithms 1–2

Evaluation across node performance and network delay

HEART was implemented in Go 1.22.6 and evaluated on heterogeneous Kubernetes 1.27.5 with one master and five workers. A two-component pairwise application and a multi-component DAG application test its behavior as call relationships become more complex.

Default Kubernetes, Istio Least Request, OptTraffic, and LATA were compared under sub-1ms inter-node latency and the differing delays of Scenarios A and B. P99 and CPU distributions were examined as load changed. An ablation against HEART without trend analysis separately assessed ATPM’s contribution.

The evaluation also examined whether increasing replica counts made scheduling computation costly. Comparing 100 to 400 replicas assessed the effects of grouping and parallel computation by component.

82ms P99 and 9.4ms Scheduling Time for 400 Replicas

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

The difference was larger on the DAG application. At 400 RPS with sub-1ms inter-node delays, P99 was 30,620ms with default Kubernetes, 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 Kubernetes increased about 61-fold. Where existing methods showed CPU utilization ranging from 27% to 103%, HEART’s maximum–minimum gap averaged about 3 percentage points across components.

Ablation experiments tested the contribution of 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 maximum–minimum CPU-utilization gap was about 15 percentage points with trend analysis and 75 without it.

As replica count grew from 100 to 400, scheduling time rose from 8.8ms to 98.1ms for LATA and from 6ms to 9.4ms for HEART. Grouping replicas by node and calculating components and component pairs in parallel limited this increase.

I participated in joint design and implementation following LATA, and the paper 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, so event-driven failure handling and integration with autoscaling remain follow-up work.

Request latency and scheduling time by experiment · All values in ms
ExperimentComparatorBaseline (ms)HEART (ms)
DAG · 400 RPS · links <1msDefault Kubernetes · P9930,62082
Same configurationLeast Request · P9976882
Trend ablation · Scenario AHEART no trend · P99366176
Trend ablation · Scenario BHEART no trend · P99528241
400 replicasLATA · scheduling time98.19.4