[Rappel] Thèse Cifre est proposée à Orange Labs sur le site de Châtillon.

THESE ORANGE LABS

Approches d’optimisation à temps garanti

pour le routage et la conception de réseaux

Encadrant : E. Gourdin

La thèse sera consacrée à l’étude et à la mise en œuvre d’approches algorithmiques pour la résolution de problèmes d’optimisation ayant en paramètre d’entrée un temps de résolution maximum à ne pas dépasser. Cet impératif vise à permettre une utilisation de l’approche dans une application concrète où un utilisateur souhaite obtenir la meilleure solution possible en un temps fixé (qui peut varier suivant le contexte, de quelques heures pour une étude de conception de réseaux, à quelques minutes ou secondes pour préparer des ajustement dynamique dans un réseau opérationnel). L’objectif de ces travaux est de fournir des outils d’aide à la décision pour la conception, le développement, la gestion des futurs réseaux SDN (Software Defined Network).

Pour parvenir à cet objectif de maitrise du temps de calcul, plusieurs approches devront être étudiées, comparées et potentiellement combinées. On s’intéressera en particulier à des approches d’approximation avec garanties de performances sur lesquelles des progrès très important ont été obtenus ces dernières années et à une problématique centrale dans les réseaux qui consiste à calculer des routes pour écouler des flux de trafic (demandes) tout en mini-misant la congestion des liens (ratio du trafic sur la capacité).

Dans un article de 2002 [1,2], H. Räcke a introduit le concept d’oblivious online routing dans lequel chaque demande origine-destination est routée sans aucune connaissance de l’état de congestion du réseau. Le résultat surprenant est qu’il existe un tel mécanisme de routage pour lequel la congestion du réseau n’est pas à plus de O(log n) de la con-gestion optimale. Ces travaux sont intéressants à plus d’un titre : d’une part, parce que le routage online donne une borne sur la qualité d’un routage distribué dynamique, et d’autre part, parce que cette borne est relativement bonne. Malheureusement, la méthode proposée dans [1] pour calculer un tel routage nécessite de résoudre des problèmes NP-difficiles. Cette complexité algorithmique est réduite dans [4] à une complexité polynomiale super-linéaire, qui reste rédhibitoire pour des réseaux de grande taille. La notion d’oblivious routing peut également être analysée dans le contexte de routage robuste, où l’on cherche à calculer un routage optimal lorsque les demandes sont incertaines [3].

Finalement, en 2013 [5], J.A. Kelner et ses co-auteurs propose un algorithme permettant de calculer la solution epsilon-approchée d'un problème de Flot Concurrent Maximum (Maximum Concurrent Flow) en un temps presque linéaire. L’approche proposée est complexe et utilise oblivious routing comme outil de base mais nécessite également de nombreux concepts (flow sparsification, flots électriques, résolution de systèmes Laplacien,…) mais semble très prometteuses pour la résolu-tion pratique de problèmes de routage dans les réseaux.

Le travail de thèse bénéficiera de l’expertise acquise depuis de nombreuses années dans le projet ORDA sur les problèmes d’optimisation de routage (problèmes de flots/multiflots,…) mais permettra également de diversifier les compétences en algorithmie en étudiant des approches nouvelles. Le travail sera également alimenté par des problématiques réelles issues d’entités opérationnelles ainsi que de données réelles ou réalistes.

L’objectif de la thèse est de parvenir à maitriser dans un contexte de réseau opérationnel les méthodes les plus efficaces pour l’optimisation du routage, puis de les combiner de manière à fournir la meilleure réponse possible (avec garantie ou en espérance) en un temps de calcul donné. Une première piste à explorer est la possibilité de combiner, au moyen de méthodes de décomposition, des approches exactes avec des méthodes approchées avec garantie de performance et d’essayer de calculer ou d’évaluer les temps de calculs obtenus.

La thèse proposée permet à la fois de se confronter à des problématiques complexes issues des réseaux de télécommunication en tentant d'apporter des solutions innovantes, mais aussi de comprendre le fonctionnement de l'innovation et les processus de transfert vers l'opérationnel des résultats de recherche dans un grand groupe tel qu'Orange.

Références

[1] Harald Räcke. 2002. Minimizing Congestion in General Networks. In Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS '02). IEEE Computer Society, Washington, DC, USA, 43-52.

[2]  Marcin Bienkowski, Miroslaw Korzeniowski, and Harald Räcke. 2003. A practical algorithm for constructing oblivious routing schemes. In Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures (SPAA '03). ACM, New York, NY, USA, 24-33. DOI=http://dx.doi.org/10.1145/777412.777418

[3] David Applegate and Edith Cohen. 2003. Making intra-domain routing robust to changing and uncertain traffic demands: understanding fundamental tradeoffs. In Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications (SIGCOMM '03). ACM, New York, NY, USA, 313-324. DOI=http://dx.doi.org/10.1145/863955.863991

[4] Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, and Harald Racke. 2003. Optimal oblivious routing in polynomial time. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (STOC '03). ACM, New York, NY, USA, 383-388. DOI: http://dx.doi.org/10.1145/780542.780599

[5] Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. 2014. An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms (SODA '14). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 217-226.