Analyse du nombre de perturbations lors du maintien d'un arbre de connexion de faible diamètre - Archive ouverte HAL Access content directly
Journal Articles Revue des Sciences et Technologies de l'Information - Série TSI : Technique et Science Informatiques Year : 2011

Analyse du nombre de perturbations lors du maintien d'un arbre de connexion de faible diamètre

(1) , (2) , (2)
1
2

Abstract

Certains services répartis sur internet comme les jeux ou les réunions virtuelles sont massifs (nombreux participants), évolutifs (les membres entrent et sortent au fil du temps) et connectés. Un arbre peut être utilisé pour connecter les divers participants. La non-permanence des membres fait que cet arbre doit être mis à jour pour s'adapter et sa qualité doit être maîtrisée. Dans cet article, nous proposons une analyse du nombre de fois où il faut modifier en profondeur les routes déjà existantes pour conserver une bonne qualité de l'arbre (ce que nous appelons reconstruction). Nous montrons que dans le pire cas une reconstruction est nécessaire quasiment à chaque étape et ceci quel que soit l'algorithme mis en œuvre. Nous proposons également un algorithme simple de mise à jour et nous prouvons que celui-ci ne fait en moyenne qu'au plus un nombre logarithmique de reconstructions (en nombre d'événements).

Dates and versions

hal-00730900 , version 1 (11-09-2012)

Identifiers

Cite

Etienne Birmele, François Delbot, Christian Laforest. Analyse du nombre de perturbations lors du maintien d'un arbre de connexion de faible diamètre. Revue des Sciences et Technologies de l'Information - Série TSI : Technique et Science Informatiques, 2011, 30 (7), pp.781--808. ⟨10.3166/tsi.30.781-808⟩. ⟨hal-00730900⟩
85 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More