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 that for any v ? V , in ( v ) + out ( v ) + deg ( v ) ? 2 r where deg ( v ) is the degree of v in the graph G. The total number of inputs is in ( V ) = ? v ? V in ( v ) = n , and the total number of outputs is out ( V ) = ? v ? V out ( v ) = n + k .An ( n , k , r ) -network is valid, if for any faulty output function out ' (that is such that 0 ? out ' ( v ) ? out ( v ) for any v ? V , and out ' ( V ) = n ), there are n edge-disjoint paths in G such that each vertex v ? V is the initial vertex of in ( v ) paths and the terminal vertex of out ' ( v ) paths.We investigate the design problem of determining the minimum number N ( 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 N ( n , k , r ) . We show N ( n , k , r ) ? ? k + 2 2 r - 2 ? ? n 2 ? . When r ? k / 2 , we prove a better upper bound: N ( n , k , r ) ? r - 2 + k / 2 r 2 - 2 r + k / 2 n + O ( 1 ) .Next, we establish some lower bounds. We show that if k ? r , then N ( n , k , r ) ? 3 n + k 2 r . We improve this bound when k ? 2 r : N ( n , k , r ) ? 3 n + 2 k / 3 - r / 2 2 r - 2 + 3 r ? k r ? .Finally, we determine N ( n , k , r ) up to additive constants for k ? 6 .