Information-Theoretic Clustering Techniques for Correlated Sources in Network Content Caching

Abstract

Two powerful and complementary tools have been presented in literature to facilitate the paradigm shift planned for the Internet, where the focus is on storing information within the network infrastructure itself. The first involves Slepian-Wolf (SW) coding, in which the high degree of correlation between pieces of information are exploited to reduce the overall size of the data. Then, Coded Caching (CC) stores parts of the information at the user end during o!-peak hours when demand is low. Although this hybrid system results in an impressive reduction of bandwidth usage during peak hours, the SW coding operation in particular becomes prohibitively complex to implement. Clustering has been proposed in other fields pertaining to SW coding to solve this issue, but the assumptions and simplifications used there are not applicable in this scenario. This work solves the problem of clustering within a hybrid Slepian-Wolf Coded Caching (SW/CC) system by first looking at a simplified single-group model. To this end, two iterative algorithms are developed and compared to the Genetic Algorithm (GA) and Ant Colony Optimisation (ACO) meta-heuristic approaches. Then, the problem is extended to multiple groups, which presents a much greater challenge. The single group algorithms are expanded and improved to cater for the new paradigm, providing close-to-optimal approaches while still running in polynomial time. At the same time, necessary conditions for optimality are derived for both cases, allowing for solutions to be further improved. The iterative approaches in particular, when used in conjunction with the optimality tests, perform comparably to the benchmark meta-heuristic ones, but with more predictable performance and much lower complexity in both the single and multi group scenarios. Clustering the files in this way greatly reduces the complexity in this system, making it more feasible to implement in practical scenarios. More research can be done to improve these algorithms, generalise the problem to arbitrarily sized groups and allow for files to belong to more than one group.