CS Paper Radar

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

cs.DC ·submitted 2026-08-27 03:31 UTC · v1
theory

Abstract

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Pod-Deployability in Kubernetes with Inter-Pod Affinity Constraints is PSPACE-Complete

cs.CC cs.DC ·2026-08-20 ·Saverio Giallorenzo, Jacopo Mauro, Gianluigi Zavattaro
similarity 0.62
Abstract

Kubernetes is the de-facto platform for container orchestration. Its scheduler combines resource capacities with label-based affinity and anti-affinity rules, and the interaction of these features can make the eventual placement of a pod. In this paper, we study the pod-deployability problem: given an initial cluster, a pod type, and a designated node, does some legal sequence of pod deployments and deletions cover the target pair? We give three complexity results. First, when dynamic constraints contain no affinity (anti-affinity is allowed), pod-deployability is decidable in polynomial time. Second, required affinity together with required anti-affinity makes the problem PSPACE-complete. Third, required affinity alone is already enough for PSPACE-completeness on a single node with one scalar capacity. The lower bounds encode, respectively, 1-safe Petri-net coverability and bounded black pebbling. These results isolate two independent sources of state-space complexity in Kubernetes scheduling: logical exclusion and resource-bounded prerequisite management.

0.33

Fleet-Scale Pod Deployment with VPC-Native Networking in Managed Kubernetes

cs.NI cs.DC ·2026-08-23 ·Sri Saran Balaji Vellore Rajakumar, Jayanth Varavani, Murat Parlakisik, Pavani Panakanti
similarity 0.58
Abstract

Managed Kubernetes pod deployment is often presented as a choice between VPC-native and overlay networking. Public EKS documentation describes prefix-mode capacity and configuration, while prior CNI studies primarily measure steady-state throughput and latency. This paper presents an operational measurement study of fleet-scale pod deployment across three VPC-native modes on Amazon EKS: individual secondary-IP allocation, ENI preallocation, and IPv4 prefix delegation, using Cilium and Calico as overlay baselines. We compare representative mode-specific warm-pool settings, so the results describe combined operating points. At 400 nodes, the tested three-address secondary-IP warm pool required 7,403 seconds to place 80,000 pods. With the tested ENI-preallocation and prefix-delegation settings, the same workload completed in approximately 495 seconds, moving address provisioning off the pod-creation critical path. In the reported 400-node runs, prefix delegation achieved approximately 162 pods/s, within the same observed range as the fastest overlay baseline and ENI-preallocation runs, while requiring fewer successful EC2 provisioning calls per pod than individual-IP allocation by allocating addresses in /28 blocks. Because each /28 contains 16 addresses and occupies one IPv4 slot, an interface with 30 slots carries 29 prefixes, representing up to 464 potential pod addresses, compared with approximately 30 IPv4 slots per ENI for individual-IP allocation when kubelet and CNI limits are configured accordingly. Prefix delegation also has lower documented network-address usage and retains direct VPC reachability and flow-log visibility but the trade-off is that /28 allocations require contiguous subnet space.

0.28

A Kubernetes-Native Request Router for Quality-Aware Inference Serving in the Computing Continuum

cs.DC ·2026-09-17 ·Ignjat Karanovic, Pantelis A. Frangoudis, Ivan Čilić, Ivana Podnar Žarko, Schahram Dustdar
similarity 0.58
Abstract

