Share Email Print

Proceedings Paper

Optimal caching algorithm based on dynamic programming
Author(s): Changjie Guo; Zhe Xiang; Yuzhuo Zhong; Jidong Long
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

With the dramatic growth of multimedia streams, the efficient distribution of stored videos has become a major concern. There are two basic caching strategies: the whole caching strategy and the caching strategy based on layered encoded video, the latter can satisfy the requirement of the highly heterogeneous access to the Internet. Conventional caching strategies assign each object a cache gain by calculating popularity or density popularity, and determine which videos and which layers should be cached. In this paper, we first investigate the delivery model of stored video based on proxy, and propose two novel caching algorithms, DPLayer (for layered encoded caching scheme) and DPWhole (for whole caching scheme) for multimedia proxy caching. The two algorithms are based on the resource allocation model of dynamic programming to select the optimal subset of objects to be cached in proxy. Simulation proved that our algorithms achieve better performance than other existing schemes. We also analyze the computational complexity and space complexity of the algorithms, and introduce a regulative parameter to compress the states space of the dynamic programming problem and reduce the complexity of algorithms.

Paper Details

Date Published: 20 July 2001
PDF: 11 pages
Proc. SPIE 4519, Internet Multimedia Management Systems II, (20 July 2001); doi: 10.1117/12.434279
Show Author Affiliations
Changjie Guo, Tsinghua Univ. (China)
Zhe Xiang, Tsinghua Univ. (China)
Yuzhuo Zhong, Tsinghua Univ. (China)
Jidong Long, Univ. of Electronics Science and Technology of China (China)

Published in SPIE Proceedings Vol. 4519:
Internet Multimedia Management Systems II
John R. Smith; Sethuraman Panchanathan; C.-C. Jay Kuo; Chinh Le, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?