GATE: GPU-Accelerated Traffic Engineering for the WAN Rahul Bothra1,2
Alexander Krentsel1,3 Saptarshi Mandal2 Brighten Godfrey2 Sylvia Ratnasamy1,3 Rob Shakir1 R. Srikant2
arXiv:2605.01748v1 [cs.NI] 3 May 2026
1 Google
2 UIUC
Abstract
cause it directly captures either network operations costs (utilization) or customer experience (e.g. throughput, latency, availability). Fast runtime is important because the TE system must react quickly to changing network conditions, such as link cuts or traffic spikes, to bring the network back into an optimal state. While the optimization objective can vary, in practice for many operators [7, 10, 15] the objective is maxmin fairness [5, 28], which balances maximizing utilization with maintaining fairness in resource allocation across users and flows. Solutions to date have involved a tradeoff between these two goals of runtime and optimality. This is because direct optimal formulations of the max-min fairness optimization goal (using either general-purpose LP solvers or special-purpose algorithms [8]) are computationally expensive, leading to runtimes of up to 5 minutes on the WANs we study in our evaluation. As a result, most approaches involve formulating the traffic engineering optimization problem as an approximation, sacrificing some optimality in exchange for faster runtimes. Approximate TE solvers have been deployed in production from the earliest SDN WAN deployments, such as the Waterfill algorithm reported in Google’s B4 paper [15] or the LP approximation in Microsoft’s SWAN [14]. Recent works on ML-based approximate solvers [31, 37] show promise in decreasing runtimes even further, but don’t support the practical objectives we focus on (discussed in §2.1), so they won’t be a focus of this paper. Another line of work has attempted to parallelize TE solving [2, 3, 37, 38], but also generally compromises optimality guarantees or does not support max-min fairness due to the difficulty of splitting TE into cleanly separable subproblems (discussed in more detail in §2.3.2). The degree of acceptable runtime vs. optimality is determined by operator preference based on their workload needs, customer sensitivity, and budgets; thus, each operator tunes their deployment and method to their needs. As networks are being rapidly scaled to meet AI demands, navigating this tradeoff is becoming increasingly problematic. First, larger networks lead to increasingly longer algorithm runtime, which stress existing formulations that scale super-
Traffic engineering (TE) has become a crucial tool for enforcing routing policy and maintaining operational efficiency in large networks. Existing TE solutions pick an objective function to optimize, aiming to balance (i) allocating traffic optimally with (ii) reacting quickly to demand changes and disruption events. However, as the scale of networks grows, the runtime of the existing optimal solution becomes infeasibly large. The alternative – approximate solvers – result in costly inefficiencies. We present GPU-Accelerated Traffic Engineering (GATE), which achieves the best of both worlds: enabling fast TE runtimes through a highly-parallelizable GPU-compatible decomposition, while iteratively converging to the provably optimal solution. GATE unlocks a unique set of desirable properties: it becomes increasingly parallelizable with network size, supports a wide spectrum of fairness objectives, and offers theoretically guaranteed convergence to the optimal solution and near-optimal convergence within a bounded time. We evaluate GATE on production traces from two large cloud WANs, and show that GATE achieves near-optimal solutions 5-10x faster than state-of-the-art.
1
3 UC Berkeley
Introduction
Traffic engineering (TE) is central to maximizing utilization and meeting performance goals in wide-area network (WAN) deployments. Large-scale networks are expensive to build and maintain, requiring a large physical footprint and expensive hardware. While traditional shortest-path routing such as that which is enabled by IS-IS and BGP can route traffic according to a predefined set of metrics, they do not consider other criteria (e.g., capacity) which can leave parts of the network highly underutilized, translating to wasted costs for network providers. Thus, large-scale cloud providers and network operators deploy TE systems [10,14,15,22] to have more control over their traffic placement. The goal of a traffic engineering system is to (1) place traffic optimally with respect to the operator’s goals, and (2) converge to a solution quickly. Optimality is important be1
2
linearly with input size. Second, larger networks lead to more frequent changes from failures, shifting demand, etc., which requires TE to run more frequently to react. We propose a new TE approach that enables both fast runtimes and convergence to optimal allocations. Our approach is based on a novel application of Lagrange Decomposition (LD) techniques, which allow us to break the global TE problem into a collection of smaller per-flow problems that exchange information and make simple updates, iterating until convergence. This process is guaranteed to converge to the optimal allocation, or can be run for a shorter time until it has converged sufficiently closely to optimal. We go beyond a straightforward application of LD to introduce the notion of adaptive learning rates that we show are critical to achieving fast convergence to optimal allocation. Furthermore, we formulate the decomposition as very simple closed-form subproblems. These design decisions give GATE three important properties that enable efficient implementations. (1) The closed-form simplicity of our decomposition formulation is amenable to a CUDA-kernel implementation over GPUs, enabling massive parallelism. (2) The dynamics of our overall allocation support differential computing, i.e. when processing new information, we can start with the previous allocation to converge much more quickly to the new optimal. Finally, (3) our formulation of the decomposition supports practical WAN TE constraints (per-flow demands and pathing) and a spectrum of objectives, including proportional fairness and the commonly used objective – max-min fairness. To our knowledge, GATE is the first GPU-accelerated WAN TE solution supporting such practical constraints with an optimality guarantee. Our evaluation shows that GATE achieves a better runtimeoptimality tradeoff than existing state of the art (SOTA) TE algorithms. Compared to SOTA TE for optimality (Danna [8]), GATE improves runtime by ~100x while achieving within 5% of the optimal allocation. Compared to the commonly used TE for runtime (k-Waterfill [16]), GATE achieves a 4% improvement in optimality within the same runtime. Based on both industry reports and our discussions with cloud providers, at today’s scale, single-digit improvements in efficiency percentages can translate to significant (>O($100M)) savings in annual network provisioning costs [9]. To capture the cumulative improvement, we introduce drift-adjusted optimality (DAO) as a single metric that captures the joint effect of runtime and optimality, which stems from lower runtimes resulting in more up-to-date routes. GATE achieves 4–6% better DAO than existing TE algorithms (Soroush, SWAN [14, 29]) on current topologies. Our results also highlight the importance of our component design contributions to making LD techniques practical for TE: adaptive learning enables a 2-3x speedup in runtime compared to a straightforward application of LD techniques [38], our GPU implementation enables a further 15-20x speedup, and warm-start enables an additional 4-6x speedup.
Background and Motivation
Over the past few decades, traditional ISPs and modern hyperscalers alike have adopted SDN-based control architectures to manage their WANs [10, 11, 14, 15]. These SDN systems are responsible for collecting state about the network such as topology and demand and programming routers accordingly. At the heart of such systems is an SDN controller that is responsible for deciding how traffic should be placed, given a view of the topology and demand matrix, by running a TE algorithm which produces path allocations for all flows. These inputs to the TE algorithm are aggregated from low-level telemetry such as interface statuses and sending rates which are continually streamed from the routers or hosts in the network. TE is invoked as often as every few minutes, with each invocation taking the latest available information as input. The end-to-end convergence time of SDN systems is made up of (1) propagation time, during which the controller learns of state changes, (2) computation time, during which the TE algorithm computes new paths, and (3) programming time, during which these paths are programmed into the network. Historically, the computation time and programming time have dominated end-to-end convergence. Recent advances in dataplane techniques such as source routing have been shown to significantly decrease programming time [21] in a way that stays constant with network size, however computation time remains significant, especially in larger networks.
2.1
Traffic Engineering Objectives
Network operators balance a variety of goals in choosing and configuring their traffic engineering deployments. These goals are driven by customer needs: providing (O.1) as much bandwidth as requested, (O.2) with minimal latency paths, (O.3) at a low cost, and (O.4) with minimal disruptions. Finally, operators aim to do this while (O.5) maintaining fairness across their customers. Meeting these goals requires operators to consider both the static and dynamic states of the network. For a given static snapshot of the network and demands, operators aim to place as much traffic as possible, using shortest paths for higher priority traffic first, then placing lower-priority traffic on longer paths with more bandwidth. Maximizing network utilization minimizes network ownership costs. To avoid unfairly starving any users of bandwidth, this traffic placement must happen with fairness in mind. The most common TE optimization formulation to meet these goals is max-min fairness [28], which aims to give all flows equal bandwidth on their best available paths, while spreading remaining bandwidth to those who need more. In reality, networks are highly dynamic systems, facing constant changes in both traffic demand as application needs change, and network topology as links fail. Prior work reports average demand swings of 35% per 5 minutes [3, 37]. We observed O(100s) of link capacity changes each day in the large cloud WAN we analyzed – which can cause traffic 2
placed on paths traversing affected links to be dropped due to congestion – in addition to link failures. Network operators deploy a variety of techniques to lessen the impact, such as establishing Fast-Reroute Bypass paths to route traffic around downed links; these backup paths place traffic in a manner that avoids dead-ends, but often diverges from the calculated traffic engineering solution’s objectives [21], necessitating recalculation to return to meeting operator goals. Even in regular times of operation without faults, demand naturally shifts over time causing traffic placement to drift further and further from optimal. For this reason, operators continually re-run TE to keep routing close to optimal. Yet most existing solvers restart from scratch each invocation, with limited warm-start benefit, so faster runtimes translate directly into fresher allocations.
2.2
they struggle from one of two challenges that lead to poor DAO: (i) slow reaction to bursts / link-cuts, or (ii) suboptimal solution with low runtimes. As network sizes grow, the DAO of existing solutions deteriorates as runtimes worsen substantially (as existing TE algorithms’ runtime grows superlinearly with network size [2, 16]) even if optimality remains the same. Thus, we set our goal to design a traffic engineering algorithm that keeps DAO high as network size grows. A secondary goal of our design is flexibility in runtimeoptimality tradeoff points. The goal of TE is to reach optimal routing quickly, but “optimal” is defined by the operator’s business needs and constraints, both of which can change due to shifting business priorities or environmental changes. Whereas existing solutions require configuring a single point in design space trading off optimality and runtime ahead of deployment, we aim to offer operators flexibility through dynamically configuring a single TE solution at runtime to their preferred tradeoff point.
Runtime-Optimality Tradeoff
Exact formulations of the max-min fairness optimization goal commonly selected by network operators are computationally expensive [8], with runtimes of >5 minutes on standard sized deployments. This is far beyond an acceptable time for operators, for whom it is important that the network can react and repair itself after a link or router failure quickly enough to mitigate user impact. Long runtimes lead to a larger deviation between the TE solver’s solution and the new network state. As a result, practitioners typically use an approximation of the exact solution, sacrificing some optimality in exchange for faster runtime. Accelerating growth in the size and footprints of globalscale WANs has made revisiting the TE problem worthwhile and important. Large-scale cloud WANs report network size growth of 4-7× over the past five years [1, 4, 20]. This growth is only expected to accelerate in projections of the next five years, driven by the needs of large-scale data processing and machine learning jobs. These larger networks increase infrastructure cost proportionally, making traffic placement efficiency increasingly valuable. At the same time, runtimes using existing TE approaches grow exponentially longer with network size (shown in §4.5), stressing acceptable network reaction times. Network growth has made selecting a good operating point balancing runtime and optimality increasingly difficult. Existing TE algorithms each provide their own tradeoff point. For instance, k-Waterfill [16] solves quickly (~2 sec) but gets a very suboptimal solution (92% of optimal). On the other hand, the exact solver computes the optimal solution, but takes a long time (~350 sec ≫ 2). The deviation within the traffic matrix in that time is (~20%), making the solution suboptimal. Neither is desirable to the operator. To quantify the joint impact of runtime and optimality of a TE solution, we introduce a new metric, Drift Adjusted Optimality (DAO), that combines the optimality penalty of the solution with the staleness penalty caused by longer runtime. The fundamental challenge of existing approximations is that
2.3
Related Work
Traffic engineering is a multicommodity flow problem, which (for linear objective functions or max-min fairness) can be formulated as a linear program (LP) optimization problem and solved with general-purpose solvers like Gurobi, or with special-purpose algorithms [8]. To improve runtime, early hyperscale WANs therefore developed approximate methods [14, 15]. Since then, there have been several major lines of work to improve the runtime-optimality tradeoff. We discuss two lines of work in depth – solving the max-min fairness objective faster (§2.3.1), and parallelizing solvers regardless of the objective (§2.3.2) – which are relevant to our goals and methods and which we’ll later compare with experimentally. 2.3.1 Accelerating Max-Min Fairness Compared to objectives like maximizing total throughput or minimizing max link utilization, max-min fairness is more difficult because it involves solving multiple LP instances: first maximizing the allocation of the minimum flow, then maximizing the minimum of the remaining flows, and so on. Soroush [29] tackled this by using geometric binning of rates which then allows it to reformulate the problem as a singleshot optimization. This introduces an approximation, but one of the methods of [29] provides a configurable bound on suboptimality (dependent on the bin separation factor) with runtime increasing as the approximation improves. 2.3.2 Parallelization Without Guarantees With problem sizes scaling, one would of course like to be able to parallelize the solver. This is tempting because large networks have many nodes, links, and flows which appear not to directly affect each other – yet it is subtly difficult because in the global solution, they affect each other indirectly through overlapping shared resources. Several recent works have tried to make progress towards parallelization, with different methods of splitting up the problem into smaller sub-problems. NCFlow [3] splits a network 3
into clusters (ideally capturing natural clustering in the topology), aggregating the problem at cluster granularity, and then solving parallelizable sub-problems within each cluster. However, this is in general not optimal for the global TE problem. POP [2] partitions the problem differently, by splitting the set of user demands and slicing resources, so that each sub-problem has a subset of users and a fraction of network resources. This is a good fit for “granular” [2] problems, with many individually-tiny demands which can flexibly be shifted to use different resources. But that property is only partially true of TE, and after merging the sub-problems the solution is again not optimal in general. Teal [37] parallelizes across flow demands, applying a neural network model to route each individual demand. The use of ML makes it a natural fit to solve the sub-problems in parallel on a GPU. More relevantly for our work, after the RL stage, Teal uses a second stage optimization to improve the solution. This stage uses a Lagrangian decomposition technique, specifically the Alternating Direction Method of Multipliers (ADMM) [6] which it can parallelize on a GPU. While ADMM in general can provide convergence guarantees, to make this particular TE formulation work, Teal avoids TE’s non-negativity constraints, instead projecting the solution back into the feasible space. This results in approximations in each iteration of ADMM, which adds up over time, and the solution can (and does) converge to a suboptimal solution, without a bound on the optimality gap. Teal runs ADMM a fixed number of iterations to heuristically improve. [37] reports that this ADMM formulation did not converge fast enough to run alone, without the RL stage. All the above approaches run into the difficulty that TE is not easily partitioned, and resort to heuristics which, for one reason or another, are not guaranteed to be optimal.
proach (i) requires careful manual tuning to make progress [6], making it infeasible for large networks, and (ii) does not support max-min fairness. PDMCF [39] also uses the primal-dual technique to implement a GPU-parallel multi-commodity flow solution. The formulation solves a simpler problem than WAN TE, since it does not concern itself with a fixed pathset, a constraint that is key to practical WAN TE (e.g., to control latency). Instead, it allows any flow to traverse any link. This formulation enables PDMCF to achieve an O(N) speedup over traditional solvers. While [24,39] do not address practical constraints, we briefly report and compare their performance with GATE in §4. Recently, DeDe [38] comes even closer to the goal of parallelizing WAN TE with practical constraints. It used an ADMM decomposition for WAN TE, but solved the individual flow sub-problems with calls to a general-purpose LP solver (Gurobi), allowing it to preserve the problem’s non-negativity constraints. As a result, for convex objective functions (such as maximizing total flow or minimizing max link utilization), DeDe converges to the optimal allocation.1 However, DeDe has two limitations that are relevant to our goals. First, it does not support solving for the max-min fairness objective commonly used in deployed TE systems. Second, while use of a general-purpose solver as a subroutine allows DeDe to flexibly apply to many optimization problems even outside of TE, it comes at a relatively high efficiency cost, due to: (a) the overhead of hundreds of calls to Gurobi, (b) the need to run general-purpose solvers like Gurobi on CPU instead of GPU, and (c) the many iterations for ADMM to converge. While these works have pushed the boundaries, they imply two open questions: Is it possible to parallelize TE in a principled way that is guaranteed to converge to the optimal, with practical constraints and objectives (e.g., path-based, max-min fairness)? Furthermore, can this be done with a direct formulation that does not resort to expensive calls to a general-purpose optimization package? As we will see, we can answer these questions in the affirmative. As in the recent work above, Lagrangian decomposition forms our principled foundation. But to answer the open questions, we need to introduce a novel carefully-designed closed-form formulation of TE, combined with an effective and theoretically-sound solution to ADMM’s slow convergence problem, and method of handling the complex nonlinear nature of max-min fairness – allowing us to leverage GPUs and continual re-optimization for huge performance gains.
2.3.3 Parallelization With Guarantees To the best of our knowledge, interestingly, all proposed parallel TE solvers with optimality guarantees leverage Lagrangean decomposition. Decomposition has a long history in network optimization. Early works designed or analyzed congestion control algorithms [18,25,33,34], where a user adapts its rate according to network feedback about Lagrange multipliers (acting as congestion signals). These are conceptually related to TE in that they are distributed solutions to optimally route traffic [12] but do not explicitly solve WAN TE. Closer to our problem, [19, 36] solve related problems of path-selection and routing cost minimization. While these solutions also leverage decomposition to enable GPU parallelization, the TE problem poses a very different set of constraints – (i) a complex objective function and (ii) runtimeoptimality tradeoff, that makes the formulation complex. The closest works to ours are [24, 38, 39] and we discuss each of these in more detail. [24] provides a formulation for multi-path TE using primal-dual descent – a decomposition technique that is an alternative to ADMM. However, this ap-
3
Design
We aim to design an algorithm to meet the operator needs discussed in §2; namely, providing both fast reaction time and a principled optimality guarantee. This motivates an algorithm that makes useful progress in a few iterations, can be warmstarted from the previous allocation, and provably converges 1While [38] does not include a formal proof, its optimality should be
inherited from its use of ADMM.
4
Term E N P Pst Ce Dst xr Sst
to as simply “max-flow” for short here. GATE’s goal is to be generalizable and effective for a spectrum of objectives. In that spirit, we use the standard notion of α-fair utility to compute the utility for a node-pair (Uα ), and aggregate the utilities across node-pair to compute the objective (U ∗ ),
Interpretation Set of all links in the network. Set of all nodes in the network. Set of all paths in-use in the network. source s and destination t. Set of paths in-use from node s to t. Capacity of link e. Demand requested from node s to t. Rate allocated over path r. Total rate allocated from node s to t (over Pst ).
Uα (b) =
(4) N,N
Table 1: Notation for a TE formulation.
Term ye,r dualdemst , dualcape , dualnegr , dualcone,r β k
U ∗ (x∗ ) = ∑ Uα s,t
Interpretation Suggested value of xr by edge e. Duals for primal constraints, (Eqs. (1), (3), (5) and (6)) Learning rate. Iteration index.
!
Pst
∑ xr r
This captures a spectrum of objectives with varying α. Table 3 lists the objectives of particular interest.
Table 2: Additional terms for GATE’s ADMM re-formulation.
to the true optimum if allowed to run. Before presenting our algorithm design to meet these goals, we first formally state the TE problem.
3.1
(b)(1−α) − 1 1−α
TE Formulation
α
Objective
α=0
Max-flow
α→1
Proportional fairness (log)
α→∞
Max-min fairness
Table 3: Objectives captured by α-utility.
WANs typically perform updates in two phases. First, there is a path computation phase which computes a set of allowed paths (e.g., k-shortest paths) for each node-pair. Then, these allowed paths are installed into the routers’ forwarding tables. The TE algorithm’s job is then to find the optimal rates over each path. As with prior TE solutions [14, 29, 38], we assume that the set of paths to be used are precomputed and provided as input (P).
3.2
Lagrangian Adaptation
GATE aims to break the global TE problem into smaller, local sub-problems, which still converge to the global optimum when solved iteratively. GATE achieves this by applying Lagrangian decomposition techniques. To do so, we first transform Eq. (2) to introduce auxiliary variables,
Variables We summarize the notations used in the TE formulation in Table 1. A node-pair (s,t) (which can be interpreted as a “user”) requests a certain demand dst from node s to node t. TE algorithms expect three inputs: (i) link capacities, (ii) requested demands, and (iii) a set P of pre-computed allowed paths. The TE algorithm will outputs the rate (xr ) for all r ∈ P.
P
∑ ye,r ≤ Ce
∀e ∈ E
(5)
∀e ∈ r, r ∈ P
(6)
r:l∈r
Constraints We constrain rates to (i) not exceed requested demands (Eq. 1), (ii) not exceed link capacities (Eq. 2) and (iii) non-negative values. (Eq. 3):
xr = ye,r
Pst
∑ xrP≤ Dst ∀s ∈ N,t ∈ N r ∑ xr ≤ Ce ∀e ∈ E r:e∈r xr ≥ 0
∀r ∈ P
(1)
Note that this transformation solves the same TE problem, but separates constraints such that there is exactly one constraint per variable. This transformation enables each variable to iteratively solve its own local constraint, while exchanging information with other variables across iterations. Next, we compute the standard Augmented Lagrangian [13] for this transformed formulation, by introducing dual variables dual∗ and a penalty constant β.
(2) (3)
Objective TE objectives can vary by operator, with maxmin fairness being the most commonly deployed in production networks [14, 15], and recent research proposals for maximum multicommodity flow [2, 3, 37, 38], which we also refer 5
Algorithm 1 GATE’s iterative, optimal algorithm with αcontinuation.
Lβ (x∗ , y∗ ; dual∗ ) = − U ∗ (x∗ ) | {z }
Input: Link capacities Ce , demands Dst , pre-computed paths {Pst }, target fairness αtarget (set to ∞ for max-min fair), and convergence threshold γ. Optional input: Initial rates x0 , and learning rate β. Output: Final allocation rates x.
primal objective
2
+
β demst + (∑r∈Pst xr − Dst ) ∑ dual 2 (s,t) | {z }
+
2 β dual + ( y −C ) ∑ ∑ | cape {zr: e∈r e,r e} 2 e∈E
demand constraint residual
1: Initialization: Dst x0 = |P , unless input is provided. |
(7)
st
capacity constraint residual
−
β ∑ 2 r∈P
dualnegr − xr | {z }
y0 = x0 slack∗ ← 0+ and dual∗ ← 0. α←0 k←0
2
non-negativity constraint residual
β + ∑ ∑ (dualcone,r + (xr − ye,r ))2 2 e∈E r: e∈r | {z }
2: while α ≤ αtarget do 3:
consensus constraint residual
Note that the Augmented Lagrangian folds the objective and constraints from §3.1 into a single expression, by representing the constraint violations as residuals and penalizing them. It intuitively follows that the optimal x∗ is the same for Eq. (7) and Eq. (4).
3.3
4:
Auxilliary updates: dual∗k+1 ← Eqs. (8)to (11)
dual updates
yk+1 e,r ← Eq. (13)
rate suggestion updates
Rate updates: Sst∗ ← §B.2 xrk+1 ← Eq. (14)
Sum computation
Convergence Optimizations: βk+1 ← Eq. (17) 6: if residuals (L k+1 − L k ) ≤ γ then 7: if kα == kα−1 then 8: break 9: else 10: α ← α+1 11: end if 12: end if 13: k ← k+1 14: end while 5:
Decomposition Iterates
Next, we use ADMM decomposition [6] to transform the Augmented Lagrangian into an iterative formulation. The goal of each iteration is to compute values of all variables (dual∗ , x∗ , y∗ ) such that the Lagrangian is maximized – comδL = 0. Within each iteration, a series of puted by setting δvar sequential steps compute these values, with information from previous iteration. Done iteratively, this eventually converges to the global optimal. Each step involves solving a large number of small subproblems, all of which are solved in parallel, giving GATE massive parallelization benefits (illustrated in Fig. 1). The steps within one iteration are: (i) Dual updates (Ln 3), (ii) Rate suggestion updates (Ln 3), (iii) Rate updates (Ln 4), and (iv) convergence optimizations (Ln 5-15). Note that the Lagrangian is improved in two ways - (i) improving the primal objective and, (ii) reducing the constraint violation penalties, both of which are desirable in computing the optimal TE allocation.
Learning rate updates
converged for αtarget converged for current α
15: Feasibility Projection x ← Projection(xk+1 , α) 16: return x.
See Algorithm 2
the ADMM formulation requires additional slack variables, described in §B.1. " # k+1 k k dualdemst = dualdemst + ∑ xr − Dst (8) r∈Pst
+
"
#
P k+1 k dualcap = dual + ∑ yke,r −Ce cap e e r:e∈r h i k+1 k dualcon = dualcon + xrk − yke,r e,r e,r
Initialization We initialize x∗ with an optional input. This enables GATE to warm-start making progress with a nearoptimal allocation, if available. Otherwise, we default start Dst by uniformly spread the rate across available paths xr = |P . st | Note that this may violate some primal constraints, but constraint violations get resolved over iterations. We initialize suggested rates ye,r = xr , dual variables dual∗ = 0 and slack variables slack∗ = 0+ .
+
h i k+1 k k dualneg = dual − x nege r r
+
(9)
+
(10) (11)
Rate Suggestion Updates The dual variables enable quantifying constraint violations. Next, we need to compute rates that would minimize constraint violations. Since we decompose this problem into independent subproblems, we first look at the subproblems tasked with enforcing capacity constraints. Each edge e computes a “suggested” rate yr for every flow passing through it xr . If the link is experiencing congestion (high dualcap ), it would “suggest” flows to back off. While deciding the extent to back off for each flow, it would choose
Dual and Slack Updates The dual variables represent the constraint violations of the TE problem. They act as signals for the subsequent steps to update rates such that constraint violations are reduced. Eqs. (8) to (11) have |D|, |E|, |P| ∗ |E|, and |P| instances, all computed parallelly. Adapting TE to 6
#edges in a path
#instances of each dual # paths
Within a step, each
y11 y12 y13
# paths
dualdem*
y1*
x1
dualcap*
y2*
x2
dualneg*
y3*
x3
…
…
Step 2: Rate Suggestion Updates (solves the grid parallely)
Step 3: Rate Updates
… Step 1: Dual Updates (solves the grid parallely)
block is solved parallely.
Step 1
Figure 1: Steps in one iteration of GATE. All blocks within a step are computed parallelly. Each steps is computed sequentially.
values such that no flow deviates disproportionately from their current rates xr . The mathematical representation of these two considerations reflects in Eq. (12), and the rate suggestions is computed in Eq. (13), where ne is the number of paths traversing edge e. All |E| ∗ |P| instances of yk+1 are computed in parallel.
xrk+1 =
1 (1 + nr )
(Sst )−α β } | {z }
k )+ ∑ (yke,r − dualcon e,r
e∈r
|
{z
Consensus with yr
−
Objective
k Sst − Dst + dualdem st
{z
}
|
(14)
Demand constraint violation
k + dualneg | {z }r
Non-negativity
k+1 k+1 coste,r = β −Ce − xrk − dualcap − dualcon e e,r
(12)
3.4
yk+1 e,r =
¯ e − coste,r cost β
¯ e= where cost +
Convergence Optimizations
Adaptive Learning Performance of the iterative algorithm can be highly sensitive to the choice of β. It determines how quickly the iterations converge, and how close to optimal they converge. How do we choose a good learning rate? In each iteration, the rate updates xr attempt to maximize the Lagrangian L (Eq. (7)). It follows that a high β would heavily penalize constraint violations such that the rate updates prioritize “being feasible” over “finding the best allocation”. The algorithm is effectively “stiff”, i.e. it satisfies limits but struggles to move towards the optimal solution (U ∗ ). We capture the stagnation in rates using the dual residual (sk+1 ). It is defined as (15) sk+1 = ∥x∗k+1 − x∗k ∥
1 ∑ coste,r ne r:e∈r (13)
Rate Updates With the duals (dual∗ ), slack variables (slack∗ ), and rate suggestions (ye,r ) computed, we extract the optimal path rates. This local update seeks to (i) optimize the objective Eq. (4), (ii) minimize demand violations Eq. (1), and (iii) maintain consensus with the link-level rate suggestions Eq. (6).
Conversely, if β is too low, the rate updates place more weight on maximizing the objective U ∗ than on minimizing constraint violations. While this yields a high objective value quickly, the resulting rates violate capacity or demand constraints, meaning they cannot physically fit on the network. We compute constraint violations using the primal residual (rk+1 ), k rk+1 = ∥dualk+1 (16) ∗ − dual∗ ∥
Sum computation: Because the utility objective and demand constraints operate on the aggregate flow across all its paths, this step first requires computing the optimal Sst = ∑r∈Pst xr , even before we can compute the individual xr . What we have is an equation of the form ASα−1 +BS +C = 0, where α depends on the objective (Eq. (4)). This makes the problem significantly complex – and we compute this using the parallel Newton-Bisection method [35], detailed in §B.2.
Our goal is for the iterates to balance optimizing the objective with enforcing constraints. We achieve this by dynamically updating β to keep the primal and dual residuals within a similar order of magnitude. We implement this using a Residual Balancing technique [6]. This scheme inflates β by a factor C when the
With Sst computed, we plug it back to compute xrk+1 via the following closed-form equation, which accounts for (i) objective function, (ii) non-negativity constraint and, (iii) demand constraints, 7
primal residual is much larger compared to the dual residual (signaling excessive constraint violation), and deflates β by C when the dual residual dominates (signaling slow convergence). Eq. (17) defines the β update rule, with A and C as tunable constants. In §4.6, we show that our adjustment scheme for β roughly halves the number of iterations needed to converge. k C ∗ β k+1 k β := β /C k β
if rk+1 > A ∗ sk+1 if sk+1 > A ∗ rk+1 otherwise
To address this, we borrow inspiration from the Homotopy Analysis Method [23] – i.e., solve a simpler problem and then modify it to the solution of a more complex solution. Instead of directly solving for a large αtarget , we restructure the problem to begin at α = 0 (a purely linear, maximum-throughput objective). Once the ADMM iterations converge for a given α – meaning the primal and dual residuals fall below the threshold γ – we increment α and resume optimization. This is beneficial for two reasons – (i) it is easier to converge for smaller α, and (ii) for large α, the optimal allocations for α and α + 1 are geometrically adjacent in the feasible space (as seen in Fig. 2 and Fig. 3), leading to fewer iterations of the ADMM loop than starting from scratch. These characteristics naturally offer a unique stopping condition when solving for max-min fairness (αtarget → ∞). While the α-increment loop is theoretically unbounded, GATE continually checks if the network state has stagnated upon an α increment (i.e. residuals ≤ γ in the next iteration after the increment). When that happens, we know that GATE has converged (under γ) for all higher α, including max-min fair. In §C, we describe how this provably converges to the max-min fair allocation.
(17)
Convergence Criteria Similar to adaptive learning rates, we also use the primal- and dual-residuals for the stopping criterion for GATE. We terminate iterations when both the primal residual (indicating constraint feasibility) and the dual residual (indicating solution stationarity) fall below a threshold γ (Eq. (18)). A low γ yields a more optimal solution but requires more iterations. We discussed in §2.2 that we want to achieve a good tradeoff between runtime and optimality. We expect γ to be selected by the operator based on their network topology and traffic patterns. For example, in §4, we select γ to optimize for a metric of our interest – Drift Adjusted Optimality. sk+1 ≤ γ
and
(18)
Optimality
1.00 0.95
100 Max-Min Fair (α = ∞)
95
0.90
90 Optimality % Users allocated ≥ Max-min fair
0.85 0.80
0
0.25
0.5
1
2
3
85 80
% Users allocated ≥ Max-min fair rate
rk+1 ≤ γ
3.5
Alpha (α)
Path prioritization for trimming While selecting paths to trim, the goal is to minimize the loss in objective. In order to do that, we compute a penalty score (score p ) for each path. This score accounts for two factors – (i) the demand served by the commodity that the path belongs to (Scα ), and (ii) the number of edges on that path with constraint violations. Paths with a higher (Sc )α are prioritized to trim, a heuristic that adheres to the α-aware operator objectives. C p ensures that paths contributing to multiple constraint violations are prioritized for trimming.
Figure 2: Optimality (relative to max-min fair) of α-utility functions with increasing α.
Objective U(x)
10 5
α = 0 (Max throughput) α = 0.5 α=2
α = 0.25 α=1 α=3
α = 10 ( → max-min fair)
0 0
2
4
6
8
Resolving Constraint Violations
While GATE’s subproblems provably converge to a feasible optimal solution, stopping the iterations early (e.g., when the residuals fall below the convergence threshold γ) can leave very small constraint violations in the final rate allocation x∗ . It is important to resolve these violations before the solution is safe to push out on the network. Therefore, GATE computes the projection of the nearly-feasible output into a strictly feasible one. In order to achieve this, GATE trims rate of multiple paths.
10
Rates allocated (x)
Projection Technique GATE resolves constraint violations in three steps (as described in Algorithm 2): 1. Non Negativity Constraints: First, we project rates on all paths to [0, ∞). 2. Demand Constraints: Next, for each commodity that was allocated more than it requested, we trim the excess. We greedily select paths to trim, in descending order of their scores (score p ). 3. Capacity Constraints: After demand is bounded, we resolve capacity constraints with a similar strategy. For
Figure 3: Curve of various α-utility objective functions (larger α swings more).
α-increments Direct optimization of the α-fair utility function (Eq. (4)) for large values of α introduces numerical stiffness. When α ≫ 1, the utility curve becomes exceedingly sharp, as shown in Fig. 3. It experiences large gradient swings at the beginning, followed by a nearly flat curve, that slows convergence within the ADMM iterations. 8
Algorithm 2 GATE’s α-aware, parallelized, Projection.
inspiration from ADMM literature [6]. We select γ depending for each topology, to optimize for the right tradeoff between runtime and optimality (DAO). We find γ = 10−3 as a good convergence threshold in our evaluations. GATE outputs the rates over each path.
Input: Path rates x with possible constraint violations, link capacities {Ce }, demands {Dc }, fairness metric α. Output: Path rates x, with no constraint violations. 1: Resolve negative rates: 2: x ← max(x, 0) 3: Auxiliary variables:
4
Sc ← ∑r∈Pc xr , Le ← ∑r:e∈r xr Demand Violations: Ec ← max(Sc − Dc , 0) Capacity Violations: Ve ← max(Le −Ce , 0) C p ← ∑e∈p I(Ve > 0) # violations per-path score p ← (Sc(p) )α ×C p
We aim to evaluate two facets of GATE’s performance: (1) how well GATE’s traffic engineering allocation satisfies the goals and priorities operators have (§2.1) for a given network, and (2) how well this performance holds up as network sizes grow. We start by formally describing the metrics we use to evaluate performance on operator goals. We then compare GATE to other SOTA TE systems, examine how GATE converges over iterations, examine its scaling behavior, and conclude by presenting a factor analysis showing how GATE’s design elements work together to enable its effective performance.
alpha-aware and violations-aware
4: Resolve demand violations: 5: for each commodity c do in parallel 6: Let Pc∗ = {p ∈ Pc }, sorted in descending order of score p . 7: Iterate through Pc∗ until Ec = 0, δx p ← min(Ec , x p ) x p ← x p − δx p Ec ← Ec − δx p 8: end for 9: Recompute auxiallary variables: (Sc , Le ,Ve , C p , score p ) 10: Resolve capacity violations: 11: for each edge e do in parallel 12: Let Pe∗ = {p ∈ P | e ∈ p}, sorted in descending order of score p . 13: Iterate through Pe∗ until Ve = 0, δx p ← min(x p ,Ve ) x p ← x p − δx p Ve ← Ve − δx p 14: end for 15: return x
4.1
Optimality. We report optimality as the distance from the optimal allocation (OPT ) for the given objective, typically maxXd min fair. For an allocation X, we compute min( max(OPT , 1) d ,ϑ) for every demand d, and report optimality as the mean across all demands. This is in-line with metrics used to evaluate production TE systems [14, 15]. This is a modification of the qϑ metric used in recent works [26, 27, 29] to not penalize allocations for serving more traffic than the optimal allocation.
Optimality Guarantee
GATE’s iterative, local sub-problems converge to the globally optimal max-min fair allocation. We provide the following theorem:
Runtime. We report runtime as the time taken by each algorithm to compute the allocation assuming a set of paths have already been computed (matching prior work [3,8,14,29,38]). We measure CPU runtimes on a 128-core AMD EPYC with 240GB memory. We measure GPU runtimes with a 1x NVIDIA A100 40GB GPU.
Theorem 1. For any α-fair objective (including the maxmin fair limit as α → ∞), GATE’s iterations asymptotically guarantee the following: A. Constraint feasibility: Capacity and demand constraints are satisfied, with the projection scheme resolving violations arising from early stopping under a numerical threshold γ. B. Objective convergence: The objective defined in (4) reaches the optimal value (within γ-tolerance). C. Consensus constraint: The rate for a path xr and all rate suggestions ye,r ∀e ∈ r are equal.
Drift Adjusted Optimality (DAO). A TE algorithm uses the network state at time T0 as input (demands0 , capacities0 ), and generates an allocation after runtime K. In that time, the network state can drift to (demandsK , capacitiesK ). We define DAO as a metric to capture the effect of this drift on the actual optimality experienced by flows, computing DAOK as the optimality of an allocation using inputs from T0 applied to the conditions at TK . This effectively captures the penalty in optimality incurred by algorithms for taking longer to solve. We note DAO is a conservative metric (i.e. overly kind), as drift increases further after the path allocations get programmed until the next solution is computed, whereas we effectively assume drift stops at programming time.
Proof sketch: Detailed in §C.
3.7
Metrics
We rely on two standard independent metrics – optimality and runtime – to characterize TE solutions. We additionally introduce a new third metric, Drift Adjusted Optimality, that captures their joint impact.
each edge where the traversing paths exceed capacity, we trim rates on paths (selected in descending order of their scores) until the violation is resolved.
3.6
Evaluation
Implementation
We implement GATE in ~1,500 lines using PyTorch and CUDA. The implementation expects the inputs described in Algorithm 1 – capacity edgelist, demand matrix, set of pre-computed paths. In our implementation, we use A = 10 and C = 2 in the adaptive learning scheme (Eq. (17)), taking 9
4.2
Experiment Setup
4.3
Cumulative Performance
We first look at GATE’s cumulative performance on the series of aggregated inputs a TE system would receive for each of our dataset networks. GATE pushes the Pareto frontier of the runtime optimality tradeoff compared to existing TE solutions. Fig. 4 compares the mean runtime and optimality of GATE and other TE solutions over production traces from WAN B. GATE offers a new operating point, considerably stretching the Pareto frontier closer to optimal. The error bars represent the p5 and p95, and the shaded points represent individual runs (randomly sampled to avoid clutter). GATE takes ~1sec to compute an allocation that is 95% of optimal, achieving a speedup of 5-10× compared to SWAN and Soroush to achieve similar quality solutions. Danna achieves the optimal allocation, but incurs ≈ 200× longer runtimes compared to GATE. K-waterfilling has similar runtimes as GATE, but gets 3-5% worse optimality than GATE, with serving 8% less demand than GATE, which translates to $ millions in increased network provisioning costs. Fig. 7 shows these results hold and even improve further on Cogentco, a smaller network with uniform capacity links. GATE achieves the highest DAO amongst evaluated TE solutions. Fig. 5 shows DAO of different algorithms computed from the same experiment as Fig. 4 (over WAN B), showing the combined impact of runtime and optimality. The shaded values represent optimality of the algorithm, to indicate the degradation in optimality due to runtime. Danna experiences a 14% degradation from its optimal value because of the significantly long runtimes (O(100) seconds). SWAN and Soroush experience a noticeable degradation. While their optimality was comparable to GATE, their DAO is 3-4% lower. GATE and k-Waterfill experience the least degradation because of their low runtimes. However, k-Waterfill had lower optimality to begin with. GATE’s shorter runtime enables it to perform disproportionately better in the worst scenarios, which is visible in the lower percentiles of the CDF of DAO in Fig. 6, corresponding to cases of large capacity changes. This is because we both reconverge quickly, and to a better state. Note that each data point in this CDF is a single snapshot; this actually dilutes some of GATE’s fast reaction benefits, because a link failure only affects some flows in a snapshot. Fast reaction to failure is more directly captured by runtime. We provide a comparison of total traffic served across algorithms in §A. GATE is an order of magnitude faster than the prior decomposition based approaches. Fig. 8 compares the runtime of GATE to the SOTA decomposition-based TE, DeDe, as well as an exact solver, across different topologies3 . We compare on proportional fairness rather than the more common max-min objective because DeDe cannot solve for max-min.
We evaluate GATE over a wide range of network topologies and sizes. We use data from four publicly-available WAN topology datasets, as well as data sourced from two production topologies (WAN A and WAN B) operated by a large-scale network operator, with sizes shown in Table 4. TE Inputs. For WAN A, we collected the live production stream of aggregated topology and demand data that was taken as input by the operator’s production TE system over three months in 2025, with data points every twelve seconds. Likewise for Abilene, we use the publicly available topology and demand snapshots [17, 30], reported every five minutes. For the rest of our datasets, the available traffic demands are less complete. Specifically, for EsNet, Cogentco, and GÉANT, we use the static topology provided and estimate a realistic demand matrix via the gravity model used in prior work [3, 32]. For WAN B, we pull historical snapshots of representative demand and topology every three months, over a three year period from January 2020 to December 2022 to capture network growth. Then, to produce a series of realistically-spread timestamped matrices and topologies, we measure the distribution of demand flow shifts (as percentages) between subsequent datapoints observed in production for WAN A, and sample from that distribution. The result is a series of 1000 realistic input snapshots. For all topologies, we use the k-shortest paths as input, with k=4 restricted by hardware constraints. We use these as the inputs to GATE and the SOTA algorithms as comparison. Streaming data. To evaluate GATE’s operation in a continuous telemetry streaming regime, we approximate the underlying telemetry datastream for each of our datasets by interpolating the difference between each pair of TE input data points: for every consecutive pair of snapshots separated by time T with N values updated, we uniformly spread the N updates in time T . Benchmarks. We compare GATE with recent SOTA TE solutions: Soroush [29], SWAN [14], k-Waterfill [16], and Danna [8]. Additionally, we compare GATE with DeDe [38], NCFlow [3], and POP [2] to evaluate performance against other decomposition techniques. For all the TE solutions, we used the open-source implementations by [29, 38].To be as fair as possible in comparisons, for each topology we perform parameter tuning for Soroush and SWAN (α ∈ {1.5, 2, 4, 8}) and DeDe (ρ ∈ [10−4 , 103 ]) and pick the parameters that result in the highest DAO. We use k = 1 for k-Waterfill, which has the lowest runtimes. We warm-start SWAN, Danna, GATE, and DeDe with the optimal allocation from the network state 300 seconds prior.2 2We note that in practice, the warm-start can be done from a more recent allocation (depending on the algorithm runtime), but we choose 300 seconds as a conservative measure.
3 The DeDe implementation failed to run (crashed) on WAN A and WAN
B, though we do not believe this is a fundamental problem.
10
1.00
Table 4: WAN topologies used for GATE’s evaluation.
Better 0.975
0.950 Danna GATE k-Waterfill SWAN Soroush
0.925
101 Runtime (s)
100
75
50
0.75
0.80 0.85 0.90 0.95 Drift Adjusted Optimality (DAO)
GATE
k-Waterfill
SWAN
Soroush
Exact (Proportional Fairness) DeDe (Proportional Fairness) GATE (Proportional Fairness)
Danna GATE k-Waterfill SWAN Soroush
101 Runtime (s)
102
101
100
103 Abilene (11)
Figure 7: Runtime and Optimality for TE algorithms over Cogentco with uniform link capacities.
Both DeDe and GATE get within 1.5% optimality of the exact solution. However, GATE is consistently 10× faster than DeDe across a range of different topologies, in large part due to GATE (1) not using Gurobi, as our subproblem formulation is further decomposed, (2) leveraging GPU, and (3) using adaptive learning rates, as we discuss in §4.6.
4.4
Danna
103
0.925
1.00
Figure 6: CDF of Drift Adjusted Optimality experienced over 80 snapshots of WAN B.
0.80
102
0.875
0.70
0.85
Figure 5: Drift Adjusted Optimality for different TE algorithms over WAN B.
0.950
100 0
0.90
Better
0.900 25
0.95
0.75
Better optimality on uniform capacity
0.975
Optimality
CDF across snapshots
SWAN Soroush k-Waterfill Danna GATE
103
Figure 4: Runtime and Optimality for different TE algorithms over WAN B. 1.000
100
102
Zero runtime (hypothetical)
Optimality lost due to runtime
1.000 Drift Adjusted Optimality (DAO)
#Edges 28 122 158 478 O(100) O(1000)
Runtime (s)
#Nodes 11 23 68 197 O(100) O(1000)
Optimality
Topology Abilene GÉANT ESNet Cogentco WAN A WAN B
GEANT (23)
ESNet (68)
Cogentco (197)
Figure 8: Runtimes for decomposition-style TE algorithms across topologies of various sizes.
not decrease significantly, the mean relative violation drops sharply and becomes less than 1% within 75 iterations. After ~50 iterations, the primal and dual residuals fall below γ, i.e. 10−3 . At this point, GATE increases α, in order to progress towards max-min fairness. Note that α = 0 itself achieves nearly 90% of optimal. GATE takes fewer iterations to converge on α = 1, as much of the progress has already been made. After ≈ 85 iterations, α increases to 2, and progresses for < 10 iterations before increasing again. At this point, on the first iteration with α = 3, GATE remains converged (residuals < γ). This is GATE’s usual stopping criterion. In the figure, we show what would happen if we continue anyway. Note that while optimality increases by a small amount even after the stopping point, the additional runtime required results in an effective loss in DAO.
Looking Inside GATE’s Convergence
We now provide insight into how GATE works by seeing inside its convergence process, shown in Fig. 12 for WAN A. Note that GATE’s convergence can be stopped at any point – either earlier or later than its default stopping criterion (§3.4) – after which projection (§3.5) runs and produces a feasible solution free of constraint violations. The figure shows post-projection optimality4 (top) and pre-projection constraint violations (middle and bottom). In the first ≈ 20 iterations, GATE makes steady progress filling in the network with traffic. For nearly the same period, the learning rate β also increases, since path rates are increasing (primal residuals) faster than constraint violations are increasing (dual residuals). Around 20 iterations, network utilization has filled up enough that increasing rates starts to violate constraints (Fig. 12 (b) and (c)). Beyond 20 iterations, the Lagrangian variables are such that rate changes tend to balance between resolving constraint violations and maximizing the objective. Interestingly, while the percentage of constraints violated does
4.5
Scaling Behavior
Next, we look at how GATE’s performance varies across different topologies and increasing network sizes. GATE’s runtime grows much more slowly with network size compared to existing SOTA TE approaches. Fig. 9 shows runtimes for SWAN, Soroush, and GATE on the historical data from WAN B, totaling growth in number of routers by a factor of two over a three-year period. The runtimes for SWAN, Soroush, and GATE increase by 2.22x, 2.48x, and 1.64x respectively. GATE enjoys a significantly more modest increase due to increasing parallelization, which keeps the per-iteration runtimes low. As the topology size becomes twice of the original, the per-iteration runtime grows only to
4 To be clear, ordinarily GATE only runs projection once at the end. Here, we run projection after each iteration to illustrate what would have resulted from stopping GATE’s convergence after that iteration.
11
4096 Topology Size
103
1.50
6
4
1.25
2
1.00
Jul '20
Jan '21
Jul '21 Date
Jan '22
10
−1
1
10−1
0
% violations
post-projection at each iteration (hypothetical) Optimality (%) Learning Rate
100
% edges violating capacity Mean relative capacity violation
75
10−2
40 30 20
25
10
% demands violated Mean relative demand violation
75
50 40 30
50
20
25
10 0
25
50
75
100
125
150
175
200
0
Iterations
Figure 12: GATE’s intermediate values with WAN A as input – (a) top: optimality after projection and learning rates, (b) middle: Capacity violations (without projection) and, (c) bottom: Demand violations (without projection).
~1.11x. In that same period, the number of iterations required to converge increases by ~1.45x of the original. GATE outperforms other SOTA TE on all but the smallest (sub-30 router) topologies, with a widening gap as network size grows. Fig. 10 compares the runtime of different TE over a variety of WAN topologies of different sizes. We observe that while GATE (0.102s) is slower on smaller topologies like Abilene than SWAN (0.0777s) and Soroush (0.0693s) – because there is less benefit to the key parallelization technique GATE employs – it beats SOTA alternatives on topologies larger than GÉANT (23 nodes). For large topologies such as those being used by the hyperscaler in WAN B (and therefore representing today’s real-world deployments), GATE actually comes to match the k-Waterfill approximation’s runtime, while providing significantly more optimal traffic placement (§4.3).
4.6
8x
6x
6x
Cogentco WAN B (197) (O(1000))
1x
1x
Baseline
1x
1x
WS
WS+CF
WS+CF +GPU
WS+CF +GPU+AR
Figure 11: GATE’s speedup with Warm Start (WS), Closed Form (CF), GPU, and Adaptive Rate (AR). Note log scale y axis.
Our optimization techniques provide a cumulative 2 0 4 1 × speedup over naive ADMM decomposition. Fig. 11 shows the incremental impact of each additional technique we applied in our design when run on WAN B. The total runtime of GATE = # iterations × per-iteration runtime. We observe how each technique independently affects either component of total runtime compared to a baseline without any techniques: • Baseline: We replaced our closed-form decomposition of Eq. (12-15) with a maximization problem similar to that used by DeDe, and call Gurobi to solve it. Otherwise, everything is identical to Algorithm 1. • Warm start (WS) decreases # iterations by 6×, by seeding with allocations from prior run’s output. • Closed form (CF): We restore our closed-form decomposition, so that Gurobi is no longer needed, but execute the solution in the machine’s 64 CPU threads (not GPU). This decreases the per-iteration runtime by 8×. • GPU: decreases per-iteration runtime by 20×, by enabling massive parallelization from running threads on GPU instead of CPU. • Adaptive rate (AR): decreases # iterations by 2.2×, by dynamically adjusting learning rate during convergence (i.e., WS+CF+GPU+AR restores the full implementation of GATE.) These optimizations combine to the cumulative convergence speedup of three orders of magnitude.
0
100
13x 6x
highly sensitive to careful parameter tuning [6]. We discuss the impact of the techniques we exploit to help.
50
50
0
% violations
ESNet (68)
Mean Relative Violation
Optimal stopping point α: 1 → 2
25
0
GEANT (23)
Figure 10: Runtimes for different TE algorithms across topologies of various sizes.
100
50
16 6x
Jul '22
Optimal (max-min fair)
157x
48x
100
Abilene (11)
α: 0 → 1
Optimality (%)
101
157x
Better
64
4
Figure 9: Runtimes of TE algorithms over a period of 3 years as WAN B grows in number of routers.
75
2041x 942x
256
Learning Rate
0 Jan '20
102
Total runtime Per-iteration runtime # Iterations
1024
Mean Relative Violation
Runtime (s)
1.75 8
Runtime (s)
10
Increase in topology size
2.00
Danna GATE k-Waterfill SWAN Soroush
Speedup
SWAN Soroush GATE
12
5
Conclusion
In this paper, we presented GATE (GPU-Accelerated Traffic Engineering), which addresses the fundamental tension between runtime scalability and solution optimality in WAN traffic engineering. GATE uses a Lagrangian decomposition, but with closed-form, highly parallelizable subproblems tailored specifically for GPU architectures, and adaptive learning rates. This design not only allows us to guarantee theoretical convergence to the global optimum but also outperforms approximate solvers in both optimality and runtime. We believe GATE provides a valuable new point in the de-
Factor Analysis
We now analyze how GATE’s design decisions contribute to its strong performance. Naively applying ADMM to TE results in exceedingly long convergence times and performance 12
sign space that is flexible and future-proof, making it practical for real-world deployment. This is not only because of the strong performance improvements we report on both runtime and optimality, but also GATE’s qualitative benefits: being able to stop computation at any point early for a suboptimal solution, and supporting a diverse set of objectives. There are several avenues of future work. Further algorithmic improvements may be possible: we have observed that GATE converges better on uniform capacity networks than nonuniform (cf. Fig. 7 vs. Fig. 4) which suggests that it might be possible to accelerate convergence (and thus improve optimality in a given amount of time) with learning rates that are adaptive across parts of the topology, rather than just across iterations. Future work could also explore using GATE as a base for a new paradigm of continuous, streaming traffic engineering where allocations are iteratively refined as telemetry arrives. We also considered exploring the possibility of running our decomposition in a distributed fashion, with subproblems running on routers. While this affects convergence time due to network communication time between subproblems, it could enable novel distributed traffic engineering schemes that provide both optimality and survivability. Our work raises no ethical concerns.
[7] E. Danna, A. Hassidim, H. Kaplan, A. Kumar, Y. Mansour, D. Raz, and M. Segalov. Upward max-min fairness. Journal of the ACM (JACM), 64(1):1–24, 2017. [8] E. Danna, S. Mandal, and A. Singh. A practical algorithm for balancing the max-min fairness and throughput objectives in traffic engineering. In 2012 Proceedings IEEE INFOCOM, pages 846–854. IEEE, 2012. [9] Dell’Oro Group. Data center it capex 5-year forecast report. Market research report, Dell’Oro Group, January 2026. Summarized in Light Reading: "Cloud Capex to Surge as AI Infrastructure Matures". [10] M. Denis, Y. Yao, A. Hatch, Q. Zhang, C. L. Lim, S. Zhang, K. Sugrue, H. Kwok, M. J. Fernandez, P. Lapukhov, et al. EBB: Reliable and evolvable express backbone network in meta. In Proceedings of the ACM SIGCOMM 2023 Conference, pages 346–359, 2023. [11] N. Feamster, J. Rexford, and E. Zegura. The road to SDN: an intellectual history of programmable networks. SIGCOMM Comput. Commun. Rev., 44(2):87–98, Apr. 2014. [12] J. He, M. Bresler, M. Chiang, and J. Rexford. Towards robust multi-layer traffic engineering: Optimization of congestion control and routing. IEEE Journal on selected areas in communications, 25(5):868–880, 2007.
References @scale 2024. [1] Networking //atscaleconference.com/events/ networking-scale-2024/, Jan. 2024. 2026-2-6.
https: Accessed:
[13] M. R. Hestenes. Multiplier and gradient methods. Journal of Optimization Theory and Applications, 4:303–320, 1969.
[2] F. Abuzaid, P. Bailis, and M. Zaharia. Solving largescale granular resource allocation problems efficiently with pop. In Proceedings of the 28th ACM Symposium on Operating Systems Principles (SOSP ’21), pages 638–652, 2021.
[14] C.-Y. Hong, S. Kandula, R. Mahajan, M. Zhang, V. Gill, M. Nanduri, and R. Wattenhofer. Achieving high utilization with software-driven wan. In Proceedings of the ACM SIGCOMM 2013 conference on SIGCOMM, pages 15–26. ACM, 2013.
[3] F. Abuzaid, S. Kandula, B. Arzani, I. Menache, M. Zaharia, and P. Bailis. Contracting wide-area network topologies to solve flow problems quickly. In 18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21), pages 175–192, 2021.
[15] S. Jain, A. Kumar, S. Mandal, J. Ong, L. Poutievski, A. Singh, S. Venkata, J. Wanderer, J. Zhou, M. Zhu, J. Zolla, U. Hölzle, S. Stuart, and A. Vahdat. B4: Experi[4] N. Annamalai. Azure networking updates ence with a globally deployed software defined wan. on security, reliability, and high availability. In Proceedings of the ACM SIGCOMM Conference, https://azure.microsoft.com/en-us/blog/ Hong Kong, China, 2013. azure-networking-updates-on-security-reliability-and-high-availability/, [16] L. Jose, S. Ibanez, M. Alizadeh, and N. McKeown. A Dec. 2025. Accessed: 2026-2-6. distributed algorithm to calculate max-min fair rates [5] D. P. Bertsekas and R. G. Gallager. Data Networks. without per-flow state. Proceedings of the ACM Prentice Hall, Englewood Cliffs, NJ, 3rd edition, 2009. on Measurement and Analysis of Computing Systems, 3(2):1–25, 2019. [6] S. Boyd, P. Neal, C. Eric, P. Borja, and E. Jonathan. Distributed optimization and statistical learning via the [17] P. Jurkiewicz. Topohub: A repository of reference alternating direction method of multipliers. Foundations gabriel graph and real-world topologies for networking and Trends® in Machine learning, 3(1):1–122, 2011. research. SoftwareX, 24:101540, 2023. 13
[18] F. P. Kelly, A. K. Maulloo, and D. K. H. Tan. Rate control for communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research society, 49(3):237–252, 1998.
[29] P. Namyar, B. Arzani, S. Kandula, S. Segarra, D. Crankshaw, U. Krishnaswamy, R. Govindan, and H. Raj. Solving max-min fair resource allocations quickly on large graphs. In 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI 24), pages 1937–1958, 2024.
[19] K. Kikuta, E. Oki, N. Yamanaka, N. Togawa, and H. Nakazato. Effective parallel algorithm for gpgpuaccelerated explicit routing optimization. In 2015 IEEE Global Communications Conference (GLOBECOM), pages 1–6, 2015.
[30] S. Orlowski, R. Wessäly, M. Pióro, and A. Tomaszewski. Sndlib 1.0—survivable network design library. Networks, 55(3):276–286, 2010.
[20] B. Koley. Google’s AI-powered next-gen global network: Built for the gemini era. Google Cloud Next 25, Apr. 2025.
[31] Y. Perry, F. V. Frujeri, C. Hoch, S. Kandula, I. Menache, M. Schapira, and A. Tamar. {DOTE}: Rethinking (predictive){WAN} traffic engineering. In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23), pages 1557–1581, 2023.
[21] A. Krentsel, N. Saran, B. Koley, S. Mandal, A. Narayanan, S. Ratnasamy, A. Al-Shabibi, A. Shaikh, R. Shakir, A. Singla, and H. Weatherspoon. A decentralized sdn architecture for the wan. In Proceedings of the ACM SIGCOMM 2024 Conference, ACM SIGCOMM ’24, page 938–953, New York, NY, USA, 2024. Association for Computing Machinery.
[32] M. Roughan, A. Greenberg, C. Kalmanek, M. Rumsewicz, J. Yates, and Y. Zhang. Experience in measuring backbone traffic variability: models, metrics, measurements and meaning. In Proceedings of the 2nd ACM SIGCOMM Workshop on Internet Measurment, IMW ’02, page 91–92, New York, NY, USA, 2002. Association for Computing Machinery.
[22] U. Krishnaswamy, R. Singh, P. Mattes, P.-A. C. Bissonnette, N. Bjørner, Z. Nasrin, S. Kothari, P. Reddy, J. Abeln, S. Kandula, H. Raj, L. Irun-Briz, J. Gaudette, and E. Lan. OneWAN is better than two: Unifying a split WAN architecture. In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23), pages 515–529, Boston, MA, Apr. 2023. USENIX Association.
[33] R. Srikant. The mathematics of Internet congestion control. Springer, 2004. [34] R. Srikant and L. Ying. Communication networks: An optimization, control and stochastic networks perspective. Cambridge University Press, 2014.
[23] S. Liao. On the homotopy analysis method for nonlinear problems. Applied Mathematics and Computation, 147(2):499–513, 2004.
[35] J. Stoer and R. Bulirsch. Introduction to Numerical Analysis, volume 12 of Texts in Applied Mathematics. Springer-Verlag, New York, 2002.
[24] X. Lin and N. B. Shroff. Utility maximization for communication networks with multipath routing. IEEE Transactions on Automatic Control, 51(5):766–781, 2006.
[36] X. Wang, Q. Zhang, J. Ren, S. Xu, S. Wang, and S. Yu. Toward efficient parallel routing optimization for largescale sdn networks using gpgpu. Journal of Network and Computer Applications, 113:1–13, 2018.
[25] S. H. Low and D. E. Lapsley. Optimization flow control. i. basic algorithm and convergence. IEEE/ACM Transactions on networking, 7(6):861–874, 1999.
[37] Z. Xu, F. Y. Yan, R. Singh, J. T. Chiu, A. M. Rush, and M. Yu. Teal: Learning-accelerated optimization of wan traffic engineering. In Proceedings of the ACM SIGCOMM 2023 Conference, pages 313–328, 2023.
[26] Y. Lu, S. Kandula, A. C. König, and S. Chaudhuri. Pretraining summarization models of structured datasets for cardinality estimation. Proceedings of the VLDB Endowment, 15(3):414–426, 2021.
[38] Z. Xu, M. Yu, and F. Y. Yan. Decouple and decompose: Scaling resource allocation with dede. In Proceedings of the 19th USENIX Symposium on Operating Systems Design and Implementation (OSDI 25). USENIX Association, July 2025.
[27] R. Marcus, P. Negi, H. Mao, C. Zhang, M. Alizadeh, T. Kraska, O. Papaemmanouil, and N. Tatbul. Neo: A learned query optimizer. arXiv preprint arXiv:1904.03711, 2019.
[39] F. Zhang and S. Boyd. Solving large multicommodity network flow problems on GPUs. Automation and Remote Control, 86(8):782–795, 2025.
[28] D. Nace and M. Pióro. Max-min fairness and its applications to routing and load-balancing in communication networks: a tutorial. IEEE Communications Surveys & Tutorials, 10(4):5–17, 2009. 14
By mathematically absorbing the overages or underages, the slack variables allow the primal rate updates for xr and ye,r to be solved as unconstrained minimizations.
1.05 Max-flow Danna GATE
k-Waterfill SWAN Soroush
Demand served w.rt. Danna
1.00
B.2 0.95
0.90
0.85
0.80
Max-flow
Danna
GATE
k-Waterfill
SWAN
Soroush
Figure 13: GATE runtime with increasing GPU threads
A
Evaluation Continued
Total flow served by GATE is at-par with other TE solutions. While the evaluated TE solutions optimize for max-min fairness, we also review the total flow served by these algorithms. Fig. 13 shows that Soroush, SWAN and GATE serve similar total flow as Danna, despite having lower optimality (max-min fairness). Waterfill serves ~8% less traffic compared to Danna.
B
Generic α-Fairness (Newton-Bisection) For a general α > 0 objective, substituting the individual rate updates back into the definition of Sst yields a polynomial equation of the form, ASα−1 + BS +C = 0.
Decomposition Iterates - Continued
Slack Variables and Inequality Constraints
To cleanly apply the Alternating Direction Method of Multipliers (ADMM) to the TE formulation, the inequality constraints governing link capacities (Eq. (2)) and requested demands (Eq. (1)) must be converted into equality constraints. Standard ADMM templates rely on exact block minimizations, which are harder if constrained by inequalities during the subproblem updates. We resolve this by introducing non-negative slack variables slackdem ≥ 0 and slackcap ≥ 0. In each iteration, these variables are computed to absorb the current inequality gaps such that ∑ x + slackcap,e = Ce and ∑ x + slackdem,st = Dst . In each iteration, we compute the slack variables alongside the dual δL variables (dual∗ ) by setting δslack = 0, " k+1 slackdem = st
β
" k+1 slackcap = e
k dualdem st
Proportional Fairness (α = 1) Quadric Root Applying the standard quadratic formula yields the exact commodity sum instantly.
C
+
+
Proof. Part I: ADMM Convergence for Fixed α We map the Augmented Lagrangian in Eq. (7) to the standard 2-block ADMM template minu,v F(u) + G(v) subject to A u + B v = c and apply the classical convergence theorem for
xrk
r∈Pst
k dualcap e + Ce − ∑ yke,r β r:e∈r
Proof of Theorem 1
Overview: The proof is structured in two parts. First, we map GATE’s formulation to a 2-block ADMM-style decomposition. Applying the standard ADMM convergence theorem ensures that for any fixed α, the inner iterations strictly satisfy capacity and demand constraints while converging to the optimal α-fair utility. Second, as α increments, the allocations track the homotopy path toward max-min fairness. We prove using Karush-Kuhn-Tucker (KKT) conditions that if the allocation stagnates across an α-increment (triggering the zero-iteration halt condition), the network is physically locked by structural bottlenecks, mathematically guaranteeing the allocation has reached its max-min fair limit.
!# + Dst − ∑
(21)
Because this function is strictly monotonic and convex over the physically valid domain of flow rates, it possesses a unique positive root. We compute this root using a parallelized NewtonBisection method [35]. GATE uses Newton-Raphson descent for rapid convergence but intelligently falls back to binary bisection if the gradient step overshoots the valid bounds. This guarantees exact convergence to Sst∗ within bounded number of GPU cycles.
We now provide a detailed description of the abridged components of §3.3.
B.1
Sum Computation (Sst )
In §3.3, we noted that extracting the optimal path rates xr requires solving a vector maximization problem over the path rate vector x ∈ R|Pst | . Unlike standard link constraints which operate element-wise, the α-fair utility objective couples the rates of all paths supporting a given demand through their aggregate sum Sst = ∑Pr st x. For instance, under proportional fairness (α = 1), the structural form of the local subproblem is akin to log(∑ x) − ∑ x + ∑(x − y)2 , differentiating which gives S1st − Sst + 2xr = 0. While this equation cannot be solved isolated, we can take the system of equations for all r ∈ Pst to get an equation of the form |Pst | ∗ S1st − |Pst ∗ |Sst + 2Sst = 0. In other words, we now have a quadratic equation in Sst .
(19)
!# (20)
15
2-block ADMM [6]. It suffices to verify: (a) closed, proper, and convex objectives, (b) existence of a primal–dual saddle point (e.g., Slater’s condition), and (c) exact block minimizations. (a) Closed, proper, convex objective: The indicator function for the non-negative orthant is closed, proper, and convex. For α > 0, the utility function ϕα is closed, proper, and convex on (0, ∞) (extended by +∞ for S ≤ 0), hence the aggregate objective fα (x) = ∑(s,t)∈K ϕα (Sst (x)) is closed, proper, and convex on its domain. Therefore, the decomposed objective blocks F and G are closed, proper, and convex. (b) Slater point (strict feasibility): Consider the original TE problem in minimization form:
to a γ-approximate condition. For a given α, the approximate allocation S̃α satisfies: (S̃α )−α −
∑ λi,α Ai ≤ O (γ)
(22)
i∈active
where Ai represents the active constraint normals and λi,α ≥ 0 represents the corresponding dual multipliers. Assume the algorithm halts due to stagnation, meaning the allocation S̃α requires zero iterations to satisfy the γ-threshold for the incremented objective α + 1. Applying the relaxed KKT condition to the new objective yields: (S̃α )−(α+1) −
∑ λi,α+1 Ai ≤ O (γ)
(23)
i∈active
min x
∑ −Uα ( ∑ xr ) s.t. x ≥ 0,
s,t∈K
For both γ-bounded conditions to hold simultaneously on the identical allocation vector S̃α while the gradient undergoes a non-linear transformation, the active constraint normals Ai must strictly dominate the gradient direction within the error bounds. Geometrically, rather than being rigidly pinned at a single vertex, the allocation S̃α is bounded within an εneighborhood of a fully saturated face or vertex of the convex polytope P , where ε is directly proportional to γ. In this γ-locked state, no feasible direction exists to increase the rate of any commodity without violating the γ-tolerance of the physical constraints. Every commodity is either fully satisfied and bounded by its absolute demand constraint (Sst ≈ Dst ), or it is constrained by a saturated bottleneck link where it holds an equal raw share of the residual capacity (up to the γ-margin). Thus, exact stagnation under a γ-threshold implies the algorithm has discovered the physical saturation point of the topology within a rigorously bounded error.
r∈Pst
Sst (x) ≤ Dst ∀(s,t) ∈ K ,
∑ xr ≤ Ce ∀e.
r: e∈r
By our construction, K contains only commodities with Pst ̸= 0/ and D > 0, and every link e that belongs to at least Sst one path in (s,t)∈K Pst has Ce > 0. For each (s,t) ∈ K , let mst := |Pst | and pick ε > 0. Set: xr◦ :=
ε , mst
∀r ∈ Pst , ∀(s,t) ∈ K .
Then Sst (x◦ ) = ε ∈ (0, Dst ) provided ε < min(s,t)∈K Dst , so ◦ x lies in the α-domain interior (Sst > 0). For each link e, the induced load is ℓe (ε) := ∑r: e∈r xr◦ = ε · κe , where κe := |{r∈Pst :e∈r}| < ∞. ∑(s,t)∈K mst Choosing ε < mine:κe >0 Ce /κe yields strict feasibility for all inequalities and domain interiority. Hence Slater’s condition holds, implying strong duality and existence of a saddle point. (c) Exact block minimizations: The rate updates (x∗ ) are exact because non-negativity is rigorously enforced via the dual equation Eq. (11), and each commodity subproblem cleanly reduces to solving a unique scalar root in §B.2. The rate suggestion updates (y∗ ) are exact because each link subproblem explicitly resolves into the closed-form bounded projection given in Eq. (13). Therefore, all hypotheses of the standard 2-block ADMM convergence theorem strictly apply. Part II: Homotopy Continuation to Max-Min Fairness under γ-Tolerance. We now prove that if the continuation loop stagnates across an α-increment (meaning the optimal allocation requires zero ADMM iterations to converge for the new α), the allocation is within a strictly bounded neighborhood of the max-min fair limit. Fairness in resource allocation here is formally measured by equal raw allocation capped by demand. Let the feasible routing space P be a convex polytope defined by the linear network capacity and demand constraints. Because the algorithm terminates when the primal and dual residuals fall below the convergence threshold γ, the exact Karush-Kuhn-Tucker (KKT) stationarity condition is relaxed 16