|Mathieu Leconte||Huawei Technologies, France|
|Apostolos Destounis||Huawei Technologies France Research Center, France|
|Georgios S Paschos||Huawei Technologies, France|
This paper addresses a major challenge in traffic engineering: the selection of a set of paths that minimizes routing cost for a random traffic matrix. We introduce the concept of pathbook: a small set of paths to which we restrict routing. The use of pathbook accelerates centralized traffic engineering algorithms, and therefore is appealing for instantiating, configuring , and optimizing large software-based networks. However, restricting routing to a few paths may lead to higher cost or infeasibility. To this end, we introduce the problem of pathbook design, wherein we search for a pathbook of constrained size that minimizes the expected routing cost of the random traffic matrix, which represents a prediction of the future traffic. The pathbook design problem is of combinatorial nature, and we show that it is NP-hard. We then study its convex relaxation for which we propose an optimal algorithm based on the projected subgradient method. For large networks, the subgradient vector is of prohibitive dimensions, hence we propose a coordinate-descent method using the Gauss-Southwell rule, which prescribes a move along the direction of largest subgradient element. We test the performance of our solution on dynamic traffic matrices from GEANT and find that our Gauss-Southwell pathbooks can accelerate standard methods by two orders of magnitude.