Network Effects in Small Networks: A Study of Cooperation

Citation

Noorzad, Parham (2017) Network Effects in Small Networks: A Study of Cooperation. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/Z9M32STV. https://resolver.caltech.edu/CaltechTHESIS:06062017-101123885

Abstract

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 "multi-terminal components." An example of a network consisting of a single multi-terminal component is the uplink in a wireless communication network 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 rate 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 network 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 "cooperation facilitator" (CF), that allows other network 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 "cooperation 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 rate 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 rate is "negligible"; that is, the cooperation rate grows sublinearly in the number of channel uses. An implication of this result is the existence of a network 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 rate leads to a positive sum-capacity gain.

Thesis Files