betaFeedback

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 nn, we denote by [n][n] the set {1,2,…,n}\{1,2,\ldots,n\}. We denote the number of nodes (e.g., routers) in a graph by nn and the number of links by mm. Let G=(V,E)G=(V,E) be a (directed or undirected) graph. Moreover, let T={(s1,t1,r1),(s2,t2,r2),…,(sk,tk,rk)}T=\{(s_1,t_1,r_1),(s_2,t_2,r_2),\ldots,(s_k,t_k,r_k)\} be a set of triples where si,ti∈Vs_i,t_i\in V are nodes (called terminals) and ri∈Q+r_i\in\mathbb{Q}^{+} is a positive number. Let w:E→Q+w:E\to\mathbb{Q}^{+} be a link-weight function. The task is to select one node pip_i (called a waypoint) and an rir_i-flow between sis_i and pip_i and between pip_i and tit_i for each triple (si,ti,ri)∈T(s_i,t_i,r_i)\in T such that each path of the flow is a shortest path (with respect to ww) between the two respective endpoints (pip_i and the terminals si/tis_i/t_i). The goal is to minimize the maximum flow over any link in the graph. The load of a link ee is ∑P∈PerP\sum_{P\in\mathcal{P}_e}r_P, where Pe\mathcal{P}_e is the set of paths in the solution that contain the link ee and rPr_P is the flow sent over the path PP.

We study the following two problem variants. Note that in one of the variants, the link-weight function ww 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 G=(V,E)G=(V,E), a set T={(s1,t1,r1),…,(sk,tk,rk)}T=\{(s_1,t_1,r_1),\ldots,(s_k,t_k,r_k)\} of triples where si,ti∈Vs_i,t_i\in V and ri∈Q+r_i\in\mathbb{Q}^{+} for all i∈[k]i\in[k], a link-weight function w:E→Q+w:E\to\mathbb{Q}^{+}, and a positive number ℓ∈Q+\ell\in\mathbb{Q}^{+}.
Question: Is there a tuple Q=(p1,p2,…,pk)Q=(p_1,p_2,\ldots,p_k) of nodes and for each i∈[k]i\in[k] two rir_i-flows Fi1F_i^1 and Fi2F_i^2 such that Fi1F_i^1 is a collection of shortest sis_i-pip_i-paths, Fi2F_i^2 is a collection of shortest pip_i-tit_i-paths, and at most ℓ\ell units of flow are sent over each link in the graph?

Table 1.

Variable-Length Traffic Engineering with Waypoints
Input: A graph G=(V,E)G=(V,E), a set T={(s1,t1,r1),…,(sk,tk,rk)}T=\{(s_1,t_1,r_1),\ldots,(s_k,t_k,r_k)\} of triples where si,ti∈Vs_i,t_i\in V and ri∈Q+r_i\in\mathbb{Q}^{+} for all i∈[k]i\in[k], and a positive number ℓ∈Q+\ell\in\mathbb{Q}^{+}.
Question: Does a tuple Q=(p1,p2,…,pk)Q=(p_1,p_2,\ldots,p_k) of nodes and a link-weight function w:E→Q+w:E\to\mathbb{Q}^{+} exist such that for each i∈[k]i\in[k], there is a unique shortest path Pi1P_i^1 between sis_i and pip_i and a unique shortest path Pi2P_i^2 between pip_i and tit_i and max⁡e∈E∑i∈[k]∑P∈{Pi1,Pi2}eP⋅ri≤ℓ\max_{e\in E}\sum_{i\in[k]}\sum_{P\in\{P_i^1,P_i^2\}}e_P\cdot r_i\leq\ell? Here, ePe_P is 1 if ee is a link in PP 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, ℓ=1\ell=1, ri=1r_i=1 for all i∈[k]i\in[k], and w(e)=1w(e)=1 for all $e\in E.

