Optimal allocation of electronic content

• Published in: Computer networks (Amsterdam, Netherlands : 1999) Netherlands : 1999), 2002-10, Vol.40 (2), p.205-218
• Main Authors: Cidon, Israel, Kutten, Shay, Soffer, Ran
• Format: Article
• Language: English
• Subjects: Algorithms; Broadband; Broadband networks; Data transmission; Electronic media; Linear programming; Network computers; Networks; Optimization; Storage; Studies; Video on demand
• ISSN: 1389-1286; 1872-7069
• DOI: 10.1016/S1389-1286(02)00251-7

The delivery of large files to individual users, such as video on demand or application programs to the envisioned network computers is expected by many to be one of the main tasks of broadband communication networks. This requires high bandwidth capacity as well as fast and dense storage servers. This motivates multimedia service providers to optimize the delivery network, as well as the electronic content allocation. A hierarchical architecture for the distribution of multimedia content was introduced by Nussbaumer, Patel, Schaffa, and Sterbenz (INFOCOM 94). They addressed the trade-off between bandwidth and storage requirements that results from the placement of the content servers in the hierarchy tree. They presented a centralized algorithm to compute the best level of the hierarchy for the server location to minimize the combined cost of communication and storage. In this work, we solve a general case where servers can be placed at different levels of the hierarchy. We develop a distributed optimal location algorithm that requires small nodal memory capacity and computational power. Previous results for related problems for caching system design are of higher complexity. Previous results for related classic operations research problems are limited to centralized algorithms, based on linear programming, that are not easy to convert into distributed algorithms. Instead, to obtain our results, we observed that the use of dynamic programming naturally lends itself to a distributed implementation. For the specific problem at hand, we also managed to find a natural function (a generalization of the problem) that simplifies the combination operation used in the design of a dynamic program.