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,outin,out are non-negative integer functions defined on V called the input and output   functions, such that for any v∈Vv∈V, in(v)+out(v)+deg(v)≤2rin(v)+out(v)+deg(v)≤2r 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)=nin(V)=∑v∈Vin(v)=n, and the total number of outputs is out(V)=∑v∈Vout(v)=n+kout(V)=∑v∈Vout(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∈Vv∈V, and out′(V)=nout′(V)=n), there are n edge-disjoint paths in G   such that each vertex v∈Vv∈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+22r−2⌉⌈n2⌉. When r≥k/2r≥k/2, we prove a better upper bound: N(n,k,r)≤r−2+k/2r2−2r+k/2n+O(1).Next, we establish some lower bounds. We show that if k≥rk≥r, then N(n,k,r)≥3n+k2r. We improve this bound when k≥2rk≥2r: N(n,k,r)≥3n+2k/3−r/22r−2+3r⌊kr⌋.Finally, we determine N(n,k,r)N(n,k,r) up to additive constants for k≤6k≤6.