arXiv CSopen access

Designing Capacitated Subnetworks for Shortest Path Routing

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

distributed-systems internet networking protocols

networking, internet, protocols, distributed systems

Designing Capacitated Subnetworks for Shortest Path Routing Markus Chimani # Theoretical Computer Science, Osnabrück University, Osnabrück, Germany Max Ilsen1 # Theoretical Computer Science, Osnabrück University, Osnabrück, Germany

arXiv:2605.06319v1 [cs.DS] 7 May 2026

Abstract In pursuit of higher energy efficiency in computer networks, one subfield of green traffic engineering aims at reducing the size of a network during times of low traffic, while still guaranteeing the ability to route all occurring demands. In this setting, we have to simultaneously solve a network design problem (choosing connections to deactivate) and a routing problem (routing paths in the active subnetwork, adhering to some routing protocol). Interestingly, there seems to be no available method to tackle the problem as a whole for the simplest (and still most commonly used) routing paradigm: shortest path routing. State-of-the-art methods either do not consider capacities, or assume that the routing paths should not change when deactivating network connections, or separate the problem into its two constituents, first solving the network design problem (using some estimators in lieu of the precise routing protocol) and only then the actual routing problem. In this paper, we present an algorithm to tackle the full combined problem exactly via a novel integer linear program, modeling dynamically changing shortest paths. To solve it, we need to devise a special-purpose column generation method. To speed up the solution process, we further propose additional provably strengthening constraints. Now having the means to yield true optimal solutions for (small) practical instances, we can for the first time give an in-depth experimental evaluation that includes the absolute quality (or quality loss) intrinsic to the above simplifying algorithms. It turns out that the arguably simplest method—first computing a routing, fixing it, and then turning off all superfluous connections—yields solutions surprisingly close to the true optimum in practice. When considering multiple different traffic demands, a recent traffic-oblivious approach (TOCA) performs best, while being comparatively straight-forward to implement. 2012 ACM Subject Classification Mathematics of computing → Network flows; Networks → Network design and planning algorithms Keywords and phrases Network design, Shortest path routing, Column generation, Experimental comparison Funding Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) grant 461207633 (CH 897/7-2).

Corresponding author.

Designing Capacitated Subnetworks for Shortest Path Routing

Introduction

Data traffic in modern backbone networks of Internet service providers (ISPs) showcases distinct peaks during the day and evenings, and lows at night and in the early morning [18,26]. Green traffic engineering approaches exploit this by turning off unnecessary resources during traffic lows, thereby saving energy and money. In this paper, we examine the emerging network design problems w.r.t. two different network models: in the setting of simplex (full-duplex) communication, we model a network as a (bi)directed graph G = (V, A) with positive (symmetric) arc capacities ccap : A → N≥1 and arc lengths len : A → N≥1 , where each vertex corresponds to a router and each arc (each pair of two opposite-facing arcs, respectively) to a link. Each link with a corresponding arc a ∈ A is understood to consist of λa ∈ N≥1 many connections, each of which provides a capacity of ccap and is capable of being deactivated separately. The full link, with all connections activated, thus has a capacity of fcap(a) := λa · ccap(a). A traffic demand of a vertex pair (s, t) ∈ V 2 is the amount of data (flow in standard algorithmic terms) that needs to be sent from s to t. All these demands are encoded in a (nonsymmetric) traffic matrix T ∈ N|V |×|V | . The terminal pairs K := {(s, t) ∈ V 2 | T (s, t) > 0} are those vertex pairs that have a positive associated traffic demand. There are several routing strategies: shortest-path routing (SPR), codified as Open Shortest Path First (OSPF), is the most commonly employed Interior Gateway Protocol (IGP) in real-world traffic engineering scenarios [22]. There, traffic is always sent along a shortest path w.r.t. the arc lengths len, which are usually called IGP weights or link metric. The newer, not yet as widely adopted, segment routing (SR) [12] chooses intermediary vertices (in many cases only one per traffic demand [1]) and routes traffic by concatenating shortest paths through them. In general, routing over arbitrary paths via multi-commodity flow (MCF) is not feasible due to hardware constraints [24]. We say T is SPR-routable (SR-routable, MCF-routable) in G if the respective routing protocol is able to satisfy all traffic demands without violating the capacities in G. In contrast to the other two, already testing whether T is SR-routable in G is NP-hard [16]. Given a network (G, ccap, len, λ) and a traffic matrix T , the Shortest-Path Network Design (SPND) problem consists of finding a vector χ ∈ N|A| with χa ≤ λa for all a ∈ A and minimum P a∈A χa such that T is SPR-routable in the subnetwork (G, ccap, len, χ). Intuitively, we say link a ∈ A has χa active connections, and aim to minimize the total number of active connections in the network. We may analogously define the Segment-Routing Network Design (SRND) problem w.r.t. SR-routability. The established problem probably most similar to SPND is Fixed-Charge Network Design [7], where there are some known algorithms based on bi-level programs when combined with shortest path routing [2, 15]. However, there, no capacities are enforced on any arcs, but the objective function sums fixed arc costs for activating an arc plus arc costs per unit of traffic routed over an arc. As such, these results are not applicable to the SPND scenario. To the best of our knowledge, there are no known approaches that directly tackle the true SPND or SRND problems, as the combination of deciding on a capacitated subnetwork simultaneously with solving the routing problem is quite intricate. We want to emphasize the major difficulty intrinsic already to shortest paths routings due to their non-monotonicity in subnetworks: Assume some traffic matrix T is not SPR-routable in some network; by deactivating a single link, even though this decreases the overall capacity of the network, T may become indeed SPR-routable, as traffic demands would now be routed over different paths with possibly higher residual capacity. This phenomenon is also known as Braess’s paradox [3]. In practice, the problems are typically considered in simplified forms: The most straight-

M. Chimani and M. Ilsen

