Traffic Engineering: From Distributed Static Optimization to Centralized Transient Control

Traffic Engineering is of fundamental importance for network operation. Traditionally, it assumes static traffic input and then looks for distributed routing solutions to optimize certain objective. Along this line, in the first part of this talk, we will present HALO (Hop-by-hop Adaptive Link-state Optimal) routing. It is the first provable optimal link-state routing solution with hop-by-hop forwarding. Furthermore, our solution does not require traffic matrix as an explicit input and can adapt to changing traffic input. We prove our solution converges and solves the standard MCF (Multi-Commodity Flow) problem.

Recently, there has been tremendous interest in SDN (Software-Defined Networking), which is an emerging network architecture that separates control and data planes. Conceivably, that means network managers can first solve Traffic Engineering optimization in a centralized manner and then translate the solution to configure network switches. Within this context, in the second part of this talk, we consider the problem of avoiding transient congestion while reconfiguring the routing paths. We formulate a flow-based and a switch-based model. For the flow-based model, we demonstrate that an optimal sequence of minimum update steps could always be found when the dependency graph is acyclic. For the switched model, we find a way to translate a feasible flow-based updating sequence to a feasible switch-based sequence subject to a tree topology constraint on the routing paths.