Many state-of-the-art Segment Routing (SR) Traffic Engineering (TE) algorithms rely on Linear Program (LP)-based optimization. However, the poor scalability of the latter and the resulting high computation times impose severe restrictions on the practical usability of such approaches for many use cases. A promising way to address these issues is to preemptively limit the number of SR paths considered during optimization by employing certain preprocessing strategies. In the first part of this paper, we conduct an extensive literature review of such preprocessing approaches together with a large-scale comparative performance study on a plethora of real-world topologies, including recent data from a Tier-1 Internet Service Provider (ISP). In the second part, we then use the insights gained from the former study to develop a novel combined preprocessing approach which also guarantees to not interfere with the satisfiability of practically important latency bound constraints. Our approach is able to reduce the number of SR paths to consider during optimization by as much as 97%–99%, while still allowing to achieve close to optimal solutions. This facilitates an around 10 × speedup for different LP-based SR TE algorithms, which is more than twice as good as what is achievable with any of the previously existing methods. Finally, we also study the applicability of the path preprocessing paradigm to the use case of tactical TE, showing that it facilitates an around 37% speedup in this context as well. All in all, this constitutes a major improvement over the current state-of-the-art and further facilitates the reliable use of LP-based TE optimization for large segment-routed networks.

Recent advancements in the context of Segment Routing (SR) have shown that the Midpoint Optimization (MO) concept enables a substantial reduction in the number of SR policies required to implement Traffic Engineering (TE) configurations. In this paper, we demonstrate that this concept can also be applied to the use case of tactical TE to considerably reduce the number of network changes required to react to critical events, thereby facilitating lower provisioning times and a generally improved time-to-repair. For this, we develop MOLS, a Local Search-based optimization routine that is able to provide close to optimal solutions within just a couple of seconds. The latter is shown based on extensive evaluations featuring various real-world topologies, including data from the backbone of a Tier-1 Internet Service Provider. Compared to state-of-the-art approaches relying on conventional SR, MOLS achieves similar or better solution quality while requiring substantially fewer configuration changes to implement the respective solutions. Furthermore, MOLS is able to resolve over 99% of overutilization scenarios resulting from different failure types, mostly within sub-second fashion and with an exceptionally small number of changes. Lastly, we also extend MOLS to adhere to specified latency bounds while even fixing initially violated ones.

Increasing the robustness of networks against failures or traffic changes is an important objective for many operators. Instead of only adapting network configurations to the new conditions in a reactive fashion after a critical event has already occurred, proactively hedging networks against those events has gained increasing popularity over the recent years. A variety of approaches have been proposed that implement this concept of proactive robustness using Segment Routing (SR). However, all of those focus solely on the use of conventional end-to-end SR. In this paper, we show that this can be a limiting factor regarding the achievable level of robustness and that utilizing the Midpoint Optimization concept for SR, instead, facilitates (sometimes considerably) more robust durable Traffic Engineering configurations. Furthermore, it also allows to reduce the number of SR policies required to implement the respective configurations. This is not only discussed from a theoretical perspective but also confirmed by evaluations on real-world data from the backbone network of a Tier-1 Internet Service Provider.

A recent innovation in the context of Segment Routing (SR) Traffic Engineering (TE) is the use of the Midpoint Optimization (MO) concept to substantially reduce the number of SR policies required to implement TE solutions. However, these benefits come at the price of a potential deterioration of traffic steering capabilities as the individual, per-demand traffic control of end-to-end (E2E) SR is lost. In this paper, we show that a hybrid SR approach utilizing both MO as well as E2E SR allows to combine the individual benefits of both approaches. It results in improved TE capabilities and, thus, enables better TE solutions. Besides discussing this with theoretical examples, we also confirm our findings in an extensive evaluation on real-world network topologies. For this, we propose a TE algorithm based on the hybrid SR approach and show that it outperforms state-of-the-art algorithms that rely solely on MO or E2E SR. Furthermore, we demonstrate that the hybrid SR approach is also suitable for the use-case of time-constrained, tactical TE.

Improving the energy efficiency of Internet Service Provider (ISP) backbone networks is an important objective for ISP operators. In these networks, the overall traffic load throughout the day can vary drastically, resulting in many backbone networks being highly overprovisioned during periods of lower traffic volume. This paper proposes a new Segment Routing (SR)-based traffic engineering algorithm to reduce power consumption of a backbone network in times of low utilization. The traffic steering capabilities of Segment Routing are utilized to remove traffic from as many links as possible. This is used to turn off the corresponding hardware components. Furthermore, it simultaneously ensures that solutions comply to additional operator requirements regarding the overall Maximum Link Utilization in the network. Based on data from a Tier-l ISP and a public available dataset, we show that our approach allows for up to 70 % of the overall linecards to be switched off, corresponding to an around 56 % reduction of the overall energy consumption of the network in times of low traffic demands.

