Source-linked AI summary
Optimizing API Gateway Placement in Multi-Cloud Kubernetes
Vinoth Punniyamoorthy, Murali Shankar Dulam, Aswathnarayan Muthukrishnan Kirubakaran, Akshay Deshpande, Nachiappan Chockalingam, Bikesh Kumar, Naga Surya Pasupuleti, Narender Reddy Bitla
TL;DR
The paper addresses cost-efficient API gateway placement across geographically distributed multi-cloud Kubernetes clusters under regional latency and capacity constraints. It formulates placement as capacitated facility location and evaluates exact MILP and greedy solutions on seeded synthetic instances. The greedy method is much faster with a modest average gap, while MILP provides certified-optimal deployments.
Problem
API gateway placement must balance infrastructure cost, replica capacity, and regional client-to-cluster latency across heterogeneous multi-cloud Kubernetes clusters.
Method
The paper jointly selects clusters, replica counts, and regional traffic assignments using a latency-constrained capacitated facility-location MILP and a load-aware incremental-cost greedy heuristic.
Results
The greedy heuristic achieves a 3.2%-4.7% mean optimality gap with a 660-3,490× runtime advantage over MILP on the evaluated instances.
Takeaways & Limitations
MILP is suitable for infrequent planning when certified optimality matters, while the faster heuristic may suit frequent re-evaluation when its solution gap is acceptable.
Takeaways & Limitations
The evaluation uses synthetic latency, demand, SLA, and cost inputs; latency excludes congestion and gateway, queueing, and backend components.
Abstract
from arXiv · showhide
The use of API gateways within geographically distributed multi-cloud Kubernetes clusters poses a tradeoff between infrastructure cost, computational resources, and network latencies. We present an optimization formulation that addresses API gateway placement as a capacitated facility location problem that jointly determines which candidate clusters to activate, how many gateway replicas to deploy, and how regional traffic should be distributed across the selected clusters. The formulation imposes an upper bound on estimated client-to-cluster network round-trip latency, excluding gateway processing, queuing, and backendservice latency, and incorporates a utilization headroom factor for gateway replica capacity. We present both a mixed-integer linear programming (MILP) formulation and a constructive greedy heuristic that ranks candidates according to incremental cost, comprising cluster-activation and marginal replica costs, per unit of assignable capacity while explicitly accounting for already committed load. Both formulations are applied to deterministic, seed-controlled, geography-based synthetic instances. For each problem size, 30 instances are generated with random seeds to analyze their performance. The greedy algorithm achieves an optimality gap of 3.2% to 4.7% to the MILP optimal solution, with a maximum observed gap of 25.0% for one particular instance, and a speedup of approximately 660x to 3,490x for 3 to 12 candidate clusters. In a canonical 10-candidate, 10-demand region instance, MILP-optimal deployment saves 24.2% in terms of monthly cost compared to the full-replication baseline. On the other hand, selecting the single cheapest candidate yields savings of 24.8% compared to the MILP optimum but does not satisfy the latency requirement for 3 out of 10 demand regions.
I. INTRODUCTION
The paper frames multi-cloud API gateway placement as a cost-and-capacity planning problem constrained by regional latency, adapting facility-location optimization to geographically distributed Kubernetes clusters.
- API gateway replicas may need geographic placement near distributed clients to satisfy network-latency requirements.
- Activating additional clusters introduces fixed operational expense and per-replica compute cost, requiring tradeoffs among proximity, capacity, and infrastructure cost.
- The planning problem jointly selects hosting clusters, replica counts, and regional traffic assignments while minimizing monthly deployment cost under capacity and latency constraints.
- The latency measure is estimated client-to-cluster network round-trip time and excludes gateway processing, queuing, load-balancer, TLS, and backend-service latency.
- Prior work does not jointly optimize gateway placement, replica allocation, and regional traffic assignment across heterogeneous multi-cloud Kubernetes clusters.
- The paper formulates the problem as capacitated facility location, proposes a load-aware incremental-cost greedy heuristic, and evaluates it using 30 seeds per problem size.
II. BACKGROUND AND RELATED WORK
Related work covers fixed-platform gateway evaluation, governance, autoscaling, and classical facility-location formulations, but these address different deployment decisions or abstractions.
- API Gateway Deployment and Governance: Benchmarks compare gateway performance and cost across orchestration platforms within one fixed cluster, rather than selecting clusters for deployment.
- API Gateway Deployment and Governance: Governance-aware architectures maintain security and performance policies across already deployed clusters, treating the cluster set as an input.
- API Gateway Deployment and Governance: Within-cluster autoscaling adjusts pod replicas using live signals, whereas this paper makes a static cross-cluster placement decision.
- Facility Location Foundations: Capacitated facility location selects candidate sites and assigns demand to opened sites while minimizing opening and delivery cost under capacity limits.
C. Cloud and Edge Service Placement
The formulation specializes capacitated facility location to gateway replicas by modeling latency-feasible traffic assignment, usable replica capacity, activation, and replica limits.
- Problem Formulation: The model represents regions with demand and latency limits, and clusters with activation costs, replica costs, capacity, and maximum replica counts.
- Problem Formulation: A utilization headroom factor ρ = 0.8 limits usable replica capacity to ρκj, reserving margin below full utilization.
- Problem Formulation: The SLA-feasible set Fi contains clusters whose estimated latency to region i does not exceed SLAi.
- Problem Formulation: Traffic may be split across multiple SLA-feasible clusters through weighted routing.
- Problem Formulation: Constraints assign all regional demand to feasible clusters, cap load by usable capacity, and link replica counts to cluster activation and limits.
- Problem Formulation: The resulting optimization is a mixed-integer capacitated facility-location problem with established NP-hard special cases.
A. Exact MILP Solution
The paper solves the placement problem exactly with a certified-optimal MILP and compares it with a corrected load-aware cost-ordered greedy heuristic.
- Exact MILP Solution: The MILP uses CBC 2.10.3 via PuLP 3.3.2, single-threaded, with zero relative MIP-gap tolerance and a documented wall-clock limit.
- Corrected Greedy Heuristic: The corrected heuristic computes available capacity from assigned load against usable capacity and recomputes replicas after each assignment.
- Corrected Greedy Heuristic: Candidate ranking divides total incremental cost, including activation and newly required replicas, by actually assignable load.
- Corrected Greedy Heuristic: The heuristic has O(|I||J|^2) worst-case time and returns INFEASIBLE when demand remains unassigned.
- Corrected Greedy Heuristic: The algorithm initializes loads and replicas, processes regions by decreasing demand, repeatedly commits to the lowest incremental-cost-per-load candidate, and returns the resulting placement or infeasibility.
V. EXPERIMENTAL SETUP
The experiments use deterministic, geography-based synthetic instances spanning cloud regions and demand centers, with a canonical instance reused across baseline and sensitivity analyses.
- Instance generation: Candidate clusters span twelve AWS, GCP, and Azure regions with relative pricing multipliers from 0.85 to 1.20.The multipliers apply to base fixed and per-replica monthly costs.
- Instance generation: 10 demand regions represent geographic client population centers with demands uniformly sampled from 200 to 4000 RPS.Regional latency thresholds are sampled from 50, 75, 100, and 150 ms.
- Canonical instance: A canonical 10-cluster, 10-region instance with requested seed 777 is reused for every baseline and sensitivity result.The requested seed required three attempts to obtain a feasible draw.
- Canonical instance: The canonical instance is documented through candidate-cluster and demand-region tables, with solver runs performed single-threaded on a commodity cloud VM.The runs use CBC 2.10.3 via PuLP 3.3.2.
VI. RESULTS
Across repeated feasible-instance trials, greedy solutions remain close to MILP optima but exhibit instance-dependent gaps, including occasional large outliers and substantial runtime advantages.
- Repeated trials: 30 independently seeded feasible instances were generated for each of five problem sizes and solved by both methods.CBC returned Optimal status for all 150 instances.
- Optimality gap: Median greedy optimality gaps range from 0.0% at 3c/4d to 4.7% at 5c/6d.The gap does not decrease monotonically with problem size.
- Optimality gap: Single-instance greedy gaps reach 25% even at small problem sizes.The results attribute gap variation to instance-specific cost, latency, and feasibility structure rather than scale alone.
- Runtime: The measured MILP-to-greedy median runtime ratio ranges from approximately 660× to 3,490× across tested sizes.The reported ratio varies by problem instance.
B. Solver Scaling Behavior
Solver scaling is irregular for MILP but remains lightweight for the greedy heuristic: MILP difficulty depends strongly on instance structure, while greedy runtime grows mildly with cluster count.
- MILP scaling: MILP median solve time peaks at 12 clusters before dropping sharply by 16 clusters.The larger-cluster experiment used five instances per size and a 60-second time limit, with all tested instances solved to Optimal status.
- Evaluation design: Table III compares greedy optimality gaps and runtimes against MILP over 30 instances per problem size, with a 100% CBC optimal rate.The accompanying distribution view reports quartiles, whiskers, medians, means, and outliers by size.
- MILP scaling: MILP solve time is not monotonic in cluster count, reflecting instance-specific cost, latency, and feasibility structure.The paper does not claim MILP solving becomes impractical at any tested scale.
- Greedy scaling: The greedy heuristic remains under 1.1 ms in median runtime through 80 candidate clusters.Its measured growth is roughly linear in cluster count, consistent with its O(|I||J|^2) worst-case complexity.
C. Baseline Comparison (Canonical Instance)
On the canonical instance, MILP-optimal placement substantially reduces monthly cost versus full replication while satisfying all regional latency SLAs; the cheapest single-cluster deployment is slightly cheaper but infeasible for some regions.
- 24.2% lower monthly cost than full replication is achieved by the MILP-optimal placement, with zero SLA violations.Full replication also achieves zero SLA violations on this instance.
- 24.8% lower cost than the MILP optimum is achieved by the single-cheapest deployment, but it violates latency SLAs for 3 of 10 regions.The result illustrates that the cheapest deployment is not necessarily latency-compliant.
- SLA Sensitivity: 15.1% higher cost and activation of 5 rather than 3 clusters result when the SLA threshold is halved on this instance.Relaxing the threshold to 3× reduces cost by 4.0% and results in 2 activated clusters.
VII. DISCUSSION
The discussion weighs exact and heuristic deployment strategies against cost, runtime, SLA feasibility, and modeling scope. It emphasizes that cluster activation costs dominate savings, while deployment automation and several real-world effects remain outside the model.
- Cost drivers: Avoiding unnecessary cluster activation is the primary modeled source of cost reduction relative to full replication.Fixed per-cluster activation cost contributes more to full replication’s cost premium than marginal replica cost.
- Operational trade-off: For infrequent planning cycles, MILP’s still sub-second solve time supports paying for a certified-optimal answer.For frequent re-evaluation, the heuristic may be preferable, particularly when periodically checked against an exact solve.
- Deployment scope: Computed placements require downstream automation for cluster-specific configuration and governance-policy consistency.Migration cost, rollout safety, and when re-solving is warranted are not modeled.
- Threats to validity: The evaluation uses synthetic latency, demand, SLA, and cost inputs, so reported costs are normalized relative figures rather than list prices.The latency model also excludes congestion, routing asymmetry, and gateway, queueing, and backend components; other omitted factors include failures, quotas, egress, and migration costs.
- SLA sensitivity: 15.1% cost increase results when the latency SLA is tightened twofold on the canonical instance.The sensitivity analysis uses the same latency matrix, demand, and costs while varying only SLA thresholds.
IX. CONCLUSION AND FUTURE WORK
The paper formulates multi-cloud API gateway replica placement as a capacitated facility-location problem and evaluates exact and greedy solution methods on seeded synthetic instances. The greedy method is much faster with a small average gap, while MILP achieves lower canonical-instance cost than full replication; the authors frame these results as feasibility and trade-off evidence rather than production validation.
- Conclusion: API gateway replica placement is formulated as a capacitated facility-location problem with strict per-region latency thresholds and replica-utilization headroom.The formulation is distinct from single-cluster gateway performance, policy governance, and within-cluster autoscaling studies.
- Evaluation: The exact MILP and corrected greedy heuristic are evaluated across repeated, independently seeded synthetic instances.The accompanying repository provides the generator, implementations, canonical parameters, solver metadata, and raw per-trial results.
- Results: 3.2-4.7% mean optimality gap accompanies a 660-3,490× runtime advantage for the greedy heuristic.These results summarize the tested instances and compare the heuristic with MILP solutions.
- Results: 24.2% lower monthly cost is achieved by MILP-optimal placement than the precisely defined full-replication baseline on the canonical instance.The canonical result has zero SLA violations.
- Future work: The results demonstrate formulation feasibility and a practical heuristic trade-off but do not establish production cost or latency improvements.Future work includes validating latency against measured inter-region paths and replacing point demand estimates.