Capacity of Erasure Networks under Spatial Network Coding

We study the capacity of point-to-point erasure networks under a restricted form of network coding to which we refer as spatial network coding. In this form of coding, the nodes can not perform coding on successive packets which are received from one incoming link. The coding at a node is restricted to the packets received at the same time slot from different incoming links to the node. In other words, the temporal aspect of coding is absent.We prove that the capacity of a unicast session under spatial network coding is the statistical average of the minimum cut of the random graph corresponding to the erasure network. Then, we consider a network with a complete, directed and acyclic graph in which the nodes are erased independently. We prove that the capacity of the network under spatial network coding is the same as its capacity under general network coding. This shows that temporal coding has no improving effect for this network. Finally, we compare the capacities under different coding schemes for the complete graph with the edges that are erased independently.