Cost-Driven Data Caching in Edge-Based Content Delivery Networks

In this paper we study a data caching problem in edge-based content delivery network (CDN) where a data item is shared between service requests. Instead of improving the hit ratio with respect to limited capacity as in traditional case, we study the problem based on a semi-homogeneous (semi-homo) cost model in the edge-based CDN with monetary cost reduction as a goal. The cost model is semi-homo in the sense that all pairs of caching nodes have the same transfer cost, but each has its own caching cost rate. In particular, given a stream of requests R to a shared data item in the edge network, we present a shortest-path based optimal off-line caching algorithm that can minimize the total transfer and caching costs within O(mn) time (m : the number of network nodes, n : the length of request stream) in a proactive fashion. While for the online case, by extending the anticipatory caching idea, we also propose a 2-competitive online reactive caching algorithm and show its tightness by giving a lower bound of the competitive ratio as 2--o(1) for any deterministic online algorithm. Finally, to combine the advantages of both algorithms and evaluate our findings, we also design a hybrid algorithm. Our trace-based empirical studies show that the proposed algorithms not only improve the previous results in both time complexity and competitive ratio, but also relax the cost model to semi-homogeneity, rendering the algorithms more practical in reality. We provably achieve these results with our deep insights into the problem and careful analysis of the solutions, together with a prototype framework.

Automated summary

In this paper, we investigate a data caching problem in an edge-based content delivery network (CDN) where multiple service requests share a data item. Instead of focusing on improving hit ratio given limited capacity, we study the problem using a semi-homogeneous cost model to reduce monetary costs. We propose an optimal offline caching algorithm based on shortest path to minimize transfer and caching costs, and an online reactive caching algorithm that is 2-competitive and achieves a tight bound of competitive ratio 2--o(1). We also present a hybrid algorithm that combines the advantages of both algorithms. Trace-based empirical studies show that our algorithms improve previous results in time complexity and competitive ratio, and also make the cost model more practical.