Article ID: | iaor20082845 |
Country: | United Kingdom |
Volume: | 34 |
Issue: | 8 |
Start Page Number: | 2436 |
End Page Number: | 2449 |
Publication Date: | Aug 2007 |
Journal: | Computers and Operations Research |
Authors: | Oguz Osman, Ouveysi Iradj, Bektas Tolga |
Keywords: | distribution, communication, programming: integer, programming: nonlinear, heuristics |
In this paper, we present a novel technique for the problem of designing a Content Distribution Network (CDN), which is a technology used to efficiently distribute electronic content throughout an existing IP network. Our design proposal consists of jointly deciding on (i) the number and placement of proxy servers on a given set of potential nodes, (ii) replicating content on the proxy servers, and (iii) routing the requests for the content to a suitable proxy server such that the total cost of distribution is minimized. We model the problem using a nonlinear integer programming formulation. The novelty of the proposed formulation lies in simultaneously addressing three interdependent problems in this context as well as explicitly representing the distribution structure of a CDN through the objective function. We offer a linearization for the model, develop an exact solution procedure based on Benders' decomposition and also utilize a variant of this procedure to accelerate the algorithm. In addition, we provide a fast and efficient heuristic that can be used to obtain near-optimal solutions to the problem. Finally, the paper concludes with computational results showing the performance of the decomposition procedure and the heuristic algorithm on randomly generated Internet topologies.