Information theory and networks

From Webresearch

Jump to: navigation, search


Information theory for networks

A network consists of a set of transmitter-receiver nodes that can communicate over a physical medium, such as copper wires, fiber-optic cables, or free space. In information theory, a network is often modeled by a discrete memoryless network or a Gaussian network. which makes it difficult to study information theoretic concepts such as capacity. Therefore, typically one is interested in scaling laws, i.e., how a metric of interest scales as the number of nodes in the network grows.

Think about an empty room which is about to get crowded for a party. Suppose the first two people enter the room and start chatting - consider them sharing information to each other at 10 bits per second. Then another pair comes into the room, starts chatting, and hence the amount of information exchanged in the room increases. As more and more people join the party, the number of communicating pairs increases, but communication will be harder and harder as the noise in the room is also increased. Here, a question of interest here is, as the number of people in the room increases, what happens to the total amount of information exchanged in the room, and at what rate (as a function of the number of people attending the party).

The Gupta-Kumar Model

Consider an area of $A$ sq. units with $n$ fixed nodes. Each node can transmit at $W$ bits per second over the common wireless channel. Assume that there are $\frac{n}{2}$ source destination pairs. The node locations and the source-destination configurations are arbitrary as shown in
Adhoc network with an arbitrary configuration
. Further, it is assumed that packets can be sent from node to node in a multi hop fashion until they reach their final destination. Also, interference is considered a hindrance. A transmission over one hop is said to be successfully received if there is no other receiver in the "vicinity" of the intended receiver, i.e., a single hop transmission from node $i$ to node $j$ is said to be successful if there is no other receiver in the vicinity of $j$. This is called the Protocol Model. For example, as seen in the figure,
Protocol model
transmission over the range $r_1$ is said to be successful when there is no other receiver in the disk of radius $\frac{\Delta r_1}{2}$ surrounding the intended receiver where the quantity $\Delta>0$ models situations where a guard zone is specified by the protocol to prevent transmissions on the same channel at the same time. To gain intuition on the definition of transport capacity, consider the figure
A special configuration
. which shows a configuration where transmissions take place only between nearest neighbors. The transmitters adjust their ranges in such a way that a set of non-interfering point to point links are formed. As more number of nodes are packed into the fixed area $A$, the transmitters will have to decrease their ranges in order to avoid interference with other transmissions. As a result, the per hop distance traveled by the bits would decrease. However, the number of concurrent transmissions increase. Transport capacity is defined as the (rate in bits per second)$\times$(distance traveled by the bits) summed over all concurrent transmissions. Successful transmission over the range $r$ consumes an area which is equal to the area of the disk of radius $\frac{\Delta r}{2}$ surrounding the intended receiver. Since the area available is limited ($A$), the sum of the areas consumed by concurrent transmissions is upper bounded by $A$.

\begin{equation*} \sum_{i=1}^{N/2}\left(\frac{\Delta r_i}{2}\right)^2 \leq A \end{equation*} By convexity of $r^2$, \begin{equation*} \sum_{i=1}^{N/2} r_i \leq \frac{8An}{\pi\Delta^2} \end{equation*} Therefore, transport capacity is given by \begin{equation*} W\sum_{i=1}^{N/2} r_i \leq \sqrt{\frac{8A}{\pi}}\frac{W}{\Delta}\sqrt{n} \end{equation*}

Thus, for any arbitrary configuration of node locations and traffic patterns, total throughput cannot grow faster than $\sqrt{nA}$ bit metres per second.

Anonymity in the network

Privacy in networked communication extends beyond the protection of communicated data; it is equally critical to protect the identities of communicating parties. Anonymous communication systems protect the privacy of the users by hiding who is talking to whom and how packets are moving in the network. These systems, several of them deployed on the Internet, support applications with strong privacy requirements such as e-voting protocols, intelligence gathering for law enforcement, military communications, and such like. The importance of such systems is increasing and the largest deployed anonymity network, Tor has attracted an estimated half a million users. Most anonymity systems such as Tor are based on the concept of Chaum mixes; a mix is special proxy server that uses layered-encryption, random bit padding and batching to provide user anonymity to transmitted packets. Commonly deployed mix-networks, while they provide good protection against packet content/length based information retrieval, are vulnerable to timing analysis of packet. The primary reason for the vulnerability is the lack of optimized mix-network protocols under resource limitations of the network nodes in terms of memory and bandwidth, and QoS requirements such as delay and fairness. Guarding against unauthorized timing analysis incurs a penalty in network resources and QoS, and it is imperative to optimize the design of anonymity systems under constraints on resources and QoS requirements.


Andreas Pfitzmann and Michael Waidner. Networks without user observability – design options. In Proceedings of EUROCRYPT 1985. Springer-Verlag, LNCS 219, 1985.

Borisov, Nikita, Waddle, Jason. Anonymity in Structured Peer-to-Peer Networks.

Personal tools