Optimal proactive caching in peer-to-peer network: analysis and application

ABSTRACT

As a promising new technology with the unique properties like high efficiency, scalability and fault tolerance, Peer-to-Peer (P2P) technology is used as the underlying network to build new Internet-scale applications. However, one of the well known issues in such an application (for example WWW) is that the distribution of data popularities is heavily tailed with a Zipf-like distribution. With consideration of the skewed popularity we adopt a proactive caching approach to handle the challenge, and focus on two key problems: where (i.e. the placement strategy: where to place the replicas) and how (i.e. the degree problem: how many replicas are assigned to one specific content)? For the where problem, we propose a novel approach which can be generally applied to structured P2P networks. Next, we solve two optimization objectives related to the how problem: MAX_PERF and MIN_COST. Our solution is called <B>PoPCache</B>, and we discover two interesting properties: (1) the number of replicas assigned to each content is proportional to its popularity; (2) the derived optimal solutions are related to the entropy of popularity. To our knowledge, none of the previous works has mentioned such results. Finally, we apply the results of PoPCache to propose a P2P base web caching, called as Web-PoPCache. By means of web cache trace driven simulation, our extensive evaluation results demonstrate the advantages of PoPCache and Web-PoPCache.

REFERENCES

• 1: In http://squid.nlanr.net.
• 2: In ftp://ircache.nlanr.net/Traces/DITL-2007-01-09.
• 3: In http://ita.ee.lbl.gov/html/contrib/BU-Web-Client.html.
• 4: Karl Aberer , Philippe Cudré-Mauroux , Anwitaman Datta , Zoran Despotovic , Manfred Hauswirth , Magdalena Punceva , Roman Schmidt, P-Grid: a self-organizing structured P2P system, ACM SIGMOD Record, v.32 n.3, September 2003 [doi>10.1145/945721.945729]
• 5: Serge Abiteboul , Angela Bonifati , Grégory Cobéna , Ioana Manolescu , Tova Milo, Dynamic XML documents with distribution and replication, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872821]
• 6: James Aspnes , Gauri Shah, Skip graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 7: Edith Cohen , Scott Shenker, Replication strategies in unstructured peer-to-peer networks, ACM SIGCOMM Computer Communication Review, v.32 n.4, October 2002
• 8: B. F. Cooper. An optimal overlay topology for routing peer-to-peer searches. In Middleware, 2005.
• 9: 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
• 10: Fred Douglis , Thomas Ball, Tracking and viewing changes on the web, Proceedings of the 1996 annual conference on USENIX Annual Technical Conference, p.14-14, January 22-26, 1996, San Diego, CA
• 11: Li Fan , Pei Cao , Jussara Almeida , Andrei Z. Broder, Summary cache: a scalable wide-area Web cache sharing protocol, ACM SIGCOMM Computer Communication Review, v.28 n.4, p.254-265, Oct. 1998
• 12: 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]
• 13: H. V. Jagadish , Beng Chin Ooi , Quang Hieu Vu, BATON: a balanced tree structure for peer-to-peer networks, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 14: David Karger , Alex Sherman , Andy Berkheimer , Bill Bogstad , Rizwan Dhanidina , Ken Iwamoto , Brian Kim , Luke Matkins , Yoav Yerushalmi, Web caching with consistent hashing, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1203-1213, May 17, 1999
• 15: P. Linga, I. Gupta, and K. Birman. Kache: Peer-to-peer web caching using kelips. In In submission, June 2004.
• 16: Qin Lv , Pei Cao , Edith Cohen , Kai Li , Scott Shenker, Search and replication in unstructured peer-to-peer networks, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 17: Gurmeet Singh Manku , Mayank Bawa , Prabhakar Raghavan, Symphony: distributed hashing in a small world, Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems, p.10-10, March 26-28, 2003, Seattle, WA
• 18: Venugopalan Ramasubramanian , Emin Gün Sirer, Beehive: O(1)lookup performance for power-law query distributions in peer-to-peer overlays, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.8-8, March 29-31, 2004, San Francisco, California
• 19: Venugopalan Ramasubramanian , Emin Gün Sirer, The design and implementation of a next generation name service for the internet, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 20: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 21: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 22: 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
• 23: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 24: Jia Wang, A survey of web caching schemes for the Internet, ACM SIGCOMM Computer Communication Review, v.29 n.5, October 1999 [doi>10.1145/505696.505701]
• 25: Allison Woodruff , Paul M. Aoki , Eric Brewer , Paul Gauthier, An investigation of documents from the World Wide Web, Proceedings of the fifth international World Wide Web conference on Computer networks and ISDN systems, p.963-980, May 1996, Paris, France
• 26: Praveen Yalagandula , Mike Dahlin, A scalable distributed information management system, ACM SIGCOMM Computer Communication Review, v.34 n.4, October 2004
• 27: V. R. Yee Jiun Song and E. G. Sirer. Optimal resource utilization in content distribution networks. In Cornell University, Computing and Information Science Technical Report TR2005-2004, Ithaca, New York, November 2005.
• 28: Ben Y. Zhao , John D. Kubiatowicz , Anthony D. Joseph, Tapestry: a fault-tolerant wide-area application infrastructure, ACM SIGCOMM Computer Communication Review, v.32 n.1, January 2002 [doi>10.1145/510726.510755]
• 29: M. Zhong and K. Shen. Popularity biased random walks for peer-to-peer search under the square root principle. In IPTPS, 2006.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Design, Performance

Keywords:
peer-to-peer, placement strategy, web caching