Sparse asymmetric connectors in communication networks

An (n, N, d)-connector is an acyclic digraph with n inputs and N outputs in which for any injective mapping of input vertices into output vertices there exist n vertex disjoint paths of length d joining each input to its corresponding output. We consider the problem of construction of sparse (n, N, 2)-connectors (depth 2 connectors) when n≪N. The probabilistic argument in [A. Baltz, G. Jäger, A. Srivastav, Elementary constructions of sparse asymmetric connectors, in Proceedings of the 23rd Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Mumbai, India, LNCS 2914, 13-22, December 2003] shows the existence of (n, N, 2)-connectors of size (number of edges) O(N) if n⩽N1/2−ɛ, ɛ>0. However, the known explicit constructions with n⩽N in [F.K. Hwang, G.W. Richards, “A two-stage rearrangeable broadcast switching network”, IEEE Trans. on Communications 33 (1985) 1025-1035],[A. Baltz, G. Jäger, A. Srivastav, Elementary constructions of sparse asymmetric connectors, in Proceedings of the 23rd Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Mumbai, India, LNCS 2914, 13-22, December 2003],[A. Baltz, G. Jäger, A. Srivastav, Constructions of sparse asymmetric connectors with Number Theoretic methods, submitted to Networks] are of size O(Nn). Here we present a simple combinatorial construction for (n, N, 2)-connectors of size O(Nlog2n). We also consider depth 2 fault-tolerant connectors under arc or node failures.