WorksComputer Science
The Complexity of Traffic Engineering in Segment Routing Networks
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.
Introduction
To make best use of their infrastructure and to provide good performance to their customers, Internet Service Providers (ISPs) employ traffic engineering (TE) to select paths for their communication traffic that minimize congestion. Segment routing (SR) has recently emerged as a powerful approach to perform TE, which received much attention in industry and standardization bodies (the IETF). Traditionally, packets are restricted to follow shortest paths which are indirectly defined by the link weights which can be set by network operators. In SR networks, there is an additional degree of freedom: packets can be equipped with a packet header defining a list of waypoints: nodes (essentially IPv6 addresses) which the packet needs to traverse on its way to the destination.1 Between each pair of waypoints as well as from the source to the first waypoint and from the last waypoint to the destination (called segments), a packet takes a shortest path, defined as usual, based on link weights. If there are multiple shortest paths, traffic is split across them on a per-flow granularity (to minimize packet reordering). Segment routing can hence be seen as a modern variant of source routing and is inspired by Valiant routing known in parallel computing [28]. Empirical studies show that such a redirection, already with a single waypoint, can significantly improve TE performance in practice [5, 29].
Segment routing networks introduce a novel graph-theoretical optimization problem: how to select waypoints in order to minimize congestion? This problem is interesting already in scenarios where link weights are given, and we will refer to this problem version as the fixed-length variant in the following (interpreting weights as distances). Here, we also consider settings which support splitting ratios [11]: scenarios where network operators can decide to assign different amounts of traffic to different shortest paths. The problem version where in addition to the waypoints, also the link weights can be chosen, is referred to as the variable-length variant.
This paper is concerned with these algorithmic problems underlying segment routing. Specifically, we investigate the case of a single waypoint per demand. Given the high interest of industry in the topic, surprisingly little is known today about the graph-theoretical challenges of traffic engineering with waypoints. Parham et al. [24] showed that a joint optimization of link weights and waypoints can in principle significantly improve traffic engineering compared to scenarios where link weights and waypoints are optimized separately. Amiri et al. [2, 3, 4] initiated the study of the parametrized complexity of routing through waypoints in a related problem in which the task is to find a shortest walk visiting a given set of waypoints and respecting edge capacities; they presented exact polynomial-time algorithms for graphs of bounded treewidth or restricted problems where the number of waypoints is logarithmically bounded. Recently, Bazgan et al. [7] showed that the fixed-length segment routing problem is NP-hard even for graphs with constant treewidth and when only one waypoint per demand is allowed. In our work, we complement these results, among others (see below), by showing that both the fixed-length variant (for which we also consider splitting ratios which Bazgan et al. did not) and the variable-length variant are NP-hard even on the practically relevant class of planar graphs (many ISP topologies are planar [25]).
Additional Related Work
Traffic engineering is a crucial concern of ISPs and an evergreen topic in networking [10, 17, 21, 27, 31]. Many innovations in networking over the last years were at least partially motivated by the desire to improve TE [13, 24]. There already exists a large body of literature on TE, for various network protocols, from MPLS [19, 30] over SDN [1] to SR [14]. There are also already several well-known analytical and complexity results on the achievable performance of TE in traditional networks [11, 17, 26].
Segment routing can be used on top of MPLS networks and on IPv6 networks [14]. Many more applied results on traffic engineering for segment routing are already available [5, 9, 20, 23] and we refer the interested reader to a recent survey by Ventre et al. [29]. Moreno et al. [23] showed that a minimal number of stacked labels suffice to exploit the benefits of segment routing successfully. Aubry et al. [5, 6] lay the algorithmic foundations of segment routing, considering different and related applications. Bhatia et al. [9] consider the problem of determining the optimal parameters for segment routing in offline and online scenarios; primarily focusing on 2-segment routing where traffic between the ingress and egress passes through exactly one intermediate node. They develop a traffic-matrix oblivious algorithm for robust segment routing in the offline setting. De Boeck [12] considers stochastic approaches to deal with uncertainty in segment routing traffic engineering. There also exists algorithmic work on local fast-rerouting for SR networks, as a reaction to link failures [16].
Our Contribution
Our main contributions concern the computational complexity of traffic engineering in segment routing networks. We first rigorously prove that even the fixed-length problem variant (where link weights are given and traffic can be distributed across paths according to operator-defined splitting ratios) is NP-hard already if the network graph is planar and if all demands and link weights are 1. We further show that the variable-length problem variant is also NP-hard already for planar networks, even with all demands being 1. Complementing these negative results, we present a compact and general mixed integer linear program to compute exact solutions. We next present the high-level idea of our two hardness results.
For the fixed-length variant, we reduce from multicolored clique. At a high level, we construct horizontal and vertical canonical paths representing the vertices of the input graph, grouped into bundles corresponding to colors. A feasible routing is forced to select one canonical path from each bundle. Where a horizontal and a vertical path meet, a small gadget determines whether both can be used simultaneously without exceeding the congestion bound: this is possible precisely if the represented vertices share an edge (or are the same vertex when considering two vertices of the same color).
For the variable-length variant, we instead reduce from a planar SAT variant. The weight assignment effectively encodes a truth assignment: in each variable gadget, making one of two alternative paths shorter forces the corresponding unique shortest paths to represent either true or false. Clause gadgets are connected to these choices such that their terminal pairs can be routed without congestion only through a literal consistent with the variable assignment. Thus, a congestion-one routing exists exactly when all clauses can simultaneously be satisfied.
Preliminaries and Formal Model
For a positive integer , we denote by the set . We denote the number of nodes (e.g., routers) in a graph by and the number of links by . Let be a (directed or undirected) graph. Moreover, let be a set of triples where are nodes (called terminals) and is a positive number. Let be a link-weight function. The task is to select one node (called a waypoint) and an -flow between and and between and for each triple such that each path of the flow is a shortest path (with respect to ) between the two respective endpoints ( and the terminals ). The goal is to minimize the maximum flow over any link in the graph. The load of a link is , where is the set of paths in the solution that contain the link and is the flow sent over the path .
We study the following two problem variants. Note that in one of the variants, the link-weight function is given as input, whereas in the second, we are free to define the function as part of the solution. In the first variant, flows can be split according to an optimizable ratio. In the second variant, flows take unique paths.
| Fixed-Length Splittable Traffic Engineering with Waypoints |
| Input: A graph , a set of triples where and for all , a link-weight function , and a positive number . |
| Question: Is there a tuple of nodes and for each two -flows and such that is a collection of shortest --paths, is a collection of shortest --paths, and at most units of flow are sent over each link in the graph? |
Table 1.
| Variable-Length Traffic Engineering with Waypoints |
| Input: A graph , a set of triples where and for all , and a positive number . |
| Question: Does a tuple of nodes and a link-weight function exist such that for each , there is a unique shortest path between and and a unique shortest path between and and ? Here, is 1 if is a link in and 0 otherwise. |
Table 2.
Analysis and Results
In this section, we show our main results. We start by proving that the fixed-length variant is NP-hard even in planar graphs with unit demands.
Theorem 1. Fixed-Length Splittable Traffic Engineering with Waypoints is NP-hard even if the input contains an undirected planar graph, , for all , and for all $e\in E.
Proof. We show a reduction from Multicolored Clique. Therein, one is given an undirected graph , an integer , and a coloring function . The question is whether there is a multicolored clique in , that is, a set of pairwise adjacent nodes containing exactly one node of each color in . It is known that Multicolored Clique remains NP-hard even when and there are the same number of nodes of each color [18]. We provide a polynomial-time reduction from such an instance of Multicolored Clique to an instance of Fixed-Length Splittable Traffic Engineering with Waypoints, where for all . We mention that the construction is similar and based on a reduction by Bentert et al. [8].
Before we give the overall construction, we start with four simple gadgets, which we call pass-through, intersection, blocking, and shortcut gadgets, respectively. They are depicted in Figure 1 and the intuitive ideas for them are as follows.
Figure 1. The four gadgets used in the proof of Theorem 1. The leftmost one is a pass-through gadget, the second is an intersection gadget, the third is a blocking gadget, and the last one is a shortcut gadget (where the dashed edge represents a path of length ).
For the pass-through gadget and the intersection gadget, consider the case that a path from the top goes to the bottom and another path comes from the left and goes to the right. In the pass-through gadget, these paths can be routed so as to avoid any overlap in the links used. This is not possible in the intersection gadget. For the blocking gadget, we have some number of paths going from left to right and terminal pairs. The maximum flow that can be routed without assigning a flow of more than one to some link is as the red links cut the left from the right. Since there is a flow of coming from the terminal pairs, at most one additional unit of flow can be routed through the gadget. Finally, the shortcut gadget allows us to have relatively short paths between the terminals while forcing the solution to include much longer paths. Consider a shortcut gadget as depicted on the right side of Figure 1 (with the same node names). We show that we can assume without loss of generality that in any solution for a flow of one is sent directly over the link for the triple and for the triple , a flow of one is sent over the link . To this end, let be the flow that is sent over the link for the triple and let be the amount of flow that is sent over the link for the triple . Note that for the triple a flow of is sent over the path from to and over the link . Analogously for the triple , a flow of is sent over the link and the --path. Since we send at most one unit of flow over any link in a solution for , it holds that (because of link ) and (because of link ). This implies that and hence we have exactly one unit of flow is sent over these two links for the two triples and . Hence, there is no capacity to send any flow for other triples over these links and since setting is a solution that sends one unit flow over these two links and no flow over any other links, we can assume without loss of generality that this is part of an optimal solution. For technical reasons, we then subdivide each link in each blocking gadget four times.
We continue with the complete construction, which is illustrated in Figure 2. We start with a “horizontal” and a “vertical” path for each node in . We call these paths the canonical paths and they will form a grid-like structure in where all paths corresponding to nodes of the same color appear consecutively. We call paths corresponding to nodes of the same color bundles. Note that there is exactly one horizontal and one vertical bundle for each color. Wherever a vertical and a horizontal path intersect, we add either a pass-through gadget or an intersection gadget as follows. Say the vertical path corresponds to a node and the horizontal path corresponds to a node . If and have different colors, then we place a pass-through gadget if and an intersection gadget if is not a link in . If and have the same color, then we place a pass-through gadget if and only if . Between any two consecutive gadgets on any path, we add two intermediate vertices. Next, we add blocking gadgets. We only describe the blocking gadgets for horizontal paths, but the procedure is exactly the same for vertical paths and depicted in Figure 2. For each horizontal bundle, we add a blocking gadget between two consecutive vertical bundles with triples . We also add blocking gadgets before the first and after the last bundle. We proceed by placing triples, one horizontal and one vertical terminal pair for each color . Let be the horizontal triple for color and be the vertical triple for color . We call all of these triples the important triples. We add a path of length between each and the first node of the horizontal path corresponding to each node of color . We also add such paths between the last node of each of these paths and and do the same for , and vertical paths. Finally, we add two new nodes and . We connect to all nodes and to all nodes with via a shortcut gadget. We add the link to conclude the construction.
Figure 2. An illustration of the reduction from Multicolored Clique to Fixed-Length Splittable Traffic Engineering with Waypoints. Left side: Example instance for Multicolored Clique with colors and nodes per color. Each node is given a label , where indicates the color of a vertex and is an index of the respective node within each color class. A multicolored clique is highlighted (by thick links). Right side: The constructed instance. The pink nodes represent pass-through gadgets, the orange nodes represent intersection gadgets, the violet objects represent blocking gadgets, and dashed links indicate shortcut gadgets. Dotted links (at the beginning and end of each path) indicate paths of length . The eight solution paths corresponding to the solution on the left are highlighted (not including the solution paths for terminals in blocking or shortcut gadgets). The waypoint can be any node on the highlighted path close enough to the middle. Note that all highlighted solution paths intersect in pass-through gadgets and hence are link-disjoint.
Note that the constructed graph is planar as each gadget is planar and all gadgets can be arranged in a planar way as shown in Figure 2. Moreover, we set , for each triple , and for each link . Since the instance can be constructed in polynomial time, it only remains to show that the constructed instance is equivalent to the original instance of Multicolored Clique. Before doing so, we note that the distance between and for any is as two shortcut gadgets have length each. These shortest paths are unique and cannot be part of a solution as this would require additional flow through a shortcut gadget, which is infeasible as shown above. Moreover, the shortest paths between and that do not pass through or have . Each vertical/horizontal path corresponding to a node of color (or ) has this length as it contains two paths of length each (the dotted lines in Figure 2), bundles with paths of the other orientation each and for each such path it passes through an intersection or pass-through gadget which increases the path by five each (two links in the gadget and three links to the beginning of the next gadget). Moreover, it passes through blocking gadgets which add a length of each. The final plus one is to address the fact that if a shortest path between two nodes and contains internal nodes, then the distance between and is . Note that and hence any path that uses at least three paths of length is longer than any canonical path.
We proceed to show that the constructed instance of Fixed-Length Splittable Traffic Engineering with Waypoints is equivalent to the original instance of Multicolored Clique. To this end, first assume that the original instance is a yes-instance, that is, there is a set of nodes containing exactly one node of each color that form a clique. For each important triple, we route a shortest path along the canonical path representing the node in of the respective color by choosing an appropriate waypoint on the middle of that path. Note that all of these paths can be routed without using any link in multiple paths as all of these paths meet in pass-through gadgets by construction. Moreover, as we only use one path in each blocking gadget, we can route paths for all triples with endpoints in blocking gadgets without leaving the blocking gadget by choosing appropriate waypoints (as shown in Figure 1). Finally, for each triple with endpoints in a shortcut gadget, we use the single link between the respective terminal nodes. Note that all of the described paths are pairwise link-disjoint and hence we can send one unit of flow over each of them to conclude that the constructed instance of Fixed-Length Splittable Traffic Engineering with Waypoints is a yes-instance.
Now assume that the constructed instance of Fixed-Length Splittable Traffic Engineering with Waypoints is a yes-instance and let be the waypoint chosen for each triple in a solution. As shown above, no important triple can have any of their flow be routed through a shortcut gadget. Note that if the shortcut gadgets are not used, then for each triple with one unit of flow is sent through blocking gadgets placed on horizontal paths and the same holds for all triples with and blocking gadgets placed on vertical paths. Note that we showed above that each blocking gadget only allows for one unit of flow to be sent through it when ignoring the flow that comes from triples with endpoints inside the gadget. Since we place exactly blocking gadgets for each bundle of canonical paths, this implies that no flow is routed through a blocking gadget placed on a vertical path for a triple with . The same holds for blocking gadgets placed on horizontal paths and triples with . This implies that each waypoint for is chosen from a canonical path since all other vertices are too close to one of their respective endpoints and a shortest path to the other endpoint returns to the first endpoint and then uses the shortcut gadgets. For each , let be the node corresponding to the canonical path on which lies. First, note that by construction, there is a unique shortest path from to and from to . This path is the canonical path representing . Note that this implies that the canonical paths representing and for have to meet in a pass-through gadget as two units of flow are routed through each of these gadgets and without violating , this is only possible in a pass-through gadget. This implies (i) for each and for each . Hence, the nodes form a clique in the original graph . Moreover, since all of these nodes come from different bundles, they have pairwise different colors. Thus, they form a multicolored clique and the original instance of Multicolored Clique is a yes-instance. □
We next show that the variable-length variant is also NP-hard. The hardness even holds for planar graphs and unit demands.
Theorem 2. Variable-Length Traffic Engineering with Waypoints is -hard even
if the input contains an undirected planar graph of maximum degree 3, , and for all .
Proof. We present a reduction from Planar 2P1N-3-Sat similar to the one by Middendorf and Pfeiffer [22]. In Planar 2P1N-3-SAT, we are given a formula in CNF where each clause contains two or three literals and each variable appears at most twice positively and exactly once negated in a clause in . Moreover, we are given a planar embedding of the (bipartite and planar) graph that contains a node for each variable and a node for each clause and a link if and only if contains or . First, we take the planar embedding of and for each link in the embedding representing that a variable appears in a clause , we add two nodes and and a link between them such that is directly left of in the planar embedding and the link (embedded as a straight line) crosses exactly the link in the embedding of . Next, we remove the link and replace the nodes in by the gadgets in Figure 3 to Figure 5 for variables, clauses with two literals, and clauses with three literals, respectively.