We introduce Adaptive Score-based Routing Balancer (ASRB), a dynamic, score-based request routing mechanism for Kubernetes-based service deployments over the computing continuum. ASRB jointly considers infrastructure-level information, response time measurements, and application-level quality indicators, with a particular focus on serving Machine Learning (ML) workloads. For these workloads, ASRB balances requests over service instances deployed in the continuum, following service provider-defined policies encoded as weighted combinations of QoS criteria to flexibly address latency-accuracy trade-offs. To drive routing decisions and swiftly adapt to changes in the operating environment, ASRB monitors a range of runtime metrics across multiple system layers. To deal with the associated monitoring overhead, particularly important for large-scale deployments, it selectively and adaptively controls monitoring intensity without sacrificing on routing quality. ASRB is implemented without requiring any modifications to Kubernetes, making it straightforward to deploy and operate in existing cluster environments. Our testbed experiments demonstrate the versatility of ASRB: When tuned for latency reduction, it achieves at least 10 ms lower mean response time compared with latency-oriented state-of-the-art routing mechanisms, while it achieves higher accuracy when this is prioritized through specific configurations, thus enabling flexible and operator-controllable trade-offs. At the same time, it attains reduced failure rates, higher responsiveness to changes in the operating environment, and up to ~70% less monitoring cost than relevant state-of-the-art solutions, at the potential expense of only a modest latency penalty in some configurations.

0.28

ScaleBench: An Extensible and Reproducible Experimental Platform for Kubernetes Autoscaling Research

cs.DC ·2026-11-18 ·Ze Wang, Sajid Alam, Amjad Ullah
similarity 0.57
Abstract · Accepted for publication in the 1st Workshop, titled ContinuumOps: DevOps for the Edge-Cloud Continuum, which was co-located with the 24th I…

Autoscaling enables cloud-native applications to meet their SLOs by dynamically adjusting computational resources at runtime. Recent research has explored a broad range of advanced autoscaling approaches, including rule-based, optimisation-based, and machine learning-based techniques, to address the limitations of traditional resource management strategies in cloud-native environments. Despite significant advances, a considerable gap remains between academic innovations and their practical adoption in real-world environments. For instance, Kubernetes deployments commonly rely on the reactive, CPU-based Horizontal Pod Autoscaler, limiting the adoption of more advanced autoscaling approaches. Recent studies have investigated challenges such as autoscaler configuration and reproducible performance evaluation; however, the practical deployment, integration complexity, and operational overhead of research-based autoscalers in Kubernetes environments have received limited attention. To address this gap, we present ScaleBench, a native Kubernetes experimental platform to enable extensible and reproducible evaluation of autoscaling solutions. Unlike existing approaches, ScaleBench integrates autoscalers as native Kubernetes components, allowing researchers to assess not only scaling performance but also deployment characteristics and integration requirements within realistic cloud-native environments. We demonstrate the effectiveness of ScaleBench by evaluating multiple autoscaling approaches through a case study. The results highlight its capability to support systematic, repeatable, and practical assessment of Kubernetes autoscaling approaches.

0.23

Holistic Buoyancy-Driven Cloud Native Resource Management

cs.DC ·2026-10-19 ·Oliver Larsson, Thijs Metsch, Cristian Klein, Erik Elmroth
similarity 0.57
Abstract · 12 pages, 8 figures, 3 tables

Efficient resource management is a challenge in multi-tenant cloud environments as workloads compete for shared resources such as last-level cache and memory bandwidth, whose congestion can change dynamically as workload composition and resource demands evolve. Existing resource management approaches often rely on static resource requirements or prior workload profiling, limiting their ability to respond to changing resource contention as required in the cloud. In this paper, we leverage workload buoyancy, a runtime framework for capturing workload sensitivity to individual resources and application-level performance, to enable adaptive scheduling and resource management. We propose a holistic approach that incorporates buoyancy into workload scheduling, node-local resource allocation, and workload rescheduling throughout the workload lifecycle. We implement our approach as a Kubernetes-native prototype and evaluate it on a multi-node cluster using diverse cloud workloads under varying levels of resource contention. In a high-congestion scenario, our approach increases the percentage of workloads satisfying their SLOs from 7.74% to 87.8% on average compared with the Kubernetes baseline, while reducing resource congestion, the severity of SLO violations, and cluster fragmentation using limited rescheduling.

0.23

LLM-Based Multi-Agent Collaboration for Constrained Multi-Objective Container Placement