In this paper, we discuss the concept of Midpoint Optimization (MO) for Segment Routing (SR). It is based on the idea of integrating SR policies into the Interior Gateway Protocol (IGP) to allow various demands to be steered into them. We discuss the benefits of this approach when compared to end-to-end SR and potential challenges that might arise in deployment. We further develop an LP-based optimization algorithm to assess the Traffic Engineering capabilities of MO for SR. Based on traffic and topology data from a Tier-1 Internet Service Provider as well as other, publicly available data, we show that this algorithm is able to achieve virtually optimal results with regards to the maximum link utilization, that are on par with state-of-the-art end-to-end SR approaches. However, our MO approach requires substantially less policies to do so. For some instances the achieved reduction ranges up to more than 99%.

The growing demand in broadband and data networks is a tremendous driver for innovation and investment. Efficient usage of resources and reliable operations are key objectives for network management. Optimization plays a pivotal role to make the best decisions in limited time. To tackle such difficult and elaborate (typically NP-hard) computational problems the latest developments in Quantum Computing are coming into focus. Successes with models for road traffic, logistics or financial industry have already demonstrated the applicability of these new methods to real-world problems. In this paper we formulate a model for resource assignment for transporting data over networks. For applicability in existing network management environments the model was designed on top of Segment Routing (SR) concepts. The validity of the model is proven for different cost and reliability targets. Based on a Digital Annealer (DA) as quantum-inspired hardware and an appropriate decomposition approach realistic data sets of a tier-1 provider can be processed. The quality of the results is comparable to classical optimization methods while the new approaches outperform those in computation time and have potential for a higher number of demands. An end-to-end comparison of quadratic model creation and solving on large data sets versus a processing as linear integer problem is presented. This shows that quantum approaches and algorithms are not only a preparation for a more distant future of fully functional quantum computers but can generate business advantages even today.

Over the recent years, Segment Routing (SR)-based Traffic Engineering (TE) received more and more attention in the research community. However, what has been mostly neglected so far is its capability to configure looping forwarding paths that visit nodes or even edges multiple times. In this paper, we show that, against intuition, the configuration of such loops can inherit (in some occasions significant) benefits with regards to common TE objectives if Equal Cost Multipath (ECMP) is used. This is not only illustrated on small theoretical examples but also confirmed for 2SR with real-world data from the backbone network of a Tier-1 Internet Service Provider, as well as other publicly available topologies.

Traffic engineering is an important concept that allows Internet Service Providers (ISPs) to utilize their existing routing hardware more efficiently. One technology that can be used is Segment Routing (SR). In this paper, we address the use of SR to increase the resilience against failure scenarios. In addition, we develop solutions that are manageable and, thus, deployable in a tier 1 ISP network. We propose a post-convergence aware SR based optimization model. With it, we can proactively find a single SR configuration that is beneficial in all predefined failure scenarios, including single link failures, shared risk link group failures, and node failures. In addition to this use-case, we also extend the optimization model to include other important practical requirements such as keeping the number of SR tunnels to a minimum, avoiding arbitrary traffic splitting, or meeting latency bounds. We evaluate our approaches with recently measured data from a tier 1 ISP and show that we can improve over state of the art routing approaches.

Traffic engineering is an important concept that allows Internet Service Providers (ISPs) to utilize their existing routing hardware more efficiently. One technology that can be used in this field is Segment Routing (SR). While transferring SR approaches from theory towards an actual deployment, it quickly becomes apparent that there are many requirements and constraints that have to be satisfied. One of the most important requirement for a traffic engineering approach is the resilience against failure scenarios. In this paper, we propose a post-convergence aware 2-SR based optimization model. With it, we are able to proactively find a single SR configuration that is beneficial in all predefined failure scenarios, including single link failures, shared risk link group failures, and node failures. We evaluate our model with recently measured data from a tier 1 ISP and show that we can improve over state of the art routing approaches.

Segment Routing (SR) based traffic engineering can be used to avoid network congestion effectively. Most research about SR considers the routing metric as a given constant. The metric defines shortest paths. As shortest paths are essential building blocks of SR paths, the metrics heavily influence SR. In this paper, we evaluate this influence thoroughly using data from a tier one Internet Service Provider (ISP) backbone, as well as other, publicly available topologies. We conclude that metrics do in fact play a role in SR optimization. Simple metrics, however, already push SR close to the optimum with respect to the most common traffic engineering objective of minimizing maximum utilization.

Segment Routing (SR) can be used as a traffic engineering strategy to counteract increasing loads on networks like Internet Service Provider (ISP) backbones. Many SR approaches, however, optimize traffic flows that were measured in the past. This paper introduces a new tunnel training architecture. It aims to show that the results of these strategies can still be beneficial for routing new traffic flows using the tunnel training architecture. We evaluate the selection of different matrices for training, as well as the choice of different tunnel selection heuristics. The results show that optimization results tend to be beneficial even for traffic matrices that were not known during the optimization. Classifying the quality of SR tunnels, though, proves to be difficult and trace dependent.