A New Replica Placement Algorithm for Improving the Performance in CDNs

Abstract

With the advent of services and applications over the Internet, speed and reliability have become critical issues for clients, and the Internet currently is not well suited for the purpose of the emerging new service delivery contemplated by today's applications. In response to these challenges, commercial Content Distribution Network (CDN) deploys a set of proxy servers called replicas and improves the content delivery performance by replicating the content to multiple replicas in the Internet.

These issues motivate us to do research in how to efficiently place replicas in the network, and then propose a cost-based replica placement algorithm which selects replica locations using a greedy fashion iteratively. We evaluated that it can yield close to optimal performance at low management and computation cost among several replica placement strategies.

The key contributions of this paper are threefold:

1. A practical cost function from the game theoretic perspective is designed, and is limited by various parameters and constraints. It can minimize either its clients' latency or its total bandwidth consumption.

2. A cost-based replica placement integrating a greedy algorithm is proposed, which can provide CDNs with the performance close to optimal.

3. The performance of the diversified replica placement algorithms is evaluated by simulating their behavior on synthetic and real network topologies. To the best of our knowledge, there are few studies on this subject.

In summary, we study the online problem of placing web replicas in CDNs to minimize the cost for clients to access data replicated from the original web servers. The novel cost-based replica placement is designed combining with the minimum k-median heuristic greedy algorithm. We evaluate the performance of the different replica placement algorithms by simulating their behavior on both synthetic and real network topologies. Based upon simulation results, we conclude that our cost-based greedy algorithm for web server replica placement can provide CDNs with performance that is close to optimal. Although the greedy algorithm depends upon estimation, we find it is a viable and practical algorithm to use in the general Internet environment. As for future work, we are interested in exploring incremental versions of the placement algorithms that also take into account the cost of changing the set of replica sites. Ideally, for placement strategies with similar performance, we prefer the one that incurs the least amount of perturbation to the system.

Keywords:

• Access frequency
• Cost function
• Content Distribution Network (CDN)
• Replica placement algorithm
• Web replica

This work was supported by National 863 High Tech R&D Program of China, No. 2006DFA11050 and No. 2006AA01Z283, National Natural Science Foundation (NSFC) of China, No. 60632030 and No. 60496312, and the German Federal Ministry of Education and Research within the “Universal Service Terminal Enhancement (UST+)” project.