2017/12/19 by Nitish K. Panigrahy, Panigrahy, Nitish K., Jian Li +5
Computer Science · #Caching and Content Delivery #Cooperative Communication and Network Coding #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1712.07307
The design of caching algorithms to maximize hit probability has been\nextensively studied. In this paper, we associate each content with a utility,\nwhich is a function of either the corresponding content hit rate or hit\nprobability. We formulate a cache optimization problem to maximize the sum of\nutilities over all contents under stationary and ergodic request processes.\nThis problem is non-convex in general but we reformulate it as a convex\noptimization problem when the inter-request time (irt) distribution has a\nnon-increasing hazard rate function. We provide explicit optimal solutions for\nsome irt distributions, and compare the solutions of the hit-rate based (HRB)\nand hit-probability based (HPB) problems. We formulate a reverse engineering\nbased dual implementation of LRU under stationary arrivals. We also propose\ndecentralized algorithms that can be implemented using limited information and\nuse a discrete time Lyapunov technique (DTLT) to correctly characterize their\nstability. We find that decentralized algorithms that solve HRB are more robust\nthan decentralized HPB algorithms. Informed by these results, we further\npropose lightweight Poisson approximate decentralized and online algorithms\nthat are accurate and efficient in achieving optimal hit rates and hit\nprobabilities.\n