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

More replicas create more 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.

Coordinating placement and traffic allocation

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.

A monitoring module measures inter-node latency every 15 s with blackbox-exporter ping probes into Prometheus, and the traffic allocator extracts component dependencies as a DAG from the Istio service mesh, optimizing each upstream–downstream pair independently.

LARP: grouping and placing replicas

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.

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: minimizing communication cost

Traffic allocation is formulated as a Minimum-Cost Flow problem. Upstream replicas supply traffic, downstream replicas receive it, and each connecting link has a capacity and cost.

Measured inter-node latency defines the link cost, so sending the same volume over a slower link is more expensive. A network-simplex solver finds the allocation that minimizes the sum of traffic × latency.

Including load balance in the constraints

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.

Experiment and results

A cluster of one master and four workers (4 cores / 8 GB each) used Linux tc to inject inter-node delays across two scenarios (A, and B = 2×A) to emulate a distributed edge cloud. On two benchmarks — Istio Bookinfo and a FastAPI DAG calling A→E sequentially — with 3–5 replicas per component, load was driven with wrk2 over 10 averaged runs against default K8s, Localization, and OptTraffic.

The experiment kept global and local replica ratios close, a configuration favorable to OptTraffic, to avoid relying on a disadvantaged baseline. 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.

The approach cut P99 tail latency by an average of 32% (up to 81%) across the three baselines. On the high-latency Bookinfo scenario B it reduced P99 by an average of 25% versus OptTraffic, and on the more complex DAG scenario B it lowered P99 by 48–72% versus Localization, 43–46% versus OptTraffic, and 67–81% versus default K8s. Notably, applying LATA alone on top of default K8s placement gave the second-best result — showing the allocation stage contributes independently of placement. Published at ICSOC 2024 (LNCS 15404), a top-tier SCIE-class venue, I took part as the third author, contributing to the algorithm and experiment design. Its placement-and-allocation view later extended to heterogeneous clusters in HEART (IEEE CLOUD 2025).