Peer-to-peer (P2P) overlay networks are widely employed in distributed systems. Furthermore, the number of hops required by a node for searching an object is the fundamental search cost of a P2P network. Hence, since placing replicas can efficiently reduce such a cost of the whole system, how to deploy replicas to reduce it as much as possible becomes a critical problem of P2P networks. In this study, the authors investigate this centre problem for the randomised P2P network ‘Symphony’. Particularly, the authors present a stochastic analysis on optimal replica placements, in terms of number of total hops, as well as proposing an optimal replica placement algorithm to perform a simulation study on this issue. Both the theoretical and experimental results show that locations of optimal replica placements in Symphony are not necessarily closest to the target node in the identifier space. Hence, based on the results, the authors evaluate one existing simple but experimentally efficient replica placement strategy, which exactly allocates replicas at nodes closest to the target node, to provide some guidelines on designing more efficient strategy applicable to the real-world Symphony.

References

1. 1)
  - 5. Ramasubramanian, V., Sirer, E.G.: ‘The design and implementation of a next generation name service for the Internet’. Proc. ACM SIGCOMM, August 2004, pp. 331–342.
2. 2)
  - 14. Oehmen, C., Nieplocha, J.: ‘ScalaBLAST: A scalable implementation of BLAST for high-performance data-intensive bioinformatics analysis’, IEEE Trans. Parallel Distrib. Syst., 2006, 17, (8), pp. 740–749 (doi: 10.1109/TPDS.2006.112).
3. 3)
  - 6. Gnutella, http://rfc-gnutella.sourceforge.net/index.html, 2012.
4. 4)
  - 27. Zink, M., Suh, K., Gu, Y., Kurose, J.: ‘Watch global cache local: YouTube network traces at a campus network – measurements and implications’. ACM/SPIE Conf. Multimedia Computing and Networking, 2008.
5. 5)
  - 29. Bertsekas, D.P.: ‘Nonlinear programming’ (Athena Scientific, Cambridge, MA, 1999, 2nd edn.).
6. 6)
  - 20. Mondal, A., Lifu, Y., Kitsuregawa, M.: ‘On improving the performance dependability of unstructured P2P systems via replication’, in Takizawa, M., Traunmüller, R. (Eds.): ‘Data base and expert systems applications’ (Springer-Verlag, Berlin, Germany, 2004), vol. 3180, pp. 601–610.
7. 7)
  - 18. Thain, D., Bent, J., Arpaci-Dusseau, A.C., Arpaci-Dusseau, R.H., Livny, M.: ‘Pipeline and batch sharing in grid workloads’. Proc. 12th IEEE Int'l ACM Symp. High-Performance Parallel and Distributed Computing, 2003, pp. 152–161.
8. 8)
  - 3. Manku, G.S., Bawa, M., Raghavan, P.: ‘Symphony: distributed hashing in a small world’. Proc. USENIX Symp. Internet Technologies and Systems, 2003, pp. 127–140.
9. 9)
  - 1. Harvesf, C., Blough, D.M.: ‘Replica placement for route diversity in tree-based routing distributed hash tables’, IEEE Trans. Dependable Secur. Comput., 2011, 8, (3), pp. 419–433 (doi: 10.1109/TDSC.2009.49).
10. 10)
  - 12. Rhea, S., Godfrey, B., Karp, B., et al: ‘OpenDHT: a public DHT service and its uses’, SIGCOMM Comput. Commun. Rev., 2005, 35, pp. 73–84 (doi: 10.1145/1090191.1080102).
11. 11)
  - 14. Stoica, I., Morris, R., Karger, D., Kaashoek, F., Balakrishnan, H.: ‘Chord: a scalable peer-to-peer lookup service for internet applications’, IEEE/ACM Trans. Netw., 2003, 11, (1), pp. 17–32 (doi: 10.1109/TNET.2002.808407).
12. 12)
  - 7. Freenet, http://freenetproject.org/, 2012.
13. 13)
  - 28. Knuth, D.E.: ‘The art of computer programming vol 4, Fascicle 1: bitwise tricks & techniques; binary decision diagrams’ ‘(Addison-Wesley Professional, 2009).
