Self-organizing algorithms for cache cooperation in content distribution networks

The delivery of video content is expected to gain huge momentum, fueled by the popularity of user-generated clips, growth of video-on-demand (VoD) libraries, and widespread deployment of Internet Protocol television (IPTV) services with features such as CatchUp/PauseLive TV and network personal video recorder (NPVR) capabilities. The time-shifted nature of these personalized applications defies the broadcast paradigm underlying conventional TV networks and increases the overall bandwidth demands by orders of magnitude. Caching strategies provide an effective mechanism for mitigating these massive bandwidth requirements by storing copies of the most popular content closer to the network edge, rather than keeping it in a central site. The reduction in the traffic load lessens the required transport capacity and capital expense and alleviates performance bottlenecks. In this paper, we develop lightweight cooperative cache management algorithms aimed at maximizing the traffic volume served from cache and minimizing the bandwidth cost. As a canonical scenario, we focus on a cluster of distributed caches and show that under certain symmetry assumptions, the optimal content placement has a rather simple structure. Besides being interesting in its own right, the optimal structure offers valuable guidance for the design of low-complexity cache management and replacement algorithms. We establish that the proposed algorithms are guaranteed to operate within a constant factor from the globally optimal performance, with benign worst-case ratios, even in asymmetric scenarios. Numerical experiments reveal that typical performance is far better than the worst-case conditions indicate.