Local View Capacity of Networks

Driving Question: The operational capacity of most networks is often much lower than the information theoretic predictions. A key element of any information theoretic analysis is the amount and type of information about the network which is either implicitly or explicitly made available to the network nodes. For example, often the nodes not only know the network topology, but channel statistics and/or channel realizations of not only their one-hop neighbours but also nodes further away from them. Implicitly, the network size is assumed to be constant and known to all nodes.

On other hand, operational networks cannot make any of the above simplifying assumptions. Hence the protocol design has to account for unknown and time-varying nature of many network parameters like size, channels, queues etc. All the protocols consume valuable network resources (time/bandwidth/power) which one would ideally want to use to send data, not control information. While it is clear that we cannot escape “protocol overhead” in some form, the fundamental question is

“what is the true network capacity?”
Uncertainity Models: Seen from the perspective of any node in the network, whether it is an infrastructure node (like a base-station or access point) or a mobile node, the knowledge it has about the network is limited. And often it is limited to be local. The locality makes sense for (i) since the local information is the easiest to measure and pass around, and (ii) the local parameters impact the success and rate of communication the most (one would guess). As a result, in all practical wireless networks, no node has a global view of the network. Instead the nodes have a local view which are mismatched from each other’s. So in the figure below, Node~A’s knowledge about the network is different from Node B and C’s view of the network.

 

 

This mismatched view of the network is an important but poorly understood aspect in theory. A well-studied example of this mismatched information is the hidden node problem in wireless networks. The view mismatch can be related to any kind of information – channel states, number of nodes, statistics of the links, queue states, to name a few.

The seeds of mismatched local views can be traced to our prior work in understanding power control over noisy feedback links, which led to transmitter and receiver being mismatched in their knowledge about the channel (see Asilomar 2008, IEEE IT 2010 and IEEE IT 2011 papers).

Local View Capacity: In our initial investigation of the work, we formalized the h-hop uncertainty model, where each node only knows about the channels which are h-hops away from it. This model is simple to specify (only one parameter h) and can be motivated by message passing algorithm (which is essentially every protocol). We noted that even in this simple model, the key essence of the problem can be captured – mismatched knowledge means that nodes cannot align their decisions and as a result, these distributed decisions can lead to significantly reduced performance.

Realizing that distributed decisions seldom lead to globally optimal choices, we proposed studying local view capacity using the metricnormalized sum-capacity – which measures the fraction of global-view capacity which can be achieved with an uncertainty model. This allows quantification of the loss due to mismatched local views. An important by-product of studying normalized sum-capacity is that it is easier to find than actual capacity of the network.

While we continue studying the normalized sum-capacity, we have also made in-roads in defining and studying the whole capacity region with local views. It turns out that local view capacity requires a re-thinking of the definition of capacity region.