On the multiple unicast capacity of 3-source, 3-terminal directed acyclic networks

الأصل · EN

We consider the multiple unicast problem with three source-terminal pairs over directed acyclic networks with unit-capacity edges. The three sᵢ-tᵢ pairs wish to communicate at unit-rate via network coding. The connectivity between the sᵢ - tᵢ pairs is quantified by means of a connectivity level vector, [k₁ k₂ k₃] such that there exist kᵢ edge-disjoint paths between sᵢ and tᵢ. In this work we attempt to classify networks based on the connectivity level. It can be observed that unit-rate transmission can be supported by routing if kᵢ ≥ 3, for all i = 1,, 3. In this work, we consider, connectivity level vectors such that = 1,, 3 kᵢ < 3. We present either a constructive linear network coding scheme or an instance of a network that cannot support the desired unit-rate requirement, for all such connectivity level vectors except the vector [1 2 4] (and its permutations). The benefits of our schemes extend to networks with higher and potentially different edge capacities. Specifically, our experimental results indicate that for networks where the different source-terminal paths have a significant overlap, our constructive unit-rate schemes can be packed along with routing to provide higher throughput as compared to a pure routing approach.