Maximum Throughput Gain of Compute-and-Forward for Multiple Unicast

Compute-and-Forward (CF), also known as reliable physical layer network coding, is a technique that provides the possibility of exploiting the features of broadcast and superposition in wireless networks. It has been shown that the throughput for multiple unicast traffic can be significantly boosted by CF. In this letter, the limit of such improvement is investigated by comparing the performance of CF with the traditional routing-based transmission schemes. For networks characterized by local interference and half-duplex constraints, it is proven that the throughput gain of CF over traditional routing, expressed by an improvement factor, is upper bounded by $3K$, where $K$ is the number of unicast sessions. Furthermore, a class of networks is presented for which an improvement by a factor of $K/2$ is feasible by applying CF. Hence, the throughput gain of CF is at most on the order of $K$ for any network, and a gain in that order is indeed achievable for some networks.