Design of fault-tolerant on-board network

Olivier Delmas 1 Mickael Montassier 1 Frédéric Havet 2 Stéphane Pérennes 2
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : An $(n,k,r)$-network is a triple $N=(G,in,out)$ where $G=(V,E)$ is a graph and $in,out$ are integral functions defined on $V$ called input and output functions, such that for any $v \inV$, $in(v)+out(v)+ deg(v)\leq2r$ with $deg(v)$ the degree of $v$ in the graph $G$. The total number of inputs is $in(V)=\sum_v\inVin(v)=n$, and the total number of outputs is $out(V)=\sum_v\inVout(v)=n+k$. An $(n,k,r)$-network is valid, if for any faulty output function $out'$ (that is such that $out'(v) \leqout(v)$ for any $v \inV$, and $out'(V) = n$), there are $n$ edge-disjoint paths in $G$ such that each vertex $v\inV$ is the initial vertex of $in(v)$ paths and the terminal vertex of $out'(v)$ paths. We investigate the design problem of determining the minimum number of vertices in a valid $(n,k,r)$-network and of constructing minimum $(n,k,r)$-networks, or at least valid $(n,k,r)$-networks with a number of vertices close to the optimal value. We first show $\frac3n+k2r-2+ \frac3r^2k \leq\calN(n,k,r)\leq\left\lceil\frack+22r-2\right\rceil\fracn2$. We prove a better upper bound when $r\geqk/2$: $\calN(n,k,r) \leq\fracr-2+k/2r^2-2r+k/2 n + O(1)$. Finally, we give the exact value of $\calN(n,k,r)$ when $k\leq6$ and exhibit the corresponding networks.
Type de document :
Rapport
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00070160
Contributeur : Rapport de Recherche Inria <>
Soumis le : vendredi 19 mai 2006 - 19:17:08
Dernière modification le : lundi 5 novembre 2018 - 15:36:03
Document(s) archivé(s) le : dimanche 4 avril 2010 - 20:21:13

Fichiers

Identifiants

  • HAL Id : inria-00070160, version 1

Citation

Olivier Delmas, Mickael Montassier, Frédéric Havet, Stéphane Pérennes. Design of fault-tolerant on-board network. [Research Report] RR-5866, INRIA. 2006, pp.20. ⟨inria-00070160⟩

Partager

Métriques

Consultations de la notice

411

Téléchargements de fichiers

178