forward approach is to stipulate that the shortest routing paths are not allowed to change in the subnetwork. We call this the Fixed-Shortest-Paths problem variant, marked by the prefix F-. Then F-SPND becomes trivial as one simply performs a standard SPR-routing and deactivates superfluous connections. In contrast, F-SRND still is NP-hard even with this stipulation, but there is an ILP-based exact algorithm [23] that can be used in practice for reasonably sized graphs. However, requiring to stick to the shortest-path routes of the full network effectively means that no link used by the initial routing can ever be completely deactivated, and much potential for energy saving seems wasted. Indeed, the optimal solution to F-SPND can be a factor of Θ(|V |) larger than an optimal solution to SPND: consider a network on a complete digraph with unit arc lengths and large capacities per connection; while for the latter a spanning cycle on O(|V |) arcs, with one connection each, may suffice, the former may have to retain at least one connection for all O(|V |2 ) many original links. The alternative idea is to split the problem into two subproblems that are solved sequentially: first, one establishes an SPR- or SR-routable subnetwork, then one computes the actual routing. The crux is, of course, in order to guarantee routability in the first step, one would already need to know the routing of step two. The key idea is to consider traffic-oblivious schemes in the first step. A traffic-aware approach requires the knowledge of a specific traffic matrix that should be routed in the subnetwork. This approach has the drawback of overfitting for this specific traffic matrix, when in reality, one only has (rough) estimates of typical traffic demands. Traffic-oblivious approaches mitigate this issue and simultaneously allow us to algorithmically split SPND (and SRND) into two phases as sketched above. Such approaches are based on the underlying assumptions that (a) the original network (i.e., with all connections active) is well-designed to route the traffic at peak hours, and (b) the traffic at low hours is, mostly, a scaled-down traffic of that at peak hours. The idea is to compute the subnetwork using only the estimated scale factor ϱ ∈ (0, 1), but no specific traffic matrix as additional input. Such approaches thus separate the problem of the network deactivation and the actual routing into separately addressable problems, but of course are only feasible in practice if the underlying assumptions (a) and (b) are (at least mostly) valid.

Our Contribution. In Section 2 we discuss the two known traffic-oblivious concepts CapacityPreserving Subgraph (CPS) and Traffic-Oblivious Cable Activation (TOCA), both of which still require to solve NP-hard problems: while there are established practical algorithms for the latter, we present the first algorithmic approach to compute exact solutions for the former. Up to now it was impossible to truly estimate the absolute quality performance of either of the described solution methods, as there is no known way to directly solve the NP-hard true SPND or SRND problems. In Section 3, we present the first exact approach to solve the former. It is based on a novel path-based integer linear program (ILP) formulation that requires a column generation scheme to solve. We further present strengthening inequalities that allow us to find provably optimal solutions for small to medium sized instances. Yet we can also conclude that already SPND, without the added complexity of SRND’s segment routing, is very challenging in practice. Our algorithm allows us to conduct the first practical study on established network benchmark sets to gauge how much potential is wasted by following the Fixed-Shortest-Paths approach or either of the traffic-oblivious approaches, see Section 4. The trivial F-SPND approach performs exceptionally well in practice; in the traffic-oblivious scenario, simple TOCA-algorithms perform best.

Designing Capacitated Subnetworks for Shortest Path Routing

Traffic-Oblivious Algorithms

2.1

Minimum Capacity-Preserving Subgraphs (CPS)

Given a (directed) graph G with arc capacities fcap : A → N≥1 , the Capacity-Preserving Subgraph (CPS) problem [5] asks for an arc-minimum subgraph H ⊆ G where the capacities cG (s, t) and cH (s, t) of minimum s-t-cuts (w.r.t. fcap) in G and H, respectively, differ by a factor of at most ϱ ∈ (0, 1), i.e., cH (s, t) ≥ ϱ · cG (s, t) for all (s, t) ∈ V 2 . As the value of a minimum s-t-cut is equal to the value of a maximum s-t-flow [10], we have that, for each (u, v) individually, we may send at least ϱ as much flow in H as in G. In [5], exact algorithms to compute such subgraphs for specific polynomial-time solvable instance families are established. For general instances, the possibility to adapt an ILP given by Dahl [8, 9] for Directed Survivable Network Design is briefly mentioned. We adapt the scenario to our setting, taking multiple connections per link and possibly full-duplex links into account, and yield the following ILP that allows us to devise the first algorithm solving CPS for general directed multigraphs. We call this algorithm cps in the following. For a vertex subset W ⊂ V , let δ − (W ) := {uv ∈ A : u ∈ W , v ̸∈ W } be all arcs leaving W . Observe that cG (s, t) is the size of a minimum-s-t-cut in G, where each arc a ∈ A has individual capacity λa · ccap(a). X min xa a∈A

ccap(a) · xa ≥ ϱ · cG (s, t)

∀(s, t) ∈ V 2 , ∀W ⊂ V : s ∈ W, t ∈ /W

(1a)

∀a ∈ A

(1b)

a∈δ − (W )

xa ∈ {0, 1, ..., λa }

The integer x-variables, whose sum we minimize, directly map to our solution description χ. In case of full-duplex links, we simply set xuv = xvu for each link {u, v}. The constraints (1a) for each (s, t) ∈ V 2 ensure that all s-t-cuts in the solution (and thus in particular also the minimum ones) are sufficiently large. Since the number of constraints (1a) is exponential in the input size, we need to facilitate a branch-and-cut scheme to speed up the ILP solving process. As per usual, we start with an empty set of (1a) constraints and, whenever an LP relaxation in the branch-andbound tree is solved, add constraints that are violated by the current model. Finding violated constraints is done via the following separation routine: For each a ∈ A, let ecap(a) := ccap(a) · x̂a be the effective capacity induced by the current solution x̂. Then, for each terminal pair (s, t) ∈ V 2 , we compute a maximum s-t-flow in (G, ecap) using Goldberg and Tarjan’s preflow algorithm [14], terminating as soon as a flow of value at least ϱ · cG (s, t) is found. If no such flow exists, we compute two violated cuts and add their respective constraints to the ILP model: the front cut close to s and the back cut close to t. To compute the front cut, we traverse arcs in the residual network (i.e., forward arcs with positive residual capacity and backward arcs with positive flow) via depth-first search (DFS) starting at s and mark all visited vertices. Arcs of the front cut are then exactly those arcs uv where u was marked and v can be reached via a backwards DFS starting at t in the original (not the residual) graph using only unmarked vertices. The back cut is identified analogously with the roles of s and t swapped and running DFSs in the respective opposite directions. This process guarantees that if we do not find any constraint to add, then indeed all constraints are satisfied even if not actively generated into the model. During separation, among cuts with the same cut value, we prefer those of lower cardinality as this gives us a slight speed advantage. We achieve this by adding a miniscule positive

M. Chimani and M. Ilsen

