Skip to Main content Skip to Navigation

Design of fault tolerant on board networks with priorities via selectors

Frédéric Havet 1
1 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 : We consider on-board networks in satellites interconnecting entering signals (inputs) to amplifiers (outputs). The connections are made via expensive switches with four links available. The paths connecting inputs to outputs should be link-disjoint. Among the input signals, some of them, called priorities, must be connected to the amplifiers which provide the best quality of service (that is to some specific outputs). In practice, amplifiers are subject to faults that cannot be repaired. Therefore we need to add extra outputs to ensure the existence of sufficiently many valid ones. Given n inputs, p priorities and k faults, the problem consists in designing a low cost network (i. e. with the minimum number of switches) where it is possible to route the p priorities to the p best quality amplifiers and the other inputs to some valid amplifiers, for any sets of k faulty and p best quality amplifiers. Let N(n,p,k) be the minimum number of switches of a such a network, called repartitor. Bermond, Havet and Toth proved that N(n,p,0)< n-p + n/2 log p and some exact values of N(n, p, k) were given when p and k are small. A (n,0, k)-repartitor is called a (n, n+k)-selector and the minimum number of switches of a (p, n)-selector is denoted by S(p, n). A selector is intrinsically easier to design than general repartitors since there exists only one type of signals to route instead of two. The approach of this paper is to construct (n, p, k)-repartitors from selectors. We show that N(n, p, k) < S( p, p+k) + S(n+k, p+k) + S(n-p, p+k) + n + k. Then we prove that S(p, n) < 33 n + 4 p + O(log n) which implies N( n, p, k)< 71 n + 37 p + 108 k + O(log ( n+ k)). At last, we exhibit minimum (p, n)-selectors when p is at most 6.
Document type :
Complete list of metadata
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 7:51:03 PM
Last modification on : Monday, October 12, 2020 - 10:30:21 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:54:25 PM


  • HAL Id : inria-00072125, version 1



Frédéric Havet. Design of fault tolerant on board networks with priorities via selectors. RR-4463, INRIA. 2002. ⟨inria-00072125⟩



Record views


Files downloads