Skip to Main content Skip to Navigation
New interface
Journal articles

Minimal selectors and fault tolerant networks

Omid Amini 1 Frédéric Giroire 2 Florian Huc 3 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 : In this paper we study a combinatorial optimization problem issued from on-board networks in satellites. In this kind of networks the entering signals (inputs) should be routed to amplifiers (outputs). The connections are made via expensive switches with four links available. The paths connecting inputs to outputs should be link-disjoint. More formally, we call it $\plk-$network an undirected graph with $p+\lambda$ inputs, $p+k$ outputs and internal vertices of degree four. A $\plk-$network is valid if it is tolerant to a restricted number of faults in the network, i.e. if for any choice of at most $k$ faulty inputs and $\lambda$ faulty outputs, there exist $p$ edge-disjoint paths from the remaining inputs to the remaining outputs. In the special case $\lambda=0$, a $\plk-$network is already known as a selector. Our optimization problem consists of determining $N\plk$, the minimum number of nodes in a valid $\plk-$network. For this, we present validity certificates and a gluing lemma from which derive lower bounds for $N\plk$. We also provide constructions, and hence upper bounds, based on expanders. The problem is very sensitive to the order of $\lambda$ and $k$. For instance, when $\lambda$ and $k$ are small compared to $p$, the question reduces to avoid certain forbidden local configurations. For larger values of $\lambda$ and $k$, the problem is to find graphs with a good expansion property for small sets. This leads us to introduce a new parameter called $\alpha$-robustness. We use $\alpha$-robustness to generalize our constructions to higher order values of $k$ and $\lambda$. In many cases, we provide asymptotically tight bounds for $N\plk$.
Document type :
Journal articles
Complete list of metadata

Cited literature [30 references]  Display  Hide  Download
Contributor : Frédéric Giroire Connect in order to contact the contributor
Submitted on : Friday, May 21, 2010 - 6:47:34 PM
Last modification on : Tuesday, October 25, 2022 - 4:17:03 PM
Long-term archiving on: : Thursday, September 16, 2010 - 3:15:27 PM


Files produced by the author(s)



Omid Amini, Frédéric Giroire, Florian Huc, Stéphane Pérennes. Minimal selectors and fault tolerant networks. Networks, 2010, 55 (4), pp.326-340. ⟨10.1002/net.20326⟩. ⟨inria-00485848⟩



Record views


Files downloads