2014 · 67 citations · 10 references
ComputingComputer ScienceComputer SystemsComputer NetworksDigital CommunicationOptimizationCachingCaching StrategiesPerformance OptimizationWireless NetworksCache ManagementCache MemoryCache OptimizationKnapsack ApproximationKnapsack ProblemsMulti-armed Bandit OptimizationPopularity-based CachingTraffic Offloading
Optimal cache content placement is studied in a wireless infostation network (WIN), which models a limited coverage wireless network with a large cache memory. WIN provides content-level selective offloading by delivering high data rate contents stored in its cache memory to the users through a broadband connection. The goal of the WIN central controller (CC) is to store the most popular content in the cache memory of the WIN such that the maximum amount of data can be fetched directly from the cache rather than being downloaded from the core network. If the popularity profile of the available set of contents is known in advance, the optimization of the cache content reduces to a knapsack problem. However, it is assumed in this work that the popularity profile of the files is not known, and only the instantaneous demands for those contents stored in the cache can be observed. Hence, the cache content placement is optimised based on the demand history, and on the cost associated to placing each content in the cache. By refreshing the cache content at regular time intervals, the CC tries to learn the popularity profile, while at the same time exploiting the limited cache capacity in the best way possible. This problem is formulated as a multi-armed bandit problem with switching cost, and an algorithm to solve it is presented. The performance of the algorithm is measured in terms of regret, which is proven to be logarithmic and sub-linear uniformly over time for a specific and a general case, respectively.
10
Asymptotically efficient adaptive allocation rules
Tze-Leung Lai, Herbert Robbins · Advances in Applied Mathematics · 1985 · 2.5K citations
Distributed Caching Algorithms for Content Distribution Networks
Sem Borst, Varun Gupta, Anwar Walid · 2010 · 697 citations