On the Multiple-Unicast Capacity of 3-Source, 3-Terminal Directed Acyclic Networks

作者：Shurui Huang, Aditya Ramamoorthy · 发表于：IEEE/ACM Transactions on Networking · 年份：2013 · DOI：10.1109/tnet.2013.2270438 · 被引用次数：20 · 研究领域：Cooperative Communication and Network Coding、Wireless Communication Security Techniques、Mobile Ad Hoc Networks

We consider the multiple-unicast problem with three source-terminal pairs over directed acyclic networks with unit-capacity edges. The three si-tipairs wish to communicate at unit-rate via network coding. The connectivity between the si-tipairs is quantified by means of a connectivity-level vector, [k1k2k3] such that there exist kiedge-disjoint paths between si and ti. In this paper, we attempt to classify networks based on the connectivity level. It can be observed that unit-rate transmission can be supported by routing if ki≥ 3, for all i = 1, ..., 3. In this paper, we consider connectivity-level vectors such that mini=1,...,3ki<; 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.