Information theory and networks

From Webresearch

• Network Coding
• Butterfly Network
• Random linear network coding
• Field size bounds
• Ford-Fulkerson Theorem
• Cut-set bounds
• The Gupta-Kumar Model
• Coding for distributed storage
• Network error correction codes

Contents 1 Information theory for networks 2 The Gupta-Kumar Model 3 Anonymity in the network 4 References

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.

• Wireless Ad Hoc Networks

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 . 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, 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.

• Transport Capacity

To gain intuition on the definition of transport capacity, consider the figure . 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.

• History

• Traffic Analysis

• Adversaries
  • Global Passive Adversaries
  • Malicious Nodes
  • Malicious External Nodes

• What is the Anonymity?
  • Sender's Anonymity: None other than the sender can deduce the source of a packet.
  • Receiver's Anonymity: None other than the receiver can know the destination of a packet.
  • Sender-Receiver Anonymity: None can know the source and destination of a packet. <\ref>

• Measures of Anonymity
  • Anonymity Set
  • Information theoretic approach

• Anonymity in the Internet
  • Chaum Mixes: David Chaum considered as father of anonymity in the network. He proposed the concept of Mix, which is actually a store and forward device. It stores packets from a number of users, encrypt them and do packet padding to make them identical. After that it sends the packets in a order which is not predictable from the order of arrival. <insert figure>
  • Onion Routing: This is the technique originally developed by US navy to hide the true destinations of the data packets. T
  • Freedom
  • Morphix
  • Tor
  • Tarzan

References

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.