Designing cost-effective content distribution networks

摘要

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 (ⅰ) the number and placement of proxy servers on a given set of potential nodes, (ⅱ) replicating content on the proxy servers, and (ⅲ) 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.