CS Paper Radar

ASCEND: Automated Shockproof Cost-Efficient Network Design

Taha ValizadehAslani, Vaibhav Phatarpekar, Cameron Brackmann, Bala Ramachandran

cs.NI ·submitted 2026-11-16 19:38 UTC · v1

Abstract

Designing resilient and cost-effective IP network topologies over an existing physical infrastructure is a challenging combinatorial optimization problem, particularly at large scale and under extensive failure modeling assumptions. Traditional deterministic approaches struggle to jointly address resiliency against shock (large customer-impact outages) and implementation cost objectives when the number of candidate circuits grows quadratically with the number of sites to be interconnected. In this paper, we propose Automated Shockproof Cost-Efficient Network Design (ASCEND), a systematic design pipeline for IP core network optimization based on a two-level optimization framework. At the outer level, ASCEND uses Multi-Objective Particle Swarm Optimization (MOPSO) to select core sites and core circuits. Given a core design, the inner-level integral Multi-Commodity Flow (MCF) formulation selects edge circuits and maps both core and edge circuits onto optical (fiber/transport) paths while prioritizing resource disjointness and latency. Network designs are evaluated using two competing objectives: a performance cost capturing resiliency under probabilistic failure scenarios and an implementation cost. The performance cost incorporates an exponentially weighted vulnerability metric that explicitly penalizes infeasible configurations. Experimental results on multiple real-world networks demonstrate that ASCEND consistently identifies designs that outperform a manually engineered baseline in both resiliency and implementation cost.

Comment
Submitted to IEEE Transactions on Network and Service Management

Closest papers

Nearest neighbours by meaning across the whole index.

Sparse Distributed Fiber Optic Sensor Placement in Metropolitan and Datacenter Elastic Optical Networks

cs.NI ·2026-10-02 ·Sleman Mouammar, Ítalo B. Brasileiro, André Drummond
similarity 0.57
Abstract

Distributed Fiber Optical Sensing (DFOS) leverages optical backscattering signals to predict failure events and enable proactive Just-In-Time (JIT) restoration. Modern network infrastructures have optical components and fibers as key enablers of high throughput and low latency. The integration of sensing features in this optical infrastructure adds features such as network diagnosis, spatial positioning and sensing, and opens up opportunities for the implementation of intelligent network control expected for the next-generation networks. In this paper, we study how the quantity and the placement of the DFOS devices in an all-optical network can mitigate failure events. In our evaluation, we consider metropolitan and data center elastic optical networks. This work also evaluates sensing devices with various prediction time capabilities, in order to assess their effectiveness when considering a variable number of deployed devices and different placement heuristics. The evaluation uses key performance metrics, including the bandwidth blocking rate, number of affected circuits by failure events, and the service downtime. Simulation results demonstrate that the Greedy Shortest Path Coverage (GSPC) heuristic substantially reduces the number of circuits affected by failure when DFOS devices cover only 5% of links, while 25% coverage shows a performance gain comparable to the full coverage scenario, which is an opportunity for significant cost reduction. Finally, for the 5% sensing coverage scenarios, our results illustrate that prediction windows of 15 ms and 7.5 ms are sufficient for JIT restoration in metropolitan and data center networks, respectively.

0.26

LASH-PAT: Deadlock-Free Adaptive Shortest-Path Routing for Inter-Chiplet Interconnects

cs.AR cs.NI ·2026-11-17 ·Patrick Iff, Torsten Hoefler
similarity 0.57
Abstract

With the slowdown of transistor scaling, chipletbased systems, and in particular chiplet-based wafer-scale integration, have emerged as a promising approach to sustain growth in computing capability per cost for modern processors and accelerators. In recent years, many specialized inter-chiplet interconnect topologies have been proposed. In these topologies, the simple, well-established, and deadlock-free dimension-order routing scheme is not applicable due to its reliance on regular mesh structures. In this work, we study routing in these recently proposed inter-chiplet interconnect topologies by categorizing and evaluating nine deadlock-free routing functions for irregular topologies known from data center networking in this new context. This reveals a trade-off between turn-based routing, which enables path diversity, and layered routing, which ensures shortest-path delivery. To resolve this trade-off, we propose LASH-PAT, a routing function that extends layered shortestpath routing with adaptive path diversity. LASH-PAT supports multiple shortest paths and dynamically selects among them based on local congestion while preserving deadlock freedom. When compared to the best-performing baseline routing function for each combination of topology, traffic pattern, and evaluated metric, LASH-PAT improves throughput by 21.15% and reduces energy per packet by 12.77%, while providing latency comparable to the lowest-latency baseline routing function.

0.21

A Global Routing Method for Electronic Circuit Design Integrating Flow Matching and Constrained A*

eess.SY ·2026-11-01 ·Sanghoon Jin, Sumin Lee, Namwoo Kang
similarity 0.55
Abstract

