Kei Ohnishi
ABSTRACT
The present paper introduces a replication method that is meant to balance the storage load of peers in unstructured peer-to-peer (P2P) networks for file sharing and to provide good search performance. According to the random walk theory on an arbitrary network, the frequency of arrival of a random walker to a peer is proportional to the degree of the peers. Therefore, to limit the increase in the number of hops required to find a requested file, it is better to make as many files as possible in peers of high degree when using random-walk-based query forwarding methods. However, this causes a load bias to peers of high degree. That is, there is a trade-off between storage load balancing and search performance. The replication method presented herein replicates a requested file in a peer of low load adjacent to a peer of interest on the present search path by using dynamically varying values that represent the state of the load of peers. Therefore, it is expected that local storage load balancing will be achieved. Furthermore, since the proposed method causes peers adjacent to peers of high degree to hold several files, it is also expected that good search performance will be obtained. In addition, a replication method that makes a replica of a requested file in a peer on the present search path with probability inversely proportional to the degree of the peer is prepared as a method for comparison. The probability is, in contrast to the proposed method, statically determined prior to the start of the search according to the theory to ensure good load balancing. The experimental results show that both the proposed method and the method for comparison achieve global load balancing, although they have totally different strategies in terms of storage load balancing. It is, however, shown that only the proposed method does not require appropriate adjustment of parameter values to a given network topology prior to the start of the search in order to achieve good search performance. This is a significant advantage over the method for comparison.
- E. K. Lua, J. Crowcroft, M. Pias, R. Sharma, and S. Lim, "A survey and comparison of peer-to-peer overlay network schemes," IEEE Communications Surveys & Tutorials, Vol. 7, no. 2, pp. 72--93, 2005.]] Google Scholar
Digital Library
- H. Yamamoto, D. Maruta, and Y. Oie, "Replication method for load balancing on distributed storages in P2P networks," IEICE Transactions on Information and Systems - Special Section on New Technologies and their Applications of the Internet III, January 2006.]] Google ScholarDigital Library
- R. Motwani and P. Raghavan, Randomized Algorithms. Cambridge University Press, 1995.]] Google ScholarDigital Library
- E. Cohen and S. Shenker, "Replication strategies in unstructured peer-to-peer networks," in Proceedings of the ACM SIGCOMM 2002, 2002.]] Google ScholarDigital Library
- Q. Lv, P. Cao, E. Cohen, and S. Li, K. Shenker, "Search and replication in unstructured peer-to-peer networks," in Proceedings of the 16th international conference on Supercomputing, 2002, pp. 84--95.]] Google ScholarDigital Library
- A. Rao, K. Lakshminarayanan, S. Surana, R. Karp, and I. Stoica, "Load balancing in structured P2P systems," in Proceedings of 2nd International Workshop on Peer-to-Peer Systems (IPTPS '03), 2003.]]Google Scholar
- D. R. Karger and M. Ruhl, "Simple efficient load balancing algorithms for peer-to-peer systems," in Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, 2004.]] Google ScholarDigital Library
- I. Clarke, O. Snadberg, B. Wiley, and T. W. Hong, "Freenet: A distributed anonymous information storage and retrieval system," in Proceedings of Workshop on Design Issue in Anonymity and Unobservability, 2000.]]Google Scholar
- A. Rowstron and P. Druschel, "Pastry: Scalable decentralized object location and routing for large-scale peer-to-peer systems," in Proceedings of IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), 2001, pp. 329--350.]] Google ScholarDigital Library
- S. Ata, Y. Gotoh, and M. Murata, "Replication strategies in peer-to-peer services over power-law overlay networks," in Proceedings of The 7th Asia-Pacific Network Operations and Management Symposium (APNOMS 2003), 2003.]]Google Scholar
- G. Cybenko, "Dynamic load balancing for distributed memory multiprocessors," Parallel and Distributed Computing, Vol. 7, no. 2, pp. 279--301, 1989.]] Google ScholarDigital Library
- J. Boillat, "Load balancing and poisson equation in a graph," Concurrency Practice and Experience, Vol. 2, no. 4, pp. 289--313, 1990.]] Google ScholarDigital Library
- A. Corradi, L. Leonardi, and F. Zambonelli, "Diffusive load balancing policies for dynamic applications," IEEE Concurrency, Vol. 7, no. 1, 1999.]] Google ScholarDigital Library
- T. Bu and D. Towsley, "On distinguishing between internet power law topology generators," in Proceedings of IEEE Infocom 2002, 2003, pp. 638--647.]]Google Scholar
- A.-L. Barabasi and R. Albert, "Emergence of scaling in random networks," SCIENCE, Vol. 286, pp. 509--512, 1999.]]Google ScholarCross Ref
- R. Albert and A.-L. Barabasi, "Topology of evolving networks: Local events and universality," Physical Review Letters, pp. 5234--5237, 2000.]]Google ScholarCross Ref
- L. A. Adamic, R. M. Lukose, A. R. Puniyani, and B. A. Huberman, "Search in power-law networks," Physical Review E 64, 046135, 2001.]]Google ScholarCross Ref
- M. Ripeanu, A. Iamnitchi, and I. Foster, "Mapping the gnutella network," IEEE Internet Computing, Vol. 6, no. 1, pp. 50--57, 2002.]] Google ScholarDigital Library
Index Terms
- Storage load balancing via local interactions among peers in unstructured P2P networks
Recommendations
Trustworthiness of Peers in P2P Overlay Networks
NBIS '12: Proceedings of the 2012 15th International Conference on Network-Based Information SystemsIn peer-to-peer (P2P) overlay networks, a group of multiple peers have to cooperate with each other. P2P systems are in nature scalable distributed systems, where there is no centralized coordinator. It is difficult for each peer to communicate with ...
A novel load balancing mechanism for P2P networking
GridNets '07: Proceedings of the first international conference on Networks for grid applicationsPeer to Peer (P2P) networking is a potential disruptive technology that can be used for the development of scalable, fully decentralized distributed applications. However, to realize its potential, P2P technology should address the needs of a variety of ...
Simple dynamic load balancing mechanism for structured P2P network and its evaluation
Many proposals have been advanced for structured Peer-to-peer (P2P) networks, but it is difficult for existing structured P2P networks to achieve dynamic load balancing sufficiently. In this paper, we propose a new structured P2P network called Well-...
Comments