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/10 - 2011  - pp.1167-1189  - doi:10.3166/tsi.30.1167-1189
TITRE
Stabilité des arbres des plus courts chemins en présence de concurrence

TITLE
Stability of selfish shortest path tree

RÉSUMÉ

Le problème de la construction d’arbre des plus courts chemins est étudié en présence de noeuds ayant des métriques propres. Ce problème est dérivé du problème de routage interdomaine où chaque noeud (ou système autonome - AS) a sa propre politique de routage. Ici, nous reprenons la modélisation de Griffin et al. sous forme de jeu en l’étendant au fait qu’il puisse exister des coalitions. Ensuite nous donnons une condition suffisante sur l’existence d’un tel arbre. Finalement, nous présentons un algorithme autostabilisant sur une instance possédant un arbre des plus courts chemins dans ce contexte.



ABSTRACT

The shortest path tree problem is studied in the context that each node has this own metric. This problem is connected to inter-domain routing where each node (AS) has policybased metric. Here, we extend the work of Griffin et al. In fact, we also consider that there exist some coalitions. Next, we give somes properties of the instances having such tree. Finally, we present a self-stabilizing algorithm and we show that it converges to a solution of an instance if it instance contains such shortest path tree.



AUTEUR(S)


MOTS-CLÉS
plus court chemin, routage interdomaine, autostabilisation, théorie des jeux.

KEYWORDS
shortest path, inter-domain routing, self-stabilization, game theory.

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  (471 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

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

 English version >> 
Lavoisier