Design of fault-tolerant on-board networks with variable switch sizes

An (n, k, r)-network is a triple N = (G, in, out) where G = (V. E) is a graph and in, out are non-negative integer functions defined on V called the input and output functions, such E that for any v E V, in(v) + out(v) + deg(v) < 2r where deg(v) is the degree of v in the = vev in(v) = n' graph G. The total number of inputs is in(V) and the total number of outputs is out(V) = E v out(v)=n+ k. An (n, k, r)-network is valid, if for any faulty output function out' (that is such that 0 < oue(v) < out(v) for any v e V, and out'(V) = n), there are n edge-disjoint paths in G such that each vertex V E V is the initial vertex of in(v) paths and the terminal vertex of outi(v) paths. We investigate the design problem of determining the minimum number Ai (n, k, r) of vertices in a valid (n,k,r)-network and of constructing minimum (n, k, r)-networks, or at least valid (n, k, r)-networks with a number of vertices close to the optimal value. We first give some upper bounds on Ar(n, k, r). We show _AI (n, k, r) < 1-A-111. When r > k/2, we prove a better upper bound: /V-(n,k, r) < 7.21--22+r+kici22n 4. 0(1). Next, we establish some lower bounds. We show that if k > r, then J\i(n, k, r) > 34. We 2r2k,. improve this bound when k > 2r: Ar(n, k, r) > 3n+2+/3-3r/2 Finally, we determine.A.r(n, k, r) up to additive constants for k < 6. (C) 2014 Published by Elsevier B.V.