Optimal placement and matching of content requests in caching systems.

In this paper, we consider models of content delivery networks (CDNs) and peer-to-peer (P2P) networks which support video-on-demand systems such as Netflix, Youtube etc., by replicating some of the most popular contents in their servers. In such systems, servers with fixed memory sizes and fixed bandwidth capacities can only store subsets of popular contents and serve a finite number of requests of the stored contents simultaneously. The throughput or the average number of requests supported per unit time by these systems critically depends on two factors: 1) The replication policy which determines how contents are replicated in the servers and 2) The request dispatching or matching policy which describes how an incoming request for a content is assigned to a server that stores the content. We investigate the effect of both factors on the performance of caching systems. We first consider a discrete time setting and formulate the problem of maximizing the average throughput or the average number of requests served in a time slot with respect to both content replication policy and request matching policy. For finite systems, the problem is shown to be strongly NP-hard. A polynomial-time greedy algorithm is proposed which is shown to achieve at least half of the optimal value in the worst case. However, in the large system limit, in which such systems typically operate, the greedy scheme is shown to be asymptotically optimal. We also show that under maximum matching of requests to the servers a randomized replication policy, where the average number of replicas of a content is proportional to the arrival rate of the content, is asymptotically optimal. We then consider a continuous time setting, where we seek to find the optimal content replication policy when a greedy randomized matching is used to match the requests to the servers. Unlike the maximum matching policy, the greedy random policy works online without breaking the already existing connections. Finally, we compare the performance of different replication policies under different matching schemes for finite systems.