SmartCache: Faster Wireless Data Rates via Caching on Smart Devices: Theoretical Analysis & Implementation

Wireless networks have been struggling the most to cope with the exponentially increasing demand for higher data throughput fueled by the massive popularity of smart phones and tablets. Given that we are already squeezing out the maximum amount of bits/s/Hz predicted by Shannon's limits on the wireless channel, in this project, we aim to investigate novel methods for temporal spectrum re-use through data caching to meet the soaring wireless data traffic.

Our key idea is to use Index Coding to broadcast data to the caches of many smart devices, even before the data is requested. Data caching has been extensively studied in the wire-line networks. However, those approaches miss the opportunities exclusive to wireless including the inherent broadcast nature of the wireless channel and the availability of unused spectrum windows. This project aims at (1) designing algorithms for data caching on smart devices that benefit from these opportunities, and (2) building a proof-of-concept wireless system for implementing and testing index codes.

index coding
architecture


Our simulation results based on idealized channel models indicate that index coding can achieve more than 40% savings in the base station downlink data. Even a small reduction of the total traffic volume by 1% can lead to savings in the order of tens of millions of dollars given the $35 billion expected investment per year in wireless infrastructure in the US through 2017. Meanwhile, we are implementing a centralized video-streaming framework, in which the server encodes the transmitted videos by index coding to enable fast streaming at the numerous android-phone-based clients concurrently.

It is known that the problem of finding optimal linear index codes is NP-hard. We investigate the performance of different heuristics based on rank minimization and matrix completion methods for constructing linear index codes over the reals. As a summary of our results, the alternating projections method gives the best results in terms of minimizing the number of broadcast bits and convergence rate and leads to up to 13% savings in communication cost compared to graph coloring algorithms studied in the literature. In this work, we also investigate how the proposed methods can be used to construct linear network codes for non-multicast networks.


Publication
  • Xiao Huang and Salim El Rouayheb, "Index Coding and Network Coding via Rank Minimization," In Proceedings of the IEEE Information Theory Workshop (ITW), Korea, October 2015. [pdf] [slides]
  • Xiao Huang, Xin Liu, Chaitanya Reddy Chatla, Dong (Kevin) Jin and Salim El Rouayheb. "Faster Data Rates via Caching on Smart Devices," IIT Research Day, April 2015 (poster) [pdf]
  • Xin Liu, Chaitanya Reddy Chatla, Dong (Kevin) Jin. "Design and Implementation of Index Coding on Smart Devices for Faster Data Rates," Technical Report, Illinois Institute of Technology, May, 2015 [pdf] [source code]
  • Xiao Huang and Salim El Rouayheb. "Index Coding and Network Coding via Rank Minimization,"
    Technical Report, Illinois Institute of Technology, 2015 [pdf] [source code]

Sponsored by the IIT Educational and Research Initiative Fund (ERIF)