Optimisation des réseaux, routage et dimensionnement

The study presented in this document proposes an industrial approach of the problem of network routing on constrained capacity . Many mathematics studies were done to define methods to design optimal backbone network, or the optimal routing plan on uncapacitated network. Those methods solve linear program or integer program. Some approximation or relaxation must be done to solve most of actual problems. Moreover, the proposed routing plans are in most of the case mono routing plan. Using shortest path algorithms make flows to use a single path, they do not allow the use of subsidiary links taht could be under utilized. We propose in this work routing methods on links of constrained capacities, the Mille Feuilles, and some evolution of the Mille Feuilles algorithm that permit limiting the number of paths. Those methods can be applied for the backbone network conception, and can be defined with several cost functions. Those methods are very close to optimal routing defined with projected gradient without limitation of the number of paths. Used with a non cumulative cost function on the path, they allow decreasing the maximal link load ratio, and increasing the network reliability to flow uncertainties and to single link failure.Moreover, we evaluate performances of several re-routing methods in case of single link failure depending of the rerouting policy applied. The link load variation and the average path lengths variation are bound depending on the re-routing. The routing and re-routing methods are not similar and a routing method adapts itself differently depending on the re-routing method. A new rerouting method is also proposed, that can be applied for any multi-routing plan.Cette étude propose une approche industrielle du problème de routage de données sur des réseaux aux capacités contraintes. Un certain nombre d'études mathématiques ont été réalisées pour définir des plans de routage, par résolution de problèmes linéaires ou en nombres entiers. On constate alors que des approximations doivent être faites pour appliquer les méthodes mathématiques aux problèmes réels. D'autre part, les routages proposés sont pour la plupart simples (mono-routage). L'utilisation des algorithmes de plus courts chemins contraint souvent les flux sur une route unique, ils ne permettent généralement pas l'utilisation de liens annexes dont la charge est faible. Nous proposons des méthodes de routage de flux sur des liens de capacités finies, le routage Mille Feuilles, et des variantes de ce routage permettant de limiter le nombre de routes. Ces méthodes sont applicables au niveau de la conception ou de l'exploitation des réseaux. Ces méthodes d'optimisation par projections successives permettent de mettre en œuvre différentes fonctions coût, elles permettent d'approcher des solutions optimales obtenues à l'aide de méthode de gradient projeté. Associée à une métrique non cumulative sur la route, elles permettent de calculer des plans de routage multi-routes, de diminuer le taux charge du lien le plus chargé sur le réseau 'augmenter la résistance du réseau aux variations de trafic et à l'apparition d'une panne simple.D'autre part, nous évaluons les performances de plusieurs méthodes de re-routage en cas de panne simple d'un lien, en fonction des méthodes de routage appliquées. L'impact des re-routages sur le réseau est évalué, la variation de la charge des liens et la variation de la longueur moyenne des routes sont bornées. Les méthodes de routages ne sont pas équivalentes et elles s'adaptent différemment aux politiques de re-routage proposées. En outre, une nouvelle politique de re-routage applicable aux plans de routage multi-routes est introduite.VERSAILLES-BU Sciences et IUT (786462101) / SudocSudocFranceF