value ε < 1/|A| to each arc capacity. This choice of ε guarantees that if one cut has a smaller unperturbed capacity than another, the same still holds after perturbation. We also include another optimization: Before starting the branch-and-cut procedure, we precompute for each arc a = st ∈ A, whether the removal of some ψa -many connections of a would lower the maximum s-t-flow in G to a value below ϱ · cG (s, t). If so, we can add the constraints xa ≥ ψa + 1. Vertex pairs (s, t) ∈ V 2 whose capacity requirement is already reached by these lower bounds never have to be considered during the separation routine.

2.2

Traffic-Oblivious Cable Activation (TOCA)

In the Traffic-Oblivious Cable Activation (TOCA) problem [6, 19], we ask for a subnetwork with minimum number of active connections (again encoded by a vector χ ∈ NA ) and the following property: for every possible traffic matrix T that is MCF-routable in the full network (G, ccap, len, λ), the scaled-down traffic matrix ϱ · T must be MCF-routable in (G, ccap, len, χ). Solving the underlying ILP turns out to be too time-consuming in practice [19], so we implement two algorithm variants proposed in [19] based on LP rounding, which are supposed to yield close-to-optimum solutions: First, a max( ϱ·λ1min , 2)-approximation, where λmin := mina∈A λa is the minimum number of connections between any two connected routers; we call this algorithm toca. It consists of computing a specific MCF LP where the arc utilization is minimized, and rounding up the resulting fractional variable values xa for each arc a ∈ A to obtain the respective number χa := ⌈xa ⌉ of active connections. Second, we also implemented a heuristic recommend in [19] to further improve solutions produced by toca; we call it toca+ : After solving the MCF LP, set the lower (upper) bound of each x-variable to the floor (ceiling, resp.) of its current value. Then, as long as the solution is non-integral, choose an arc a with the smallest difference of its x-variable to the next higher integer value, fix the x-variable to that value, and recompute the LP. As this heuristic computes up to |A| many LPs instead of only one, it is a lot slower than toca. Yet, it retains the approximation guarantee and produces feasible solutions with significantly fewer connections.

Exact Shortest-Path Network Design

We now devise the first ILP-based approach to solve the full SPND problem exactly. We make two assumptions: First, the traffic demands are SPR-routable in the full network, without any deactivations. As we consider the traffic demands to correspond to some low-traffic phase for which we want to deactivate superfluous connections, the fully activated network can safely be assumed to be capable of handling higher traffic during peak phases. Second, we assume that shortest paths are unique, i.e., for any vertex pair (s, t) ∈ V 2 , the arc length function len induces a total order ≺ on the s-t-paths. We can ensure this by enforcing an arbitrary tie-breaking between s-t-paths of the same length. We may start with considering the following ILP for SPND. For any (s, t) ∈ K, let Ps,t denote the set of all s-t-paths in G.

Designing Capacitated Subnetworks for Shortest Path Routing

min

a∈A

zP ≥ 1

∀(s, t) ∈ K

(2a)

zP ≤ ya

∀(s, t) ∈ K, a ∈ A

(2b)

∀a ∈ A

(2c)

∀(s, t) ∈ K, P ∈ Ps,t

(2d)

ya ≤ xa

∀a ∈ A

(2e)

xa ≤ λa · ya

∀a ∈ A

(2f)

xa ∈ {0, 1, . . . , λa }

∀a ∈ A

(2g)

ya ∈ {0, 1}

∀a ∈ A

(2h)

zP ∈ {0, 1}

∀(s, t) ∈ K, P ∈ Ps,t

(2i)

P ∈Ps,t

X P ∈Ps,t : a∈P

T (s, t) · zP ≤ ccap(a) · xa

(s,t)∈K P ∈Ps,t : a∈P

|P | −

X a∈P

ya ≥

zP ′

P ′ ∈Ps,t : P ≺P ′

The integer variables xa encode how many connections per arc are active. They directly map to our solution vector χ and are thus minimized. The binary variables ya indicate whether any connection along a is active, in which case we may say the arc is active. This property is enforced via (2e) and (2f). For every (s, t) ∈ K, we have a binary zP variable for each P ∈ Ps,t , which indicates whether P is active, i.e., whether it is the shortest s-t-path in the solution subgraph. Constraint (2a) establishes that each terminal pair is connected by an active path in the solution; constraint (2b) guarantees that all arcs on an active path are active as well; constraint (2c) ensures that the total traffic routed over any arc does not exceed its capacity. Correct shortest path routing is achieved via constraint (2d): it ensures that, when all arcs on an s-t-path P are active, no s-t-path longer than P can be active. Above, we considered general simplex-connections; for full-duplex links, we simply enforce xst = xts and yst = yts for all st ∈ A. We could also enforce zP = zP ′ for all paths P and their respective reverse paths P ′ , however, a pilot study showed that this only slows the algorithm down when using the strengthening inequalities of Section 3.2. In any case, we obtain the LP relaxation by replacing constraints (2g)–(2i) by: 0 ≤ xa ≤ λa

∀a ∈ A

(2g’)

0 ≤ ya ≤ 1

∀a ∈ A

(2h’)

∀(s, t) ∈ K, P ∈ Ps,t

(2i’)

0 ≤ zP

The constraint (2b) already implies zP ≤ 1 for all paths P . Our ILP contains a variable for every path in the input digraph and thus the total number of variables is exponential in |A|. This prohibits to straight-forwardly solve the ILP with standard means. We follow the branch-and-price paradigm [20]: Starting with an initial model that only contains a subset of the variables (and constraints), we repeatedly solve the LP relaxation and add variables not yet in the model whose addition may allow to improve the current solution value (a process called column generation or pricing). When the latter

M. Chimani and M. Ilsen

fails, we resort to branching, i.e., we pick any variable with fractional value f and generate two subproblems which enforce ≤ ⌊f ⌋ or ≥ ⌈f ⌉ on the domain of the variable, respectively. We observe that in our ILP we never have to enforce integrality on the z-variables: whenever we have an optimal solution with integral x- and y-variables, it is never beneficial to choose a non-binary value for any z-variable. Thus, our scheme never branches on z-variables.

3.1

Column Generation

