ABSTRACT The purpose of this work is to develop an algorithmic optimization approach for a capacitated multi‐commodity flow problem, where the objective is to minimize the total link costs, where the cost of each arc increases convexly with its utilization. This objective is particularly relevant in telecommunication networks, where device performance can deteriorate significantly as the available bandwidth on a link becomes limited. By optimizing this convex function, traffic is efficiently distributed across the network, ensuring optimal use of available resources and preserving capacity for future demands. This paper describes the convex multi‐commodity flow problem and presents methodologies to solve both its Splittable and Unsplittable variants. In the Splittable version, flows can be fractionally distributed across multiple paths, while in the Unsplittable version, each commodity must be routed through a single path. Our approach employs Column‐Generation techniques to address the convexly increasing cost functions associated with arc utilization, effectively accommodating various forms of convex increasing cost functions, including non‐differentiable or black‐box convex increasing functions. The proposed methods demonstrate strong computational efficiency, offering a robust framework for managing network flows in complex telecommunication environments.

Solving the multi-commodity flow problem in large networks is the core of current telecommunication networks. Integer linear programming shows its ability to solve this problem efficiently in large networks by using decomposition techniques such as the Dantzig-Wolfe method to obtain a model based on path variables. Thanks to the sparsity of telecommunication networks, the path model can solve large-scale instances through a small mathematical model. This paper proposes a spatial decomposition derived from the Dantzig-Wolfe decomposition method. The goal is to split the network into several areas and treat each one independently. Column generation is used to find a routing consensus between areas. We show the gain in terms of linear relaxation and computational time using spatial decomposition on the well-known IPRAN network structure.

ABSTRACT In real‐life applications, most optimization problems are variants of well‐known combinatorial optimization problems, including additional constraints to fit with a particular use case. Usually, efficient algorithms to handle a restricted subset of these additional constraints already exist or can be easily derived, but combining them together is difficult. The goal of our paper is to provide a framework that allows merging several so‐called atomic algorithms to solve an optimization problem, including all associated additional constraints together. The core proposal, referred to as Atomic Column Generation (ACG) and derived from Dantzig–Wolfe decomposition, allows converging to an optimal global solution with any kind of atomic algorithms. We show that this decomposition improves the continuous relaxation and describe the associated Branch‐and‐Price algorithm. We consider a specific use case in telecommunication networks where several Path Computation Elements (PCE) are combined as atomic algorithms to route traffic. We demonstrate the efficiency of ACG on the resource‐constrained shortest path problem associated with each PCE and show that it remains competitive with benchmark algorithms.

Traffic Engineering (TE) represents one of the most essential tools in modern telecommunication networks. The rapid growth of exchanged traffic has required tackling a known NP-hard problem called the Multi-Commodity Flow problem (MCF). Many studies in the literature have already considered different variants of this problem. In this paper, we propose a new way to use a double Dantzig-Wolfe decomposition formulation to improve the quality of the linear relaxation. We apply our method on the classical multi-commodity flow problem where the throughput acceptance is first maximized and then the routing cost is minimized. We provide a computational experiment and conduct an in-depth analysis of the algorithm based on realistic instances.

In backbone networks, it is fundamental to quickly protect traffic against any unexpected event, such as failures or congestions, which may impact Quality of Service (QoS). Standard solutions based on Segment Routing (SR), such as Topology-Independent Loop-Free Alternate (TI-LFA), are used in practice to handle failures, but no distributed solutions exist for distributed and tactical congestion mitigation. A promising approach leveraging SR has been recently proposed to quickly steer traffic away from congested links over alternative paths. As the pre-computation of alternative paths plays a paramount role to efficiently mitigating congestions, we investigate the associated path computation problem aiming at maximizing the amount of traffic that can be rerouted as well as the resilience against any 1-link failure. In particular, we focus on two variants of this problem. First, we maximize the residual flow after all possible failures. We show that the problem is NP-Hard, and we solve it via a Benders decomposition algorithm. Then, to provide a practical and scalable solution, we solve a relaxed variant problem, that maximizes, instead of flow, the number of surviving alternative paths after all possible failures. We provide a polynomial algorithm. Through numerical experiments, we compare the two variants and show that they allow to increase the amount of rerouted traffic and the resiliency of the network after any 1-link failure.

Various routing protocols are deployed to operate networks, and border routers manage the exchange of routing information. Network engineers carefully configure routing policies to ensure reliable, efficient, and secure connectivity. However, the complexity of these configurations can lead to errors and issues like routing loops. Existing control plane verification solutions offer comprehensive analysis but struggle with scalability. This demonstration presents a scalable verification tool capable of locating routing loops in large multi-protocol and multi-instance networks, demonstrating its efficiency and performance with numerical results and live verification.

We propose a constraint programming (CP)–based branch-and-price-and-cut framework to exactly solve bipath multicommodity flow (MCF): an MCF problem with two paths for each demand. The goal is to route demands in a capacitated network under the minimum cost. The two paths must have disjoint arcs, and the delays accumulated along the two paths must be within a small deviation of each other. CP is used at multiple points in this framework: for solving pricing problems, for cut generation, and for primal and branching node heuristics. These modules use a CP solver designed for network routing problems and can be adapted to other combinatorial optimization problems. We also develop a novel, complete, two-level branching scheme. On a set of diverse bipath MCF instances, experimental results show that our algorithm significantly outperforms monolithic CP and mixed integer linear programming models and demonstrate the efficiency and flexibility brought by the tailored integration of linear programming and CP methodologies. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: This work was supported by the Natural Sciences and Engineering Research Council of Canada; Huawei Technologies. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0128 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0128 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

