Optimal caching algorithm based on dynamic programming

Changjie Guo; Zhe Xiang; Yuzhuo Zhong; Jidong Long

doi:10.1117/12.434279

20 July 2001 Optimal caching algorithm based on dynamic programming

Changjie Guo, Zhe Xiang, Yuzhuo Zhong, Jidong Long

Proceedings Volume 4519, Internet Multimedia Management Systems II; (2001) https://doi.org/10.1117/12.434279
Event: ITCom 2001: International Symposium on the Convergence of IT and Communications, 2001, Denver, CO, United States

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.

Citation Download Citation

Changjie Guo, Zhe Xiang, Yuzhuo Zhong, and Jidong Long "Optimal caching algorithm based on dynamic programming", Proc. SPIE 4519, Internet Multimedia Management Systems II, (20 July 2001); https://doi.org/10.1117/12.434279

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available