Optimal cooperative content placement algorithms in hierarchical cache topologies

The tremendous growth in the use of the World Wide Web and the expansion of Video On Demand and IPTV services increase the bandwidth demands, enforcing the creation of congestion in Internet´s links and the experience of big delays to the users. Replicating content at caches which are close to the users can improve the access time for them and reduce the network bandwidth usage as well. In this work, we focus on hierarchical cache topologies, as IPTV networks tend to have a mostly hierarchical tree structure, making the content placement problem in them a topic of major importance. The problem is NP-Complete in it´s general form. In this paper, we make the simplifying assumption that the size of each object is equal to one. Under that assumption we show that certain instances of the content placement problem are of polynomial complexity, while we provide an algorithm for their solution. Besides, we extend the proposed algorithm to handle the general case of arbitrary object sizes. Simulation experiments for typical popularity distributions depict the performance distance between the optimal solution and some low complexity heuristic algorithms that are commonly applied nowadays.