Allocation de bande passante dans les grands réseaux stochastiques

Thèse préparée à Inria Paris-Rocquencourt et soutenue par Mathieu Feuillet du laboratoire sécurité des réseaux et des protocoles de l'ANSSI le jeudi 12 juillet 2012.

Jury :

-* Bonald Thomas, Telecom ParisTech (Co-directeur de thèse)
-* Borst Sem, Technische Universiteit Eindhoven/Bell Labs (Rapporteur)
-* Graham Carl, École polytechnique (Examinateur)
-* Massoulié Laurent, Technicolor (Rapporteur)
-* Mazumdar Ravi, University of Waterloo (Président du jury)
-* Robert Philippe, Inria (Directeur de thèse)
-* Simonian Alain, Orange Labs (Examinateur)
-* Wierman Adam, California Institute of Technology (Rapporteur)

Résumé :

L'objectif de cette thèse est de traiter trois problèmes relatifs aux réseaux de grande taille. Les outils utilisés à cette fin sont issus des probabilités et plus spécifiquement de la théorie des files d'attente.
En plus d'améliorer la compréhension des systèmes étudiés, les travaux réalisés dans cette thèse ont permis de prouver des résultats théoriques nouveaux ainsi que d'illustrer certains phénomènes probabilistes.

Dans le Chapitre II, un modèle de réseau à partage de bande passante est étudié. Contrairement à ce qui avait été étudié dans la littérature, les utilisateurs n'utilisent pas de contrôle de congestion. On suppose qu'ils envoient des données avec un débit maximum et protègent leur transmission à l'aide d'un mécanisme basé sur des codes correcteurs d'erreur. Le modèle obtenu est analysé pour deux topologies de réseaux spécifiques : les réseaux linéaires et les arbres montants. A l'aide de limites fluides, les conditions de stabilité de ces réseaux sont établies. Ces limites fluides donnent lieu à un phénomène intéressant de moyennage stochastique. Ensuite, une autre méthode de renormalisation est utilisée pour prouver que la région de stabilité de ces processus converge vers la région optimale lorsque que les débits maximaux des utilisateurs deviennent infiniment petits par rapport à la taille des liens du réseau.

Dans le Chapitre III, on se propose d'étudier CSMA/CA, un algorithme d'accès implémenté dans certains standards de réseaux sans fil. Chaque lien est constitué d'un émetteur et d'un récepteur et un graphe d'interférence modélise les collisions potentielles entre les liens. Les arrivées et les départs de ces derniers sont prises en compte. Une approximation est faite en supposant que la dynamique d'accès au canal est infiniment plus rapide que la dynamique des arrivées et départs de liens. Il est alors établi que le CSMA permet une utilisation optimale des ressources radio dans le cadre des réseaux ad-hoc. Cependant, il est également prouvé que ce même algorithme n'est pas efficace pour les réseaux avec une station de base ; dans ce cas, un biais en faveur des transmissions vers la station de base est observé. A la fin du chapitre, l'hypothèse simplificatrice est discutée.

Les deux derniers chapitres de la thèse sont consacrés à l'étude d'un grand système distribué de stockage de données avec pertes. L'objectif est d'estimer la vitesse de perte des fichiers ou la durée de vie d'un fichier donné. Dans le Chapitre IV, c'est le premier point de vue qui est adopté. Le système est considéré de manière globale. Le système est constitué d'un grand nombre de fichiers qui peuvent avoir chacun deux copies au maximum. Chaque copie disparaît au bout d'un temps aléatoire.
Un mécanisme centralisé de sauvegarde permet alors de restaurer les copies perdues. Un fichier dont les deux copies ont été détruites est définitivement perdu. Le système est étudié dans le cas limite où le nombre de fichiers tend vers l'infini. Afin de décrire correctement le système, trois échelles de temps différentes sont étudiées. Ralentir le temps permet de comprendre le mécanisme de sauvegarde ; laisser le temps inchangé permet de définir la capacité du système ; accélérer le temps permet d'évaluer la vitesse de perte des fichiers. Le principe de moyennage stochastique est également observé à l'échelle de temps la plus rapide.

Dans le chapitre V, le point de vue d'un fichier donné est adopté. Des liens sont établis avec les modèles classiques d'Ehrenfest, issu de la physique statistique, et d'Erlang, issu des télécommunications. Des méthodes basées sur les martingales sont utilisées pour calculer la transformée de Laplace des temps d'atteinte de ces deux processus. Ces transformées permettent alors d'estimer le comportement asymptotique de ces temps d'atteinte et notamment le temps de disparition d'un fichier.