Search papers, labs, and topics across Lattice.
This paper formulates the problem of API gateway placement in multi-cloud Kubernetes clusters as a capacitated facility location problem, optimizing for cost, resource allocation, and network latency. By employing both a mixed-integer linear programming (MILP) approach and a greedy heuristic, the authors demonstrate that their methods can significantly reduce monthly costs while adhering to latency constraints. The greedy algorithm achieves a competitive optimality gap of 3.2% to 4.7% compared to the MILP solution, highlighting its efficiency with a speedup of up to 3,490x across various candidate clusters.
Achieving up to 24.2% cost savings in multi-cloud API gateway deployment while meeting strict latency requirements could revolutionize cloud infrastructure optimization.
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.
