Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Analyse et optimisation de performance des r´ eseaux de communication Olivier B

Analyse et optimisation de performance des r´ eseaux de communication Olivier Brun To cite this version: Olivier Brun. Analyse et optimisation de performance des r´ eseaux de communication. R´ eseaux et t´ el´ ecommunications [cs.NI]. Universit´ e Paul Sabatier - Toulouse III, 2012. HAL Id: tel-00728757 https://tel.archives-ouvertes.fr/tel-00728757 Submitted on 6 Sep 2012 HAL is a multi-disciplinary open access archive for the deposit and dissemination of sci- entiﬁc research documents, whether they are pub- lished or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L’archive ouverte pluridisciplinaire HAL, est destin´ ee au d´ epˆ ot et ` a la diﬀusion de documents scientiﬁques de niveau recherche, publi´ es ou non, ´ emanant des ´ etablissements d’enseignement et de recherche fran¸ cais ou ´ etrangers, des laboratoires publics ou priv´ es. Habilitation à Diriger des Recherches delivrée par l’Université Toulouse III Spécialité : Réseaux et Communications par Olivier BRUN Analyse et Optimisation de Performance des Réseaux de Communication Soutenue publiquement le 6 février 2012 devant le jury composé de : M. Thierry Gayraud Président M. Jean-Marie Garcia Directeur de recherche M. Konstantin Avrachenkov Rapporteur M. Tijani Chahed Rapporteur M. Philippe Mahey Rapporteur M. Prosper Chemouil Examinateur Remerciements Ce document synthétise une dizaine d’années de travaux menés au LAAS-CNRS. Mes pre- miers remerciements ne peuvent donc qu’aller à mes collègues du LAAS, et en particulier à Jean- Marie Garcia, qui m’a guidé dans mes recherches depuis ma thèse, ainsi qu’à Thierry Monteil, Urtzi Ayesta et Balakrishna Prabhu avec lesquels j’ai collaboré sur plusieurs des sujets décrits dans ce mémoire. Je tiens à les assurer de mon amitié et du plaisir que j’ai eu à travailler avec eux. J’exprime aussi ma gratitude envers mes étudiants, et notamment ceux dont j’ai eu le plaisir d’encadrer la thèse. Je remercie chaleureusement les membres de mon jury qui ont accepté de rapporter sur cette thèse et d’assister à la soutenance malgré des conditions climatiques particulièrement diﬃciles. Leur participation au jury fut un grand honneur pour moi. Enﬁn, merci à toutes les personnes que j’ai pu côtoyer durant toutes ces années passées au LAAS et avec j’ai eu tant de plaisir à travailler. Résumé Les réseaux de communication jouant un rôle de plus en plus important dans nos activités quotidiennes, l’interruption des services qu’ils fournissent, ou même une dégradation signiﬁca- tive de leur qualité, deviennent de moins en moins acceptables. La sécurisation des réseaux et le contrôle de qualité de service sont ainsi devenus des enjeux majeurs qui nécessitent de réelles avancées méthodologiques dans plusieurs domaines. Nos contributions en ce sens peuvent se ré- partir en deux volets : d’une part celui de l’évaluation de performance et d’autre part celui de l’optimisation de réseaux. Nos travaux en évaluation de performance sont basés sur la théorie des ﬁles d’attente et sur la théorie des jeux. Ils visent le développement de modèles stochastiques analytiques ou de simu- lation permettant le passage à l’échelle pour l’évaluation, en régimes stationnaire et transitoire, des principales métriques de performance au niveau paquet (délai, taux de perte et gigue), mais aussi au niveau ﬂot (nombre de sessions actives, temps de téléchargement, etc). Ils concernent également l’analyse pire cas de la performance des stratégies de routage décentralisées. Les travaux en optimisation sont quant à eux essentiellement consacrés au développement de méthodes pour la conception de réseaux (d’accès ou de backbone) résilients, leur dimen- sionnement et l’optimisation de leur routage (avec OSPF ou MPLS). Les problèmes abordés étant généralement des problèmes combinatoires diﬃciles, avec souvent des fonctions objectifs non-linéaires, les approches heuristiques sont privilégiées. D’autres travaux sont consacrés à l’or- donnancement de tâches strictement périodiques dans les systèmes embarqués avioniques. Mots-clés: Modèles stochastiques de performance, ﬁles d’attente, théorie des jeux, optimisation, réseaux de communication Abstract With communication networks getting more and more present in our daily activities, network outages or even signiﬁcant degradations of the quality of service become less and less tolerable. Network survivability and the control of the quality of service have thus become critical issues that require signiﬁcant methodological progresses in various scientiﬁc ﬁelds. Our contri- butions fall in two broad categories : performance evaluation and optimization of networks. Our research works on the performance evaluation of networks are based on queueing and game theories. They aim at the development of analytical or simulation-based methods for the large-scale evaluation of the main performance metrics, both at the packet level (delay, loss rate and jitter) and at the ﬂow level (number of active sessions, download times, etc). They also deal with the worst-case analysis of the performance of decentralized routing algorithms. The second category of contributions are mainly devoted to the development of new optimiza- tion methods for the design of survivable access and backbone networks, for capacity-planning and for route optimization in OSPF and MPLS networks. Since most of these problems are NP-hard combinatorial problems, often with non-linear cost functions, we usually have to resort to dedicated heuristics. Another work in the applied optimization ﬁeld deals with the strictly periodic scheduling of tasks in embedded avionic systems. Keywords: Stochastic performance models, Queueing systems, Game theory, Optimization, Communication networks Table des matières 1 Introduction 1 1.1 Evolution des réseaux de communication . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Objectifs des travaux de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Un mot sur ce qui n’est pas décrit dans ce document . . . . . . . . . . . . . . . . 4 1.4 Organisation de ce document . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 Contexte des Recherhes 5 2.1 Projets de recherche collaboratifs . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Encadrement de thèses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Enseignement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.4 Activités de valorisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3 Evaluation de Performances des Réseaux 11 3.1 Modélisation dynamique des traﬁcs . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1.1 Modélisation des Réseaux à Commutation de Circuits Multiclasses . . . . 12 3.1.2 Modélisation des Réseaux à Commutation de Paquets . . . . . . . . . . . 14 3.1.3 Simulation Hybride Distribuée . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 Analyse de la ﬁle M/D/1/N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2.1 Solution stationnaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2.2 Solution transitoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.3 Analyse de la gigue des ﬂux audio et vidéo . . . . . . . . . . . . . . . . . . . . . . 19 3.3.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.3.2 Le cas d’un seul noeud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.3.3 Le cas de plusieurs noeuds . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.3.4 Exemple d’application . . . uploads/Management/hdr-main.pdf