Stochastic Networks and Algorithms

Réseaux Stochastiques et Algorithmes

Philippe Robert (1)

1 RAP - Networks, Algorithms and Probabilities

In this document, scaling methods used to analyze stochastic networks are presented. Ths first class of scaling investigated is the fluid limit regime, Markov jump processes are scaled in time and space in order to get a kind of functional law of large numbers for these processes. Several aspects of these scalings are discussed: non-deterministic fluid limits and the infinite dimensional case when the Markov processes are string valued. Studies concerning large networks with either a large number of nodes (thermodynamic limit regime) or with links of large capacity (Kelly's scaling) are also discussed.
The mathematical studies of several distributed algorithms used in these stochastic networks are presented. The emphasis is on the probabilistic methods used in a context which is not necessarily probabilistic. It is shown in particular how they can extend and simplify the results previously known in this domain.

Ce document présente plusieurs méthodes de renormalisation utilisées dans l'étude des réseaux stochastiques. En premier lieu il s'agit d'analyser les limites de processus markoviens de sauts renormalisés en temps et en espace suivant une échelle d'Euler (type loi fonctionnelle des grands nombres). Plusieurs aspects sont détaillés: la question des limites non déterministe et ses conséquences, ainsi que le cas de la dimension infinie intervenant pour les processus de Markov à valeurs dans
les chaînes de caractères. L'étude des réseaux avec un grand nombre de noeuds (limite thermodynamique) ou avec des liens de capacité très grandes (Régime limite de Kelly) est discuté ainsi que les perspectives de ce type d'étude.
L'étude mathématique de plusieurs algorithmes distribués gérant des réseaux stochastiques est présentée. L'accent est mis sur les méthodes probabilistes utilisées dans un contexte qui n'est pas nécessairement probabiliste, elles permettent notamment d'étendre et de simplifier une partie des résultats connus dans ce domaine.

Mots clés: Stochastic Networks; Algorithms; Fluid Limits

Domaines: Mathématiques [math]

Philippe Robert. Réseaux Stochastiques et Algorithmes. Mathématiques [math]. Université Pierre et Marie Curie - Paris VI, 2006. ⟨tel-00166813⟩