Figure 3. The variable gadget for a variable appearing positively in clauses and and negated in . The rectangular nodes represent terminal nodes and the dashed links are the links introduced before. The - and -nodes are the previously introduced - and -nodes. We choose which one is which as to preserve planarity. If the variable appears only once positively, then we replace and and the dashed link between them by two new nodes with a regular link between them.
Figure 5. The clause gadget for a clause containing three variables , and .
We next show that all gadgets can be rotated and/or mirrored to ensure that they can be embedded in a planar way given the already placed (dashed) links. We start with variables. To this end, let be a node in corresponding to a variable in . Let be the clause in which appears negated and let and be the clauses in which appears positively (or ignore if only appears positively once). For the sake of presentation, we assume that the node representing clause is to the left of and the nodes representing and are to the right with the one representing being higher in the planar embedding of . If this is not the case, then we can rotate the gadget appropriately and/or swap the nodes with and with . Similarly, for a clause gadget for a clause containing two literals, we can rotate the gadget to ensure that the gadget can be added to the current graph without introducing link crossings. For clauses containing three literals , , and , we can do the same if the variables appear in clockwise fashion. If they appear in counter-clockwise fashion, then we can mirror the gadget and then rotate it appropriately. Note that any sequence of three variables is ordered either clockwise or counter clockwise. Thus, the entire graph can be embedded in the plane without link crossings. To conclude the construction, we set to be the set of all triples for which and are the terminal pairs shown in Figure 3 to Figure 5.
We next prove that the input formula is satisfiable if and only if the produced instance of Variable-Length Traffic Engineering with Waypoints is a yes-instance. Since the reduction can be computed in polynomial time, Planar 2P1N-3-SAT is NP-hard, and the resulting graph has maximum degree at most three, it follows that Variable-Length Traffic Engineering with Waypoints is NP-hard even if the input graph is planar and has maximum degree three.
First, assume that is satisfiable and let a satisfying assignment be given. We next show how can be used to show that the produced instance of Variable-Length Traffic Engineering with Waypoints is a yes-instance. To this end, we set the length of links between and to 1 for all pairs of a variable and a clause where contains . For each variable , if assigns to true, then we set the length of all links in the left half of Figure 3 to 1 and of all links in the right half to 2 (ignoring the dashed links). If assigns to false, then we set the length of all links in the right half to 1 and of all links in the left half (again ignoring dashed links) to 2.
For each clause , let be a variable such that the assignment of with respect to satisfies . If multiple such variables exist, then we choose one arbitrarily. If contains two variables and corresponds to in Figure 4, then we set the length of all links in the upper half of Figure 4 to 1 and the length of both non-dashed links in the lower half to 2. If corresponds to in Figure 4, then we set the length of all links in the lower half to 1 and the length of both non-dashed links in the upper half to 2. Finally, if contains three literals, then there is a unique shortest path (in the unweighted graph) between the first terminal pair in Figure 5 in such a way that there exist shortest paths and (again in the unweighted graph) between the second and third terminal pair, respectively, such that passes through and , all three paths are pairwise node disjoint and neither nor use any of the - or -nodes. We set the length of all links in , , and to 1 and all other links (ignoring dashed links) to 2. It is easy to see that all shortest paths between any terminal pair are unique, stay within a clause gadget or within a variable gadget, and only use links that we assigned length 1. By construction, these only overlap in the nodes and . Since is a satisfying assignment, whenever the clause gadget for uses these two nodes, then the variable gadget for does not use them. Thus, all terminal paths are pairwise node-disjoint (and therefore also link-disjoint) and thus we constructed a solution for . We pick one waypoint on each of these paths arbitrarily.

