Supervision : Philippe CHRÉTIENNE

Optimisation du routage dans les réseaux de télécommunications avec prise en compte de la qualité de service

Ces travaux de thèse visent à aborder trois problématiques liées à la prise en compte de la qualité de service dans l'optimisation du routage. Tout d'abord, il est nécessaire de définir la qualité de service et de l'évaluer de manière rapide. La qualité de service est mesurée par trois principaux indicateurs : le délai, le taux de perte et la gigue qui sont relatifs à chaque classe de trafic. Nous présentons donc un ensemble de résultats issus de la théorie des files d'attente permettant de les évaluer analytiquement au travers de modèles de différents niveaux de complexité. Puis, en se basant sur l'évaluation du délai, nous montrons le gain d'une solution optimale de routage au sens de la qualité de service face à une solution basée sur la minimisation de la congestion. Or, lors de l'intégration d'une telle solution de routage dans un réseau, il est primordial que le nombre de chemins portant chaque demande soit minimal. Nous proposons donc une étude théorique de ce problème NP-difficile au sens fort et des caractéristiques de ses solutions avant d'expérimenter deux heuristiques de résolution.

2002-2008 Publications

• 2008
  • B. Vatinlen, F. Chauvet, Ph. Chrétienne, Ph. Mahey : “Simple Bounds and Greedy Algorithms for Decomposing a Flow into a Minimal Set of Paths”, European Journal of Operational Research, vol. 185 (3), pp. 1390-1401, (Elsevier) (2008)
• 2004
  • B. Vatinlen : “Optimisation du routage dans les réseaux de télécommunications avec prise en compte de la qualité de service”, thesis, phd defence 09/23/2004, supervision Chrétienne, Philippe (2004)
  • B. Vatinlen, F. Chauvet, Ph. Chrétienne, Ph. Mahey : “Minimisation du nombre de chemins décomposant un flot”, Algotel, Batz-sur-mer, France (2004)
• 2003
  • B. Vatinlen, F. Chauvet, Ph. Chrétienne, L. Chauvier : “Routing optimisation with consideration of Quality-of-Service in telecommunications networks”, EURO conference, Istanbul, Turkey (2003)
  • B. Vatinlen, Ph. Mahey, Ch. Duhamel, F. Chauvet : “Minimizing congestion with a minimal bounded number of paths”, Algotel 2003 - 5^e Rencontres Francophones sur les aspects Algorithmiques des Télécommunications, Banyuls sur mer, France (2003)
  • B. Vatinlen, F. Chauvet, Ph. Chrétienne, L. Chauvier : “Routage avec prise en compte de la qualité de service”, 5^e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2003), Avignon, France (2003)
• 2002
  • B. Vatinlen, F. Chauvet, R. Nait‑Abdallah : “Algorithme de plus courts chemins et détection de circuit négatif”, CO 2002 - 12^th International Symposium on Combinatorial Optimization, Paris, France (2002)