This paper proposes a new replica placement algorithm that expands the exhaustive search limit with reasonable calculation time. It combines a new type of parallel data-flow processor with an architecture tuned for fast calculation. The replica placement problem is to find a replica-server set satisfying service constraints in a content delivery network (CDN). It is derived from the set cover problem which is known to be NP-hard. It is impractical to use exhaustive search to obtain optimal replica placement in large-scale networks, because calculation time increases with the number of combinations. To reduce calculation time, heuristic algorithms have been proposed, but it is known that no heuristic algorithm is assured of finding the optimal solution. The proposed algorithm suits parallel processing and pipeline execution and is implemented on DAPDNA-2, a dynamically reconfigurable processor. Experiments show that the proposed algorithm expands the exhaustive search limit by the factor of 18.8 compared to the conventional algorithm search limit running on a Neumann-type processor. 1. Introduction Content delivery networks (CDNs) [1–3] are being developed to improve the user’s experience when downloading voluminous files such as music and videos, a rapidly growing component of the traffic on the Internet. A CDN consists of two types of servers: origin server and replica server. The original data is stored in the origin server and then copied to the replica servers, which are geographically distributed. A user requesting content is connected to a replica server automatically selected by the network, which then sends the content to the user. Replica selection is based on the distance between the server and the user, and usually, the closest server is selected [4]. One important issue in CDN performance is replica placement [5]. The problem is in deciding which servers are to hold which replicas. Replica servers cache the original servers’ contents to prevent traffic congestion and to maintain user performance. They allow CDN providers to minimize the capital expenditures (CapEx) and operational expenditures (OpEx). Note that cache size is restricted; no replica server can hold all of the contents held by the origin server. For each content, we must pick those servers, not all, that will hold the replica. In addition, in order to achieve adequate user performance, each replica server must have a limited delivery area. The delivery area is expressed as the distance from the replica server. Each user must lie within the delivery area of at least one replica
References
[1]
“Akamai,” http://www.akamai.com/.
[2]
“Level 3,” http://www.level3.com/.
[3]
“Mirrorimge,” http://www.mirror-image.com/.
[4]
F. L. Presti, C. Petrioli, and C. Vicari, “Dynamic replica placement and user request redirection in content delivery networks,” in Proceedings of the 4th Annual IEEE International Conference on Communications (ICC '05), vol. 3, pp. 1495–1501, May 2005.
[5]
L. Qiu, V. N. Padmanabhan, and G. M. Voelker, “On the placement of web server replicas,” in Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '01), vol. 3, pp. 1587–1596, April 2001.
[6]
M. Karlsson and C. Karamanolis, “Bounds on the replication cost for QoS,” Tech. Rep., Hewlett Packard Labs, 2003.
[7]
C. Toregas, C. ReVelle, and L. Bergman, “The location of emergency service facilities,” Operations Research, vol. 19, pp. 1363–1373, 1971.
[8]
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, 1979.
[9]
K. Jain, M. Mahdian, and A. Saberi, “A new greedy approach for facility location problems,” in Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pp. 731–740, May 2002.
[10]
J. Kangasharju, J. Roberts, and K. W. Ross, “Object replication strategies in content distribution networks,” Computer Communications, vol. 25, no. 4, pp. 376–383, 2002.
[11]
X. Tang and J. Xu, “QoS-aware replica placement for content distribution,” IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 10, pp. 921–932, 2005.
[12]
H. Wang, P. Liu, and J.-J. Wu, “A QoS-aware heuristic algorithm for replica placement,” in Proceedings of the 7th IEEE/ACM International Workshop on Grid Computing, pp. 96–103, September 2006.
[13]
S. Zaman and D. Grosu, “A distributed algorithm for the replica placement problem,” IEEE Transactions on Parallel and Distributed Systems, vol. 22, no. 9, pp. 1455–1468, 2011.
[14]
T. Sato, H. Watanabe, and K. Shiba, “Implementation of dynamically reconfigurable processor DAPDNA-2,” in Proceedings of the IEEE VLSI-TSA International Symposium on VLSI Design, Automation and Test (VLSI-TSA '05), pp. 323–324, April 2005.
[15]
D. S. Johnson, “Approximation algorithms for combinatorial problems,” Journal of Computer and System Sciences, vol. 9, no. 3, pp. 256–278, 1974.
[16]
T. Sugawara, K. Ide, and T. Sato, “Dynamically reconfigurable processor implemented with IPFlex's DAPDNA technology,” IE-ICE Transactions on Information and Systems, vol. E87-D, no. 8, pp. 1997–2003, 2004.
[17]
M. Beeler, R. W. Gosper, and R. Schroeppel, “HAKMEM ITEM175,” http://www.cl.cam.ac.uk/~am21/hakmemc.html.
[18]
M. Beeler, R. W. Gosper, and R. Schroeppel, in C: A Reference Manual, S. P. Harbison and G. L. Steele Jr., Eds., p. 176, Prentice-Hall, 2nd edition, 1978.
[19]
E. W. Dijkstra, “A note on two problems in connection with graphs,” Numerische Mathematik, vol. 1, no. 1, pp. 269–271, 1959.
