Towards an Information Theory of Large Networks: An Achievable Rate Region

We study communication networks of arbitrary size and topology under a general vector discrete memoryless channel. We propose an information-theoretic constructive scheme for obtaining an achievable rate region in such networks. Many well-known capacity-defining achievable rate regions can be derived as special cases of the proposed scheme. A few such examples are the physically degraded and reversely-degraded relay channels, the Gaussian multiple access channel, and the Gaussian broadcast channel. The proposed scheme also leads to inner bounds for the multicast and allcast capacities. Applying the proposed scheme to a specific wireless network of $n$ nodes located in a region of unit area, we show that a transport capacity} of $Theta(n)$ bit-meters/sec is feasible in a certain family of networks, as compared to the best possible transport capacity of $Theta(sqrt{n})$ bit-meters/sec shown earlier in [14] where the receiver capabilities were limited. Even though the improvement is shown for a specific class of networks, a clear implication is that designing and employing more sophisticated multi-user coding schemes can provide sizable gains in at least some large wireless networks.