CS Paper Radar

Segment Routing Traffic Engineering with Time-Based Reconfiguration Constraints

Brigitte Jaumard, Nguyen Phuc Tran, Junior Momo Ziazet

cs.NI cs.PFeess.SY ·submitted 2026-10-03 20:54 UTC · v1
published

Abstract

Segment routing (SR) involves routing requests through shortest paths or a limited number of segments, which are themselves the shortest paths between their endpoints. While this flexibility makes segment routing attractive for traffic engineering (TE) in IP/MPLS networks, it becomes challenging to update when some links become unavailable (e.g., maintenance) and routing decisions must adapt while limiting the number of configuration changes between two consecutive periods. We address the problem of dynamically selecting SR-TE configurations for multiple traffic demands with the objective of minimizing the maximum link utilization (MLU). In addition, a reconfiguration budget is imposed in order to limit the number of segments modified. Based on this representation, we develop a MLU column-generation optimization framework. It allows to jointly consider traffic distribution, SR configuration complexity, and temporal reconfiguration costs in time-varying IP/MPLS networks. The numerical results are obtained using realistic datasets provided by Orange, with topologies containing up to 1,263 nodes and 15,000 traffic demands. The optimality gap (i.e., accuracy) is below 5% in 80.45% of the 133 instance-time evaluations.

Comment
Accepted for publication in the IEEE LATINCOM 2026 - IEEE Latin-American Conference on Communications 2026. This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible

Closest papers

Nearest neighbours by meaning across the whole index.

The Complexity of Traffic Engineering in Segment Routing Networks

cs.DS ·2026-11-13 ·Matthias Bentert, Stefan Schmid
theory similarity 0.65
Abstract

Segment routing is a modern variant of source routing which has recently become popular in the Internet. It allows operators to equip network packets with an additional header which specifies segments: a list of waypoints the packet needs to traverse on its way to the destination. This is reminiscent of Valiant routing in parallel computing and introduces an additional degree of freedom in traffic engineering. This flexibility can be exploited to minimize congestion in the network. This paper sheds light on the computational complexity of traffic engineering in segment routing networks. We consider two problem variants: a fixed-length variant where link weights are given and only waypoints can be chosen, and a variable-length variant where additionally the network operator can also choose the link weights, which then define the shortest paths taken between the waypoints. We prove that the first variant is NP-hard even if the network graph is planar and if all demands and link weights are 1. We also show that the second variant is NP-hard already for planar network graphs with all demands being 1. On the positive side, we present a compact and general mixed integer linear program to compute exact solutions for the first variant.

0.32

Strengthening Compact Vehicle Routing Formulations through Arc-Flow Aggregation and Refinement

cs.DM math.OC ·2026-11-15 ·Julian Yarkony, Willem-Jan van Hoeve, Anthony Karahalios, Martin Karyamsetty, Soheyl Khalilpourazari +2 more
similarity 0.58
Abstract · 47 pages. Submitted to Transportation Science

Arc-flow formulations can provide strong relaxations for mixed-integer program formulations of vehicle routing problems, but the associated networks may be prohibitively large. We study the setting in which multiple arc flow relaxations may be applied, and introduce a dual-guided aggregation and refinement framework that constructs substantially smaller arc-flow formulations while recovering the LP bound of the original networks. Dual information is used both to identify states that can be aggregated without weakening the bound and to guide node disaggregation. We show that the resulting procedure converges finitely to the arc-flow bound of the full arc-flow formulation. The framework retains the original decision variables, allowing cutting planes to be added directly in the original variable space. Moreover, it produces an explicit MILP formulation without relying on column generation or pricing to determine the arc-flow relaxation bound. We apply our approach to the vehicle routing problem with time windows for which we define two arc flow relaxations, as well as two families of cutting planes over the original variable space. Computational experiments show that strong bounds can be obtained using substantially aggregated networks. The resulting root bounds are competitive with those obtained by the branch-and-price solver RouteOpt, while retaining a formulation that can be solved directly by a general-purpose MILP solver.

0.30

DiffRouter: A Differentiable Routing Framework for UltraScale FPGAs

cs.AR ·2026-10-24 ·Xiaohan Gao, Zhili Xiong, Yusu Wang, David Z. Pan
published similarity 0.58
Abstract

