Design of fault-tolerant on-board networks with variable switch sizes

Olivier Delmas 1 Frédéric Havet 2 Mickaël Montassier 3 Stéphane Pérennes 2
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
3 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : An \emph{$(n,k,r)$-network} is a triple $N=(G,\inp,\outp)$ where $G=(V,E)$ is a graph and $\inp,\outp$ are non-negative integer functions defined on $V$ called the \emph{input} and \emph{output} functions, such that for any $v \in V$, $\inp(v)+\outp(v)+ \degree(v)\leq 2r$ where $\degree(v)$ is the degree of $v$ in the graph $G$. The total number of inputs is $\inp(V)=\sum_{v\in V}\inp(v)=n$, and the total number of outputs is $\outp(V)=\sum_{v\in V}\outp(v)=n+k$. An $(n,k,r)$-network is \emph{valid}, if for any \emph{faulty} output function $\outp'$ (that is such that $0\leq \outp'(v) \leq \outp(v)$ for any $v \in V$, and $\outp'(V) = n$), there are $n$ edge-disjoint paths in $G$ such that each vertex $v\in V$ is the initial vertex of $\inp(v)$ paths and the terminal vertex of $\outp'(v)$ paths. We investigate the design problem of determining the minimum number ${\cal N}(n,k,r)$ 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 give some upper bounds on ${\cal N}(n,k,r)$. We show ${\cal N}(n,k,r)\leq \left\lceil \frac{k+2}{2r-2}\right\rceil \left\lceil\frac{n}{2}\right\rceil$. When $r\geq k/2$, we prove a better upper bound: ${\cal N}(n,k,r) \leq \frac{r-2+k/2}{r^2-2r+k/2} n + O(1)$. Next, we establish some lower bounds. We show that if $k\geq r$, then ${\cal N}(n,k,r) \geq \frac{3n+k}{2r}$. We improve this bound when $k\geq 2r$: $\displaystyle {\cal N}(n,k,r) \geq \formule$. Finally, we determine ${\cal N}(n,k,r)$ up to additive constants for $k\leq 6$.
Document type :
Journal articles
Liste complète des métadonnées

Cited literature [10 references]  Display  Hide  Download
Contributor : Frederic Havet <>
Submitted on : Monday, November 13, 2017 - 10:17:04 PM
Last modification on : Friday, April 12, 2019 - 10:18:10 AM
Document(s) archivé(s) le : Wednesday, February 14, 2018 - 12:37:48 PM


Files produced by the author(s)



Olivier Delmas, Frédéric Havet, Mickaël Montassier, Stéphane Pérennes. Design of fault-tolerant on-board networks with variable switch sizes. Theoretical Computer Science, Elsevier, 2015, 562, pp.75-89. ⟨10.1016/j.tcs.2014.09.034⟩. ⟨hal-01111370⟩



Record views


Files downloads