Content-selection strategies for the periodic prefetching of WWW resourcesvia satellite

In this paper we study satellite-caching, that is, the employment of satell ite multicasting for the dissemination of prefetched content to WWW caches. This approach is currently being deployed by major satellite operators and ISPs around the world. We introduce a theoretical framework to study satel lite-caching and formalize the notions of Utility and Quality of Service. W e explore two charging schemes, Usage-and Subscription-based pricing, and p ropose a framework for negotiating the provision of the satellite-caching s ervice between a satellite operator and its potential clients. We use this negotiation framework to compare theoretically the two pricing schemes at h and. We apply our modeling to formulate the selection of Web-content for sa tellite-multicasting as a combinatorial optimization problem. We study the complexity of Web-content selection and prove it is NP-complete. Finally, w e propose and implement an approximation algorithm for content selection, a nd conduct experiments to assess its efficiency, validity and applicability . (C) 2001 Elsevier Science B.V. All rights reserved.