Stabilité des arbres des plus courts chemins en présence de concurrence

摘要

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.%Le problème de la construction d'arbre des plus courts chemins est étudié en présence de nœuds ayant des métriques propres. Ce problème est dérivé du problème de routage interdomaine où chaque nœud (ou système autonome - AS) a sa propre politique de routage. Ici, nous reprenons la modélisation de Grijfin 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.