Proof. We show a reduction from Multicolored Clique. Therein, one is given an undirected graph G=(V,E)G = (V, E), an integer kk, and a coloring function c:V→[k]c: V \to[k]. The question is whether there is a multicolored clique in GG, that is, a set of pairwise adjacent nodes containing exactly one node of each color in [k][k]. It is known that Multicolored Clique remains NP-hard even when k≥4k \ge4 and there are the same number ν=nk\nu= \frac{n}{k} of nodes of each color [18]. We provide a polynomial-time reduction from such an instance (G,c,k)(G, c, k) of Multicolored Clique to an instance (G′=(V′,E′),T,w,1)(G' = (V', E'), T, w, 1) of Fixed-Length Splittable Traffic Engineering with Waypoints, where w(e)=1w(e) = 1 for all e∈E′e \in E'. 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 25n25n).

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 qq of paths going from left to right and q−1q - 1 terminal pairs. The maximum flow that can be routed without assigning a flow of more than one to some link is qq as the qq red links cut the left from the right. Since there is a flow of q−1q - 1 coming from the q−1q - 1 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 ℓ=1\ell= 1 a flow of one is sent directly over the link {s1,t1}\{s_1, t_1\} for the triple (s1,t1,1)(s_1, t_1, 1) and for the triple (s2,t2,1)(s_2, t_2, 1), a flow of one is sent over the link {s2,t2}\{s_2, t_2\}. To this end, let qq be the flow that is sent over the link {s1,t1}\{s_1, t_1\} for the triple (s1,t1,1)(s_1, t_1, 1) and let rr be the amount of flow that is sent over the link {s2,t2}\{s_2, t_2\} for the triple (s2,t2,1)(s_2, t_2, 1). Note that for the triple (s1,t1,1)(s_1, t_1, 1) a flow of 1−q1 - q is sent over the path from s1s_1 to s2s_2 and over the link {s2,t2}\{s_2, t_2\}. Analogously for the triple (s2,t2,1)(s_2, t_2, 1), a flow of 1−r1 - r is sent over the link {s1,t1}\{s_1, t_1\} and the s1s_1-s2s_2-path. Since we send at most one unit of flow over any link in a solution for ℓ=1\ell= 1, it holds that q+(1−r)≤1q + (1 - r) \le1 (because of link {s1,t1}\{s_1, t_1\}) and (1−q)+r≤1(1 - q) + r \le1 (because of link {s2,t2}\{s_2, t_2\}). This implies that q=rq = r and hence we have exactly one unit of flow is sent over these two links for the two triples (s1,t1,1)(s_1, t_1, 1) and (s2,t2,1)(s_2, t_2, 1). Hence, there is no capacity to send any flow for other triples over these links and since setting q=1=rq = 1 = r 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 GG. We call these paths the canonical paths and they will form a grid-like structure in G′G' 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 uu and the horizontal path corresponds to a node vv. If uu and vv have different colors, then we place a pass-through gadget if {u,v}∈E\{u,v\} \in E and an intersection gadget if {u,v}\{u,v\} is not a link in GG. If uu and vv have the same color, then we place a pass-through gadget if and only if u=vu = v. 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 ν−1\nu- 1 triples (sj,tj,1)(s_j,t_j,1). We also add blocking gadgets before the first and after the last bundle. We proceed by placing 2k2k triples, one horizontal and one vertical terminal pair for each color i∈[k]i \in[k]. Let (si,ti,1)(s_i,t_i,1) be the horizontal triple for color ii and (sk+i,tk+i,1)(s_{k+i},t_{k+i},1) be the vertical triple for color ii. We call all of these triples the important triples. We add a path of length 25n25n between each sis_i and the first node of the horizontal path corresponding to each node of color ii. We also add such paths between the last node of each of these paths and tit_i and do the same for sk+i,tk+is_{k+i},t_{k+i}, and vertical paths. Finally, we add two new nodes c1c_1 and c2c_2. We connect c1c_1 to all nodes sis_i and c2c_2 to all nodes tit_i with i∈[2k]i \in[2k] via a shortcut gadget. We add the link {c1,c2}\{c_1,c_2\} 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 k=4k = 4 colors and ν=3\nu= 3 nodes per color. Each node is given a label (i,j)(i,j), where ii indicates the color of a vertex and jj 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 25n=30025n = 300. 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 ℓ=1\ell= 1, ri=1r_i = 1 for each triple (si,ti,ri)(s_i,t_i,r_i), and w(e)=1w(e) = 1 for each link ee. 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 sis_i and tit_i for any i∈[2k]i \in[2k] is 50n+950n + 9 as two shortcut gadgets have length 25n+425n + 4 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 sis_i and tit_i that do not pass through c1c_1 or c2c_2 have L=50n+k⋅(5ν)+(k+1)(10ν)+1L = 50n + k \cdot(5\nu) + (k + 1)(10\nu) + 1. Each vertical/horizontal path corresponding to a node of color ii (or i−ki-k) has this length as it contains two paths of length 25n25n each (the dotted lines in Figure 2), kk bundles with ν\nu 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 k+1k+1 blocking gadgets which add a length of 10ν10\nu each. The final plus one is to address the fact that if a shortest path between two nodes uu and vv contains xx internal nodes, then the distance between uu and vv is x+1x+1. Note that L<75nL < 75n and hence any path that uses at least three paths of length 25n25n 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 KK 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 KK 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 wiw_i be the waypoint chosen for each triple (si,ti,1)(s_i,t_i,1) 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 (si,ti,1)(s_i,t_i,1) with i∈[k]i \in[k] one unit of flow is sent through k+1k+1 blocking gadgets placed on horizontal paths and the same holds for all triples (sk+i,tk+i,1)(s_{k+i},t_{k+i},1) with i∈[k]i \in[k] 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 k+1k+1 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 (si,ti,1)(s_i,t_i,1) with i∈[k]i \in[k]. The same holds for blocking gadgets placed on horizontal paths and triples (sk+i,tk+i,1)(s_{k+i},t_{k+i},1) with i∈[k]i \in[k]. This implies that each waypoint wiw_i for i∈[2k]i \in[2k] 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 i∈[2k]i \in[2k], let viv_i be the node corresponding to the canonical path on which wiw_i lies. First, note that by construction, there is a unique shortest path from sis_i to wiw_i and from wiw_i to tit_i. This path is the canonical path representing viv_i. Note that this implies that the canonical paths representing viv_i and vk+jv_{k+j} for i,j∈[k]i,j \in[k] have to meet in a pass-through gadget as two units of flow are routed through each of these gadgets and without violating ℓ=1\ell= 1, this is only possible in a pass-through gadget. This implies (i) vi=vk+iv_i = v_{k+i} for each i∈[k]i \in[k] and [vi,vk+j]∈E[v_i,v_{k+j}] \in E for each i≠j∈[k]i \ne j \in[k]. Hence, the nodes v1,v2,…,vkv_1,v_2,\ldots,v_k form a clique in the original graph GG. 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 NPNP-hard even