Figure 4. The clause gadget for a clause with two variables and .
For the other direction, assume that the constructed instance of Variable-Length Traffic Engineering with Waypoints is a yes-instance. In particular, there are pairwise edge-disjoint paths between all terminal pairs. Since the maximum degree is three and terminals have degree 2, these paths are also vertex-disjoint. Since all links in the clause gadget depicted in Figure 4 are incident to terminal vertices (or are dashed links), the only way for a solution of a variable gadget to leave the variable gadget is to pass through at least two gadgets in Figure 5. However, routing any additional path through the gadget in Figure 5 is impossible. This was shown by Middendorf and Pfeiffer [22] and can be summarized in the following observation. If an additional path is routed through the gadget, then this path uses at least one endpoint of two of the dashed links. If all three dashed links are unavailable, then it is impossible to route paths between all three terminal pairs in the gadget and using exactly one of the dashed links requires to use both central nodes or the dashed link . In the former case, no additional path can be routed through the gadget and in the latter case, only a path from to can be routed. This path, however, makes it impossible to connect the terminal pair . Thus, solution path between terminal vertices in the variable gadget is completely contained in the variable gadget.
Let now be an assignment to the variables of the original formula that assigns a variable to true if the solution path between the terminal vertices in this variable’s gadget uses the left half (in Figure 3). We claim that satisfies . Assume towards a contradiction that there is some clause in that is not satisfied by . This means that none of the variables appearing in satisfy the clause under assignment . By construction, this means that solution path between the terminal vertices in all variable gadgets for a variable in uses the respective pair of and vertices. Hence, the solution paths between the terminal vertices in the clause gadget for (depicted in either Figure 4 or Figure 5) cannot use the - and -vertices ( and in the pictures). Note that without these vertices, there is only a single path between the first terminal pair in Figure 5 that avoids the other terminals. Moreover, no such path exists between the terminal pair in Figure 4. However, for the unique path between the first terminal pair in Figure 5 that avoids all - and -vertices, there is no vertex-disjoint path between the third terminal pair . Hence, the assumption that is not a satisfying assignment contradicts the fact that we assumed the constructed instance to be a yes-instance. This concludes the proof.
We conclude by showing that Fixed-Length Splittable Traffic Engineering with Waypoints can be solved by the relatively simple mixed integer linear program presented in Figure 6.
Figure 6. A mixed integer linear program for Fixed-Length Splittable Traffic Engineering with Waypoints for undirected graphs. For directed graphs, replace Constraint (2) by for all .
Proposition 1. Fixed-Length Splittable Traffic Engineering with Waypoints can be encoded in a mixed integer linear program with integer variables and (continuous) variables and constraints.
Proof. For each and each node , we add a variable . This variable will be set to 1 if is the waypoint for the triple in a solution. We precompute all distances in the graph in time using the Floyd–Warshall algorithm [15]. We denote by the distance between and in . Note that a link can only be used on a shortest path between and (or and ) if . Moreover, it can only be used in one direction (from the node closer to to the node further away from ). For this reason, we can define a directed graph where contains all directed links whose undirected counterpart is contained in and where the link points away from . That is, we set . If is already directed, this is just a subgraph of . We do the same for each and call the resulting link set . That is, . Note that this reverses the arcs in case is directed.
The constraints of our mixed integer linear program for undirected graphs are given in Figure 6. It uses variables for each and , for each , and and for each and . Each of these variables can be assigned a rational number between 0 and . Finally, we have one variable that restricts the maximum flow sent over any link in in a solution. The goal is to compute a solution which minimizes . We mention that constraint (2) includes some terms that are not valid variables as not all edges have to be included in and/or . Those are of course not included in the sum, but we kept this presentation for the sake of readability.
The basic idea is that constraint (1) guarantees that precisely one waypoint is picked for each triple . The flow between and (between and , respectively) is then captured by the assignment of (respectively ) variables as follows. If we assign some positive value , then this corresponds to sending units of flow from to . We do the same for . Here, we use the arc in the opposite direction and produce a flow “from to ”. Constraints (3) and (5) then ensure that flow leaves unless that is the chosen waypoint. Constraints (4) and (6) are the usual flow-preservation constraints.
We mention that a similar mixed integer linear program can also be used to solve the variant where we need to select a single path between each terminal pair. Simply constrain the and variables to be assigned either 0 or 1, remove in all constraints, and add it to constraint (2) instead.
Conclusion
We charted a refined landscape of the complexity of traffic engineering in segment routing networks which recently received much interest in industry. In particular, we studied the practically relevant case of planar graphs and showed that two very basic models remain NP-hard: when link weights are fixed and the operator may optimize the splitting of traffic among shortest paths and when link weights and waypoints may be chosen and every segment must follow a unique shortest path. Our results also show that the computational difficulty is fundamentally combinatorial and not caused by the numbers involved. At the same time, our compact mixed integer linear formulation for the fixed-weight splittable setting provides a direct approach for computing exact solutions and a baseline for evaluating other approaches.
Acknowledgements
This research is supported by the German Research Foundation (DFG), SPP 2378: ReNO-2 (project number 511099228).
References
- [1]S. Agarwal, M. S. Kodialam, and T. V. Lakshman. Traffic engineering in software defined networks. In Proceedings of the 32nd IEEE Conference on Computer Communications (INFOCOM), pages 2211–2219. IEEE, 2013.
- [2]S. A. Amiri, K.-T. Foerster, R. Jacob, M. Parham, and S. Schmid. Waypoint routing in special networks. In Proceedings of the 17th IFIP Networking Conference and Workshops (IFIP Networking), pages 496–504. IFIP, 2018.DOI
- [3]S. A. Amiri, K.-T. Foerster, R. Jacob, and S. Schmid. Charting the algorithmic complexity of waypoint routing. Computer Communication Review, 48(1):42–48, 2018.DOI
- [4]S. A. Amiri, K.-T. Foerster, and S. Schmid. Walking through waypoints. Algorithmica, 2020.
- [5]F. Aubry. Models and algorithms for network optimization with segment routing. PhD thesis, 2020.
- [6]F. Aubry, S. Vissicchio, O. Bonaventure, and Y. Deville. Robustly disjoint paths with segment routing. In CoNEXT, pages 204–216. ACM, 2018.DOI
- [7]C. Bazgan, M. Chopin, A. Nichterlein, and C. Richer. Parameterized complexity of segment routing. In Proceedings of the 2025 IEEE Conference on Computer Communications (INFOCOM), pages 1–10. IEEE, 2025.arxiv.org/abs/2501.03871
- [8]M. Bentert, A. Nichterlein, M. Renken, and P. Zschoche. Using a geometric lens to find k-disjoint shortest paths. SIAM Journal on Discrete Mathematics, 37(3):1674–1703, 2023.
- [9]R. Bhatia, F. Hao, M. S. Kodialam, and T. V. Lakshman. Optimized network traffic engineering using segment routing. In Proceedings of the 34th IEEE Conference on Computer Communications (INFOCOM), pages 657–665. IEEE, 2015.DOI
- [10]M. Chiesa, G. Rétvári, and M. Schapira. Lying your way to better traffic engineering. In Proceedings of the 12th International Conference on Emerging Networking Experiments and Technologies (CoNEXT), pages 391–398. ACM, 2016.arxiv.org/abs/1610.02728
- [11]M. Chiesa, G. Kindler, and M. Schapira. Traffic engineering with equal-cost-multipath: An algorithmic perspective. IEEE/ACM Transactions on Networking, 25(2):779–792, 2017.
- [12]J. De Boeck, B. Fortz, and S. Schmid. The case for stochastic online segment routing under demand uncertainty. In Proceedings of the 22nd IFIP Networking Conference (IFIP Networking), pages 1–8. IEEE, 2023.DOI
- [13]N. Feamster, J. Rexford, and E. W. Zegura. The road to SDN: An intellectual history of programmable networks. Computer Communication Review, 44(2):87–98, 2014.
- [14]C. Filsfils, S. Previdi, L. Ginsberg, B. Decraene, S. Litkowski, and R. Shakir. Segment routing architecture. RFC, 8402:1–32, 2018.
- [15]R. W. Floyd. Algorithm 97: Shortest path. Communications of the ACM, 5(6):345, 1962.DOI
- [16]K.-T. Foerster, M. Parham, M. Chiesa, and S. Schmid. TI-MFA: keep calm and reroute segments fast. In Global Internet Symposium. IEEE, 2018.DOI
- [17]B. Fortz and M. Thorup. Increasing Internet Capacity Using Local Search. Computational Optimization and Applications, 29(1):13–48, 2004.DOI
- [18]M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
- [19]A. Gupta, A. Kumar, and R. Rastogi. Traveling with a pez dispenser (or, routing issues in mpls). SIAM Journal on Computing, 34(2):453–474, 2005.
- [20]R. Hartert. Fast and scalable optimization for segment routing. PhD thesis, 2018.
- [21]P. Kumar, Y. Yuan, C. Yu, N. Foster, R. Kleinberg, P. Lapukhov, C. Lim, and R. Soulé. Semi-oblivious traffic engineering: The road not taken. In Proceedings of the 15th USENIX Symposium on Networked Systems Design and Implementation (NSDI), pages 157–170. USENIX Association, 2018.
- [22]M. Middendorf and F. Pfeiffer. On the complexity of the disjoint paths problem. Combinatorica, 13(1):97–107, 1993.DOI
- [23]E. Moreno, A. Beghelli, and F. Cugini. Traffic engineering in segment routing networks. Computer Networks, 114:23–31, 2017.DOI
- [24]M. Parham, T. Fenz, N. Süss, K.-T. Foerster, and S. Schmid. Traffic engineering with joint link weight and segment optimization. In Proceedings of the 17th International Conference on emerging Networking EXperiments and Technologies (CoNEXT), pages 313–327. ACM, 2021.DOI
- [25]Y.-A. Pignolet, S. Schmid, and G. Trédan. Tomographic node placement strategies and the impact of the routing model. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1(2):42:1–42:23, 2017.
- [26]M. Pióro, Á. Szentesi, J. Harmatos, A. Jüttner, P. Gajowniczek, and S. Kozdrowski. On open shortest path first related network optimisation problems. Performance Evaluation, 48(1/4):201–223, 2002.DOI
- [27]H. Räcke and S. Schmid. Compact oblivious routing. In Proceedings of the 27th Annual European Symposium on Algorithms (ESA), pages 75:1–75:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.arxiv.org/abs/1812.09887
- [28]Leslie G. Valiant. A scheme for fast parallel communication. SIAM Journal on Computing, 11(2):350–361, 1982.
- [29]P. L. Ventre, S. Salsano, M. Polverini, A. Cianfrani, A. Abdelsalam, C. Filsfils, P. Camarillo, and F. Clad. Segment routing: A comprehensive survey of research activities, standardization efforts, and implementation results. IEEE Communications Surveys and Tutorials, 23(1):182–221, 2021.arxiv.org/abs/1904.03471
- [30]X. Xiao, A. Hannan, B. Bailey, and L. M. Ni. Traffic engineering with MPLS in the internet. IEEE Network, 14(2):28–33, 2000.DOI
- [31]G. Zuzic, B. Haeupler, and A. Roevskoe. Sparse semi-oblivious routing: Few random paths suffice. In Proceedings of the 42nd ACM Symposium on Principles of Distributed Computing (PODC), pages 222–232. ACM, 2023.arxiv.org/abs/2301.06647