Routing has become a major bottleneck in large-scale FPGA design flows, where traditional routers rely on sequential net-by-net processing and rip-up-reroute heuristics. This inherent sequentialism limits parallelism, leads to suboptimal utilization of routing resources, and significantly increases runtime on modern FPGAs. This paper introduces DiffRouter, the first differentiable, gradient-based FPGA routing framework with GPU acceleration. By lifting routing into a continuous optimization space, DiffRouter enables highly concurrent routing and improved global optimality before projecting solutions back onto the discrete fabric. The framework consists of three key stages: (1) Resource-pruned preprocessing, which extracts compact routing variables per net to reduce memory footprint and problem complexity; (2) Differentiable global routing via gradient descent, which formulates routing as a Lagrangian-relaxed optimization that minimizes wirelength while iteratively enforcing connectivity and congestion constraints as relaxed terms; and (3) Postprocessing, which maps the continuous wire distributions to a valid UltraScale routing solution and completes solutions by detailed routing. Experiments on the FPGA 2024 Routing Contest benchmarks show that DiffRouter outperforms state-of-the-art parallel routers, achieving over 5x speedup over RWRoute and 2x over Vivado, and running 18% faster than the state-of-the-art academic FPGA router Potter while delivering competitive critical path wirelength.

0.28

Stochastic Corridor Time Network Capacity Planning for Low Altitude Airspace Systems

cs.CE ·2026-08-11 ·Yipu Yao, Li Ding, Yanlu Zhao
similarity 0.57
Abstract

Regulators in China, the United States, and the European Union now provide low-altitude airspace access as priced, time-windowed corridor authorizations, booked in advance and forfeited if unused. We ask how much capacity a UAV logistics planner should reserve on each corridor--time unit before demand is realized, to maximize expected profit net of reservation cost. Reserved capacity cannot be transferred across corridors or time windows and is consumed jointly along time-respecting paths, so reservations are coupled through the network in ways that models with exogenous airspace capacity cannot capture. We formulate a two-stage stochastic program whose recourse selects and routes accepted requests on a time-expanded network, prove its arc-based and path-packing forms equivalent, and solve it by Benders decomposition with column-generated subproblems. The decomposition operates on the LP relaxation, and all reported reservation and routing decisions are recovered as integer plans. Computational experiments achieve single-digit LP-Benders gaps on moderate-sized networks and extend to much larger instances through a truncated-path approach. A Shenzhen case study shows reservations concentrating on structurally central corridors, with demand level and reservation price having more influence on the quantity of capacity reserved than the selection of corridors.

0.04

Scalable Full-Horizon SFC Deployment over Predictable SAGIN Topologies via Configurable Column Generation Framework

cs.NI ·2026-11-06 ·Hang Li, Hao Huang, Yihu Xu, Zixuan Kong, Yanling Jin
similarity 0.57
Abstract · 18 pages, 10 figures, 4 tables

Space-air-ground integrated networks (SAGINs) integrate heterogeneous communication and computing resources to support ubiquitous services. Service function chains (SFCs) enable complex services to be composed of ordered functions and executed collaboratively across these resources. Mobility continuously reshapes connectivity throughout service execution, yet much of the resulting topology evolution is predictable. Decisions based only on isolated topology snapshots may therefore overlook valuable future connectivity. We formulate an admission-first, cost-aware model on a time-expanded graph for SFC deployment. Our key observation is that temporal feasibility is request-specific, whereas global coupling arises mainly from shared-resource competition. We therefore develop a configurable column-generation framework in which complete request deployments form columns and a restricted master problem coordinates admission and resources. SAGINFE, a fast constructive heuristic built on per-flow embedding (PFE), supplies a standalone feasible solution and initial columns. Configurable pricing schedules combine early-terminated and stricter searches, supplemented by selective PFE candidates. Candidates undergo feasibility and exact reduced-cost checks. Request-wise pricing can run in parallel, followed by finite-pool integer selection. The default configuration improves the admission-first objective over initialization on all 120 main instances. Four pricing workers achieve up to a 2.69-fold median pricing-stage speedup while preserving admitted request counts in the tested cases.

0.20

EvoSignal: LLM-Guided Evolutionary Design of Modular Traffic Signal Control Programs

cs.LG ·2026-10-07 ·Leizhen Wang, Peibo Duan, Zhenlin Qin, Yancheng Ling, Jian Xu +3 more
code/data similarity 0.57
Abstract