if the input contains an undirected planar graph of maximum degree 3, ℓ=1\ell= 1, and ri=1r_i = 1 for all i∈[k]i \in[k].

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 Φ\Phi 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 Φ\Phi. Moreover, we are given a planar embedding of the (bipartite and planar) graph HH that contains a node viv_i for each variable xix_i and a node uju_j for each clause CjC_j and a link {uj,vi}\{u_j, v_i\} if and only if CjC_j contains xix_i or ¬xi\neg x_i. First, we take the planar embedding of HH and for each link ee in the embedding representing that a variable xx appears in a clause AA, we add two nodes α(x,A)\alpha(x, A) and β(x,A)\beta(x, A) and a link between them such that α(x,A)\alpha(x, A) is directly left of β(x,A)\beta(x, A) in the planar embedding and the link (embedded as a straight line) crosses exactly the link ee in the embedding of HH. Next, we remove the link ee and replace the nodes in HH by the gadgets in Figure 3 to Figure 5 for variables, clauses with two literals, and clauses with three literals, respectively.

Variable gadget for a variable $x$ appearing positively in clauses $A$ and $B$ and negated in $C$

Figure 3. The variable gadget for a variable xx appearing positively in clauses AA and BB and negated in CC. The rectangular nodes represent terminal nodes and the dashed links are the links introduced before. The γ\gamma- and δ\delta-nodes are the previously introduced α\alpha- and β\beta-nodes. We choose which one is which as to preserve planarity. If the variable xx appears only once positively, then we replace γ(x,B)\gamma(x, B) and δ(x,B)\delta(x, B) and the dashed link between them by two new nodes with a regular link between them.