Global routing is a fundamental issue in the design of electronic circuits, as it directly relates to the efficiency, reliability, and compactness of the overall layout of integrated systems. As the demand for higher functionality and reliability within a limited chip area increases, the importance of routing as a design consideration has never been greater. Efficient global routing optimization techniques are therefore required to connect all pins with minimal wirelength (WL), while avoiding congestion and interference across multiple nets within the design space. As the number of nets to be routed increases, global routing inherently suffers from a combinatorial explosion in the design space, making it increasingly difficult to obtain feasible solutions. In this paper, we focus on solving constrained global routing problems based on a heuristic A*-based framework. Based on this concept, a hybrid approach is proposed by integrating constrained A* with flow matching (FM). The method utilizes FM to construct a global cost map that captures routing tendencies across the design space, which is then used to guide the constrained A* search process. This enables efficient exploration of the solution space while satisfying routing constraints. Experimental results demonstrate that the proposed method achieves comparable WL and via usage to baseline methods while maintaining constraint satisfaction across a wide range of scenarios. Notably, the framework shows strong capability in solving complex routing instances that are difficult to handle using conventional approaches. Additionally, the method shows robust generalization performance across different problem sizes and net configurations.

0.27

TANGCO: Learning Topology-Aware Capacity Allocation for Overload-driven Cascading Failures

cs.LG cs.SI ·2026-08-13 ·Orkun Irsoy, Leman Akoglu, Osman Yagan
similarity 0.53
Abstract

Networked systems, from power grids to traffic networks and cloud clusters, carry loads across nodes with limited capacity. A node whose load exceeds its capacity fails and sheds its load onto its neighbors, which can trigger a system-wide cascade. We study how to allocate a fixed capacity budget across nodes to resist these cascades under local load redistribution. The problem is difficult because no optimal allocation is known, and the fail-or-survive objective is non-differentiable and piecewise constant, so exact and gradient-based optimization methods do not directly apply. We introduce TANGCO (Topology-Aware Neural Graph-Guided Capacity Optimization), which uses a graph neural network policy trained through the cascade simulator with policy-gradient learning and a heuristic anchor. We evaluate TANGCO on five synthetic graph families and five real networks spanning power, road, air, and Internet topologies. The learned policy improves on the best of four hand-designed heuristics in all 450 synthetic instances and in 40 of 45 real-network conditions, with robustness gains ranging from 1.6% to 246%. The learned policies transfer to unseen graphs within a family and partially across related topologies, and TANGCO$^{pre}$, pre-trained on synthetic graphs, matches per-network training on unseen real networks. Training scales near-linearly with graph size, and TANGCO$^{pre}$ allocates on a new network with no per-target training, matching the deployment cost of a hand-designed heuristic. Free-vector variants without the GNN, stay close to the heuristics, so the graph representation carries the gain beyond numerical search. Finally, analysis of the learned allocations identifies when local risk is sufficient, leads to an improved closed-form heuristic, and reveals the regimes where a topology-aware learned policy remains necessary.

0.04

Approximation Algorithms for Multi-Criteria Network Design Problems

cs.DS ·2026-11-03 ·Mehrshad Taziki, Ali Vakilian
theoryhot direction similarity 0.53
Abstract

Min-max multi-criteria optimization asks for a single feasible solution minimizing the maximum of its costs under $\ell$ nonnegative cost functions, a formulation that captures both fairness across groups and robustness across scenarios. It has proved hard to approximate even for basic problems: for robust shortest paths, polylogarithmic approximations are known only in quasi-polynomial time. For network design, the best known guarantee is an $\ell$-approximation, which is tight for the natural LP relaxation. We show that exponentially better and nearly optimal guarantees are achievable for two fundamental network design problems. For multi-criteria connectivity augmentation (MC-CAP), which asks to increase the edge connectivity of a given undirected graph by one, we give a randomized polynomial-time $O(\log \ell)$-approximation algorithm. Applying our augmentation procedure iteratively and analyzing its randomized choices jointly across iterations yields an $O(\log k \log \ell)$-approximation for the multi-criteria $k$-edge-connected spanning subgraph (MC-$k$-ECSS) problem, for every $k \geq 2$. We complement these algorithms with a nearly matching lower bound: for every fixed $\varepsilon > 0$, MC-CAP admits no polynomial-time $O(\log^{1-\varepsilon} \ell)$-approximation, even when the underlying graph is a star, unless $\mathsf{NP}\subseteq\mathsf{DTIME}\bigl(n^{\log^{O(1)}n}\bigr)$. The same hardness extends to the MC-$k$-ECSS problem.

0.27

Budget-Constrained Graph Augmentation for Robust Network Design via Kirchhoff Index Minimization

cs.SI math.OCeess.SP ·2026-09-24 ·Omkar Bhoite, V Sateeshkrishna Dhuli, Stefan Werner, Kimmo Kansanen
benchmarktheory similarity 0.53
Abstract · 12 pages, 7 figures, 3 tables. Submitted to IEEE Transactions on Network Science and Engineering. A preliminary version of this work was pre…

