Online algorithms for caching multimedia streams
We consider the problem of caching multimedia streams in the internet. We use the dynamic caching framework of Dan et al. and Hofmann et al.. We define 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 different 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 increase the cache sizes by O(K). Here K is the number of caches in the network.
Duke Scholars
Published In
DOI
EISSN
ISSN
Publication Date
Volume
Start / End Page
Related Subject Headings
- Artificial Intelligence & Image Processing
- 46 Information and computing sciences
Citation
Published In
DOI
EISSN
ISSN
Publication Date
Volume
Start / End Page
Related Subject Headings
- Artificial Intelligence & Image Processing
- 46 Information and computing sciences