Figure 5. The clause gadget for a clause AA containing three variables xx, yy and zz.

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 viv_i be a node in HH corresponding to a variable xix_i in Φ\Phi. Let CC be the clause in which xix_i appears negated and let AA and BB be the clauses in which xix_i appears positively (or ignore BB if xix_i only appears positively once). For the sake of presentation, we assume that the node representing clause CC is to the left of viv_i and the nodes representing AA and BB are to the right with the one representing AA being higher in the planar embedding of HH. If this is not the case, then we can rotate the gadget appropriately and/or swap the nodes γ(x,A)\gamma(x, A) with γ(x,B)\gamma(x, B) and δ(x,A)\delta(x, A) with δ(x,B)\delta(x, B). 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 xx, yy, and zz, 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 TT to be the set of all triples (s,t,1)(s,t,1) for which ss and tt are the terminal pairs shown in Figure 3 to Figure 5.

We next prove that the input formula Φ\Phi 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 Φ\Phi is satisfiable and let a satisfying assignment aa be given. We next show how aa 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 α(x,A)\alpha(x,A) and β(x,A)\beta(x,A) to 1 for all pairs of a variable xx and a clause AA where AA contains xx. For each variable xx, if aa assigns xx 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 aa assigns xx 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 AA, let xAx_A be a variable such that the assignment of xAx_A with respect to aa satisfies AA. If multiple such variables exist, then we choose one arbitrarily. If AA contains two variables and xAx_A corresponds to xx 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 xAx_A corresponds to yy 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 AA contains three literals, then there is a unique shortest path P1P_1 (in the unweighted graph) between the first terminal pair in Figure 5 in such a way that there exist shortest paths P2P_2 and P3P_3 (again in the unweighted graph) between the second and third terminal pair, respectively, such that P1P_1 passes through α(xA,A)\alpha(x_A,A) and β(xA,A)\beta(x_A,A), all three paths are pairwise node disjoint and neither P2P_2 nor P3P_3 use any of the α\alpha- or β\beta-nodes. We set the length of all links in P1P_1, P2P_2, and P3P_3 to 1 and all other links (ignoring dashed links) to 2. It is easy to see that all shortest paths between any terminal pair (si,ti)(s_i,t_i) 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 α(x,A)\alpha(x,A) and β(x,A)\beta(x,A). Since aa is a satisfying assignment, whenever the clause gadget for AA uses these two nodes, then the variable gadget for xx does not use them. Thus, all terminal paths are pairwise node-disjoint (and therefore also link-disjoint) and thus we constructed a solution for ℓ=1\ell= 1. We pick one waypoint on each of these paths arbitrarily.

Clause gadget for a clause $A$ with two variables $x$ and $y$

Figure 4. The clause gadget for a clause AA with two variables xx and yy.

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 {γ(z,A),δ(z,A)}\{\gamma(z,A),\delta(z,A)\}. In the former case, no additional path can be routed through the gadget and in the latter case, only a path from δ(x,A)\delta(x,A) to γ(y,A)\gamma(y,A) can be routed. This path, however, makes it impossible to connect the terminal pair (sA2,tA2)(s_A^2,t_A^2). Thus, solution path between terminal vertices in the variable gadget is completely contained in the variable gadget.

