Optimization of Link Load Balancing in Multiple Spanning Tree Routing Networks

Abstract

In telecommunication networks based on the current Ethernet technology, routing of traffic demands is based on multiple spanning trees: the network operator configures different routing spanning trees and assigns each demand to be routed in one of the selected spanning trees. A major optimization issue in this solution is the combined determination of (i) a set of appropriate spanning trees, and (ii) assignment of demands to the trees, in order to achieve an optimal load balancing on the links of the network. In this paper we consider models and solving techniques for lexicographical optimization of two load balancing objective functions. The first objective is the min-max optimization of the n worst link loads (with n up to the total number of network links), and the second objective is the minimization of the average link load (when n is smaller than the total number of network links). Besides exact methods, a heuristic technique that can compute both feasible solutions and lower bounds for the addressed optimization problem is proposed. Finally, we discuss effectiveness of different solution using results of a numerical study of realistic case studies. The authors wish to thank Michal Zagozdzon for the fruitful discussions on the adaptation of the max-min fairness solution methods to the problems addressed in this paper. This work has been done under the Joint Specific Project METRO-ETHERNET within the FP7 Network of Excellence "Euro NF". The Portuguese coauthors have been partially funded by FCT (Fundacao para a Ciencia e a Tecnologia) through project PTDC/EIA/64772/2006 and through the post-doc grant SFRH/BPD/41581/2007 of D. Santos. The co-authors from Warsaw University of Technology have been partially funded by the Polish Ministry of Science and Higher Education (MNiSW, grant no. N517 397334 "Optimization Models for NGI Core Networks"). M. Pioro has been also supported by the Swedish Research Council (Vetenskapsradet, grant no. 621-2006-5509 "Modeling and Design of Core Internet Networks").