Enhancing the robustness of deployed networks against failures and disruptions is critical for reliable operation. This requires deciding which new links to install and how strongly to weight them under limited resources. We study this problem through the Kirchhoff index, or total effective resistance, a spectral measure of global connectivity. The resulting augmentation problem couples discrete candidate-edge selection with continuous weight allocation under heterogeneous per-unit deployment costs, a total budget, and an exact-cardinality constraint. For a fixed weighted base graph, this yields a mixed-integer formulation and a semidefinite relaxation whose optimum lower-bounds the mixed-integer optimum. We cast the relaxation as a cone program and solve it numerically using a homogeneous self-dual embedding and first-order operator splitting. Feasible discrete designs are recovered through rounding-and-repair procedures and assessed by \emph{a posteriori} gap estimates relative to the numerical semidefinite program (SDP) benchmark. As a scalable alternative, we develop an exact-$k$, budget-feasible greedy heuristic built on rank-one Laplacian updates and biharmonic-distance caching, and interpret its progress through a Bellman value-to-go benchmark with a conservative spectral lower bound on the local policy ratio. Experiments on synthetic and real infrastructure networks across graph sizes, budgets, weight distributions, and cost regimes show that, under fixed budgets, distance-proportional costs limit the achievable resistance reduction and shift installed conductance toward shorter links relative to uniform per-unit costs.

0.21

Constant-Factor Approximation for Non-Splitting Coflow Scheduling in Heterogeneous Parallel Networks via Iterative Relaxation

cs.DS ·2026-10-29 ·Chi-Yeh Chen
similarity 0.52
Abstract

Coflows capture the collective communication requirements of data-parallel applications, and scheduling them well is essential to the performance of modern data centers. We study non-splitting coflow scheduling in a heterogeneous parallel network whose $m$ network cores may be Electronic Packet Switches (EPS), not-all-stop Optical Circuit Switches (OCS), or all-stop OCS, where every flow must be transmitted entirely through a single core. Previous approximation algorithms for this setting have guarantees that grow linearly with the number of cores $m$ or with the maximum flow degree $τ$ of a port, and therefore become weak as data centers deploy more cores. The source of this dependence is the rounding step: rounding each flow to the core holding its largest fractional value can inflate the load of a port by a factor of $m$. We replace this step with an iterative relaxation rounding scheme that handles the input-port and output-port capacity constraints simultaneously. For minimizing the makespan, this yields approximation ratios of $\min\{τ, 3\}$, $2\min\{τ, 3\}$, and $4\min\{τ, 3\}$ for pure EPS, pure not-all-stop OCS, and pure all-stop OCS networks, respectively. For minimizing the total weighted coflow completion time, we obtain approximation ratios of $8\min\{τ, 4\}$, $16\min\{τ, 4\}$, and $32\min\{τ, 4\}$ for the same three architectures. In a hybrid network, the guarantee is governed by the weakest architecture present, so the overall ratios are at most $4\min\{τ,3\}\le 12$ and $32\min\{τ,4\}\le 128$, respectively. Unlike all previous guarantees for non-splitting coflow scheduling in heterogeneous parallel networks, these bounds are absolute constants that do not grow with the number of cores $m$ or with the flow degree $τ$. We also show that the integrality gap of the underlying linear program is at least $2$.

0.29

A Matched Evaluation of QUBO Action Models and Defensive Remediation in Cyber Attack Graphs

cs.CR ·2026-11-01 ·Kasymkhan Khubiev, Yaroslav Kholodov, Alexey S. Petrenko
similarity 0.52
Abstract · 20 pages, 3 figures

This study examines how vulnerability-specific actions affect quadratic unconstrained binary optimization (QUBO) models for minimum-cost cyber attack paths and defensive remediation. Edge-flow and variable-length hop formulations are evaluated using simulated annealing, steepest descent, and tabu search against exact classical references. Experiments on six independent synthetic topologies separate the effects of transition eligibility, vulnerability labels, exploit costs, and multiple exploit alternatives. A single labeled action per eligible transition preserves feasible paths, optimal costs, and QUBO size. Under the tested settings, multiple exploit alternatives were associated with approximately unchanged valid-path recovery, lower optimal-path recovery, and substantially larger representations, particularly for the hop formulation. These recovery differences remain descriptive because they are not statistically significant after correction for multiple comparisons. An evaluation on a published 3CX attack graph with synthetic costs demonstrates applicability beyond the generated topologies. The defensive extension selects patches within a budget to raise attack-path costs to specified thresholds or disconnect protected targets. Against exhaustive and mixed-integer references, the tested QUBO heuristics recovered an optimal patch set in 12 of 16 calls across eight scenarios on one topology. The results characterize formulation correctness, solution recovery, and resource requirements using classical local optimization, without establishing quantum computational advantage.

0.29