Replication algorithms to retrieve scalable streaming media over Content Delivery Networks

ABSTRACT

CDN (Content Delivery Networks) improves end-user performance by replicating web contents on a group of geographically distributed content servers. Replication Algorithm plays an important role in helping users to retrieve Web objects from the content servers. If a user can directly get the requested objects from the content server, he need not to contact the remote origin server and the user delay can be reduced. However, current replica strategies in CDN are to simply and repeatedly keep the complete replica of the original object on many content servers. This method has some disadvantages, including too much consumed server space and a waste of the storage cost. It is more serious for replicating some large-sized objects such as streaming media, which are being distributed over the Internet more and more.In this paper, we discuss a replication strategy for scalable video streaming in CDN to reduce user response and storage cost. Based on theoretical analysis, assuming layered video coding, we propose a novel replication algorithm which deals with following three problems. (1) How many content servers should be selected to replicate a given video content? (2) For a single video content, how many layers should be kept in a given content server? (3) After selecting a group of content servers for each video content, how do we decide the replication priority for each content server? Simulation results show that the proposed algorithm can efficiently resolve the above problems, and provide much better performance than the conventional methods.

REFERENCES

• 1: J. Kangasharju and K. W. Ross," Performance Evaluation of Redirection Schemes in Content Distribution Networks", The 5th International Web Caching and Content Delivery Workshop, May 2000.
• 2: A. Beck and M. Hofmann, "Enabling the Internet to Delivery Content-Oriented Services" Proc. The 6th International Web Caching and Content Distribution, Boston, USA Jun 2001.
• 3: Adero, <URL: http: www.adero.com>
• 4: Akamai, <URL: http: www.akamai.com>
• 5: Napster, <URL: http://www.napster.com>
• 6: L. Gao, "On Inferring Automonous System Relationships in the Internet" IEEE Global Internet, 2002, Nov.
• 7: H M. Radha, M. V. D. Schaar, and Y. Chen, "The MPEG-4 Fine Grained Scalable Video Coding Method for Multimedia Streaming Over IP", IEEE Trans. Multimedia Vol. 3, No. 1, pp. 53--67, March 2001.
• 8: Jussi Kangasharju , Felix Hartanto , Martin Reisslein , Keith W. Ross, Distributing Layered Encoded Video through Caches, IEEE Transactions on Computers, v.51 n.6, p.622-636, June 2002 [doi>10.1109/TC.2002.1009148]
• 9: John Byers , Jeffrey Considine , Michael Mitzenmacher , Stanislav Rost, Informed content delivery across adaptive overlay networks, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 10: M. Chesire, A. Wolman, G. M. Voelker, and H. M. Levy, "Measurement and Analysis of a Stream Media Workload", USITIS'01, San Francisco, CA, Mar. 2001.
• 11: S. Acharya and B. Smith and P. Parnes, "Characterizing User Access To Videos on the Videos On the World Wide Web" SPIE/ACM MMCN 2000, San Jose, CA, Jan 2000.
• 12: J. Kangasharju, J. Roberts, K. W. Ross, "Object replication strategies in Content Distribution Networks", Computer Communications, 25 2002.
• 13: P. Krishnan , Danny Raz , Yuval Shavitt, The cache location problem, IEEE/ACM Transactions on Networking (TON), v.8 n.5, p.568-582, Oct. 2000 [doi>10.1109/90.879344]
• 14: B. Li, M. J. Golin, G. F. Italiano, and X. Deng. On the optimal placement of web proxies in the internet. In Proceedings of IEEE Infocom, New York, NY, pp 21--25, March 1999.
• 15: L. Qiu, V. N. Padmanabhan, and G. M. Voelker. On the placement of web server replicas. In Proceedings of IEEE Infocom, Anchorage, AK, pp 22--26, April 2001.
• 16: S. Sen, J. Rexford, and D. Towsley, "Proxy Prefix Caching for Multimedia Streams," IEEE INFOCOM99, N. Y, Mar. 1999.
• 17: Sung-Ju Lee, Wei-Ying Ma, and Bo Shen "An Interactive Video Delivery and Caching System Using Video Summarization", WCW2001, Boston, MA, June 2001
• 18: R. Rejaie, H. Yu, M. Handley, and D. Estrin, "Multimedia proxy caching mechanism for quality adaptive streaming applications in the Internet," IEEE INFOCOM 2000, March 2000.
• 19: M. Sasabe, N. Wakamiya, M. Murata, and H. Miyahara, "Proxy caching mechanisms with video quality adjustment", SPIE ITCom Feb. 2001.
• 20: L. Breslao, P. Cao, L. Fan, G. Phillips, and S. Shenker "Web Caching and Zip-like Distributions: Evidence and Implications" Proc. IEEE INFOCOM'99, New York, April, 1999.
• 21: L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker, "On the Implications of Zipf's Law for Web Caching", In 3rd International WWW Caching Workshop, June 1998.
• 22: Z. Su, J. Katto, T. Nishikawa, M. Murakami and Y. Yasuda, "Stream Caching Using Hierarchically Distributed Proxies with Adaptive Segments Assignment", IEICE Trans on Commun, Vol. E86-B, Jun. 2003, pp 1859--1869.
• 23: Z. Su, T. Washinzawa, J. Katto, and Y. Yasuda, "Integrated Prefetching and Caching Algorithm for Graceful Image Caching", IEICE Trans on Commun, Vol. E86-B, No. 9, Sep. 2003, pp 2753--2763.
• 24: Q. Lv, P. Cao, E. Cohen, K. Li, S. Shenker: "Search and Replication in Unstructured Peer-to-Peer Networks". ICS 2002.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms

Keywords:
Content Distribution Networks, network traffic, replication algorithm, scalable, streaming, web performance