The capacity of next generation of cellular networks using femtocaches is studied when multihop communications and decentralized cache placement are considered. We show that the storage capability of future network User Terminals (UT) can be effectively used to increase the capacity in random decentralized uncoded caching. We further propose a random decentralized coded caching scheme which achieves higher capacity results than the random decentralized uncoded caching. The result shows that coded caching which is suitable for systems with limited storage capabilities can improve the capacity of cellular networks by a factor of log(n) where n is the number of nodes served by the femtocache.
Coded caching has been previously suggested @cite_10 @cite_14 as an efficient caching technique for devices with small storage capacity. Our results demonstrate that apart from the practical importance of coded caching in small storage systems, it can be useful in increasing the capacity of cached networks.
@cite_14 @cite_10
2232152748 2145438521
We present a new architecture to handle the ongoing explosive increase in the demand for video content in wireless networks. It is based on distributed caching of the content in femtobasestations with small or non-existing backhaul capacity but with considerable storage space, called helper nodes. We also consider using the wireless terminals themselves as caching helpers, which can distribute video through device-todevice communications. This approach allows an improvement in the video throughput without deployment of any additional infrastructure. The new architecture can improve video throughput by one to two orders-of-magnitude. We investigate the problem of coded caching for nonuniform demands when the structured clique cover algorithm proposed by Maddah-Ali and Niesen for decentralized caching is used for delivery. We apply this algorithm to all user demands regardless of their request probabilities. This allows for coding among the files that have different request probabilities but makes the allocation of memory to different files challenging during the content placement phase. As our main contribution, we analytically characterize the optimal placement strategy that minimizes the expected delivery rate under a storage capacity constraint. It is shown that the optimal placement follows either a two or a three group strategy, where a set of less popular files are not cached at all and the files within each of the other sets are allocated identical amounts of storage as if they had the same request probabilities. We show that for a finite set of storage capacities, that we call the base-cases of the problem, the two group strategy is always optimal. For other storage capacities, optimal placement is achieved by memory sharing between certain base-cases and the resulting placement either follows a two or a three group strategy depending on the corresponding base-cases used. We derive a polynomial time algorithm that determines the base-cases of the problem given the number of caches and popularity distribution of files. Given the base-cases of the problem, the optimal memory allocation parameters for any storage capacity are derived analytically. Caching has emerged as a vital tool in modern communication systems for reducing peak data rates by allowing popular files to be pre-fetched and stored locally at end users' devices. With the shift in paradigm from homogeneous cellular networks to the heterogeneous ones, the concept of data offloading to small cell base stations (sBS) has garnered significant attention. Caching at these small cell base stations has recently been proposed, where popular files are pre-fetched and stored locally in order to avoid bottlenecks in the limited capacity backhaul connection link to the core network. In this paper, we study distributed caching strategies in such a heterogeneous small cell wireless network from a reinforcement learning perspective. Using state of the art results, it can be shown that the optimal joint cache content placement in the sBSs turns out to be a NP-hard problem even when the sBS's are aware of the popularity profile of the files that are to be cached. To address this problem, we propose a coded caching framework, where the sBSs learn the popularity profile of the files (based on their demand history) via a combinatorial multi-armed bandit framework. The sBSs then pre-fetch segments of the Fountain-encoded versions of the popular files at regular intervals to serve users' requests. We show that the proposed coded caching framework can be modeled as a linear program that takes into account the network connectivity and thereby jointly designs the caching strategies. Numerical results are presented to show the benefits of the joint coded caching technique over naive decentralized cache placement strategies. We develop approximation algorithms for the problem of placing replicated data in arbitrary networks, where the nodes may both issue requests for data objects and have capacity for storing data objects so as to minimize the average data-access cost. We introduce the data placement problem to model this problem. We have a set of caches @math , a set of clients @math , and a set of data objects @math . Each cache @math can store at most @math data objects. Each client @math has demand @math for a specific data object @math and has to be assigned to a cache that stores that object. Storing an object @math in cache @math incurs a storage cost of @math , and assigning client @math to cache @math incurs an access cost of @math . The goal is to find a placement of the data objects to caches respecting the capacity constraints, and an assignment of clients to caches so as to minimize the total storage and client access costs. We present a 10-approximation algorithm for this problem. Our algorithm is based on rounding an optimal solution to a natural linear-programming relaxation of the problem. One of the main technical challenges encountered during rounding is to preserve the cache capacities while incurring only a constant-factor increase in the solution cost. We also introduce the connected data placement problem to capture settings where write-requests are also issued for data objects, so that one requires a mechanism to maintain consistency of data. We model this by requiring that all caches containing a given object be connected by a Steiner tree to a root for that object, which issues a multicast message upon a write to (any copy of) that object. The total cost now includes the cost of these Steiner trees. We devise a 14-approximation algorithm for this problem. We show that our algorithms can be adapted to handle two variants of the problem: (a) a @math -median variant, where there is a specified bound on the number of caches that may contain a given object, and (b) a generalization where objects have lengths and the total length of the objects stored in any cache must not exceed its capacity.