CD-PAN: a protocol for peer-to-peer content distribution in a weakly connected and heterogeneous personal area network

ABSTRACT

This paper presents CD-PAN, a mechanism to automatically distribute content objects to weakly connected heterogeneous content devices in a personal area network without a global namespace. The content devices under consideration range from cell phones to personal computers, each of which is capable of downloading content objects on its own. The proposed mechanism alleviates the need to manually synchronize content that is downloaded to each of these content devices. A simulation study shows that CD-PAN outperforms other prefetching schemes in all our workload experiments. The performance improvement tended to increase with increase in popularity distribution skew, temporal locality and frequency of content creation/updates. The performance of CD-PAN increases when pair-wise communication capabilities are higher, and also adapts well to increasing power and metadata constraints.

REFERENCES

• 1: Atul Adya , Paramvir Bahl , Lili Qiu, Analyzing the browse patterns of mobile clients, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505226]
• 2: Anand Balachandran , Geoffrey M. Voelker , Paramvir Bahl , P. Venkat Rangan, Characterizing user behavior and network performance in a public wireless LAN, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 3: Azer Bestavros and Carlos Cunha. Server-initiated document dissemination for the www. IEEE Data Engineering Bulletin, September 1996
• 4: Anawat Chankhunthod , Peter B. Danzig , Chuck Neerdaels , Michael F. Schwartz , Kurt J. Worrell, A hierarchical internet object cache, Proceedings of the 1996 annual conference on USENIX Annual Technical Conference, p.13-13, January 22-26, 1996, San Diego, CA
• 5: Antony Rowstron , Peter Druschel, Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 6: Alec Wolman , M. Voelker , Nitin Sharma , Neal Cardwell , Anna Karlin , Henry M. Levy, On the scale and performance of cooperative Web proxy caching, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.16-31, December 12-15, 1999, Charleston, South Carolina, United States
• 7: Balachander Krishnamurthy , Craig Wills , Yin Zhang, On the use and performance of content distribution networks, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505224]
• 8: Carlos R. Cunha , Carlos F. B. Jaccoud, Determining WWW User's Next Access and Its Application to Pre-fetching, Proceedings of the 2nd IEEE Symposium on Computers and Communications (ISCC '97), p.6, July 01-03, 1997
• 9: Carlos Cunha , Azer Bestavros , Mark Crovella, Characteristics of WWW Client-based Traces, Boston University, Boston, MA, 1995
• 10: Carla Schlatter Ellis, The Case for Higher-Level Power Management, Proceedings of the The Seventh Workshop on Hot Topics in Operating Systems, p.162, March 28-30, 1999
• 11: Dennis Fetterly , Mark Manasse , Marc Najork , Janet L. Wiener, A large-scale study of the evolution of web pages, Software—Practice & Experience, v.34 n.2, p.213-237, February 2004 [doi>10.1002/spe.577]
• 12: Dahlia Malkhi and Doug Terry. Concise version vectors in WinFS. In Symposium on Distributed Computing, 2005
• 13: Daniel Peek , Jason Flinn, EnsemBlue: integrating distributed storage and consumer electronics, Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation, p.16-16, November 06-08, 2006, Seattle, WA
• 14: Evangelos P. Markatos and Catherine E. Chronaki. A top-10 approach to prefetching on the web. Technical report No. 173, ICS-FORTH, August 1996
• 15: Edmund B. Nightingale , Jason Flinn, Energy-efficiency and storage flexibility in the blue file system, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.25-25, December 06-08, 2004, San Francisco, CA
• 16: Elizabeth Shriver , Christopher Small , Keith A. Smith, Why does file system prefetching work?, Proceedings of the annual conference on USENIX Annual Technical Conference, p.6-6, June 06-11, 1999, Monterey, California
• 17: Frank Dabek , M. Frans Kaashoek , David Karger , Robert Morris , Ion Stoica, Wide-area cooperative storage with CFS, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 18: Guanling Chen , David Kotz, A Survey of Context-Aware Mobile Computing Research, Dartmouth College, Hanover, NH, 2000
• 19: Guohong Cao, Proactive Power-Aware Cache Management for Mobile Computing Systems, IEEE Transactions on Computers, v.51 n.6, p.608-621, June 2002 [doi>10.1109/TC.2002.1009147]
• 20: Geoffrey H. Kuenning , Gerald J. Popek, Automated hoarding for mobile computers, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.264-275, October 05-08, 1997, Saint Malo, France
• 21: Gene T.J. Wuu , Arthur J. Bernstein, Efficient solutions to the replicated log and dictionary problems, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.233-242, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806750]
• 22: Hui Lei , Dan Duchamp, An analytical approach to file prefetching, Proceedings of the annual conference on USENIX Annual Technical Conference, p.21-21, January 06-10, 1997, Anaheim, California
• 23: R. H. Patterson , G. A. Gibson , E. Ginting , D. Stodolsky , J. Zelenka, Informed prefetching and caching, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.79-95, December 03-06, 1995, Copper Mountain, Colorado, United States
• 24: Huaping Shen, Mohan Kumar, Sajal K. Das and Zhijun Wang. Energy-efficient caching and prefetching with data consistency in mobile distributed systems. In Proceedings of the International Parallel and Distributed Processing Symposium. 2004
• 25: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 26: Junghoo Cho , Hector Garcia-Molina, The Evolution of the Web and Implications for an Incremental Crawler, Proceedings of the 26th International Conference on Very Large Data Bases, p.200-209, September 10-14, 2000
• 27: James Griffioen , Randy Appleton, Reducing file system latency using a predictive approach, Proceedings of the USENIX Summer 1994 Technical Conference on USENIX Summer 1994 Technical Conference, p.13-13, June 06-10, 1994, Boston, Massachusetts
• 28: James J. Kistler , M. Satyanarayanan, Disconnected operation in the Coda File System, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.3-25, Feb. 1992 [doi>10.1145/146941.146942]
• 29: Jianliang Xu , Qinglong Hu , Wang-Chien Lee , Dik Lun Lee, An Optimal Cache Replacement Policy for Wireless Data Dissemination under Cache Consistency, Proceedings of the 2001 International Conference on Parallel Processing, p.267-276, September 03-07, 2001
• 30: Karin Petersen , Mike J. Spreitzer , Douglas B. Terry , Marvin M. Theimer , Alan J. Demers, Flexible update propagation for weakly consistent replication, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.288-301, October 05-08, 1997, Saint Malo, France
• 31: http://www.us.31g.com/RutUS_prod/Documents/12/Consumer %20Convergence%20study.pdf
• 32: Lee Breslau, Pei Cao, Li Fan, Graham Phillips and Scott Shenkar. Web Caching and Zipf-like Distributions: Evidence and Implications. In Proceedings of IEEE INFOCOM, 1999
• 33: Lei Guo , Songqing Chen , Zhen Xiao , Xiaodong Zhang, Analysis of multimedia workloads with implications for internet streaming, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060821]
• 34: Li Fan , Pei Cao , Wei Lin , Quinn Jacobson, Web prefetching between low-bandwidth clients and proxies: potential and performance, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.178-187, May 01-04, 1999, Atlanta, Georgia, United States
• 35: Laura Marie Feeney, Martin Nilsson. Investigating the energy consumption of a wireless network interface in an Ad hoc networking environment. In IEEE Proceedings of INFOCOM, 2001
• 36: Liangzhong Yin , Guohong Cao , Chita Das , Ajeesh Ashraf, Power-Aware Prefetch in Mobile Environments, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.571, July 02-05, 2002
• 37: 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
• 38: Minaxi Gupta and Mostafa Ammar. A Novel Multicast Scheduling for multimedia servers with variable access patterns. In Proceedings of the IEEE International conference on Communications. 2003
• 39: Maria Papadopouli and Henning Schulzrinne. Design and Implementation of a Peer-to-Peer Data Dissemination and Prefetching Tool for Mobile Users. First NY Metro Area Networking Workshop, 2001
• 40: Marvin McNett , Geoffrey M. Voelker, Access and mobility of wireless PDA users, ACM SIGMOBILE Mobile Computing and Communications Review, v.9 n.2, April 2005 [doi>10.1145/1072989.1072995]
• 41: Michael N. Nelson , Brent B. Welch , John K. Ousterhout, Caching in the Sprite network file system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.134-154, Feb. 1988 [doi>10.1145/35037.42183]
• 42: MagicSync: http://www.pdatopsoft.com/SmartPhones/MagicSync-Lite-(SmartPhone)
• 43: Nalini Belaramani , Mike Dahlin , Lei Gao , Amol Nayate , Arun Venkataramani , Praveen Yalagandula , Jiandan Zheng, PRACTI replication, Proceedings of the 3rd conference on Networked Systems Design & Implementation, p.5-5, May 08-10, 2006, San Jose, CA
• 44: http://www.44ab.tkk.fi/~hverkasa/verkasalo_hmr_2006.pdf
• 45: Paul Barford , Mark Crovella, Generating representative Web workloads for network and server performance evaluation, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.151-160, June 22-26, 1998, Madison, Wisconsin, United States
• 46: Paul Barford , Azer Bestavros , Adam Bradley , Mark Crovella, Changes in Web client access patterns: Characteristics and caching implications, World Wide Web, v.2 n.1-2, p.15-28, 1999 [doi>10.1023/A:1019236319752]
• 47: Pei Cao , Edward W. Felten , Anna R. Karlin , Kai Li, Implementation and performance of integrated application-controlled file caching, prefetching, and disk scheduling, ACM Transactions on Computer Systems (TOCS), v.14 n.4, p.311-343, Nov. 1996 [doi>10.1145/235543.235544]
• 48: PocketMirror: http://www.chapura.com/
• 49: Richard G. Guy, John S. Heidemann, Wai Mak, Thomas W. Page Jr., Gerald J. Popek, Dieter Rothmeier, Implementation of the Ficus replicated file system. In USENIX Summer Conference, 1990
• 50: Rivka Ladin , Barbara Liskov , Liuba Shrira , Sanjay Ghemawat, Providing high availability using lazy replication, ACM Transactions on Computer Systems (TOCS), v.10 n.4, p.360-391, Nov. 1992 [doi>10.1145/138873.138877]
• 51: R. H. Patterson , G. A. Gibson , E. Ginting , D. Stodolsky , J. Zelenka, Informed prefetching and caching, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.79-95, December 03-06, 1995, Copper Mountain, Colorado, United States
• 52: Renu Tewari , Michael Dahlin , Harrick Vin, Design Considerations for Distributed Caching on the Internet, University of Texas at Austin, Austin, TX, 1998
• 53: Swarup Acharya , Stanley Zdonik, Broadcast disks: dissemination-based data management for asymmetric communication environments, Brown University, Providence, RI, 1998
• 54: Stephanos Androutsellis-Theotokis , Diomidis Spinellis, A survey of peer-to-peer content distribution technologies, ACM Computing Surveys (CSUR), v.36 n.4, p.335-371, December 2004 [doi>10.1145/1041680.1041681]
• 55: Syncexpress: www.syncdata.it/syncexpress.html
• 56: Sitaram Iyer , Antony Rowstron , Peter Druschel, Squirrel: a decentralized peer-to-peer web cache, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571861]
• 57: Shudong Jin , Azer Bestavros, Temporal locality in Web request streams (poster session) (extended abstract): sources, characteristics, and caching implications, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.110-111, June 18-21, 2000, Santa Clara, California, United States
• 58: Savvas Gitzenis and Nicholas Bambos. Power Controlled Data Prefetching/Caching in Wireless Packet Networks. In IEEE Proceedings of INFOCOM 2002
• 59: Sumeet Sobti , Nitin Garg , Chi Zhang , Xiang Yu , Arvind Krishnamurthy , Randolph Y. Wang, PersonalRAID: Mobile Storage for Distributed and Disconnected Computers, Proceedings of the Conference on File and Storage Technologies, p.159-174, January 28-30, 2002
• 60: Thomas M. Kroeger , Darrell D. E. Long , Jeffrey C. Mogul, Exploring the bounds of web latency reduction from caching and prefetching, Proceedings of the USENIX Symposium on Internet Technologies and Systems on USENIX Symposium on Internet Technologies and Systems, p.2-2, December 08-11, 1997, Monterey, California
• 61: Thomas M. Kroeger , Darrell D. E. Long, The Case for Efficient File Access Pattern Modeling, Proceedings of the The Seventh Workshop on Hot Topics in Operating Systems, p.14, March 28-30, 1999
• 62: Thomas Kunz , Thomas Barry , James P. Black , Hugh M. Mahoney, WAP traffic: description and comparison to WWW traffic, Proceedings of the 3rd ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems, p.11-19, August 20-20, 2000, Boston, Massachusetts, United States [doi>10.1145/346855.346858]
• 63: Tom M. Kroeger , Darrell D. E. Long, Design and Implementation of a Predictive File Prefetching Algorithm, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.105-118, June 25-30, 2001
• 64: Todd C. Mowry , Angela K. Demke , Orran Krieger, Automatic compiler-inserted I/O prefetching for out-of-core applications, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.3-17, October 29-November 01, 1996, Seattle, Washington, United States
• 65: Tao Ye , H.-Arno Jacobsen , Randy Katz, Mobile awareness in a wide area wireless network of info-stations, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.109-120, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288264]
• 66: Venkata N. Padmanabhan , Lili Qiu, The content and access dynamics of a busy Web site: findings and implications, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.111-123, August 28-September 01, 2000, Stockholm, Sweden
• 67: Venkata N. Padmanabhan , Jeffrey C. Mogul, Using predictive prefetching to improve World Wide Web latency, ACM SIGCOMM Computer Communication Review, v.26 n.3, p.22-36, July 1996 [doi>10.1145/235160.235164]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Data sharing

General Terms:
Design