Our initial model contains all x- and y-variables. For every terminal pair (s, t) ∈ K, let ′ Ps,t ⊆ Ps,t denote the set of s-t-paths whose z-variables are in the current model. Initially, ′ Ps,t contains the five shortest s-t-paths in G. Whenever a new LP solution is found, we start our pricing routine to identify and add beneficial z-variables. When adding a variable to the model, observe that this automatically also adds the corresponding constraint (2d) and ′ updates the other constraints according to the now larger subsets Ps,t . We consider the dual program to our LP. As per usual, a variable is (potentially) beneficial if and only if its dual constraint is violated by the current dual solution. If no such variable exists, we have found an LP solution that is optimal w.r.t. the full LP, not only the current model [20]. For brevity, and since it can canonically be obtained from the above LP, we refrain from presenting the full dual program here. We are only interested in the dual constraints corresponding to our (primal) z-variables. Let α, β, γ, and δ be the dual variables corresponding to the constraints (2a), (2b), (2c), and (2d), respectively. Recall that there are no explicit upper bound constraints zP ≤ 1, so the dual constraint is: X X X αs,t − βs,t,a − T (s, t) · γa − δs,t,P ′ ≤ 0 ∀(s, t) ∈ K, P ∈ Ps,t . (3) a∈P

a∈P

P ′ ∈Ps,t : P ′ ≺P

Consequently, for each terminal pair (s, t) ∈ K, we search for a path P that violates this dual constraint. At the same time, we aim to find paths of the optimal solution early on to speed up the solving process, and such paths tend to be short w.r.t. the arc length len. Hence, our pricing problem consists of finding a shortest path (w.r.t. len) among those paths whose total dual cost is below the limit αs,t . This kind of pricing problem, the constrained shortest path (CSP) problem, is commonly found in column generation algorithms for network design problems such as spanners [27]. However, there is a crucial difference in our pricing problem that complicates the process: Since the variables δs,t,P ′ are not only dependent on the terminal pair (s, t) but also on other paths P ′ we must define our dual cost function P P dcost(a) := a∈P βs,t,a + T (s, t) · a∈P γa , for all a ∈ A, without them. Since all dual values ≤dcost are non-negative, the set Ps,t of dcost-feasible s-t-path is thus a strict superset of those paths that have a truly violated dual constraint. It also contains paths that are not violated and thus may already be in our current model. In particular, the shortest path (w.r.t. len) ≤dcost among Ps,t may indeed be of that type. In our scheme, we need to account for this to ≤dcost ′ ensure that we identify a path of Ps,t \ Ps,t if any exist. We solve the pricing problem for each terminal pair (s, t) ∈ K using a label setting algorithm: First, we may abort the algorithm immediately if already the previous attempt (w.r.t. (s, t)) was unsuccessful and we can further infer from the total reductions in arc costs and cost limit that a new path adhering to the new cost limit cannot exist. Otherwise, for all vertices v ∈ V , we precompute the cost dcost(v, t) of a dcost-minimum v-t-path (disregarding len) and the length len(s, v) of a shortest (w.r.t. len) s-v-path (disregarding dcost). Then, during the actual path computation, we manage both a global priority queue Q with vertices and a heap Hv with labels at every vertex v. Each such label ℓ corresponds to a path Pℓ from s P P to vertex v(ℓ) with length len(ℓ) := a∈Pℓ len(a) and dual cost dcost(ℓ) := a∈Pℓ dcost(a).

Designing Capacitated Subnetworks for Shortest Path Routing

3 Ps,t 2 Ps,v 2 Ps,t

1 Ps,v

1 Ps,t

Figure 1 SPND instance considered in the proof of Theorem 1. Arcs Athin (Athick ) are drawn as thin (thick) lines and have capacity 1 (2, respectively).

When queried for its top element, a heap Hv returns the label ℓ with the lexicographical minimum according to (len(ℓ) − len(s, v(ℓ)), len(s, v(ℓ)), dcost(ℓ)), and Q returns the vertex with the lexicographical minimum label among all heaps. We thus first process one label per vertex v in the order of len(s, v), i.e., in the order of Dijkstra’s algorithm [11], before moving on to other labels. This allows us to find the shortest (w.r.t. len) path violating (3) first. While Q is non-empty, we pop the top vertex v(ℓ) from Q and the top label ℓ from Hv(ℓ) , reinserting v(ℓ) into Q only if Hv(ℓ) contains more labels to process. If v(ℓ) = t, we check ′ whether path Pℓ ∈ Ps,t already, and accordingly discard ℓ or return Pℓ . Otherwise, we scan all of v(ℓ)’s neighbors w where w is not yet in Pℓ (to avoid cycles) and w satisfies dcost(ℓ) + dcost(v(ℓ)w) + dcost(w, t) < αs,t . Then, we create a new label ℓ′ where Pℓ′ is obtained by appending v(ℓ)w to Pℓ , and insert ℓ′ into Hw (and w into Q if it is not yet contained). In contrast to other CSP problems, we cannot simply discard a label ℓ′ if it is dominated (i.e., another label in Hv(ℓ′ ) has smaller cost and length), as dominating labels may only ′ expand to s-t-paths that already are in Ps,t . However, to speed up the algorithm, we run the pricing routine for (s, t) once discarding dominated labels (and thus avoiding the need to explicitly check for cycles), and only if no new paths are found this way, we run it again without the domination check.

3.2

Strengthening Inequalities

A (feasible) constraint polyhedrally strengthens [20, Def. 13.2] a minimizing ILP formulation if there are instances such that the value of the corresponding LP relaxation increases when adding the constraint to the model. In other words, while not necessary from the point of integer feasible solutions, adding the constraint to the model can yield stronger bounds in the branch-and-bound framework, and thus potentially lead to faster running times. Let P ⟨u, v⟩ denote the subpath of a path P that starts at vertex u and ends at vertex v. While not necessary to model SPND, these inequalities strengthen the ILP formulation by establishing the well-known property that subpaths of shortest paths are also shortest paths: zP ⟨s,v⟩ ≥ zP

zP ⟨v,t⟩ ≥ zP

∀(s, t) ∈ K, P ∈ Ps,t , v ∈ V (P )

(4)

▶ Theorem 1. Constraint (4) is polyhedrally strengthening, even when all arc lengths are 1. Proof. Consider the digraph G = (V, A) and its vertices s, v, t ∈ V as shown in Figure 1. i i For i ∈ {1, 2}, let Ps,v be the unique s-v-path containing exactly i arcs and Ps,t the i 3 unique s-t-path containing Ps,v ; further, let be Ps,t the last remaining s-t-path. Lastly, let S i Athin := i∈{1,2} Ps,v be the three arcs on s-v-paths and Athick := A \ Athin . Consider the

M. Chimani and M. Ilsen

