Group for Research in Decision Analysis

Minimal Selectors and Fault Tolerant Networks

Florian Huc – INRIA, France

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 $$N(p,\lambda,k)$$-network an undirected graph with $$p+\lambda$$ inputs, $$p+k$$ outputs and internal vertices of degree four. A $$N(p,\lambda,k)$$-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 $$N(p,\lambda,k)$$-network is already known as a selector.

Our optimization problem consists of determining $$N(p,\lambda,k)$$-, the minimum number of nodes in a valid $$N(p,\lambda,k)$$-network.