Let now bb be an assignment to the variables of the original formula Φ\Phi 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 bb satisfies Φ\Phi. Assume towards a contradiction that there is some clause AA in Φ\Phi that is not satisfied by bb. This means that none of the variables appearing in AA satisfy the clause under assignment bb. By construction, this means that solution path between the terminal vertices in all variable gadgets for a variable xx in AA uses the respective pair of α(x,A)\alpha(x,A) and β(x,A)\beta(x,A) vertices. Hence, the solution paths between the terminal vertices in the clause gadget for AA (depicted in either Figure 4 or Figure 5) cannot use the α\alpha- and β\beta-vertices (γ\gamma and δ\delta 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 α\alpha- and β\beta-vertices, there is no vertex-disjoint path between the third terminal pair (sA3,tA3)(s_A^3,t_A^3). Hence, the assumption that bb 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 ∑i∈[k]x(u,v)i+y(v,u)i≤ℓ\sum_{i\in[k]} x^i_{(u,v)} + y^i_{(v,u)} \le\ell for all (u,v)∈E(u,v)\in E.

Proposition 1. Fixed-Length Splittable Traffic Engineering with Waypoints can be encoded in a mixed integer linear program with nknk integer variables and O(k⋅(n+m))O(k\cdot(n+m)) (continuous) variables and constraints.

Proof. For each i∈[k]i \in[k] and each node v∈Vv \in V, we add a variable wvi∈{0,1}w_v^i \in\{0,1\}. This variable will be set to 1 if vv is the waypoint for the triple (si,ti,ri)(s_i,t_i,r_i) in a solution. We precompute all distances in the graph in O(n3)O(n^3) time using the Floyd–Warshall algorithm [15]. We denote by dist⁡(u,v)\operatorname{dist}(u,v) the distance between uu and vv in GG. Note that a link {u,v}\{u,v\} can only be used on a shortest path between sis_i and wiw_i (or tit_i and wiw_i) if dist⁡(si,u)=dist⁡(si,v)+w({u,v})\operatorname{dist}(s_i,u)=\operatorname{dist}(s_i,v)+w(\{u,v\}). Moreover, it can only be used in one direction (from the node closer to sis_i to the node further away from sis_i). For this reason, we can define a directed graph (V,Asi)(V,A_{s_i}) where AsiA_{s_i} contains all directed links whose undirected counterpart is contained in EE and where the link points away from sis_i. That is, we set Asi={(u,v)∣{u,v}∈E∧d(s,v)=d(s,u)+w({u,v})}A_{s_i}=\{(u,v)\mid\{u,v\}\in E\land d(s,v)=d(s,u)+w(\{u,v\})\}. If GG is already directed, this is just a subgraph of GG. We do the same for each tit_i and call the resulting link set AtiA_{t_i}. That is, Ati={(u,v)∣{u,v}∈E∧d(u,t)=d(u,t)+w({u,v})}A_{t_i}=\{(u,v)\mid\{u,v\}\in E\land d(u,t)=d(u,t)+w(\{u,v\})\}. Note that this reverses the arcs in case GG is directed.

The constraints of our mixed integer linear program for undirected graphs are given in Figure 6. It uses variables wviw_v^i for each i∈[k]i \in[k] and v∈Vv \in V, xaix_a^i for each i∈[k]i \in[k], and a∈Asia \in A_{s_i} and yaiy_a^i for each i∈[k]i \in[k] and a∈Atia \in A_{t_i}. Each of these variables can be assigned a rational number between 0 and rir_i. Finally, we have one variable ℓ≥0\ell\ge0 that restricts the maximum flow sent over any link in GG in a solution. The goal is to compute a solution which minimizes ℓ\ell. We mention that constraint (2) includes some terms that are not valid variables as not all edges have to be included in AsiA_{s_i} and/or AtiA_{t_i}. Those are of course not included in the sum, but we kept this presentation for the sake of readability.

∑v∈Vwvi=1for all i∈[k](1)\sum_{v\in V} w^i_v = 1 \qquad\text{for all } i \in[k] \tag*{(1)}
∑i∈[k](x(u,v)i+x(v,u)i+y(u,v)i+y(v,u)i)≤ℓ∀{u,v}∈E(2)\sum_{i\in[k]} \left(x^i_{(u,v)} + x^i_{(v,u)} + y^i_{(u,v)} + y^i_{(v,u)}\right) \le\ell\qquad\forall\{u,v\}\in E \tag*{(2)}
∑(si,v)∈Asix(si,v)i=ri−ri⋅wsii∀i∈[k](3)\sum_{(s_i,v)\in A_{s_i}} x^i_{(s_i,v)} = r_i - r_i \cdot w^i_{s_i} \qquad\forall i\in[k] \tag*{(3)}
∑(u,v)∈Asix(u,v)i=∑(v,u)∈Asix(v,u)i+ri⋅wvi∀v∈V∖{si},i∈[k](4)\sum_{(u,v)\in A_{s_i}} x^i_{(u,v)} = \sum_{(v,u)\in A_{s_i}} x^i_{(v,u)} + r_i \cdot w^i_v \qquad\forall v\in V\setminus\{s_i\}, i\in[k] \tag*{(4)}
∑(ti,v)∈Atiy(ti,v)i=ri−ri⋅wtii∀i∈[k](5)\sum_{(t_i,v)\in A_{t_i}} y^i_{(t_i,v)} = r_i - r_i \cdot w^i_{t_i} \qquad\forall i\in[k] \tag*{(5)}
∑(u,v)∈Atiy(u,v)i=∑(v,u)∈Atiy(v,u)i+ri⋅wvi∀v∈V∖{ti},i∈[k](6)\sum_{(u,v)\in A_{t_i}} y^i_{(u,v)} = \sum_{(v,u)\in A_{t_i}} y^i_{(v,u)} + r_i \cdot w^i_v \qquad\forall v\in V\setminus\{t_i\}, i\in[k] \tag*{(6)}

The basic idea is that constraint (1) guarantees that precisely one waypoint wiw_i is picked for each triple (si,ti,ri)(s_i,t_i,r_i). The flow between sis_i and wiw_i (between tit_i and wiw_i, respectively) is then captured by the assignment of xx (respectively yy) variables as follows. If we assign xu,vix^i_{u,v} some positive value pp, then this corresponds to sending pp units of flow from uu to vv. We do the same for yu,viy^i_{u,v}. Here, we use the arc in the opposite direction and produce a flow “from tit_i to wiw_i”. Constraints (3) and (5) then ensure that flow rir_i leaves si/tis_i/t_i 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 xx and yy variables to be assigned either 0 or 1, remove rir_i 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. [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. [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. [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. [4]S. A. Amiri, K.-T. Foerster, and S. Schmid. Walking through waypoints. Algorithmica, 2020.
  5. [5]F. Aubry. Models and algorithms for network optimization with segment routing. PhD thesis, 2020.
  6. [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. [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. [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. [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. [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. [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. [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. [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. [14]C. Filsfils, S. Previdi, L. Ginsberg, B. Decraene, S. Litkowski, and R. Shakir. Segment routing architecture. RFC, 8402:1–32, 2018.
  15. [15]R. W. Floyd. Algorithm 97: Shortest path. Communications of the ACM, 5(6):345, 1962.DOI
  16. [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. [17]B. Fortz and M. Thorup. Increasing Internet Capacity Using Local Search. Computational Optimization and Applications, 29(1):13–48, 2004.DOI
  18. [18]M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
  19. [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. [20]R. Hartert. Fast and scalable optimization for segment routing. PhD thesis, 2018.
  21. [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. [22]M. Middendorf and F. Pfeiffer. On the complexity of the disjoint paths problem. Combinatorica, 13(1):97–107, 1993.DOI
  23. [23]E. Moreno, A. Beghelli, and F. Cugini. Traffic engineering in segment routing networks. Computer Networks, 114:23–31, 2017.DOI
  24. [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. [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. [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. [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. [28]Leslie G. Valiant. A scheme for fast parallel communication. SIAM Journal on Computing, 11(2):350–361, 1982.
  29. [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. [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. [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

Paper details

vlnc:W_cnf3adxn
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents