The Capacity Of Certain Communication Networks


Michael Gastpar


Information theory provides a variety of tools that permit a quite detailed analysis of point-to-point communication systems. In particular, it gives upper bounds on the performance of any coding technique, no matter how sophisticated. Unfortunately, it is not easy to generalize those tools to the analysis of communication networks. Several attempts have been made in the last three decades, and results have been found for very small and for very simple networks. Among the most recent attempts is a paper by Gupta and Kumar, IEEE Trans Info Theory, March 2000. Their approach is to study the performance of a quite simple (but still fairly general) network as the number of nodes in the network tends to infinity. However, their results are not information-theoretic; they cannot be argued to be outer limits to the performance. More precisely, the authors consider only point-to-point communication, hence no multi-accessing, broadcasting etc. is included in their approach. Our project was triggered by that paper, and the omissions therein. On the one hand, we apply their kind of analysis to other networks, on the other, the quest is to derive true outer bounds to the performance of their network.

Main contributions

The major parameters for a network are: node locations, interaction mechanism and traffic pattern. We play with these parameters and perform an analysis similar to Gupta and Kumar. For example, we considered partially wired networks (node pairs to be connected by a wire are selected uniformly at random), and found that the average rate per source/destination pair becomes proportional to the number of wires plus the rate for the wireless part. Moreover, we also study the performance of a network from the point of view of simple joint source/channel codes. This is a followup to one of our earlier projects. This approach has yielded promising results for a point-to-point link that is assisted by a large number of relay nodes.


Martin Vetterli, Emre Telatar.


May 2000 – December 2002 (end of PhD thesis).


ETHZ/EPFL exchange fellowship.

Major publications

M. Gastpar and M. Vetterli, On the capacity of wireless networks: the relay case, Proc. IEEE Infocom, Vol. 3, pp. 1577-1586, 2002.
[detailed record] [bibtex]