Asymptotic behavior of network capacity under spatial network coding

We study the asymptotic behavior of the capacity of erasure networks under a restricted class of network coding schemes, called spatial network coding. In spatial network coding, nodes are permitted to only combine data units received from distinct incoming links; multiple data units arriving on the same link may not be coded together. Elsewhere, it has been shown that the network capacity under spatial network coding is the statistical mean of the minimum cut value. In this paper, we come up with a new concept in the random graph theory referred to as typical min-cut family, which parallels the information theoretic notion of typical sequences, and use it to develop an analytical tool for the comparison of the capacity under spatial network coding and the capacity under unrestricted coding. Applying this tool to point-to-point erasure networks with a regular multi-layer topology, we show that, as the number of nodes per layer increases, the capacity under spatial network coding asymptotically converges to the capacity under unrestricted coding, provided that the number of layers separating the source and the destination does not increase faster than exponentially, with respect to the number of nodes per layer. Numerical study, showing fast convergence, suggests that spatial diversity may be exploited through network coding to provide an effective substitute for time diversity, where the latter cannot be exploited.