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

Olivier Delmas 1 Frédéric Havet 2 Mickaël Montassier 3
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , 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$.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2015, 562, pp.15
Liste complète des métadonnées

https://hal.inria.fr/hal-01111370
Contributeur : Frederic Havet <>
Soumis le : vendredi 30 janvier 2015 - 11:28:47
Dernière modification le : jeudi 21 janvier 2016 - 01:13:41

Identifiants

  • HAL Id : hal-01111370, version 1

Collections

Citation

Olivier Delmas, Frédéric Havet, Mickaël Montassier. Design of fault-tolerant on-board networks with variable switch sizes. Theoretical Computer Science, Elsevier, 2015, 562, pp.15. <hal-01111370>

Partager

Métriques

Consultations de la notice

226