An achievable region for double-unicast networks with linear network coding

Abstract

In this paper, we present an achievable rate region for double-unicast networks by assuming that the intermediate nodes perform random linear network coding, and the source and sink nodes optimize their strategies to maximize the achievable region. Such a setup can be modeled as a deterministic interference channel, whose capacity region is known. For the particular class of linear deterministic interference channels of our interest, in which the outputs and interference are linear deterministic functions of the inputs, we show that the known capacity region can be achieved by linear strategies. As a result, for a given set of network coding coefficients chosen by the intermediate nodes, the proposed linear precoding and decoding for the source and sink nodes will give the maximum achievable rate region for double-unicast networks. We further derive a suboptimal but easy-to-compute rate region that is independent of the network coding coefficients used at the intermediate nodes, and is instead specified by the min-cuts of the network. It is found that even this suboptimal region is strictly larger than the existing achievable rate regions in the literature.