Minimal Selectors and Fault Tolerant Networks

Omid Amini 1 Frédéric Giroire 2 Florian Huc 1 Stéphane Pérennes 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
2 ALGO - Algorithms
Inria Paris-Rocquencourt
Résumé : Un reseau $\plk$ est un graphe non oriente avec $p + \lambda$ entrees, $p + k$ sorties et des noeuds internes de degre $4$. Un reseau $\plk$ est valide si pour n'importe quel choix de $p$ entrees et de $p$ sorties il existe $p$ chemins aretes disjoints reliant les entrees aux sorties. Dans le cas particulier $\lambda = 0$, un reseau $\plk$ est un {selecteur}. Notre objectif est de determiner $N\plk$ : le nombre minimum de noeuds d'un reseau $\plk$ valide. Pour cela, on utilise une condition suffisante de validite qui nous permet d'obtenir les bornes inferieures pour $N\plk$. D'autre part on propose des constructions de reseaux valides utlisant des {expandeurs}, ce qui donne les bornes supperieures. Le probleme depend tres fortement des ordres de $\lambda$ et $k$, par exemple lorsque $\lambda $ et $k$ sont petits par rapport a $p$, certains patterns sont interdits. Pour les valeurs plus grandes de $\lambda$ et $k$, on peut construire un reseau $\plk$ valide a partir d'un graphe ayant de bonne propriete d'expansion concernant les petits ensembles de sommets. Cela nous emmene a introduire un nouveau parametre : la {robustness}. On obtient dans de nombreux cas des bornes asymptotiques exactes.
Type de document :
Rapport
[Research Report] 2006, pp.24
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00082015
Contributeur : Omid Amini <>
Soumis le : vendredi 7 juillet 2006 - 15:53:38
Dernière modification le : vendredi 25 mai 2018 - 12:02:02
Document(s) archivé(s) le : lundi 5 avril 2010 - 23:25:17

Fichiers

Identifiants

  • HAL Id : inria-00082015, version 1

Collections

Citation

Omid Amini, Frédéric Giroire, Florian Huc, Stéphane Pérennes. Minimal Selectors and Fault Tolerant Networks. [Research Report] 2006, pp.24. 〈inria-00082015〉

Partager

Métriques

Consultations de la notice

308

Téléchargements de fichiers

631