Minimal Selectors and Fault Tolerant Networks
In this article, we study a combinatorial optimization problem arising from on-board networks in satellites. In these kinds of networks, the entering signals (inputs) should be routed to amplifiers (outputs). The connections are made via expensive switches with four available links. The paths connecting inputs to outputs should be link-disjoint. More formally, we call a (p, lambda, k) network an undirected graph with p + lambda inputs, p + k outputs, and internal vertices of degree four. A (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 lambda faulty inputs and k faulty outputs, there exist p edge-disjoint paths from the remaining inputs to the remaining outputs. Our optimization problem consists of determining N(p, lambda, k), the minimum number of vertices in a valid (p, lambda, k) network. We present validity certificates and a quasi-partitioning technique from which we derive lower bounds for N(p, lambda, k). We also provide constructions, and hence upper bounds, based on expanders. The problem is shown to be sensitive to the order of lambda and k. For instance, when lambda and k are small compared with p, the question reduces to the avoidance of some 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 for larger values of k and lambda. In many cases, we provide asymptotically tight bounds for N(p, lambda, k). (C) 2009 Wiley Periodicals, Inc. NETWORKS, Vol. 55(4), 326-340 2010
fault tolerant networks routing connectivity expanders switching networks network design concentrators disjoint paths