Skip to content
← Publications
ICSOC 2024 2024

Optimizing Traffic Allocation for Multi-replica Microservice Deployments in Edge Cloud

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

22nd International Conference on Service-Oriented Computing

Summary

Nearby replica placement alone does not eliminate slow requests. LARP accounts for network latency during placement, while LATA adjusts traffic shares under load-balancing constraints.

Role
Third authoralgorithm and experiment design
Outcome
67–81% lower P99 than default Kubernetes in DAG Scenario B; LATA was also evaluated independently of the placement algorithm.
Overall system architecture: replica placement, traffic allocator, and monitoring modules
The overall system architecture

More Replicas, More Complex Communication Paths

If an upstream component has A replicas and a downstream component has B, their communication paths grow to A×B. Each path can have a different inter-node delay. Placement methods built around one replica per component do not account for all of these path costs.

Remote paths increase communication delay, but sending all traffic to nearby replicas can overload them. Doubling inter-node latency raised default routing’s mean latency by 33–44% and P99 by 57–97%. Routing only to the nearest replica increased mean latency from 11ms to 4,890ms and P99 from 22ms to 12,250ms as load rose from 100 to 300 RPS.

OptTraffic allocates traffic locally first and distributes the remainder to balance load. Slow critical paths remained after that step. In the comparison, mean latency fell by 35% but P99 by only 6%, motivating explicit use of link latency in the allocation.

From Replica Placement to Traffic Routing

LARP first places communicating replicas on nearby nodes. LATA then adjusts link-level traffic shares during execution, reducing communication delay without concentrating load on one replica. The two stages handle placement and routing separately.

The monitoring module collects inter-node delays every 15 seconds with blackbox-exporter ping probes and stores them in Prometheus. The traffic allocator extracts component dependencies as a DAG from the Istio service mesh and calculates shares for each upstream–downstream pair.

LARP: Replica Placement That Accounts for Resource Capacity and Network Latency

The placement stage creates groups from the average replica count per component and assigns replicas in round-robin order: three A replicas and two B replicas form two groups. Grouping communicating replicas reduces cross-node traffic, while distributing groups avoids concentrating every replica on one node.

A group is a placement unit for communicating replicas, not a requirement to place the entire application on one node. Its resource demand is summed and checked against node capacity even when components have different replica counts, combining communication delay with placement feasibility.

Placement is formulated as an integer program that minimizes total delay between the selected nodes. A greedy approximation places the most resource-demanding group first, then assigns others to nodes with sufficient capacity and low delay to the initial placement. This trades guaranteed optimality for a practical computation time.

LATA: Traffic Allocation with Network Latency as a Cost

LATA decides how much traffic each replica should send to each destination replica. Upstream replicas supply traffic, downstream replicas receive it, and each connecting link has a capacity and cost. This forms a Minimum-Cost Flow (MCF) problem.

Measured inter-node latency is the link cost. Network simplex minimizes the sum of each link’s traffic proportion multiplied by its latency. A slower link costs more for the same traffic, so the objective favors nearby paths within the load-balancing constraints.

Reducing total communication cost differs from reducing the latency of the slowest requests. A minimum-cost solution can still use some slow links. This distinction motivates comparing both mean latency and P99, and the high-latency link filtering added in the later HEART study.

Load Balance Preserved While Reducing Network Latency

Balancing traffic after allocation can reintroduce slow paths. LATA instead requires each upstream replica to send all its traffic and each downstream replica to receive the prescribed equal share. It minimizes communication cost within these constraints.

With A upstream and B downstream replicas, each sender transmits 100% of its own traffic and each receiver gets 1/B of the aggregate sending volume. This does not require equal shares on every link. Individual link proportions can change while balanced receiving totals are preserved.

Even after LARP chooses an initial placement favorable to communication, routing must be computed from the running replica counts and call relationships. Placement and link-level allocation are therefore separate stages, and LATA was also evaluated on default Kubernetes placement.

Controlled comparisons of network delay and request load

The evaluation used one master and four workers, each with 4 cores and 8GB of memory. Linux tc injected inter-node delays to emulate a distributed edge cloud, with Scenario B set to twice Scenario A’s delay. Istio Bookinfo and a FastAPI DAG calling A→E sequentially ran 3–5 replicas per component. Load was generated with wrk2, and results averaged over 10 runs were compared with default Kubernetes, Localization, and OptTraffic.

Node resources and application configurations remain the same across the two scenarios; only inter-node latency changes. Increasing request load within each condition separates processing bottlenecks from the effect of communication delay.

The experiment distinguishes the combined placement-and-allocation method from LATA applied to default placement. Comparing those conditions on the same service and workload examines the roles of placement and routing separately.

67–81% Lower P99 Latency in a High-Latency DAG Environment

The experiment used replica ratios favorable to OptTraffic’s local allocation. The proposed method was not faster at every percentile: OptTraffic led in the lower 65% of the DAG Scenario B distribution, while the proposed method improved the tail and mean response time.

P99 fell by an average of 32% and up to 81% across the three baselines. In high-latency Bookinfo Scenario B, the reduction versus OptTraffic averaged 25%. In DAG Scenario B, P99 was 48–72% lower than Localization, 43–46% lower than OptTraffic, and 67–81% lower than default Kubernetes. Applying LATA to default Kubernetes placement also produced the second-best result, showing that traffic allocation contributed independently of the placement algorithm.

The paper was published at ICSOC 2024 (LNCS 15404), an SCIE-compatible top-tier venue. As third author, I contributed to algorithm and experiment design. This combined approach to placement and traffic allocation later extended to heterogeneous clusters in HEART (IEEE CLOUD 2025).

P99 reductions for Bookinfo and DAG in high-latency Scenario B
ExperimentBaselineP99 reduction
Bookinfo · Scenario BOptTraffic25% on average
DAG · Scenario BLocalization48–72%
DAG · Scenario BOptTraffic43–46%
DAG · Scenario BDefault Kubernetes67–81%