The stretched exponential distribution of internet media access patterns

ABSTRACT

The commonly agreed Zipf-like access pattern of Web workloads is mainly based on Internet measurements when text-based content dominated the Web traffic. However, with dramatic increase of media traffic on the Internet, the inconsistency between the access patterns of media objects and the Zipf model has been observed in a number of studies. An insightful understanding of media access patterns is essential to guide Internet system design and management, including resource provisioning and performance optimizations.

In this paper, we have studied a large variety of media workloads collected from both client and server sides in different media systems with different delivery methods. Through extensive analysis and modeling, we find: (1) the object reference ranks of all these workloads follow the stretched exponential (SE) distribution despite their different media systems and delivery methods; (2) one parameter of this distribution well characterizes the media file sizes, the other well characterizes the aging of media accesses; (3) some biased measurements may lead to Zipf-like observations on media access patterns; and (4) the deviation of media access pattern from the Zipf model in these workloads increases along with the workload duration.

We have further analyzed the effectiveness of media caching with a mathematical model. Compared with Web caching under the Zipf model, media caching under the SE model is far less effective unless the cache size is enormously large. This indicates that many previous studies based on a Zipf-like assumption have potentially overestimated the media caching benefit, while an effective media caching system must be able to scale its storage size to accommodate the increase of media content over a long time. Our study provides an analytical basis for applying a P2P model rather than a client-server model to build large scale Internet media delivery systems.

REFERENCES

• 1: http://iblnews.com/story.php?id=17429.
• 2: http://www.youtube.com/.
• 3: http://www.imdb.com/chart/top.
• 4: Buffer settings in windows media player. http://support.microsoft.com/.
• 5: Helix universal proxy. http://www.realnetworks.com/.
• 6: IFILM. http://www.ifilm.com/.
• 7: Using the Microsoft Windows media proxy with ACNS 5.1. http://www.cisco.com/.
• 8: Windows media services. http://www.microsoft.com/.
• 9: S. Acharya, B. Smith, and P. Parnes. Characterizing user access to videos on the world wide web. In Proc. of MMCN, 2000.
• 10: Martin F. Arlitt , Carey L. Williamson, Web server workload characterization: the search for invariants, Proceedings of the 1996 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.126-137, May 23-26, 1996, Philadelphia, Pennsylvania, United States
• 11: A. Bellissimo, B. Levine, and P. Shenoy. Exploring the use of BitTorrent as the basis for a large trace repository. Technical report, Department of Computer Science, University of Massachusetts, Amherst, 2004.
• 12: L. Breslau, P. Cao, L. Fan, G. Philips, and S. Shenker. Web caching and Zipf-like distributions: Evidence and implications. In Proc. of INFOCOM, Mar. 1999.
• 13: Meeyoung Cha , Haewoon Kwak , Pablo Rodriguez , Yong-Yeol Ahn , Sue Moon, I tube, you tube, everybody tubes: analyzing the world's largest user generated content video system, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA [doi>10.1145/1298306.1298309]
• 14: Ludmila Cherkasova , Minaxi Gupta, Characterizing locality, evolution, and life span of accesses in enterprise media server workloads, Proceedings of the 12th international workshop on Network and operating systems support for digital audio and video, May 12-14, 2002, Miami, Florida, USA [doi>10.1145/507670.507676]
• 15: Maureen Chesire , Alec Wolman , Geoffrey M. Voelker , Henry M. Levy, Measurement and analysis of a streaming-media workload, Proceedings of the 3rd conference on USENIX Symposium on Internet Technologies and Systems, p.1-1, March 26-28, 2001, San Francisco, California
• 16: J. Chu, K. Labonte, and B. Levine. Availability and popularity measurements of peer-to-peer file systems. In Proc. of SPIE ITCom, July 2002.
• 17: Phillipa Gill , Martin Arlitt , Zongpeng Li , Anirban Mahanti, Youtube traffic characterization: a view from the edge, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA [doi>10.1145/1298306.1298310]
• 18: Carsten Griwodz , Michael Bär , Lars C. Wolf, Long-term movie popularity models in video-on-demand systems: or the life of an on-demand movie, Proceedings of the fifth ACM international conference on Multimedia, p.349-357, November 09-13, 1997, Seattle, Washington, United States [doi>10.1145/266180.266386]
• 19: Krishna P. Gummadi , Richard J. Dunn , Stefan Saroiu , Steven D. Gribble , Henry M. Levy , John Zahorjan, Measurement, modeling, and analysis of a peer-to-peer file-sharing workload, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 20: Lei Guo , Xiaodong Zhang, Insights into access patterns of internet media systems: measurements, analysis, and system design, Ohio State University, Columbus, OH, 2008
• 21: Lei Guo , Songqing Chen , Zhen Xiao , Enhua Tan , Xiaoning Ding , Xiaodong Zhang, Measurements, analysis, and modeling of BitTorrent-like systems, Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement, p.4-4, October 19-21, 2005, Berkeley, CA
• 22: Lei Guo , Songqing Chen , Zhen Xiao , Xiaodong Zhang, DISC: Dynamic Interleaved Segment Caching for Interactive Streaming, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, p.763-772, June 06-10, 2005 [doi>10.1109/ICDCS.2005.22]
• 23: Lei Guo , Enhua Tan , Songqing Chen , Zhen Xiao , Oliver Spatscheck , Xiaodong Zhang, Delving into internet streaming media delivery: a quality and resource utilization perspective, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177108]
• 24: A. Iamnitchi, M. Ripeanu, and I. Foster. Small-world file-sharing communities. In Proc. of IEEE INFOCOM, Mar. 2004.
• 25: J. Laherrere and D. Sornette. Stretched exponential distributions in nature and economy: “fat tails" with characteristic scales. European Physical Journal B, 2:525--539, 1998.
• 26: Osama Saleh , Mohamed Hefeeda, Modeling and Caching of Peer-to-Peer Traffic, Proceedings of the Proceedings of the 2006 IEEE International Conference on Network Protocols, p.249-258, November 12-15, 2006 [doi>10.1109/ICNP.2006.320218]
• 27: Kunwadee Sripanidkulchai , Bruce Maggs , Hui Zhang, An analysis of live streaming workloads on the internet, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028795]
• 28: Wenting Tang , Yun Fu , Ludmila Cherkasova , Amin Vahdat, MediSyn: a synthetic streaming media service workload generator, Proceedings of the 13th international workshop on Network and operating systems support for digital audio and video, June 01-03, 2003, Monterey, CA, USA [doi>10.1145/776322.776327]
• 29: Eveline Veloso , Virgílio Almeida , Wagner Meira , Azer Bestavros , Shudong Jin, A hierarchical characterization of a live streaming media workload, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637220]
• 30: A. Williams, M. Arlitt, C. Williamson, and K. Barker. Web Content Delivery, chapter Web Workload Characterization: Ten Years Later. Springer, 2005.
• 31: Carey Williamson, On filter effects in web caching hierarchies, ACM Transactions on Internet Technology (TOIT), v.2 n.1, p.47-77, February 2002 [doi>10.1145/503334.503337]
• 32: Hongliang Yu , Dongdong Zheng , Ben Y. Zhao , Weimin Zheng, Understanding user behavior in large-scale video-on-demand systems, Proceedings of the 1st ACM SIGOPS/EuroSys European Conference on Computer Systems 2006, April 18-21, 2006, Leuven, Belgium

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)

General Terms:
Measurement, Performance

Keywords:
modeling, multimedia, traffic analysis