Abstract

The calculation of virtual topologies on mapped onto physical topologies is one of the main techniques in traffic engineering. For a given physical network topology with fixed capacities, and a traffic matrix to route, the problem is the one of finding a virtual topology which will optimally route the given traffic matrix over the physical topology. When the traffic matrix evolves on long timescales, we will need to recalculate such optimal layout. Our first contribution consists in the definition of cost functions which better represent the actual costs of operation from an operator's standpoint. The second contribution consists in taking into account the costs of reconfiguring the layout to adapt it to the new optimal layout. Considering actual operation and maintenance costs, it would be interesting to reduce the layout complexity, measured as a function of the number of virtual paths required by the layout. We have formulated different optimization problems minimizing layout complexity, under QoS constraints. This realistic model results in hard to solve problems. We have developped heuristic methods to approximatelly solve large network topologies. We have shown the interest of reducing the layout complexity compared to results obtained when optimizing the layout with classical cost functions. The layout reconfiguration induces first a cost of operation, and second a cost associated to the service disruption times needed to reconfigure. We have formulated a family of problems which take into account the reconfiguration costs when calculating the new layout. One of the above mentioned heuristics has been adapted to solve the reconfiguration problem.; La superposition de topologies virtuelles à la topologie physique d'un réseau est un des principaux mécanismes de l'ingénierie de trafic. Soit un réseau physique d'une certaine topologie et capacité fixées et une matrice de trafic à véhiculer, il s'agit trouver une topologie logique permettant de mapper de manière optimale la matrice de trafic sur le réseau physique. Lors de l'évolution de la matrice de trafic sur des échelles de temps longues, il faudra agir sur le layout. La première contribution concerne la définition de fonctions de coût mieux adaptées à la réalité d'un opérateur, la deuxième contribution concerne la prise en compte du coût de changement du layout. Il s'avère intéressant d'un point de vue opérateur de réduire la complexité du layout, mesurée comme une fonction du nombre de chemins virtuels. Nous avons donc formulé divers problèmes de minimisation de la complexité du layout sous des contraintes de QoS. Il s'agit d'une modélisation réaliste mais qui engendre des modèles difficiles à résoudre. Nous avons développés des heuristiques qui permet de trouver des solutions approchées pour des réseaux de grande taille. Nous avons montré que la complexité des layouts peut être significativement réduite en comparaison avec celle obtenue suite à l'optimisation des fonctions de coût classiques. Le changement du layout implique d'une part un coût d'opération et d'autre part peut engendrer des coupures de service qui affecteront directement le coût d'opération. Nous avons formulé une famille de problèmes prenant en compte le coût de reconfiguration du layout. L'une des heuristiques citées a été adaptée pour analyser ces nouveaux problèmes.

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