More Like this

1. Learning to Cache and Caching to Learn: Regret Analysis of Caching Algorithms

   https://doi.org/10.1109/TNET.2021.3105880  

   Bura, Archana; Rengarajan, Desik; Kalathil, Dileep; Shakkottai, Srinivas; Chamberland, Jean-Francois (January 2021, IEEE/ACM Transactions on Networking)

   null (Ed.)

   Crucial performance metrics of a caching algorithm include its ability to quickly and accurately learn a popularity distribution of requests. However, a majority of work on analytical performance analysis focuses on hit probability after an asymptotically large time has elapsed. We consider an online learning viewpoint, and characterize the ``regret'' in terms of the finite time difference between the hits achieved by a candidate caching algorithm with respect to a genie-aided scheme that places the most popular items in the cache. We first consider the Full Observation regime wherein all requests are seen by the cache. We show that the Least Frequently Used (LFU) algorithm is able to achieve order optimal regret, which is matched by an efficient counting algorithm design that we call LFU-Lite. We then consider the Partial Observation regime wherein only requests for items currently cached are seen by the cache, making it similar to an online learning problem related to the multi-armed bandit problem. We show how approaching this ``caching bandit'' using traditional approaches yields either high complexity or regret, but a simple algorithm design that exploits the structure of the distribution can ensure order optimal regret. We conclude by illustrating our insights using numerical simulations. 

   more » « less
2. Individual Preference Aware Caching Policy Design in Wireless D2D Networks

   https://doi.org/10.1109/TWC.2020.2994581  

   Lee, Ming-Chun; Molisch, Andreas F. (July 2020, IEEE Transactions on Wireless Communications)

   Cache-aided wireless device-to-device (D2D) networks allow significant throughput increase, depending on the concentration of the popularity distribution of files. Many studies assume that all users have the same preference distribution; however, this may not be true in practice. This work investigates whether and how the information about individual preferences can benefit cache-aided D2D networks. We examine a clustered network and derive a network utility that considers both the user distribution and channel fading effects into the analysis. We also formulate a utility maximization problem for designing caching policies. This maximization problem can be applied to optimize several important quantities, including throughput, energy efficiency (EE), cost, and hit-rate, and to solve different tradeoff problems. We provide a general approach that can solve the proposed problem under the assumption that users coordinate, then prove that the proposed approach can obtain the stationary point under a mild assumption. Using simulations of practical setups, we show that performance can improve significantly with proper exploitation of individual preferences. We also show that different types of tradeoffs exist between different performance metrics and that they can be managed through caching policy and cooperation distance designs. 

   more » « less
3. Joint Drone Association and Content Placement in Cache-Enabled Internet of Drones

   https://doi.org/10.1109/GLOBECOM38437.2019.9013274  

   Yao, Jingjing; Ansari, Nirwan (December 2019, 2019 IEEE Global Communications Conference (GLOBECOM))

   Internet of drones (IoD), employing drones as the internet of things (IoT) devices, brings flexibility to IoT networks and has been used to provision several applications (e.g., object tracking and traffic surveillance). The explosive growth of users and IoD applications injects massive traffic into IoD networks, hence causing congestions and reducing the quality of service (QoS). In order to improve the QoS, caching at IoD gateways is a promising solution which stores popular IoD data and sends them directly to the users instead of activating drones to transmit the data; this reduces the traffic in IoD networks. In order to fully utilize the storage-limited caches, appropriate content placement decisions should be made to determine which data should be cached. On the other hand, appropriate drone association strategies, which determine the serving IoD gateway for each drone, help distribute the network traffic properly and hence improve the QoS. In our work, we consider a joint optimization of drone association and content placement problem aimed at maximizing the average data transfer rate. This problem is formulated as an integer linear programming (ILP) problem. We then design the Drone Association and Content Placement (DACP) algorithm to solve this problem with low computational complexity. Extensive simulations demonstrate the performance of DACP. 

   more » « less
4. Fair Caching Networks

   https://doi.org/10.1145/3453953.3453973  

   Liu, Yuezhou; Li, Yuanyuan; Ma, Qian; Ioannidis, Stratis; Yeh, Edmund (March 2021, ACM SIGMETRICS Performance Evaluation Review)

   null (Ed.)

   We study fair content allocation strategies in caching networks through a utility-driven framework, where each request achieves a utility of its caching gain rate. The resulting problem is NP-hard. Submodularity allows us to devise a deterministic allocation strategy with an optimality guarantee factor arbitrarily close to 1-1/e. When 0 < α ≤ 1, we further propose a randomized strategy that attains an improved optimality guarantee, (1 - 1/e)1-α, in expectation. Through extensive simulations over synthetic and real-world network topologies, we evaluate the performance of our proposed strategies and discuss the effect of fairness. 

   more » « less
5. Efficient Algorithms for Coded Multicasting in Heterogeneous Caching Networks

   https://doi.org/10.3390/e21030324  

   Vettigli, Giuseppe; Ji, Mingyue; Shanmugam, Karthikeyan; Llorca, Jaime; Tulino, Antonia; Caire, Giuseppe (March 2019, Entropy)

   Coded multicasting has been shown to be a promising approach to significantly improve the performance of content delivery networks with multiple caches downstream of a common multicast link. However, the schemes that have been shown to achieve order-optimal performance require content items to be partitioned into several packets that grows exponentially with the number of caches, leading to codes of exponential complexity that jeopardize their promising performance benefits. In this paper, we address this crucial performance-complexity tradeoff in a heterogeneous caching network setting, where edge caches with possibly different storage capacity collect multiple content requests that may follow distinct demand distributions. We extend the asymptotic (in the number of packets per file) analysis of shared link caching networks to heterogeneous network settings, and present novel coded multicast schemes, based on local graph coloring, that exhibit polynomial-time complexity in all the system parameters, while preserving the asymptotically proven multiplicative caching gain even for finite file packetization. We further demonstrate that the packetization order (the number of packets each file is split into) can be traded-off with the number of requests collected by each cache, while preserving the same multiplicative caching gain. Simulation results confirm the superiority of the proposed schemes and illustrate the interesting request aggregation vs. packetization order tradeoff within several practical settings. Our results provide a compelling step towards the practical achievability of the promising multiplicative caching gain in next generation access networks. 

   more » « less