Study of probabilistic models for peer-to-peer and mobile networks
Étude de modèles probabilistes de réseaux pair-à-pair et de réseaux avec mobilité
Résumé
The goal of this thesis is to solve four problems motivated by modern com- munication networks; the appropriate tools to solve these problems belong to the theory of probability. Solving these problems gives insight into the original physi- cal systems, and contributes at the same time to the theory since new theoretical results of independent interest are proved. Two kinds of communication networks are considered. Mobile networks are these networks where customers perform trajectories within the network indepen- dently of the service they receive; in contrast with classical queueing networks, transitions of customers are not triggered by service completions. In peer-to-peer networks the distinction between clients and servers is abolished, since in these net- works a server is a former client that offers a file once it has downloaded it. These last networks are especially efficient in spreading large or popular files. In Chapters I and II, the stationary behavior of such networks is considered. In each case, one describes the network through a discrete state-space, continuous time Markov process, and establishes its ergodicity or transience. A specificity of these two models is that the transition rates of the corresponding Markov processes are unbounded: in the case of the mobile network of Chapter I this is due to the fact that customers move independently of one another, while for the peer-to-peer network of Chapter II this is because the capacity of the system is proportional to the number of customers. Classically, to analyze the stability of a stochastic network, one can study the limits of a sequence of suitably rescaled Markov processes, the so-called fluid limits. This scaling is well suited for “locally additive” processes, i.e., processes which lo- cally behave as random walks; this is however not the case when the transition rates are unbounded. These techniques are nonetheless adapted to study the stability of the mobile network of Chapter I: using fluid limits to study the stability of Markov processes with unbounded transition rates represents one of the contributions of this work. The peer-to-peer network of Chapter II is not amenable to the same techniques, and Lyapounov type arguments are used. Another additional key ingredient is re- lated to a special class of branching processes. These new branching processes are defined and studied in Chapter II, and estimates on their extinction time make it possible, thanks to coupling arguments, to derive stability results on the stochastic network. In addition to the stationary behavior of peer-to-peer networks, their transient behavior can also be studied: this is the object of the simple model of Chapter III.
Le but de cette thèse est de traiter quatre problèmes motivés par les réseaux de communication modernes ; les outils appropriés pour résoudre ces problèmes ap- partiennent à la théorie des probabilités. La résolution de ces problèmes améliore la compréhension des systèmes physiques initiaux, et contribue en même temps à la théorie puisque de nouveaux résultats théoriques, intéressants en soi, sont prouvés. Deux types de réseaux de communication sont considérés. Les réseaux mobiles sont ces réseaux où les clients se déplacent dans le réseau indépendamment du service qu'ils reçoivent ; contrairement aux réseaux de files d'attente classiques, les transitions des clients ne sont pas liées aux fins de service. Dans les réseaux pair- à-pair, la distinction entre client et serveur est abolie, puisque dans ces réseaux un serveur est un ancien client qui offre le fichier après l'avoir téléchargé. Ces derniers réseaux sont particulièrement efficaces pour disséminer des fichiers gros ou popu- laires. Dans les Chapitres I et II, le comportement stationnaire de tels réseaux est considéré. Dans chaque cas, le réseau est décrit par un processus de Markov à espace d'état discret et à temps continu, et l'on s'intéresse à son ergodicité ou au contraire à sa transience. Une spécificité de ces deux modèles est que les taux de transition des processus de Markov correspondants sont non bornés : dans le cas du réseau mobile du Chapitre I ceci est dû au fait que les clients bougent indépendamment les uns des autres, alors que pour le réseau pair-à-pair du Chapitre II, cela tient au fait que la capacité du système est proportionnelle au nombre de clients. Habituellement, l'analyse de la stabilité d'un réseau stochastique se fait par l'étude des limites d'une suite de processus de Markov correctement renormalisés, appelées limites fluides. Cette procédure est bien adaptée pour les processus “locale- ment additifs”, i.e., les processus qui se comportent localement comme des marches aléatoires ; cette propriété disparaît quand les taux de transition sont non bornés. Ces techniques sont néanmoins adaptées pour étudier la stabilité du réseau mobile du Chapitre I : utiliser des limites fluides pour étudier la stabilité de processus de Markov avec des taux de transition non bornés représente l'une des contributions de ce travail. Le réseau pair-à-pair du Chapitre II ne se prête quant à lui pas à ces tech- niques, et la stabilité découle alors de l'existence d'une fonction de Lyapounov. Un autre ingrédient clef est lié à une classe spéciale de processus de branchement. Ces nouveaux processus de branchement sont définis et étudiés dans le Chapitre II, et des estimations sur leur temps d'extinction permettent, avec des arguments de cou- plage, d'établir des résultats de stabilité du réseau stochastique. Outre le comportement stationnaire des réseaux pair-à-pair, leur comportement transient peut aussi être étudié : ce comportement est l'objet du modèle simple du Chapitre III. Ce modèle se concentre sur l'initialisation d'un réseau pair-à-pair dans un scénario d'arrivée en masse : au temps t = 0, un pair propose un nouveau fichier que N autres pairs veulent télécharger. Contrairement au modèle du Chapitre II, ici le flot d'arrivée de nouvelles requêtes n'est pas stationnaire, il est initialement très intense puis le devient de moins en moins. Bien que le système démarre avec un serveur et beaucoup de clients, le nombre de serveurs disponibles augmente avec le temps et l'on s'intéresse au temps nécessaire pour que le réseau se mette à niveau avec la grande demande initiale. Ce problème engendre un problème de boules et d'urnes intéressant en soi, qui est traité dans le Chapitre IV. Dans ce problème de boules et d'urnes, la distribution de probabilité qui décrit la manière dont les boules sont jetées est aléatoire : il s'agit donc d'un problème de boules et d'urnes en environnement aléatoire. De plus, les boules sont jetées dans un nombre infini d'urnes. Les problèmes de boules et d'urnes avec une infinité d'urnes sont bien étudiés, mais les résultats sur les problèmes de boules et d'urnes en environnement aléatoire sont peu nombreux. Quand il y a une infinité d'urnes, on peut s'intéresser à des quantités géométriques telle que l'emplacement de la première urne vide. De telles quantités ont parfois été étudiées dans des travaux antérieurs, en environnement déterministe : ici, grâce à l'utilisation de processus ponctuels, nous décrivons d'un coup tout le paysage des premières urnes vides, ce qui diffère des travaux précédents. En résumé, cette thèse contribue à la modélisation des réseaux mobiles et pair- à-pair ; d'un point de vue technique, des problèmes liés à la stabilité des processus de Markov, aux processus de branchement et aux problèmes de boules et d'urnes sont résolus.
Loading...