Inondation dans les réseaux dynamiques - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

Inondation dans les réseaux dynamiques

Résumé

Cette note résume nos travaux sur l'inondation dans les réseaux dynamiques. Ces derniers sont définis à partir d'un processus Markovien de paramètres $p$ et $q$ générant des séquences de graphes $(G_0,G_1,G_2,\ldots)$ sur un même ensemble $[n]$ de sommets, et tels que $G_t$ est obtenu à partir de $G_{t-1}$ comme suit~: si $e\notin E(G_{t-1})$ alors $e\in E(G_{t})$ avec probabilité $p$, et si $e\in E(G_{t-1})$ alors $e\notin E(G_{t})$ avec probabilité $q$. Clementi et al. (PODC 2008) ont analysé différent processus de diffusion de l'information dans de tels réseaux, et ont en particulier établi un ensemble de bornes sur les performances de l'inondation. L'inondation consiste en un protocole élémentaire où chaque n{\oe}ud apprenant une information à un temps $t$ la retransmet à tous ses voisins à toutes les étapes suivantes. Evidemment, en dépit de ses avantages en terme de simplicité et de robustesse, le protocole d'inondation souffre d'une utilisation abusive des ressources en bande passante. Dans cette note, nous montrons que l'inondation dans les réseaux dynamiques peut être mis en {\oe}uvre de façon à limiter le nombre de retransmissions d'une même information, tout en préservant les performances en termes du temps mis par une information pour atteindre tous les n{\oe}uds du réseau. La principale difficulté de notre étude réside dans les dépendances temporelles entre les connexions du réseaux à différentes étapes de temps.
Fichier principal
Vignette du fichier
FloodingAlgoTel.pdf (67.16 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00383915 , version 1 (13-05-2009)

Identifiants

  • HAL Id : inria-00383915 , version 1

Citer

Hervé Baumann, Pierluigi Crescenzi, Pierre Fraigniaud. Inondation dans les réseaux dynamiques. AlgoTel, 2009, Carry-Le-Rouet, France. ⟨inria-00383915⟩
135 Consultations
71 Téléchargements

Partager

Gmail Facebook X LinkedIn More