CNS Core: Small: New Caching Paradigms for Distributed and Dynamic Networks


Project Team

  • Principal Investigators: Ness Shroff and Atilla Eryilmaz
  • Graduate students: Guocong Quan and Abolhassani, Bahman

  • Vision

      Over the last few decades, Content Distribution Networks (CDNs) have been used to cache data of popular interest closer to the end-users in order to make them rapidly accessible when requested. As the source content becomes increasingly more dynamic and the caching capabilities move closer to the end-users for low-delay access, the nature of the content requests in the emerging CDNs exhibit fundamentally different characteristics from their traditional counterparts. This necessitates the design of starkly different caching solutions from the currently available ones.

      The objective of this project is to establish the models and develop distributed caching and communication strategies that incorporate these non-traditional request-dynamics as well as data generation dynamics for the efficient utilization of edge network and end-user memory spaces. In particular, the project identifies and systematically investigates complementary scenarios that must employ different caching principles based on the generation dynamics of content, the position of the memory space, and the nature of the demand that arrives from end-users. Our research is multidisciplinary and will bring together elements from caching, scheduling, anomaly detection, coding, learning and optimization theories towards the design of integrated caching solutions for the increasingly distributed and dynamic networks of the future.

      We envision that the broader insights and specific mechanisms that emanate from our research will reveal the key components and guiding principles of distributed caching solutions in increasingly dynamic and personalized networks of the future. Achieving this end will help society at large by improving end-user experience for numerous emerging applications, spanning mobile-health, entertainment, security, etc. The interdisciplinary research conducted on this project will help train the next generation of engineers and academicians with the tools it takes to succeed in solving increasingly complex and challenging problems. The expertise that will be developed through this project will be vital for the efficient management of big data in the context of future dynamic and large-scale networks, driven by IoT and CPS applications. The outcomes of this research will also be integrated into various undergraduate and graduate courses across ECE and CSE at OSU (e.g., wireless networks, network optimization, communication networks).


    Key Accomplishments

      Our main results along the above directions are as follows:

      (i) Fresh caching for dynamic content generation: We introduced a framework and provably-efficient schemes for ‘fresh’ caching at the (front-end) local cache of content that is subject to ‘dynamic’ updates at the (back-end) database. We started by formulating the hard-cache-constrained problem for this setting, which quickly becomes intractable due to the limited cache. To bypass this challenge, we first proposed a flexible time-based-eviction model to derive the average system cost function that measures the system’s cost due to the service of aging content in addition to the regular cache miss cost. Next, we solved the cache-unconstrained case, which reveals how the refresh dynamics and popularity of content affect optimal caching. Then, we extended our approach to a soft-cache-constrained version, where we can guarantee that the cache use is limited with arbitrarily high probability. The corresponding solution reveals the interesting insight that ‘whether to cache an item or not in the local cache?’ depends primarily on its popularity level and channel reliability, whereas ‘how long the cached item should be held in the cache before eviction?’ depends primarily on its refresh rate. Moreover, we investigated the cost-cache saving trade-offs and proved that substantial cache gains can be obtained while also asymptotically achieving the minimum cost as the database size grows.

      (ii) Caching for predictable requests: Strategically prefetching data has been utilized in practice to improve caching performance. Apart from caching data items upon requests, they can be prefetched into the cache before requests actually occur. The caching and prefetching operations compete for the limited cache space, whose size is typically much smaller than the number of data items. A key question is how to design an optimal prefetching and caching policy, assuming that the future requests can be predicted to certain extend. This question is non-trivial even under an idealized assumption that the future requests are precisely known. To investigate this problem, we proposed a cost-based service model. The objective is to find the optimal online prefetching and caching policy that minimizes the accumulated cost for a given request sequence. By casting it as a min-cost flow problem, we were able to find the optimal policy for a data trace of length N in expected time O(N^(3/2)) via flow-based algorithms. However, this requires the entire trace for each request and cannot be applied in real time. To this end, we analytically characterized the optimal policy by obtaining an optimal cache eviction mechanism. We derived conditions under which proactive prefetching is a better choice than passive caching. Based on these insights, we proposed a lightweight approximation policy that only exploits predictions in the near future. Moreover, the approximation policy can be applied in real time and processes the entire trace in O(N) expected time. We proved that the competitive ratio of the approximation policy is less than sqrt(2). Our extensive simulations verified its near-optimal performance, for both heavy and light-tailed popularity distributions.

      (iii) Multi-dispatch load balancing for caching/computing jobs in large-scale data centers: We consider the load balancing problem in large-scale heterogeneous caching and computing systems with multiple dispatchers. We introduce a general framework called Local-Estimation-Driven (LED). Under this framework, each dispatcher keeps local (possibly outdated) estimates of the queue lengths for all the servers, and the dispatching decision is made purely based on these local estimates. The local estimates are updated via infrequent communications between dispatchers and servers. We derive sufficient conditions for LED policies to achieve throughput optimality and delay optimality in heavy-traffic, respectively. These conditions directly imply delay optimality for many previous local-memory based policies in heavy traffic. Moreover, the results enable us to design new delay optimal policies for heterogeneous systems with multiple dispatchers. Finally, the heavy-traffic delay optimality of the LED framework also sheds light on a recent open question on how to design optimal load balancing schemes using delayed information.

      (iv) Efficiently Keeping Cached Content Fresh: How to efficiently keep information content fresh is a significant challenge. We have developed new techniques to keep information content fresh in both multi-hop network settings as well as settings where information updates could be costly. In particular, our schemes have been rigorously shown to make sure maximize the freshness of information and data subject to energy, throughput, and complexity requirements.

      (v) Low-Regret Caching for Multi-Layer CDNs: Edge caching has been widely implemented to efficiently serve data requests from end users. Numerous edge caching policies have been proposed to adaptively update the cache contents based on various statistics. One critical statistic is the miss cost, which could measure the latency or the bandwidth/energy consumption to resolve the cache miss. Existing caching policies typically assume that the miss cost for each data item is fixed and known. However, in real systems, they could be random with unknown statistics. A promising approach would be to use online learning to estimate the unknown statistics of these random costs, and make caching decisions adaptively. Unfortunately, conventional learning techniques cannot be directly applied, because the caching problem has additional cache capacity and cache update constraints that are not covered in traditional learning settings. In this research direction, we have resolved these issues by developing a novel edge caching policy that learns uncertain miss costs efficiently, and is shown to be asymptotically optimal in time. We first derived an asymptotic lower bound on the achievable regret. We then designed a Kullback-Leibler lower confidence bound (KL-LCB) based edge caching policy, which adaptively learns the random miss costs by following the “optimism in the face of uncertainty” principle. By employing a novel analysis that accounts for the new constraints and the dynamics of the setting, we proved that the regret of the proposed policy matches the regret lower bound, thus showing asymptotic optimality. Further, via numerical experiments we demonstrated the performance improvements of our policy over natural benchmarks.


    Broader Impacts

    PI Shroff has given a number of keynotes and distinguished university talks on this topic. We recruited a female PhD student to work in this area for Autumn 2021. We will continue our efforts to recruit female and under-represented minority students. PI Eryilmaz has developed and taught a new graduate-level course on ``Online Learning'', which introduced the interested students to methods of sequential-learning for optimizing the exploration-exploitation tradeoff. This course has already motivated new work on caching that we are currently pursuing with a co-advised PhD student.


    Products

      The results in the NSF Public Access Repository will include a comprehensive listing of all journal publications recorded to date that are associated with this award.

    • S. Kang, A. Eryilmaz, and N. B. Shroff, ``Remote Tracking of Distributed Dynamic Sources over A Random Access Channel with One-bit Updates", WIOPT, 2021.
    • Z. Shi, and A. Eryilmaz, ``A Bayesian Approach for Stochastic Continuum-armed Bandit with Long-term Constraints", AISTATS, 2022.
    • X. Zhou, I. Koprulu, A. Eryilmaz, and M. J. Neely, ``Efficient Distributed MAC for Dynamic Demands: Congestion and Age Based Designs", IEEE/ACM Transactions on Networking, 2022.
    • G. Quan, A, Eryilmaz, and N. B. Shroff, ``Regret-Optimal Learning for Minimizing Edge Caching Service Costs", WiOpt, 2022.
    • B. Abolhassani, J. Tadrous, A. Eryilmaz, and E. Yeh, ``Fresh Caching of Dynamic Content Over the Wireless Edge. IEEE/ACM Transactions on networking, 2022.
    • B. Abolhassani, J. Tadrous, and A. Eryilmaz, ``Optimal Load-Splitting and Distributed-Caching for Dynamic Content", WIOPT, 2021.
    • B. Abolhassani, J. Tadrous, and A. Eryilmaz, ``Delay Gain Analysis of Wireless Multicasting for Content Distribution", IEEE/ACM Transactions on Networking, 2021.
    • B. Abolhassani, J. Tadrous, and A. Eryilmaz, ``Single vs Distributed Edge Caching for Dynamic Content", IEEE/ACM Transactions on Networking, 2022.
    • Z. Shi, and A. Eryilmaz, ``A Flexible Distributed Stochastic Optimization Framework for Concurrent Tasks in Processing Networks", IEEE/ACM Transactions on Networking, 2021.
    • X. Zhou, I. Koprulu, A. Eryilmaz, and M. J. Neely, ``Low-Overhead Distributed MAC for Serving Dynamic Users over Multiple Channels", WIOPT, 2021.
    • S. Cayci, Y. Zheng, and A. Eryilmaz, ``A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback", AAAI, 2022.
    • Z. Shi, and A. Eryilmaz, ``Communication-efficient Subspace Methods for High-dimensional Federated Learning" MSN, 2021.
    • J. Yun, A. Eryilmaz, and C. Joo, ``Remote Tracking of Dynamic Sources under Sublinear Communication Costs". IEEE Infocom, 2021.
    • S. Kang, A. Eryilmaz, and N. B. Shroff, ``Comparison of Decentralized and Centralized Update Paradigms for Remote Tracking of Distributed Dynamic Sources", IEEE Infocom, 2021.
    • S. Cayci, S. Gupta, and A. Eryilmaz, ``Group-Fair Online Allocation in Continuous Time", NeurIPS, 2020.
    • X. Zhou, N. B. Shroff, and A. Wierman, ``Asymptotically optimal load balancing in large-scale heterogeneous systems with multiple dispatchers", Performance Evaluation, 2021.
    • B. Abolhassani, J. Tadrous, A. Eryilmaz, and E. Yeh, ``Fresh Caching for Dynamic Content", IEEE Infocom, 2021.
    • A. M. Bedewy, Y. Sun, R. Singh, and N. B. Shroff, ``Optimizing information freshness using low-power status updates via sleep-wake scheduling", ACM MobiHoc, 2020.
    • G. Quan, J. Tan, and A. Eryilmaz, ``Counterintuitive Characteristics of Optimal Distributed LRU Caching Over Unreliable Channels", IEEE/ACM transactions on networking, 2020.
    • A. M. Bedewy, Y. Sun, and N. B. Shroff, ``The Age of Information in Multihop Networks", IEEE/ACM Transactions on Networking, 2019.
    • G. Quan, A. Eryilmaz, J. Tan, and N. B. Shroff, ``Prefetching and caching for minimizing service costs: Optimal and approximation strategies", Performance Evaluation, 2021.