|
Abstract : |
We consider the problem of caching multimedia streams in the internet. We use the dynamic caching framework of Dan et al. [3] and Hofmann et al. [5]. We dene a novel performance metric based on the maximum number of simultaneous cache misses, and present near-optimal on-line algorithms for determining which parts of the streams should be cached at any point in time for the case of a single server and single cache. We extend this model to case of a single cache with dierent per-client connection costs, and give an 8-competitive algorithm in this setting. Finally, we propose a model for multiple caches in a network and present an algorithm that is O(K)-competitive if we are able to increase the cache sizes by an O(K) factor. Here K is the number of caches in the network., |
