In-network caching is recognized as an effective solution to offload content servers and the network. A cache service provider (SP) always has incentives to better utilize its cache resources by taking into account diverse roles that content providers (CPs) play, e.g., their business models, traffic characteristics, preferences. In this paper, we study the cache resource allocation problem in a Multi-Cache Multi-CP environment. We propose a cache partitioning approach, where each cache can be partitioned into slices with each slice dedicated to a content provider. We propose a content-oblivious request routing algorithm, to be used by individual caches, that optimizes the routing strategy for each CP. We associate with each content provider a utility that is a function of its content delivery performance, and formulate an optimization problem with the objective to maximize the sum of utilities over all content providers. We establish the biconvexity of the problem, and develop decentralized (online) algorithms based on convexity of the subproblem. The proposed model is further extended to bandwidth-constrained and minimum-delay scenarios, for which we prove fundamental properties, and develop efficient algorithms. Finally, we present numerical results to show the efficacy of our mechanism and the convergence of our algorithms.
Bibliographical noteFunding Information:
Zhi-Li Zhang received the B.S. degree in computer science from Nanjing University, Jiangsu, China, in 1986, and the M.S. and Ph.D. degrees in computer science from the University of Massachusetts Amherst, Amherst, in 1992 and 1997, respectively. In 1997, he joined the Computer Science and Engineering faculty at the University of Minnesota, Minneapolis, MN, where he is currently a Professor. From 1987 to 1990, he conducted research with the Computer Science Department, Aarhus University, Aarhus, Denmark, under a fellowship from the Chinese National Committee for Education. He has held visiting positions with Sprint Advanced Technology Labs, Burlingame, CA; IBM T.J. Watson Research Center, Yorktown Heights, NY; Fujitsu Labs of America, Sunnyvale, CA; Microsoft Research China, Beijing, China; and INRIA, Sophia-Antipolis, France. He is a Fellow of the IEEE.
The work was supported by the National Natural Science Foundation of China (Grant No. 61502393 ), the Natural Science Basic Research Plan in Shaanxi Province of China (Grant No. 2017JM6066), the Fundamental Research Funds for the Central Universities (Grant No. 3102017zy031), and the National Science Foundation under grants CNS-1413998, CNS-1617437, CNS-1618339 and CNS-1617729. The work by John C.S. Lui is supported in part by the GRF 14200117.
© 2017 Elsevier B.V.
- cache partitioning
- cache resource allocation
- distributed algorithms
- request routing