HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadata

Cited literature [5 references]  Display  Hide  Download

https://hal.inria.fr/inria-00070160
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 7:17:08 PM
Last modification on : Monday, December 20, 2021 - 4:50:11 PM
Long-term archiving on: : Sunday, April 4, 2010 - 8:21:13 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

161

Files downloads

96