TY - JOUR
T1 - Object replication strategies in content distribution networks
AU - Kangasharju, Jussi
AU - Roberts, James
AU - Ross, Keith W.
N1 - Funding Information:
The routing data summaries used in constructing the network topologies were provided by National Science Foundation Cooperative Agreement No. ANI-9807479, and the National Laboratory for Applied Network Research. We would also like to thank Anat Bremler-Barr of Tel Aviv University for the discussions about the topology models.
PY - 2002/3/1
Y1 - 2002/3/1
N2 - Recently, the Internet has witnessed the emergence of content distribution networks (CDNs). In this paper, we study the problem of optimally replicating objects in CDN servers. In our model, each Internet autonomous system (AS) is a node with finite storage capacity for replicating objects. The optimization problem is to replicate objects so that when clients fetch objects from the nearest CDN server with the requested object, the average number of ASs traversed is minimized. We formulate this problem as a combinatorial optimization problem. We show that this optimization problem is NP complete. We develop four natural heuristics and compare them numerically using real Internet topology data. We find that the best results are obtained with heuristics that have all the CDN servers cooperating in making the replication decisions. We also develop a model for studying the benefits of cooperation between nodes, which provides insight into peer-to-peer content distribution.
AB - Recently, the Internet has witnessed the emergence of content distribution networks (CDNs). In this paper, we study the problem of optimally replicating objects in CDN servers. In our model, each Internet autonomous system (AS) is a node with finite storage capacity for replicating objects. The optimization problem is to replicate objects so that when clients fetch objects from the nearest CDN server with the requested object, the average number of ASs traversed is minimized. We formulate this problem as a combinatorial optimization problem. We show that this optimization problem is NP complete. We develop four natural heuristics and compare them numerically using real Internet topology data. We find that the best results are obtained with heuristics that have all the CDN servers cooperating in making the replication decisions. We also develop a model for studying the benefits of cooperation between nodes, which provides insight into peer-to-peer content distribution.
KW - Content distribution networks
KW - Cooperation
KW - Optimal replication strategies
KW - Peer-to-peer networks
UR - http://www.scopus.com/inward/record.url?scp=0036497474&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0036497474&partnerID=8YFLogxK
U2 - 10.1016/S0140-3664(01)00409-1
DO - 10.1016/S0140-3664(01)00409-1
M3 - Article
AN - SCOPUS:0036497474
SN - 0140-3664
VL - 25
SP - 376
EP - 383
JO - Computer Communications
JF - Computer Communications
IS - 4
ER -