Interplay of Request Number and Cache Size in Coded Caching
Kai Huang, Xiaoxia Wang, Jinbei Zhang, Kechao Cai, Xiangwei Zhu · IEEE Transactions on Communications · 2024
Coded caching is an effective method to reduce the traffic load on network bottleneck. While the heterogeneities on the number of requests and cache sizes in coded caching have been studied independently, their joint impact is still unclear. This paper investigates coded caching in scenarios with heterogeneous number of requests and cache sizes. We propose two achievable schemes. The first scheme, based on file grouping and multi-round decentralized coded caching, is demonstrated to be order optimal under the worst setting, i.e., when user with the i-th smallest cache has the i-th largest number of requests. Moreover, we obtain an important insight that the lower bound of the achievable rate is predominantly influenced by users with high$\frac {X_{i}}{M_{i}}$ratios, where$X_{i}$and$M_{i}$represent the number of requests and cache size of user i, respectively. Since the achievable rate of our first scheme is difficult to analyze in the general setting, we further propose the second scheme to derive a tractable upper bound. Based on the insight, the second scheme rearranges the users according to their$\frac {X_{i}}{M_{i}}$ratios and employs a threshold to divide them into the head users who may have a large impact on the lower bound, and the tail users who may have a small impact on the lower bound. The server transmits the demands of the head users directly while applying the first scheme in groups among the tail users. Under the general setting, the gap between the rate of our second scheme and the lower bound is proved to be within a logarithmic factor. Simulations are conducted to verify the superior performance of our proposed schemes.