ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique
Auteurs : soumettez
votre article en ligne
Autres revues >>

Technique et Science Informatiques

0752-4072
Revue des sciences et technologies de l'information
 

 ARTICLE VOL 30/7 - 2011  - pp.781-808  - doi:10.3166/tsi.30.781-808
TITRE
Analyse du nombre de perturbations lors du maintien d’un arbre de connexion de faible diamètre

TITLE
Analysis of the number of rebuilding steps in an update process of a connection tree

RÉSUMÉ
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).


ABSTRACT
Many internet distributed services, as games or virtual meetings, are massive (many participants), dynamic (members can join and leave) and connected. A tree can be used to connects the members. The dynamic aspect implies that this tree must be updated and its quality must be controlled. In this paper we propose an analysis of the number of changes in routing paths that are necessarily to keep a good quality (we call that a rebuilding). We show in a first part that in the worst case, a rebuilding is necessarily more or less at each step, for any algorithm. In a second part we propose a simple updating algorithm and we prove (using random walks) that it makes at most a logarithmic (in the number of events) number of rebuilding.


AUTEUR(S)
Étienne BIRMELÉ, François DELBOT, Christian LAFOREST, Nicolas THIBAULT

MOTS-CLÉS
arbre de connexion, dynamicité, marche aléatoire, analyse en moyenne.

KEYWORDS
connection tree, dynamicity, random walks, average analysis.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 12.5 €
• Non abonné : 25.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (369 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier