Design of fault-tolerant on-board networks with variable switch sizes
An (n,k,r) ( n , k , r ) -network  is a triple N=(G,in,out) N = ( G , in , out ) where G=(V,E) G = ( V , E ) is a graph and in,out in , out are non-negative integer functions defined on V called the input and output  functions, such that for any v?V v ? V , in(v)+out(v)+deg(v)?2r in ( v ) + out ( v ) + deg ( v ) ? 2 r where deg(v) deg ( v ) is the degree of v in the graph G . The total number of inputs is in(V)=?v?Vin(v)=n in ( V ) = ? v ? V in ( v ) = n , and the total number of outputs is out(V)=?v?Vout(v)=n+k out ( V ) = ? v ? V out ( v ) = n + k . An (n,k,r) ( n , k , r ) -network is valid, if for any faulty  output function out? out ? (that is such that 0?out?(v)?out(v) 0 ? out ? ( v ) ? out ( v ) for any v?V v ? V , and out?(V)=n out ? ( V ) = n ), there are n edge-disjoint paths in G  such that each vertex v?V v ? V is the initial vertex of in(v) in ( v ) paths and the terminal vertex of out?(v) out ? ( v ) paths. We investigate the design problem of determining the minimum number N(n,k,r) N ( n , k , r ) of vertices in a valid (n,k,r) ( n , k , r ) -network and of constructing minimum (n,k,r) ( n , k , r ) -networks, or at least valid (n,k,r) ( 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) N ( n , k , r ) . We show N ( n , k , r ) ? ? k + 2 2 r ? 2 ? ? n 2 ? . When r?k/2 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 k ? r , then N ( n , k , r ) ? 3 n + k 2 r . We improve this bound when k?2r 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) N ( n , k , r ) up to additive constants for k?6 k ? 6 .
fault tolerance switching networks flow networks vulnerability