Information-Theoretical Principles for Networking and Computing

it_logo_3_final-pngIn applications of information theory to the fields of networking and computing, two main principles seem to be mostly invoked to reduce the communication overhead when uploading/downloading data to/from a number of nodes:

  1. Network coding: If all the other nodes in a group have the information required by any given node in the group, one transmission of a coded packet is sufficient to satisfy all the nodes’ requests. As a result, if each node has a properly selected fraction r of all data, groups of size proportional to r can be created, and the communication rate to upload the information requested by all nodes decreases as 1/r.
  2. MDS coding: If all nodes have a coded fraction r of some data, then downloading information from 1/r of them is sufficient to retrieve the data.

Both principles produce principles similar (r vs. 1/r) trade-offs between what a node “has” via storage, transfer or computing, and the communication overhead for uploading/downloading.

The network coding principle is instrumental in reducing communication overhead in multicast channels, e.g., multi-hop, Ethernet or wireless links, when side information can be transmitted, stored, collected or computed. This has been found useful in applications such as routing, caching and distributed computing (see here and here).

The MDS coding principle, instead, enables the reduction of the number of nodes from which one needs to download data by increasing the amount of data stored or computed at each node. This produces a tension between computing power and latency or reliability for set-ups in which nodes may have random delays or be unreliable. Applications include distributed computing and virtualization for wireless networks.

The two gains can also be combined for applications, such as distributed computing, that involve both multicasting and data collection.

As information theorists tackle fundamental problems in modern networking and computation applications, areas that seem ripe for the discovery of new principles encompass set-ups of relevance for 5G systems including massive number of users and/or ultra-reliability constraints.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s