Fault tolerant on board networks with priorities

Jean-Claude Bermond 1 Frédéric Havet 1 C.D. Toth 2
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , 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, each of which has four available links. The paths connecting inputs to outputs should be link-disjoint. Some of the input signals, 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 prone to fail and the faults cannot be repaired. Therefore, extra outputs have to be built into the network to ensure that every input can be routed to operational outputs. Given three integers, $n$, $p$, and $f$, we would like to design a low cost network (where the network cost is proportional to the total number of switches) such that it is possible to route all $n$ inputs to $n$ operational amplifiers, and to route the $p$ priorities to the $p$ best quality amplifiers for any set of $f$ faulty and $p$ best-quality amplifiers. Let $R(n,p,f)$ be the minimum number of switches of such a network. We prove here that $R(n,p,f)\leq \frac{n+f}{2} \lceil \log_2 p \rceil +\frac{5}{2}(n-p) +g(f)$ with $g$ a function depending only on $f$. We then compute $R(n,p,f)$ exactly for a few small values of $p$ and $f$.
Type de document :
Article dans une revue
Networks, Wiley, 2006, 47 (1), pp.9-25
Liste complète des métadonnées


https://hal.inria.fr/inria-00430156
Contributeur : Jean-Claude Bermond <>
Soumis le : jeudi 5 novembre 2009 - 18:16:13
Dernière modification le : jeudi 5 novembre 2009 - 20:22:59
Document(s) archivé(s) le : jeudi 17 juin 2010 - 19:32:33

Fichier

BHT06.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00430156, version 1

Collections

Citation

Jean-Claude Bermond, Frédéric Havet, C.D. Toth. Fault tolerant on board networks with priorities. Networks, Wiley, 2006, 47 (1), pp.9-25. <inria-00430156>

Partager

Métriques

Consultations de
la notice

227

Téléchargements du document

90