cs.DC cs.MA ·2026-10-04 ·Suvarthi Sarkar, Abhishek Hazra, Akshat Mittal, Aryabartta Sahu
published similarity 0.57
Abstract · Accepted in IEEE Cloud 2026

Container placement in data centers must simultaneously minimize power consumption and maximize affinity preferences, while satisfying multi-resource capacity and anti-affinity constraints. Traditional approaches typically rely on fixed rules, which lack adaptability to dynamic cluster states and are difficult to extend for adaptive decision-making. On the other hand, meta-heuristic methods, although more flexible, are often computationally expensive, slower and prone to getting trapped in local optima. In this work, we propose an adaptive and efficient approach based on an LLM-driven multi-agent collaboration framework, where four specialized agents operate in a closed-loop ReAct cycle at each placement step. A Power Consumption Agent and an Affinity Agent debate over competing objectives, while a Placement Agent resolves conflicts using Tolerance-Gated Arbitration (TGA). A Rearrangement Agent further refines decisions through the Monotone Improvement Rule (MIR) in a post-placement refinement phase. All the agents reason over deterministic, feasibility-filtered candidate tables provided by the environment, ensuring that every proposed action inherently satisfies hard constraints. Based on experimental evaluation using the Google Cluster Trace with a configuration of 100 applications and 25 machines, the proposed framework consumes 8.36% less power and achieves 39.30% higher affinity than the power-greedy baseline. Ablation studies confirm that each architectural component, the multi-round debate mechanism, the TGA in the Placement Agent, and the MIR in the Rearrangement Agent, contributes meaningfully to the overall performance, with removal of any single component degrading both power consumption and affinity satisfaction.

0.43

Busy Time Minimization with Preemption, Migration, and One Resource Requirement

cs.DS ·2026-09-19 ·Gruia Calinescu, Mozhengfu Liu
similarity 0.57
Abstract

We study the Busy Machine Time with Preemption and Migration and One Resource Requirement problem, motivated by energy minimization in cloud data centers. Given unlimited identical-capacity machines and jobs with release times, deadlines, processing times, and resource requirements, we allow free preemption and migration at integer times and seek to minimize total machine busy time. The problem is NP-hard, and previous results consist of a 2-approximation, 2-competitive algorithm for the case of uniform heights. We obtain a 22/9 < 2.445-approximation algorithm and a 2.5-competitive online algorithm, both running in O(n^2 log n) time. Our methods are based on new non-asymptotic performance bounds for the First Fit Decreasing algorithm for Bin Packing, and a new generalization of Span Minimization, the Huge-Tiny Busy Time problem, for which we present an exact offline algorithm and an optimal (3/2)-competitive deterministic online algorithm.

0.10

Optimal Energy and LLM Task Scheduling for Multiple Cloud Data Centers

eess.SY ·2026-11-17 ·Zhongqi Zhao, Lei Fan, Zhu Han
similarity 0.56
Abstract

This paper studies coordinated Large Language Model (LLM) training-task scheduling and facility operation for geographically distributed cloud data centers (CDCs). The central question is how two scheduling flexibilities - cross-CDC task transfer and task reordering - affect service and economic outcomes when remote execution remains subject to compute, bandwidth, energy, and zone-temperature constraints. We formulate a mixed-integer optimization model that jointly determines task outcomes, heterogeneous-node assignment, execution timing, pre-execution data transfer, node activation, and facility operation. A deterministic 24-hour case study contains 3 CDCs, 15 heterogeneous graphics processing unit (GPU) nodes, 4 thermal zones per CDC, and 103 tasks. In this instance, enabling transfer increases net profit by 57.9% relative to the otherwise matched no-transfer variant and increases completed tasks from 76 to 103. The more restrictive no-transfer FIFO-prefix variant completes 14 tasks and yields negative profit. The proposed schedule transfers 39 tasks, achieves 70.3% node utilization, and maintains zone temperatures within 24°C-27°C. These fixed-instance results indicate that cross-CDC transfer and task-reordering flexibility can improve the modeled profit and task-completion outcomes under the studied conditions.

0.31