Skip to Main content Skip to Navigation

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.
Document type :
Complete list of metadata

Cited literature [5 references]  Display  Hide  Download
Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 7:17:08 PM
Last modification on : Wednesday, October 14, 2020 - 4:23:50 AM
Long-term archiving on: : Sunday, April 4, 2010 - 8:21:13 PM


  • HAL Id : inria-00070160, version 1


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⟩



Record views


Files downloads