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

Abstract

In Europe, all Air Navigation Service Providers (ANSPs) finance their activities by charging airlines using their airspace. These ‘en route charges’ usually account for a significant part of the cost of a flight, and they can therefore influence the route choice: airlines may decide to fly longer routes to avoid countries with higher charges. If ANSPs want to maximize their revenues, they must choose the optimal charge to impose on their airspace. We show that this optimal charge can be identified through a Network Pricing Problem (NPP) formulation in the form of Bilevel Programming where the leader (i.e. the ANSP) owns a set of arcs (the airways in its national airspace) and charges the commodities (i.e. the flights) passing through them. As the en route charges are proportional to a Unit Rate value fixed by the ANSP, we are able to apply a similar methodology as in the case of a single toll arc for the NPP. By exploiting the structure of the problem, we propose an exact algorithm to compute the optimal Unit Rate and apply it to a case study relying on real air traffic data and realistic flight cost figures. Abstract disponible à l'adresse suivante :http://www.icrat.org/downloads/bookofabstract.pdf info:eu-repo/semantics/published