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.
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/ .
To improve bandwidth utilization, flow aggregates are typically split over multiple paths. This demonstration shows that load balancing can be enhanced by exploiting traffic predictions. We present a Model Predictive Control (MPC) based load balancing framework that optimizes the maximum link utilization to proactively mitigate congestion.