Design of Fault Tolerant Satellite Networks with Priorities via Selectors

摘要

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. In [3], it was proved that N(n, p, 0) ≤ n - p + (n/2) [log_2 p] and some exact values of N(n,p,k) were given when p and k are small. A (n, 0, k)-repartitor (or a (n, n, 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 and N(n,p,k) ≤ S(p,p + k) + S(n + k,p + k) +S(n -p,p + k). Then we prove that S(p,n) ≤ 33n+4p+O(logn) which implies N(n,p,k) ≤ 71n + 37p + 108k+ O(log(n + k)). At last, we study (p,n)-selectors when p is fixed. We prove that: if p is even then S(p,n) ≥(2~(p/2)―1)/(2~(p/2)) n+θ(1); if p us odd then S(p,n) ≥(2~((p+3)/2)―3)/(2~((p+3)/2)) n+θ(1). We conjecture that equality holds and show it for p ≤ 6.