14. 14)
  - 10. Rowstron, A., Druschel, P.: ‘Pastry: scalable, decentralized object location, and routing for large-scale peer-to-peer systems’. Proc. the 18th IFIP/ACM Int'l Conf. Distributed Systems Platforms (Middleware 2001), November 2001, pp. 329–350.
15. 15)
  - 26. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: ‘Introduction to algorithms’ (MIT Press and McGraw-Hill, 2001, 2nd edn.).
16. 16)
  - 23. Ghodsi, A., Alima, L.O., Haridi, S.: ‘Symmetric replication for structured peer-to-peer systems’. Proc. Int. Workshops on Databases, Information Systems, and Peer-to-Peer Computing, 2005, pp. 74–85.
17. 17)
  - 15. Huang, C.-M., Yang, C.-C., Tseng, C.-Y.: ‘Peer-to-peer-like telematics service discovery using the distributed-region-server-based approach’, IET Netw., 2012, 1, (3), pp. 136–145 (doi: 10.1049/iet-net.2012.0051).
18. 18)
  - 2. Rao, W., Chen, L., Fu, A.W.-C., Wang, G.: ‘Optimal resource placement in structured peer-to-peer networks’, IEEE Trans. Parallel Distrib. Syst., 2010, 21, (7), pp. 1011–1026 (doi: 10.1109/TPDS.2009.136).
19. 19)
  - 17. Cheng, X., Liu, J.: ‘NetTube: exploring social networks for peer-to-peer short video sharing’. Proc. INFOCOM 2009, 2009, pp. 1152–1160.
20. 20)
  - 24. Saroiu, S., Gummadi, K., Gribble, S.: ‘A measurement study of peer-to-peer file sharing systems’. Proc. Multimedia Computing and Networking Conf. (MMCN), January 2002, pp. 156–170.
21. 21)
  - 13. Chen, J.-B.: ‘Fuzzy based approach for P2P file sharing detection’, J. Internet Technol., 2011, 12, (6), pp. 921–929.
22. 22)
  - 21. Rowstron, A.I.T., Druschel, P.: ‘Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility’. Proc. ACM Symp. Operating Systems Principles (SOSP), 2001, pp. 188–201.
23. 23)
  - 19. Cohen, E., Shenker, S.: ‘Replication strategies in unstructured peer-to-peer networks’, SIGCOMM Comput. Commun. Rev., 2002, 32, (4), pp. 177–190 (doi: 10.1145/964725.633043).
24. 24)
  - 25. Chou, J.C.-Y., Huang, T.-Y., Huang, K.-L., Chen, T.-Y.: ‘SCALLOP: A scalable and load-balanced peer-to-peer lookup protocol’, IEEE Trans. Parallel Distrib. Syst., 2006, 17, (5), pp. 419–433 (doi: 10.1109/TPDS.2006.66).
25. 25)
  - 11. Ratnasamy, S., Francis, P., Handley, M., Karp, R.M., Shenker, S.: ‘A scalable content-addressable network’. Proc. ACM SIGCOMM, 2001, pp. 161–172.
26. 26)
  - 22. Ramasubramanian, V., Sirer, E.G.: ‘Beehive: exploiting power law query distributions for O(1) lookup performance in peer to peer overlays’. Int. Symp. Networked Systems Design and Implementation, San Francisco CA, March 2004, pp. 331–342.
27. 27)
  - 4. Dabek, F., Kaashoek, M.F., Karger, D.R., Morris, R., Stoica, I.: ‘Wide area cooperative storage with CFS’. Proc. ACM Symp. Operating Systems Principles (SOSP), 2001, pp. 202–215.
28. 28)
  - 9. Zhao, B.Y., Huang, L., Stribling, J., Rhea, S.C., Joseph, A.D., Kubiatowicz, J.D.: ‘Tapestry: a resilient global-scale overlay for service deployment’, IEEE J. Sel. Areas Commun., 2004, 22, (1), pp. 41–53 (doi: 10.1109/JSAC.2003.818784).
29. 29)
  - 16. Yang, C.-T., Leu, F.-Y., Yang, M.-F.: ‘A peer-to-peer video file resource sharing system for mobile devices’, J. Internet Technol., 2010, 11, (1), pp. 69–78.

On optimally reducing search costs for placing replicas in Symphony P2P networks

References

Related content