Traffic engineering of telecommunication networks based on multiple spanning tree routing

Abstract

This paper focuses on tra±c engineering of telecommunica- tion networks, which arises in the context of switched Ethernet networks. It addresses the minimization of the maximum network link load. With the IEEE 802.1s Multiple Spanning Tree Protocol, it is possible to de¯ne multiple routing spanning trees to provide multiple alternatives to route VLAN tra±c demands. Two compact mixed integer linear programming models de¯ning the optimization problem and several models based on the Dantzig-Wolfe decomposition principle, which are solved by branch- and-price, are proposed and compared. The di®erent decompositions re- sult from de¯ning as subproblems either the supporting spanning trees and/or the demand routing paths, which can be solved by well known e±cient algorithms.