Title: Near-optimal Online Traffic Engineering
Authors: Arvin Ghavidel (University of Southern California), Pooria Namyar (Microsoft Research), Nikolai Matni (University of Pennsylvania), Walter Willinger (Northwestern University), Ramesh Govindan (University of Southern California)
Introduction
This paper studies a central problem in wide-area network operations: how to perform traffic engineering fast enough for modern WAN dynamics while still staying close to the optimal solution. In a large WAN, operators need to route millions of ingress-to-egress demands over geographically distributed links. A common objective is to minimize maximum link utilization, so that traffic is spread efficiently and no link becomes a persistent bottleneck.
Traditional TE systems are usually centralized. They collect traffic demands from the network, solve an optimization problem at a controller, and then carefully program the new traffic splits into switches. This loop is operationally clean, but it is slow: demand collection, solving, and update deployment can take minutes. Meanwhile, traffic demand and failures can change on a much shorter time scale. As a result, even if the centralized solver eventually finds a good solution, the network may spend much of its time operating with stale or suboptimal routing decisions.
The paper asks whether TE can be made truly online: when demand changes or a failure occurs, the system should quickly move toward a near-optimal solution rather than waiting for the next slow centralized optimization cycle. The authors propose OnlineTE, a distributed TE architecture that uses optimization tools to make this goal practical.
Key idea and contribution
The core idea of OnlineTE is to make traffic engineering a distributed online optimization problem rather than a periodic centralized batch computation. Instead of sending all demands to one controller and waiting for a global solution, switches observe local demand, compute local routing updates, and coordinate through a lightweight global mechanism. This changes the TE loop: collection becomes local, programming becomes local, and the remaining challenge is to make the distributed solver converge quickly and reliably.
OnlineTE uses ADMM, the Alternating Direction Method of Multipliers, as the main mathematical framework. Intuitively, each iteration has three parts. Switches first update their local traffic decisions based on the current global state. A coordinator then aggregates link-level information and updates global capacity-related variables. Finally, dual variables are adjusted to reduce disagreement between local and global views. Repeating this process drives the system toward an optimal or near-optimal TE solution.
The paper’s contributions can be understood at four levels.
First, it formulates WAN TE as a distributed ADMM problem. This gives OnlineTE a principled way to decompose the optimization across switches while preserving convergence toward the global objective. The design supports both path-based TE, where candidate paths are already known, and edge-based TE, where the system can jointly choose paths and traffic splits.
Second, the paper reduces communication overhead by using link-based dual variables. A textbook ADMM formulation would require variables for every demand-path pair, which is too large for WANs with millions of demands. OnlineTE instead exchanges information at the link level, making communication depend mainly on the number of links rather than the number of demands.
Third, the authors introduce Nested ADMM to improve convergence under changing traffic. Since one shared link-level variable may be affected by many demands, direct updates can create oscillations. Nested ADMM separates global updates from local stabilization: the coordinator can hold some variables fixed while switches perform several inner iterations, and then update the global state after the local solutions become more stable.
Fourth, the paper introduces Hierarchical ADMM for geographically distributed WANs. A fully synchronous distributed solver would have to wait for the slowest region in every iteration, which is costly in a global network. OnlineTE groups switches into latency-aware clusters, runs faster synchronization within each region, and uses asynchronous coordination across regions. This hierarchy directly addresses propagation delay and straggler effects.
The paper also extends the framework to edge-based TE. This is more expressive than path-based TE because the system can optimize over the network topology itself, but it also risks selecting unnecessarily long paths. OnlineTE uses sparsity and regularization to control path stretch, making it possible to trade off utilization improvement against delay.
Evaluation
The evaluation uses large WAN topologies, including KDL with about 750 nodes and Cogent with about 300 nodes. The experiments compare OnlineTE with centralized TE and with different ADMM variants, focusing on convergence time, solution quality, and the practical cost of distributed coordination.
The results show that OnlineTE can move toward high-quality solutions much faster than a centralized TE loop. In the path-based setting, the system typically needs about 80 iterations, with each iteration taking around 100 ms, reaching a near-optimal result in roughly 20 to 30 seconds. Compared with centralized TE, OnlineTE converges to better solutions about 2 to 6 times faster in the evaluated scenarios.
The experiments also show why the algorithmic refinements matter. Nested ADMM reduces oscillation and improves convergence when demand changes. Hierarchical ADMM improves performance in wide-area settings by avoiding the cost of waiting for slow cross-region synchronization in every iteration. The comparison with synchronous and asynchronous ADMM shows that the hierarchy is important for making distributed optimization practical in real WANs.
For edge-based TE, the paper evaluates different sparsity coefficients and measures both maximum link utilization and delay metrics. The results show a clear tradeoff: stronger sparsity can reduce path stretch and tail latency, while more flexible routing can improve utilization. This demonstrates that OnlineTE is not only a faster version of existing TE systems, but also a framework that can support richer optimization choices.
Personal thoughts
In my view, the main value of this paper is that it treats online TE as both an optimization problem and a systems problem. The work does not simply propose a faster heuristic. Instead, it redesigns where computation happens, what state is exchanged, and how global consistency is maintained. This makes the proposed architecture more convincing from an operational perspective.
Another important point is the way the paper connects theory with deployment constraints. ADMM provides the optimization foundation, but the system would not be practical without link-based variables, nested updates, hierarchical coordination, warm starts, and regularization for edge-based routing. These details show that the paper is not only concerned with mathematical optimality, but also with communication overhead, propagation delay, failure response, and path quality.
More broadly, OnlineTE suggests that future WAN traffic engineering may move beyond slow centralized control loops and simple heuristics. A distributed optimization framework can potentially provide a better balance between speed, optimality, and operational control. For networks whose demand changes quickly, this direction is especially meaningful.