Index Coding : a framework for distributed multi-flow management in wired and wireless networks
Action line: ComEx
Project Members : Wan Kai (Phd Student)
Coordinator : Daniela TUNINETTI (L2S, Supélec)
Subject : Fundamental performance limits of index coding
Documents: See the complete presentation for submission to the Emergence program .
Note that due to personal constraints, Daniela Tuninetti had to return to University of Illinois at Chicago without completing the full program she had prepared. She could however maintain her work with Wan Kai, in cooperation with Pablo Piantanida.
Scientific productions :
- Caching in combination networks: Novel multicast message generation and delivery by leveraging the network topology K Wan, M Ji, P Piantanida, D Tuninetti 2018 IEEE International Conference on Communications (ICC), 1-6
- On cache-aided relay networks K Wan, D Tuninetti, P Piantanida, M Ji The 22nd International ITG Workshop on Smart Antennas (WSA 2018)
- On Combination Networks with Cache-aided Relays and Users K Wan, D Tuninetti, P Piantanida, M Ji WSA 2018; 22nd International ITG Workshop on Smart Antennas, 1-7
- Recent advances on combination networks with end-user caches W Kai, M Ji, P Piantanida, D Tuninetti Information Theory and Applications Workshop (ITA)
- Novel outer bounds for combination networks with end-user-caches K Wan, M Ji, P Piantanida, D Tuninetti Information Theory Workshop (ITW), 2017 IEEE, 444-448
- Combination networks with caches: Improved achievable scheme based on interference alignmentK Wan, M Ji, P Piantanida, D Tuninetti 51nd Asilomar Conference on Signals, Systems and Computers, 2017
- State-of-the-art in cache-aided combination networks K Wan, D Tuninetti, M Ji, P Piantanida Signals, Systems, and Computers, 2017 51st Asilomar Conference on, 641-645
- Novel inner bounds with uncoded cache placement for combination networks with end-user-caches K Wan, M Ji, P Piantanida, D Tuninetti Communication, Control, and Computing (Allerton), 2017 55th Annual Allerton …
- Novel delivery schemes for decentralized coded caching in the finite file size regime K Wan, D Tuninetti, P Piantanida Communications Workshops (ICC Workshops), 2017 IEEE International Conference …
- A novel index coding scheme and its application to coded caching K Wan, D Tuninetti, P Piantanida Information Theory and Applications Workshop (ITA), 2017, 1-6
- On the optimality of uncoded cache placement K Wan, D Tuninetti, P Piantanida Information Theory Workshop (ITW), 2016 IEEE, 161-165
- On caching with more users than files K Wan, D Tuninetti, P Piantanida Information Theory (ISIT), 2016 IEEE International Symposium on, 135-139
Classical Information Theory deals prevalently with the problem of reliable transfer of data though a point-to-point (i.e., from one source to one destination) noisy channel. This framework has been extended to some multiuser situations, such as multiple access and broadcast channels that model the uplink and downlink of wireless cellular systems, respectively. However, extensions so as to include interference and multi-hop communication encountered in practical systems are available only for networks with a very small number of users. Such small networks are seldom met in actual communication problems and might actually not give the right insight on performance scaling with the number of users. In other words, Network Information Theory is not at the same level of maturity as classical Information Theory.
The lack of a fundamental understanding of the performance of networks with many users is reflected in the way commercially available systems are engineered. In practical system, in vague terms, orthogo-
nality is used to transform the network problem, with many complex interactions between users, in a set
of simple well-understood point-to-point links. However, this is clearly not optimal in general. A number of counterexamples are known, namely network coding and interference alignment, that demonstrate that large performance improvements can be obtained by allowing users to simultaneously access the channel. For example, network coding has shown the strict sub-optimality of routing in multicast networks, and interference alignment has shown that the throughput can scale linear with the number of users in wireless interference networks.
This project aims at studying the so-called index coding problem, which includes as special cases a number of simple-to-describe canonical network communication models. The index coding problem is equivalent to the general network coding problem and also includes several other “big data” problems such as distributed storage and caching. Index coding can take advantage of several interference alignment approaches. This research aims to further our knowledge on the fundamental performance trade-offs in index coding. Any deep understanding of index coding can therefore have implications on many practical problems. From its very positioning, this project is at the interface of digital communications, networking, and computer science. It can have a substantial impact on problems of distributed storage and caching, for wired networks, and of throughput for ad-hoc and peer-to-peer wireless networks.