SPND instance on network (G, ccap, len, λ) and traffic T with len(a) = λa = 1, ∀a ∈ A, and   (  2 if (u, w) = (s, t), 1 if a ∈ Athin , ccap(a) = fcap(a) = T (u, w) = 1 if (u, w) = (s, v),  2 if a ∈ Athick ;  0 otherwise. The instance allows a feasible integer solution (of value 9) by picking precisely the single 1 3 arc on Ps,v and all arcs on Ps,t . The following fractional solution (x̄, ȳ, z̄) has only objective value 8.5 and satisfies all constraints of the original LP relaxation:  1  ( if P = Ps,v ,  1 1 if a ∈ Athin , 2 3 x̄a = ȳa = z̄P = 1/2 if P ∈ {Ps,t , Ps,t }, 1/2 if a ∈ A   thick ; 0 otherwise. 2 2 , adding constraint (4) would cut off this solution. Since z̄Ps,v < z̄Ps,t It remains to argue that the LP including (4) enforces an objective value strictly larger than 8.5. Since λ = 1, we have xa = ya for each a ∈ A by (2e) and (2f). A key ingredient is that zP , 0 ≤ zP ≤ 1, represents a traffic of volume zP if P is an s-v-path (since T (s, v) = 1), i but a traffic of volume 2zP if P is an s-t-path (since T (s, t) = 2). Let ai ∈ Ps,v , i ∈ {1, 2}. By the capacity constraint (2c) for ai we have i i . xai ≥ zPs,v + 2zPs,t

(5)

1 2 By the shortest-path constraint (2d) for Ps,v we get zPs,v ≤ 1 − xa1 and together with (5) for 2 1 − 2zP 1 . Since zP 1 + zP 2 1 a1 we have zPs,v ≤ 1 − zPs,v ≥ 1 this simplifies to 0 ≤ −2zPs,t and s,v s,v s,t 1 2 2 . Let zP 2 2 consequently zPs,t = 0. By the strengthening (4), we have zPs,t ≤ zPs,v − zPs,t = s,v 2 1 2 ε ≥ 0. For any a2 ∈ Ps,v we can use (5) to thus deduce xa2 ≥ 3zPs,t + ε. For a1 ∈ Ps,v 1 2 2 − ε. Observe that for any arc a ∈ A, we have we know xa1 = zPs,v ≥ 1 − zPs,v = 1 − zPs,t xa = ya at least large enough to satisfy constraint (2c), where exactly the arcs Athick have capacity 2. So we can deduce the objective function value as X X X X X xa = xa + xa + xa + xa a∈A

3 a∈Ps,t

2 \P 2 a∈Ps,t s,v

2 a∈Ps,v

3 3 /2) ≥ |Ps,t | · (T (s, t) · zPs,t

1 a∈Ps,v

2 2 2 /2) |Ps,t \ Ps,v | · (T (s, t) · zPs,t

2 1 2 + ε) + |P 2 − ε) + |Ps,v | · (3zPs,t s,v | · (1 − zPs,t 2 ) + 3zP 2 + 2(3zP 2 + ε) + 1(1 − zP 2 − ε) = 9 + ε ≥ 9. = 8(1 − zPs,t s,t s,t s,t

◀

We do not need to add constraints for |P ⟨s, v⟩| = 1 and |P ⟨v, t⟩| = 1 whenever the arc length function len is one-shortest, i.e., if two vertices s, t ∈ V are connected by a direct arc st ∈ A, there is no shorter path than st. ▶ Observation 2. For one-shortest arc lengths, the constraints (4) for |P ⟨s, v⟩| = 1 and |P ⟨v, t⟩| = 1 are already implied by the original LP relaxation. Proof. We only argue the case |P ⟨s, v⟩| = 1; |P ⟨v, t⟩| = 1 is analogous. Let a = sv be the first edge on some path P ∈ Ps,t with |P | > 1. Clearly, a itself is a path P ′ ∈ Ps,v , and so (2b)

(2d)

zP ≤ ya ≤ 1 −

X P̄ ∈Ps,v : P ′ ≺P̄

(2a)

zP̄ ≤ 1 − 1 − zP ′ −

zP̂ ≤ zP ′ ,

P̂ ∈Ps,t : P̂ ≺P ′

where the last sum evaluates to 0 since there are no path P̂ ≺ P ′ as len is one-shortest.

◀

Designing Capacitated Subnetworks for Shortest Path Routing

Experiments

We consider our column generation scheme spnd for exact solutions of SPND (Section 3) together with the traffic-oblivious algorithms cps, toca, and toca+ presented in Section 2. Furthermore, we consider the trivial algorithm spnd ◦ that computes an optimal solution for F-SPND. All algorithms are implemented in C++, using functionality of the Open Graph Drawing Framework (OGDF [4], www.ogdf.net) release ‘2025.10 Foxglove’. The implementations will be made public as part of the next OGDF release but are already available—alongside the complete dataset and detailed results discussed herein—at tcs.uos. de/research/spnd. The code is compiled with GCC 12.2.0 using optimization level -O3. Each computation is performed on a single physical processor of a Xeon Gold 6134 CPU (3.2 GHz) running Debian GNU/Linux 12 ‘Bookworm’ with Linux kernel version 6.1.0-18amd64. LP computations are performed using Gurobi 11.0.1; spnd uses SCIP 9.0.0 as a branch-and-price framework. We enforce a time limit of 10 minutes for each run.

4.1

Instances

We use the three instance sets of the REPETITA framework for ‘repeatable experiments on Traffic Engineering algorithms’ [13], which contain network topologies including arc capacities and lengths, as well as traffic matrices that are designed for a maximum link utilization (MLU) of 90% when routed via MCF in the original network topology. DEFO [17]: Nine network topologies with 50–315 vertices and 276–1944 arcs, synthetically generated for benchmarking traffic engineering algorithms, and one traffic matrix each. Rocketfuel [28]: Six network topologies with 79–315 vertices and 294–1944 arcs, collected using Internet mapping techniques and each one accompanied by five traffic matrices. Topology Zoo (TZ) [21]: 260 real-world topologies with 4–197 vertices and 8–490 arcs as reported by official company websites, each one accompanied by five different traffic matrices. Since the original data set does not contain arc lengths, we consider it once with unit arc lengths and once with arc lengths that are inversely proportional to the arc capacities, as these are the standard link metrics used in practice [13]. For each combination of network topology and traffic matrix, we consider the network topology once in the simplex and once in the full-duplex communication setting. We preprocess each instance by removing all parallel arcs, enforcing the same arc length in both directions of each link for the full-duplex setting, and scaling down the traffic matrix such that SPR on the instance produces an MLU of exactly 1. We consider two further parameters for each network topology: the number of connections per link λ ∈ {1, 5}, and the retention ratio ϱ ∈ {0.3, 0.5, 0.7}. Given an SPR-feasible traffic matrix T for the full network, we consider the SPND instance with scaled matrix ϱT to simulate phases of low and medium traffic. Recall that cps, toca, and toca+ are oblivious to the traffic matrix (and the arc lengths) but require ϱ as an input parameter.

4.2

Results

We examine the implemented algorithms w.r.t. success rate, running time, number of active connections in the solution, and maximum link utilization. Our main observations hold across all instance sets; also, the choice of arc lengths for the TZ instances has surprisingly no significant impact on the results. In the following, we often focus on the largest set TZ.

M. Chimani and M. Ilsen

simplex, λ = 5, % = 0.3

simplex, λ = 5, % = 0.7

102

running time (s)

102

101

100

101

100

0 0

100

solved instances (%)

full-duplex, λ = 5, % = 0.3

full-duplex, λ = 5, % = 0.7

100

102

running time (s)

102

running time (s)

cps toca toca + spnd spnd ◦

101

100

101

100

0 0

solved instances (%)

100

solved instances (%)

Figure 2 Performance plots for representative parameter settings.

100

Designing Capacitated Subnetworks for Shortest Path Routing

101 40

running time (s)

cps toca toca + spnd spnd ◦

102

number of network topologies

102

running time (s)

simplex, λ = 5, % = 0.7

60 101 40

number of network topologies

simplex, λ = 5, % = 0.3

100

90 10 5 12 0 13 5 15 > 0 15 0

|V |

full-duplex, λ = 5, % = 0.3

full-duplex, λ = 5, % = 0.7

102

running time (s)

number of network topologies

60 101

102

60 101 40

20 100

number of network topologies

running time (s)

20 100

|V |

75 90 10 5 12 0 13 5 15 > 0 15 0

45 60

15 30

75 90 10 5 12 0 13 5 15 > 0 15 0

45 60

15 30

|V |

Figure 3 Median running times for representative parameter settings. Timeouts are not displayed.

M. Chimani and M. Ilsen

spnd

spnd ◦

cps

toca

toca+

spnd

spnd ◦

cps

toca

toca+

ϱ=0.3

ϱ=0.5

179

117

116

ϱ=0.7

118

ϱ=0.3

118

ϱ=0.5

ϱ=0.7

λ=1

full-duplex

λ=5

λ=1

simplex

Figure 4 Median running times (in sec) over all ‘large’ networks (|V | > 150); ‘TO’ denotes timeout.

Success Rate and Running Time. (cf. Figures 2–4) A clear hierarchy of the algorithms emerges: Due to its simplicity, spnd ◦ is almost always the fastest algorithm, solving every instance in every parameter setting within one second. The algorithm is closely followed by toca, which only has to solve a single LP and thus always terminates on TZ instances in less than five (ten) seconds for the full-duplex (simplex, resp.) setting. Even the largest DEFO and Rocketfuel topologies were usually solvable by toca in the full-duplex setting whereas it reached the time limit otherwise. This is because toca was designed to leverage structural properties of full-duplex networks to speed up computations. The costly post-processing provided by toca+ operates more quickly in the simplex setting due to its greedy-like nature but still raises the running time significantly to several hundred seconds on large instances. While the setting of λ has nearly no effect on the running time of spnd ◦ , cps is highly sensitive to these parameters: As it is designed for general digraphs, it has trouble with the full-duplex setting, where it already reaches the time limit for TZ instances with 50–100 vertices. Unsurprisingly, cps is faster when considering only λ = 1 connection per link. It is also faster for larger ϱ (and indeed very quick for λ = 1, ϱ = 0.7 in both communication settings), but degrades rapidly for smaller ϱ. We speculate that this is due to simpler capacity interactions between different terminal pairs when more connections are active. The most complicated algorithm spnd performs worst not only w.r.t. running time but indeed already w.r.t. the success rate, reaching the time limit of 10 minutes for 57% of all TZ runs. Pilot studies showed that a larger time limit does not significantly improve the situation. Generally, however, spnd can find provably optimal solutions for instances with up to roughly 80 vertices in both communication settings. Due to its size, the ILP is inherently difficult to solve even when using our column generation scheme. While the pricing routine is computationally cheap (only running for half a minute within the 10 minute time frame), a large amount of paths must be added to the ILP until a solution without violated dual path constraints is found. Setting λ = 5 surprisingly lowers the running time, with several TZ topologies containing 50–90 vertices only being solved for λ = 5 but not λ = 1. Presumably, a higher number of connections allows spnd to find good solutions that do not deactivate links completely, thus limiting the search of different possible routing paths.

Designing Capacitated Subnetworks for Shortest Path Routing

simplex, λ = 1, % = 0.5

simplex, λ = 1, % = 0.5, non-timeout spnd only

cps toca toca + spnd spnd ◦

40 60

30 40 20

number of network topologies

percentage of deactivated connections (%)

100

number of network topologies

percentage of deactivated connections (%)

100

20 10

100

75 >

90 10 5 12 0 13 5 15 > 0 15 0

|V |

simplex, λ = 5, % = 0.5

simplex, λ = 5, % = 0.5, non-timeout spnd only 100

80 30

20 40 15

number of network topologies

percentage of deactivated connections (%)

10 20 5

|V |

75 >

75 90 10 5 12 0 13 5 15 > 0 15 0

45 60

15 30

|V |

Figure 5 Median percentage of deactivated connections for representative parameter settings. On the left, spnd is not shown; on the right, only instances where spnd did not timeout are considered.

M. Chimani and M. Ilsen

simplex, λ = 1, % = 0.5, non-timeout spnd only

2.00

60 1.25

1.00 40 0.75

0.50

1.50

40 1.25

MLU

1.50

1.75

number of network topologies

1.75

MLU

cps toca toca + spnd spnd (opt.) spnd ◦ spnd ◦ (opt.)

2.00

1.00

0.75

number of network topologies

simplex, λ = 1, % = 0.5

0.50

10 0.25

0.25

75 >

0.00

90 10 5 12 0 13 5 15 > 0 15 0

0.00

|V |

simplex, λ = 5, % = 0.5

simplex, λ = 5, % = 0.5, non-timeout spnd only 40

2.00

2.00 35 80

1.75

|V |

0.00

number of network topologies

75 90 10 5 12 0 13 5 15 > 0 15 0

45 60

15 30

0.00

0.25

0.50

0.75

20 1.00

25 1.25

MLU

1.00

1.50

MLU

60 1.25

number of network topologies

30 1.50

|V |

Figure 6 Median MLU for representative parameter settings. On the left, spnd is not shown; on the right, only instances where spnd did not timeout are considered. Dotted lines, labeled with ‘(opt.)’, show the MLU only w.r.t. to the traffic matrix that spnd or spnd ◦ was optimized for.

Designing Capacitated Subnetworks for Shortest Path Routing

Number of Active Connections (Solution Value). (cf. Figure 5) The great weakness of spnd ◦ becomes apparent for λ = 1, where it is only able to deactivate those connections that do not belong to links on any shortest path. In practice, that means that there are only few, large instances where it can deactivate any connection at all. In contrast, spnd shows the maximum number of connections that can be deactivated while still guaranteeing SPR-routability. This value has a very high variance across instances, depending greatly on the specific topology (recall that we only know this value for the comparably small instances due to spnd’s inapplicability to larger instances). Clearly, we require more connections the larger the value of ϱ is. The same holds when switching from simplex to full-duplex communication, as the deactivation of a connection requires that it is not needed in either direction. In the simplex (full-duplex) setting, a maximum of 64% (55%) of connections can be deactivated for ϱ = 0.3, and 53% (41%, resp.) for ϱ = 0.7. The traffic-oblivious algorithms cps, toca, and toca+ often surpass the upper bound given by spnd, in particular for larger instances and at lower ϱ-values: since they optimize for individual max-flows or MCF-routing respectively, they often return subnetworks that do not allow for a shortest-path routing anymore (see the MLU comparison below). The results shift greatly for λ = 5, which is the more realistic scenario since backbone networks contain multiple connections per link [24]: Here, spnd ◦ suggests some of the highest energy savings, deactivating only 1.1 percentage points fewer connections than spnd, which—depending on the communication setting and ϱ—deactivates a median of 67–80% of connections. The traffic-oblivious algorithms deactivate much fewer connections since they aim to allow for a feasible routing even if the traffic changes. Their reduction rates show very little variance in deactivated connections across network topologies, with toca deactivating 60% (40%, 20%) for ϱ = 0.3 (0.5, 0.7, resp.), and toca+ (cps) deactivating only a median of 2 (4, resp.) percentage points more connections. Maximum Link Utilization. (cf. Figure 6) It is only beneficial to deactivate connections if this does not inhibit the routability of the traffic. Hence, we analyze the maximum link utilization (MLU), i.e., the maximum ratio between the total traffic over an arc and its capacity in the computed subnetwork w.r.t. shortest-path routing. An MLU below 1.0 guarantees SPR-routability. Values above 1.0 suggest that one needs to consider a lower ϱ compared to the actually measured traffic decrease (which is typically done for safety margins in practice anyhow [25]). Of course, spnd and spnd ◦ are optimized w.r.t. one specific traffic matrix ϱT , allowing them to always obtain an MLU below 1.0 on ϱT . We show the median of these optimized MLUs as dotted lines. To allow a fair comparison between the traffic-aware and -oblivious approaches, given a ϱT -specific solution by spnd and spnd ◦ , we also evaluate the median MLU across all five (ϱ-scaled) traffic matrices for each instance. Be aware that in rare occurrences, a traffic-aware algorithm may disconnect the network due to missing traffic between the connected components, leading to an infinite MLU on other traffic matrices. Naturally, the median MLU of the algorithms is strongly correlated to the number of connections they deactivate. With increasing ϱ, the median MLU also increases but showcases a lower variance across algorithms. For λ = 1, the median MLU is also always below 1.0 for all algorithms, but the per-instance MLU for spnd and cps sometimes already surpass this threshold, suggesting that these algorithms deactivate connections too aggressively for traffic-oblivious scenarios. This effect becomes more apparent for λ = 5 (and the simplex setting in particular), where both traffic-aware algorithms and cps almost always surpass the MLU-threshold of 1, with spnd reaching higher MLU values than spnd ◦ (as it was more successful in deactivating links). The MLU of cps varies wildly, even reaching values above 2.0.

M. Chimani and M. Ilsen

In contrast, toca stays reliably in the 0.75–0.90 range and toca+ only slightly above that, occasionally peaking above 1. Key Takeaways. The traffic-oblivious algorithm with the best compromise between many deactivated connections and acceptable MLU is toca+ . In comparison, toca serves as a useful alternative when a low running time is required. The algorithm cps is clearly the wrong tool for the job as it is rather slow while taking neither the simultaneous routing of all traffic demands nor the routing via shortest paths into account, leading to extremely high MLUs. While unsuited for general traffic-oblivious scenarios due to high MLUs, the trivial-toimplement and blazing fast spnd ◦ is the best choice for traffic-aware scenarios, which may include scenarios were the variance between different expected traffic matrices is very small. It deactivates close-to-optimal many connections and never surpasses an MLU of 1. The exact algorithm spnd turned out to be a worthwhile tool: only by it, we were able to establish that spnd ◦ indeed finds solutions very close to the optimum. Yet, this comparably small amount of additionally deactivated connections by spnd does not justify its exorbitant running times and effortful implementation, so it does not lend itself to practical scenarios. Overall, our evaluation gives credence to network design research that uses precomputed shortest paths in the input network as a basis for their routing [23].

Outlook

Our proposed ILP for SPND uses the simplifying assumption that the shortest path for any (s, t) ∈ K is unique. Practical protocols like OSPF deal with non-unique shortest paths by implementing Equal Cost Multipath (ECMP), i.e., whenever shortest paths diverge, the traffic is split up equally among them. Modeling this in a (still manageable) ILP is extremely difficult, so computationally less expensive strategies to deal with this problem would be desirable. One could also ask for extending our model to SRND, i.e., using a segment-routing protocol. However, the fact that our current model is already at the border of what is practically feasible to compute, this seems out of reach as of yet.

Designing Capacitated Subnetworks for Shortest Path Routing

References 1

3 4

5 6

8 9 10 11 12 13

14 15

Randeep Bhatia, Fang Hao, Murali S. Kodialam, and T. V. Lakshman. Optimized network traffic engineering using segment routing. In Proc. INFOCOM 2015, pages 657–665. IEEE, 2015. doi:10.1109/INFOCOM.2015.7218434. Ikram Bouras, Rosa Figueiredo, Michael Poss, and Fen Zhou. On two new formulations for the fixed charge network design problem with shortest path constraints. Comput. Oper. Res., 108:226–237, 2019. doi:10.1016/J.COR.2019.04.007. Dietrich Braess. Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung, 12(1):258–268, 1968. doi:10.1007/BF01918335. Markus Chimani, Carsten Gutwenger, Michael Jünger, Gunnar W. Klau, Karsten Klein, and Petra Mutzel. The Open Graph Drawing Framework (OGDF). In Handbook on Graph Drawing and Visualization, pages 543–569. Chapman and Hall/CRC, 2013. doi:10.1201/b15385. Markus Chimani and Max Ilsen. Directed capacity-preserving subgraphs: hardness and exact polynomial algorithms. Acta Informatica, 62(10), 2025. doi:10.1007/s00236-024-00475-7. Markus Chimani and Max Ilsen. Traffic-oblivious multi-commodity flow network design. In Proc. ISAAC 2025, LIPIcs, pages 19:1–19:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.ISAAC.2025.19. Teodor Gabriel Crainic, Michel Gendreau, and Bernard Gendron, editors. Network Design with Applications to Transportation and Logistics. Springer International Publishing, 2021. doi:10.1007/978-3-030-64018-7. Geir Dahl. The design of survivable directed networks. Telecommun. Syst., 2(1):349–377, 1993. doi:10.1007/BF02109865. Geir Dahl. Directed steiner problems with connectivity constraints. Discret. Appl. Math., 47(2):109–128, 1993. doi:10.1016/0166-218X(93)90086-4. George Bernard Dantzig and Delbert Ray Fulkerson. On the Max-Flow Min-Cut Theorem of Networks, pages 215–222. Princeton University Press, 2016. doi:10.1515/9781400881987-013. Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269–271, 1959. doi:10.1007/BF01386390. Clarence Filsfils, Stefano Previdi, Les Ginsberg, Bruno Decraene, Stephane Litkowski, and Rob Shakir. Segment routing architecture. RFC, 8402:1–32, 2018. doi:10.17487/RFC8402. Steven Gay, Pierre Schaus, and Stefano Vissicchio. REPETITA: repeatable experiments for performance evaluation of traffic-engineering algorithms. CoRR, abs/1710.08665, 2017. arXiv:1710.08665. Andrew V. Goldberg and Robert Endre Tarjan. A new approach to the maximum-flow problem. J. ACM, 35(4):921–940, 1988. doi:10.1145/48014.61051. Pedro Henrique González, Luidi Simonetti, Philippe Michelon, Carlos Alberto de Jesus Martinhon, and Edcarllos Santos. A variable fixing heuristic with local branching for the fixed charge uncapacitated network design problem with user-optimal flow. Comput. Oper. Res., 76:134–146, 2016. doi:10.1016/J.COR.2016.06.016. Renaud Hartert, Pierre Schaus, Stefano Vissicchio, and Olivier Bonaventure. Solving segment routing problems with hybrid constraint programming techniques. In Proc. CP 2015, volume 9255 of LNCS, pages 592–608. Springer, 2015. doi:10.1007/978-3-319-23219-5_41. Renaud Hartert, Stefano Vissicchio, Pierre Schaus, Olivier Bonaventure, Clarence Filsfils, Thomas Telkamp, and Pierre François. A declarative and expressive approach to control forwarding paths in carrier-grade networks. In Proc. SIGCOMM 2015, pages 15–28. ACM, 2015. doi:10.1145/2785956.2787495. Avinatan Hassidim, Danny Raz, Michal Segalov, and Ariel Shaqed. Network utilization: The flow view. In Proc. INFOCOM, pages 1429–1437. IEEE, 2013. doi:10.1109/INFCOM.2013.65 66937. Max Ilsen, Daniel Otten, Nils Aschenbruck, and Markus Chimani. No traffic to cry: Trafficoblivious link deactivation for green traffic engineering. CoRR, abs/2601.13087, 2026. Accepted at INFOCOM 2026. arXiv:2601.13087.

M. Chimani and M. Ilsen

22 23

Michael Jünger, Thomas M. Liebling, Denis Naddef, George L. Nemhauser, William R. Pulleyblank, Gerhard Reinelt, Giovanni Rinaldi, and Laurence A. Wolsey, editors. 50 Years of Integer Programming 1958-2008 - From the Early Years to the State-of-the-Art. Springer, 2010. doi:10.1007/978-3-540-68279-0. Simon Knight, Hung X. Nguyen, Nick Falkner, Rhys Alistair Bowden, and Matthew Roughan. The internet topology zoo. IEEE J. Sel. Areas Commun., 29(9):1765–1775, 2011. doi: 10.1109/JSAC.2011.111002. John Moy. OSPF version 2. RFC, 2328:1–244, 1998. doi:10.17487/RFC2328. Daniel Otten, Alexander Brundiers, Timmy Schüller, and Nils Aschenbruck. Green segment routing for improved sustainability of backbone networks. In Proc. LCN 2023, pages 1–9. IEEE, 2023. doi:10.1109/LCN58197.2023.10223317. Daniel Otten, Max Ilsen, Markus Chimani, and Nils Aschenbruck. An extended look at green traffic engineering by minimizing active linecards. IEEE Open J. Commun. Soc., 7:2794–2813, 2026. doi:10.1109/OJCOMS.2026.3673375. Timmy Schüller, Nils Aschenbruck, Markus Chimani, and Martin Horneffer. Failure resiliency with only a few tunnels - enabling segment routing for traffic engineering. IEEE/ACM Trans. Netw., 29(1):262–274, 2021. doi:10.1109/TNET.2020.3030543. Timmy Schüller, Nils Aschenbruck, Markus Chimani, Martin Horneffer, and Stefan Schnitter. Predictive traffic engineering with 2-segment routing considering requirements of a carrier IP network. In Proc. LCN, pages 667–675, 2017. Mikkel Sigurd and Martin Zachariasen. Construction of minimum-weight spanners. In Proc. ESA 2004, Lecture Notes in Computer Science, pages 797–808. Springer, 2004. doi: 10.1007/978-3-540-30140-0_70. Neil T. Spring, Ratul Mahajan, David Wetherall, and Thomas E. Anderson. Measuring ISP topologies with rocketfuel. IEEE/ACM Trans. Netw., 12(1):2–16, 2004. doi:10.1109/TNET.2 003.822655.

Record · ID 168239 · SHA-256 a9107f7b6d6488de
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.