Network Effects in Small Networks: A Study of Cooperation
Parham Noorzad · 2017
Communication over a point-to-point link is relatively well understood. However, when such a link is part of a larger network, our understanding is far from complete. Nonetheless, progress in this area has important consequences in both the theoretical and practical aspects of communication networks. In this work, we focus on the role of a single link in networks that in addition to point-to-point links, contain components. An example of a consisting of a single multi-terminal component is the uplink in a wireless communication where multiple transmitters communicate with a single receiver over a shared medium. We demonstrate the existence of a class of such networks where a finite capacity link results in a gain for each source that far exceeds the capacity of that link. This is an example of a network effect: the phenomenon where a resource, here link capacity, is significantly more valuable in a than in isolation. Here we measure the value of the finite capacity link by the sum-capacity gain per source that it enables. The central idea behind the construction of networks that exhibit such effects is the introduction of a node, referred to as the facilitator (CF), that allows other nodes to work together to reduce interference. In the setting of the classical multiple access channel (MAC), an example of a CF is a node that receives rate-limited information from each transmitter and broadcasts rate-limited information back to the transmitters through a common bottleneck link. Let the rate be the capacity of the CF bottleneck link. We show that for a class of MACs, the presence of a CF leads to a sum-capacity gain that, as a function of the cooperation rate, has an infinite slope at cooperation zero. This means that the bottleneck link of the CF is significantly more valuable in some networks than in isolation. This class of MACs includes well-known examples such as the Gaussian MAC and the binary adder MAC. In addition to sum-capacity gain, cooperation under the CF model also improves reliability. Specifically, in the case of the MAC with two transmitters, whenever the CF has full access to both messages, the maximal- and average error capacity regions coincide. This effect is observed even when the cooperation is negligible; that is, the cooperation grows sublinearly in the number of channel uses. An implication of this result is the existence of a whose maximal-error sum-capacity is not continuous with respect to the capacities of its edges; this means that in some networks, even a negligible cooperation leads to a positive sum-capacity gain.