Effective traffic signal control (TSC) requires policies that respond to changing traffic demand and network conditions while meeting different control objectives. However, adapting existing strategies often involves repeated manual design and adjustment, making it difficult to systematically explore better control rules for a target network. Large language models (LLMs) can automate this process, but directly using them to select signal phases leaves decision rules embedded in black-box models and incurs recurring inference costs and latency. This paper formulates TSC as a modular program design problem and proposes EvoSignal, an LLM-guided evolutionary framework using traffic knowledge and performance feedback. The modular representation separates traffic feature extraction, local phase prioritization, and optional network-based priority adjustment. Starting from several established strategies, EvoSignal improves programs through feedback on congestion and signal operation, retaining strategies with different performance trade-offs. The resulting programs operate without online LLM inference. Simulation experiments across five scenarios on two real-world road networks show that the selected default EvoSignal program reduces waiting time by 16.8--49.2\% relative to the lowest waiting time achieved by the 20 conventional, reinforcement learning-based, and LLM-based baselines in each scenario. A program prioritizing travel time and queue length outperforms all 20 baselines on all three metrics in the search scenario and remains among the top three on each metric when transferred unchanged to the other four scenarios. These findings support automated design of inspectable control programs that transfer across the evaluated road networks and traffic demands. Code is available at https://github.com/georgewanglz2019/EvoSignal.

0.32

Hierarchical Traffic Engineering for Scalable Software-Defined Satellite Networks

eess.SY ·2026-11-18 ·Mohamed Khiari, Wiem Abderrahim, Olfa Ben Yahia, Fatma Abdelkefi, Wessam Ajib +1 more
similarity 0.56
Abstract

Future satellite systems are shifting toward regenerative payloads that interconnect many modem banks into a reconfigurable on-board network. However, conventional constellation-level routing overlooks intra-payload congestion and load imbalance, which can limit the traffic each satellite can accommodate. This paper proposes a hierarchical software-defined networking (SDN)framework for traffic engineering (TE) across both the constellation and payload levels. The system is represented by a two-level graph, where each satellite node in the constellation graph is expanded into an internal network of interconnected modem banks. The proposed hierarchical payload-aware allocation (HPAA) algorithm coordinates the two levels through the exchange of assigned traffic demand and advertised capacity budgets. Simulation results show that, under heavy load, HPAA delivers about 9 times the throughput of shortest-path routing, with 17% lower end-to-end delay and no packet loss. These findings highlight that hierarchical control accounting for the on-board network constraints of regenerative payloads is a key lever to improve the performance of satellite constellations.

0.20

CARRS: A Constraint-Aware, Real-Time Routing System for Emergency Vehicles in Urban Environments

cs.AI ·2026-10-19 ·Vincent Sello, Timothy Adeliyi, Ridewaan Hanslo
similarity 0.56
Abstract · 10 pages, 3 figures, 3 tables

Emergency vehicles such as police vehicles, fire engines, and ambulances require a stable and efficient route optimization to reach life-critical events in the shortest times possible. However, the dynamic nature of urban traffic makes this ideal scenario much more challenging, causing critical life-threatening delays. Traditional civilian navigation systems cannot account for real-time traffic changes alongside vehicle-specific constraints, creating inadequate routing scenarios. This research presents the Constraint-Aware Real-Time Routing System (CARRS), a unified software architecture tailored for emergency coordination. The CARRS architecture is engineered to fuse together classical pathfinding algorithms such as A*, Dijkstra, and Bidirectional A*, with Constraint Satisfaction Problem methodologies. The Design Science Research Methodology is the research framework, and prototyping is the iterative process. The artifact was empirically evaluated using OpenStreetMap data for major metropolitan road networks, combined with simulated dynamic traffic scenarios. Performance metrics focused on route optimality, constraint adherence, rerouting responsiveness, and the potential for future system scalability. Findings revealed the system's capability to generate optimal routes for operationally relevant subgraphs in under 35 seconds, with incremental rerouting responsiveness below 20 seconds. Furthermore, the system achieved more than 90% adherence to vehicle-specific constraints, making the CARRS architecture viable for real-time dynamic routing requirements. This study delivers a routing platform that bridges artificial intelligence-driven optimization with software engineering operational compliance, presenting a practical transformative step toward adaptive emergency vehicle coordination in dynamic urban environments.

0.28