Design of fault-tolerant on-board networks with variable switch sizes - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2015

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

Résumé

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$.
Fichier principal
Vignette du fichier
revise.pdf (353.51 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01111370 , version 1 (13-11-2017)

Identifiants

Citer

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, 2015, 562, pp.75-89. ⟨10.1016/j.tcs.2014.09.034⟩. ⟨hal-01111370⟩
376 Consultations
124 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More