network infrastructure engineers

Abstract: Service orchestration across the edge--cloud continuum increasingly uses language models (LMs) to translate intents and operational evidence into scheduling, configuration, diagnosis, and remediation decisions. Yet, useful model outputs do not by themselves establish dependable orchestration: reliability also depends on where the LM enters the decision process, what authority it is granted, how actions are constrained, and what system-level evidence supports the claimed effect. Existing surveys provide limited synthesis of the links between continuum-specific orchestration decisions, LM responsibility, operational authority, assurance controls, and supporting empirical evidence. We systematically review 39 primary studies and develop a five-dimensional analytical framework for connecting system context, orchestration decisions, LM agency, operational safeguards, and evaluation evidence. The synthesis reveals predominantly hybrid designs in which LMs support interpretation, candidate generation, and mitigation planning, while downstream components commonly retain feasibility enforcement and execution authority. Bounded closed-loop remediation is emerging, but continuum-specific constraints remain unevenly represented in decision formulations, and production-scale evidence across heterogeneous edge--cloud environments remains limited. These findings suggest that reliance on LM-enabled orchestration depends on aligning decision constraints, operational authority, safeguards, and evaluation evidence with the claimed system effect.

Abstract: We consider the problem of maintaining the triconnectivity in some biconnected graph G in the incremental dynamic setting. We consider updates in the form of edge insertions and edge subdivisions, and triconnectivity queries, i.e. queries of the form "are there at least three vertex disjoint paths between a and b?". All algorithms presented in this paper are deterministic. All queries and updates are answered in worst-case $O(\log n)$ time. By combining this result for biconnected graphs with a result of Holm and Rotenberg [SODA'20] we get an algorithm for general graphs with a worst-case running time of $O(\log^2 n)$ per operation. These algorithms represent an improvement of the state-of-the-art by a factor of $O(\log n)$.

Abstract: In this paper, we introduce WL-SeqVAE, a sequence-based variational autoencoder for generating graphs. The key observation behind WL-SeqVAE is that node colors induced by the Weisfeiler-Leman (WL) algorithm provide compact discrete summaries of local graph structure and can therefore serve as structural tokens for generation. Rather than learning a distribution over adjacency matrices directly, our method maps each graph to a sequence of WL colors and employs a variational autoencoder that encodes this sequence into a Gaussian latent distribution, from which an autoregressive decoder reconstructs the graph. During generation, compatibility constraints derived from the WL colors guide node and edge predictions, combining global information from the latent representation with local structural consistency. This formulation turns graph generation into a sequence generation problem and avoids directly parameterizing a quadratic adjacency matrix. We evaluate WL-SeqVAE on molecular and general graph generation tasks. Across the evaluated datasets, WL-SeqVAE is competitive with established baselines on several local structural and molecular quality metrics. Code is available at https://github.com/iakovosevdaimon/WL-SeqVAE

Abstract: Post-quantum key encapsulation mechanisms carry public keys far larger than the established VPN handshake protocol IKEv2 was designed for. At the same time, its initial exchange comprising the public keys cannot be fragmented. In response, the IETF discusses a range of protocol adjustments, yet these proposals have never been compared in terms of their performance and stability under identical conditions. We systematically screened the IETF document corpus for such proposals, added three of our own (one using forward error correction and two using IKEv2 with QUIC, namely QUIKE and QUIKE with a composite key exchange), identified two specification gaps in existing acknowledgment drafts, and implemented all eight on the same open-source codebase. Measurements across different bandwidths, latencies, and packet loss rates, and with ML-KEM, FrodoKEM, and Classic McEliece, total 126 500 handshakes in 1296 different configurations and show that no mechanism fully compensates for the effect of the key size on performance. For Classic McEliece, no approach handles challenging conditions acceptably. The approaches either congest the link or take up to nearly two minutes per handshake on average. For ML-KEM and FrodoKEM, there are two ways forward: building on already standardized extensions or delegating the transport. The former requires the larger implementation change and needs further optimization, such as acknowledgment mechanisms or error-correcting codes, but grants continuity and compatibility. The latter can use a composite key exchange to avoid these drawbacks and achieve a faster, more resilient handshake and leaner implementation, with QUIKE-composite offering the best overall performance.

Abstract: Ambient Internet of Things (A-IoT) devices operate under stringent energy constraints, relying on harvested power in the $μ$W-to-mW range and limited energy storage. The A-IoT air interface for active devices is still under development; we therefore use Narrowband Internet of Things (NB-IoT) as an implementable reference for evaluating autonomous Uplink (UL) access under harvested energy. Under these conditions, the standard NB-IoT contention-based Random Access (RA) procedure incurs substantial per-packet overhead, making UL access in dense A-IoT networks increasingly energy-expensive. Context-retaining UL access schemes reduce this overhead, but their energy-latency trade-offs are insufficiently studied in literature under realistic harvesting and protocol constraints. To address this gap, we extend the LENA-NB ns-3 module with solar energy harvesting, supercapacitor storage, and a hysteretic brown-out mechanism, and propose Hybrid Scheduling Request (HSR), a hybrid UL access scheme combining reserved request occasions with opportunistic contention. We compare RA, Scheduling Request (SR), HSR and an Idealized Fast Uplink Grant (FUG) serving as a performance bound. Results show that HSR reduces mean packet delay by up to 69% and SR reduces energy per delivered bit by up to 24%, both relative to RA.

Abstract: KV cache reuse is one of the most effective ways to reduce LLM inference cost, but today its benefits are largely confined to a single cluster. When a provider serves the same model across geographically distributed regions, each region may repeatedly prefill the same popular prefixes, wasting GPU time and increasing time-to-first-token (TTFT). Exploiting reuse across regions involves discovering which worker currently holds a reusable KV cache for each request's prefix. We show that this KV cache discovery problem is structurally harder than conventional object lookup. Unlike hash-placement mechanisms such as DHTs, where an object's location is a deterministic function of its key, KV caches are created on the workers that serve requests, and their holder sets change with subsequent requests and KV cache evictions. KV cache discovery therefore calls for decoupling KV cache identity from placement. We present KVCompass, a discovery plane for Internet-scale KV cache sharing. The discovery index supports variable-length prefix lookup with constant-time local table reads at the edge, allowing each request to be forwarded to the worker that best balances KV cache reuse against load and network distance. Evaluation includes a 64-worker geo-distributed simulation and a 14-worker three-continent real-machine testbed. Evaluation shows that KVCompass achieves $1.3-14\times$ lower P99 TTFT than the baselines, up to $3.7\times$ lower P99 end-to-end latency, up to $4.7\times$ the throughput, and a peak load factor within 2% of the Oracle floor.

Abstract: The Emergency Vertex Cover problem (Em-VC) assigns budgets to stations at graph vertices to cover every edge while minimizing the total budget. The cost of covering an edge from a station is the shortest-path distance from the station to the nearer endpoint plus the edge length. We study how restricting the number of stations affects the cost of ordinary and fault-tolerant coverage. In ordinary Em-VC, we prove that the optimal solution using at most two stations costs at most $5/4$ times the unrestricted optimum, improving the known $4/3$ guarantee for a single station. A recurrence extends this bound to larger station limits, giving approximation factors that converge to $\sqrt{5}-1$. Budget-threshold enumeration computes the restricted optimum in polynomial time for every fixed station limit. Under $k$-fold coverage, every edge must be covered by at least $k$ distinct stations, ensuring coverage after any $k-1$ station failures. We prove that selecting the $k$ vertices with the smallest full-coverage costs yields a $2$-approximation relative to the unrestricted optimum for $k$-fold coverage. When $k=2$, we combine upper bounds derived from the structure of the covering balls to improve the approximation guarantee to $5/3$.

Abstract: For Vertex Cover, a minimal blocking set of a graph $G$ is an inclusion-wise minimal vertex set contained in no minimum vertex cover of $G$. Bougeret et al. [SIDMA 2022] showed that, for all minor-closed graph classes $\mathcal{G}$, Vertex Cover has a polynomial kernel parameterized by the distance to $\mathcal{G}$ if and only if $\mathcal{G}$ has bounded minimal blocking sets. In this work, we explore how far this connection between minimal blocking sets and kernelization extends to $\mathcal{F}$-Minor Deletion parameterized by the deletion distance to $\mathcal{G}$. A minimal $\mathcal{F}$-blocking set of $G$ is a minimal vertex set not contained in any optimal $\mathcal{F}$-Minor Deletion solution of $G$. For connected families $\mathcal{F}$, we show that if some graph class $\mathcal{G}$ closed under disjoint union has unbounded minimal $\mathcal{F}$-blocking sets, then $\mathcal{F}$-Minor Deletion parameterized by the deletion distance to $\mathcal{G}$ has no polynomial kernel. This generalizes a result of Hols et al. [SIDMA 2022] for Vertex Cover. We then show that this criterion does not capture all kernelization lower bounds for $\mathcal{F}$-Minor Deletion, even for minor-closed graph classes. Motivated by the work of Dekker and Jansen [Discrete Appl. Math. 2024], we study the more general notion of extended $\mathcal{F}$-blocking sets and the kernelization lower bounds they yield. For every fixed integer $η\geq 1$, Pw-$η$ Deletion is the problem of deleting at most $k$ vertices to reduce the pathwidth to at most $η$. We show that it has no polynomial kernel parameterized by the distance to graphs with pathwidth at most $η+1$. Moreover, for connected families $\mathcal{F}$, we show that $\mathcal{F}$-Minor Deletion parameterized by the distance to graphs with pathwidth at most $\max_{F\in\mathcal{F}} pw(F)+1$ has no polynomial kernel.

Abstract: For a battery-powered UAV base station, every gram and watt devoted to RAN-compute competes with flight-duration margin. We therefore keep the 5G Core (5GC) and central unit (CU) on the ground and design the airborne unit around only the backhaul endpoint, distributed unit (DU), and radio. The key question is then a practical one: can widely available commodity ARM computers sustain a real radio OpenAirInterface (OAI) 5G DU with useful performance over heterogeneous F1? We answer it with Raspberry Pi~5 and Jetson Orin Nano as DUs, a USRP B210, a commercial handset, and Ethernet, Wi-Fi/GRE, and 5G/WireGuard backhaul. Jetson preserves 88.4% of x86 split-DU Ethernet DL throughput and 87.5-89.0% across all three bearers; 5G/WireGuard preserves 76.4-77.1% of each host's wired DL rate. The validated Jetson/B210/RM500Q-GL electronics weigh 657.4 g and draw about 28 W under sustained traffic (757.4 g with integration allowance). A controlled link adaptation intervention raises split DL from 23.4 to 99.4 Mb/s as the dominant Modulation and Coding Scheme (MCS) moves from 3 to 26. Finally, synchronized radio, F1-U, CPU, and UHD evidence narrows the remaining monolithic-split gap to split-path scheduling/timing behavior. Beyond performance, this capability serves the emergency-response use case that motivates the aerial cell: once deployed above an affected area, it can broadcast a PWS warning message. We release the OAI patch that carries the single-segment Write-Replace Warning over F1 from CU to DU, where SIB8 is scheduled to the handset. The public artifact makes the payload, performance, and emergency-broadcast baseline reproducible with laboratory-accessible hardware.

Abstract: The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weighted sum of the cut edges. Over the last years, we engineered a range of fast algorithms for this problem. Our fastest exact algorithm uses an inexact algorithm to obtain a better bound for the problem, reductions that depend on this bound, improved data structures and parallel contraction routines. It is available in the open-source package VieCut and, on real-world instances, outperformed the previously fastest solvers by a factor of up to 2.5 sequentially and up to 12.9 when run in parallel. We improve this algorithm using agentic algorithm engineering (AAE), a methodology that we introduce here, in which autonomous large language model agents run the algorithm engineering cycle on an existing code base: they form hypotheses about where running time is lost, implement them, benchmark the result on a fixed instance set and keep or discard the change. Even though we had already tuned our algorithm by hand extensively, the agent finds significant optimizations, in particular on the DIMACS core instances: factors of 1.28 (sequential) and 1.63 (32 threads) on real-world k-cores, and 6.26 and 127 on the DIMACS core instances.