ComboTE: Scalable Mixed-link based Traffic Engineering for Hybrid WANs

In recent years, enterprises are increasingly moving from private WANs to hybrid WANs, for the purpose of cost saving, better scalability and improved user experience. To utilize network resource of both private and public networks, existing traffic engineering (TE) solutions for hybrid WANs perform traffic classification at the application level, i.e., sending traffic of high-priority applications to private WANs while letting other traffic go to the Internet. Unfortunately, such a strategy falls short of achieving optimal performance and has inherent limitation in making desired tradeoff between cost and performance. In this paper, we present comboTE, a mixed-link based TE framework to optimize both performance and cost over hybrid WAN. Specifically, comboTE designs a fine-grained TE strategy that considers link(s) from both types of networks at every hop when deciding the routing path for each traffic demand. To address the scalability issues, we leverage Lagrangian relaxation, a decomposition technique for solving large scale integer linear programs, combined with a novel augmented-graph-based approach to derive the most cost-efficient link compositions within a segment. Our comboTE achieves the near-optimal solution with a theoretically proven gap that is better than linear programming relaxation. The experimental results on realistic topologies and traffic matrices show that comboTE scales well and achieves solutions of high quality. Compared to prior TE algorithms, comboTE achieves a solution with tighter gap in limited time, and takes 2.2× less execution time without a time budget.