With the advent of big data applications, coflow scheduling has become a cornerstone for the engineering of traffic in datacenters. Minimizing the average weighted Coflow Completion Times (CCT) is a crucial step to minimize the execution time of jobs running in distributed computing frameworks. In this paper, we present a new$\sigma $-order coflow scheduling solution, ONE-PARIS, an online semi-clairvoyant and semi-distributed implementation suitable to minimize the weighted CCT in production environments. We achieves this through ONE-PARIS scheduler for ordering coflows and a decentralized resource allocation mechanism, called Sync-Rate, enabling to respect the order of priority of coflows provided by ONE-PARIS and ensuring efficient synchronization between flows of the same coflow in order to free up bandwidth for low-priority flows. Extensive simulations on both synthetic and real traffics show that our proposed coflow scheduler outperforms other state-of-art schemes.

Tactical Traffic Engineering (TE) solutions are a must to adapt traffic steering when unexpected congestions occur. While already available, centralized solutions to locally optimizes congested tunnels and links suffer from a slow reaction time of several minutes. To address this issue, we propose a distributed Congestion Mitigation (CM) mechanism that leverages Segment Routing (SR) to offload traffic away from congested links using Unequal Cost Multi Paths (UCMP) over alternative paths. In this paper, we introduce an efficient algorithm for alternative paths’ computation, and two methods to compute UCMP weights, depending on whether remote link loads are available or not. We show that the proposed path computation method is faster than a modified K-shortest path algorithm. For traffic splitting, we show that the knowledge of remote link loads and per-destination traffic is a key to mitigate congestions in loaded scenarios, approaching the results obtained with an optimal solution. However, when not available, a local solution can already mitigate congestions in lightly loaded scenarios.

Data routing in networks is required to be efficient and reliable. Fast detection and recovery from link or path failures play crucial roles in the reliability guarantee. In this work, we investigate a variant of the multi-commodity flow problem to address one formalization of reliability, where for each demand, a primary path transmits the demand without exceeding a jitter limit and an arc-disjoint secondary path signals the possible failure of the primary path. We first present a compact mixed-integer linear programming model and then we devise a Branch-and-Benders-Cut algorithm to solve this combinatorial optimization problem. On a diverse set of instances, we evaluate the algorithm's performance and discuss several numerical results.

Nowadays, centralized Path Computation Elements (PCE) integrate control plane algorithms to optimize routing and load-balancing continuously. When a link fails, the traffic load is automatically transferred to the remaining paths according to the configuration of load-balancers. In this context, we propose a load-balancing method that anticipates load transfers to ensure the protection of traffic against any Shared-Risk-Link-Group (SRLG) failure. The main objective of this approach is to make better use of bandwidth compared to existing methods. It consists in reserving a minimum amount of extra bandwidth on links so that the rerouting of traffic is guaranteed. We propose a non-linear non-convex model for the problem of minimizing the bandwidth reservation cost. We introduce a new approximation approach based on a neural network to convexify the problem and apply Kelley’s cutting plane method to solve the problem. Finally, we show that our algorithm significantly improves the CPU time against a compact model solved using the SCIP solver.

To improve bandwidth utilization in IP networks, flow aggregates are typically split over multiple paths. In this context, we propose a fully distributed load balancing mechanism that operates only from the edge. Each source is able to determine the split ratios based on already available link state information so as to minimize the maximum link utilization in the network. Without extra signaling, our solution provides a feasible load balancing at each iteration and diminishing returns until convergence to a stable state. Through numerical results on a wide variety of instances, we show that it converges to a near-optimal solution in a few iterations. Thanks to packet-level simulations on an SD-WAN scenario, we also compare its performance in a dynamic environment over centralized and legacy load balancing solutions.

In this paper we discuss a variant of the well-known k-separator problem. Given a simple graph G = (V ∪ T, E) with V ∪ T the set of vertices, where T is a set of distinguished vertices called terminals, and E a set of edges, the multi-terminal vertex separator problem consists in partitioning V ∪T into k+1 subsets {S, V1, ..., Vk} such that the size of S is minimum, each subset Vicontains exactly one terminal and no vertex in Viis adjacent to a vertex in Vj. Three extended formulations are proposed for the problem. We develop Branch-and-Price algorithms for the two first formulations and a Branch-and-Cut-and-Price algorithm for the third one. Some experimental results are also discussed.

Given G = (V;E) an undirected graph and a nonnegative cost function c : E → ℚ, the 2-edge connected spanning subgraph problem (TECSP for short) is to find a two-edge connected subgraph HP = (V; F) of G with minimum cost (i.e., c(F) = Σe∈Fc(e) is minimum). If c(e) > 0 for all e ∈ E then every optimal solution for TECSP is an inclusionwise minimal two-edge connected subgraph. In this paper we provide preliminary results, from a polyhedral point of view, concerning the inclusionwise minimal solutions of TECSP. This problem is clearly NP-Hard. We propose an ILP formulation for the problem and study the associated polytope for the wheels. Morever, we describe some valid inequalities and propose a branch-and-cut algorithm for the problem.