Abstract

Traffic Engineering (TE) uses methods and models from a variety of mathematical fields, such as statistics and optimization, to improve the performance of telecommunication networks. In this thesis, we study TE problems dealing with networks that impose single-path routing. As the name infers, in this type of routing, the traffic flow of each "commodity" cannot be split in its path between its origin and destination. Given its cheap cost, single-path routing is widely used in today's data centers, where thousands of stored servers perform computations or host Internet services. One common case of single-path routing is the one enforced by the Spanning Tree Protocol (STP) in switched Ethernet networks. The STP requires the network to keep its activated links loop-free, while maintaining the other redundant links ready for back-up, in case of link failure. The Multiple Spanning Tree Protocol (MSTP) extends the STP by installing multiple virtual networks compliant with the STP, over a single physical topology. Therefore, the MSTP is greatly beneficial for network service providers, as it allows for a more efficient use of the existing resources.Network design problems dealing with the MSTP are generally highly combinatorial and very hard to solve. As such, TE literature mainly suggests heuristic methods, which can quickly produce reasonable designs. Notwithstanding, due to a scarce existence of lower bounds to the optimum values of such problems, there is little knowledge about the quality of the solutions provided by these heuristics.In this sense, we propose mathematical programming models and methods that can provide optimal designs for these networks, or at the very least, obtain valid lower bounds. Taking into mind the goal of avoiding congestion in the network, we focus on two problems that deal with the following load-balancing objectives: the minimization of the worst-case link utilization, and the minimization of flow costs given by piecewise linear functions that penalize heavily-loaded links. The study of both these problems yielded relevant by-products: the first is the study of a MSTP network design problem, where we minimize the total load, and the second is the study of a fundamental unsplittable multicommodity flow problem with piecewise linear costs.For all the considered problems, we provide studies of complexity, extensive polyhedral studies to compare the proposed formulations, and a wide array of computational experiments to evaluate the performance of the proposed models and methods. Doctorat en Sciences info:eu-repo/semantics/nonPublished