Cost-Effective Replication Schemes for Query Load Balancing in DHT-Based Peer-to-Peer File Searches
2
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
In past few years, distributed hash table (DHT)-based P2P systems have been proven to be a promising way to manage decentralized index information and provide efficient lookup services. However, the skewness of users' preferences regarding keywords contained in a multi-keyword query causes a query load imbalance that combines both routing and response load. This imbalance means long file retrieval latency that negatively influences the overall system performance. Although index replication has a great potential for alleviating this problem, existing schemes did not explicitly address it or incurred high cost. To overcome this issue, we propose, in this paper, an integrated solution that consists of three replication schemes to alleviate query load imbalance while minimizing the cost. The first scheme is an active index replication that is used in order to decrease routing load in the system and to distribute response load of an index among peers that store replicas of the index. The second scheme is a proactive pointer replication that places location information of each index to a predetermined number of peers for reducing maintenance cost between the index and its replicas. The third scheme is a passive index replication that guarantees the maximum query load of peers. The result of simulations indicates that the proposed schemes can help alleviate the query load imbalance of peers. Moreover, it was found by comparison that our schemes are more cost-effective on placing replicas than PCache and EAD.
Abstract
In past few years, distributed hash table (DHT)-based P2P systems have been proven to be a promising way to manage decentralized index information and provide efficient lookup services. However, the skewness of users' preferences regarding keywords contained in a multi-keyword query causes a query load imbalance that combines both routing and response load. This imbalance means long file retrieval latency that negatively influences the overall system performance. Although index replication has a great potential for alleviating this problem, existing schemes did not explicitly address it or incurred high cost. To overcome this issue, we propose, in this paper, an integrated solution that consists of three replication schemes to alleviate query load imbalance while minimizing the cost. The first scheme is an active index replication that is used in order to decrease routing load in the system and to distribute response load of an index among peers that store replicas of the index. The second scheme is a proactive pointer replication that places location information of each index to a predetermined number of peers for reducing maintenance cost between the index and its replicas. The third scheme is a passive index replication that guarantees the maximum query load of peers. The result of simulations indicates that the proposed schemes can help alleviate the query load imbalance of peers. Moreover, it was found by comparison that our schemes are more cost-effective on placing replicas than PCache and EAD.
참고문헌 (21)
- I. Stoica, "Chord: a scalable peer -to-peer lookup service for Internet applicatios", Proceedings of the 2001 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM2001), pp.149~160 (2001)
- S. Ratnasamy, "A scalable content-addressable network", Proceedings of the 2001 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM2001), pp.161~172 (2001)
- A. Rowstron, "Pastry: scalable, decentralized object location, and routing for large-scale peer-to systems", Proceedings of the IFIP, 2001, 329~350
- Tapestry: an infrastructure for fault-tolerant widearea location and routing, "B. Y. Zhao", University of California at Berkeley, ~ (2001)
- M. E. Newman, "Power laws, Pareto distributions and Zipf's law", Contemporary Physics, 46(5), pp.323~351 (2005)
- V. Ramasubramanian, "Beehive: O(1) lookup performance for power-law query distributions in peer-to-peer overlays", Proceedings of the 1st Symposium on Networked Systems Design and Implementation (NSDI2004), pp.8~8 (2004)
- W. Rao, "Optimal resource placement in structured peer-to-peer networks", IEEE Transactions on Parallel and Distributed Systems, 21(7), pp.1011~1026 (2010)
- H. Shen, "An efficient and adaptive decentralized file replication algorithm in P2P file sharing systems", IEEE Transactions on Parallel and Distributed Systems, 21(6), pp.827~840 (2010)
- J. Zhow, "Clustered K-center : effective replica placement in peer-to-peer systems", Proceedings of the Global Communications Conference (GLOBECOM2007), pp.2008~2013 (2007)
- A. Ghodsi, "Databases, Information Systems, and Peer-to-peer Computing", pp.74~85 (2005), Springer
- F. Dabek, "Wide-area cooperative storage with CFS", Proceedings of the 18th ACM Symposium on Operating System Principles (SOSP2001), pp.202~215 (2001)
- B. Godfrey, "Load balancing in dynamic structured P2P systems", Proceedings of 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2004), pp.2253~2262 (2004)
- A. Rao, "Load balancing in structured P2P systems", Proceedings of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS2003), pp.68~79 (2003)
- S. Rieche, "A thermal-dissipation-based approach for balancing data load in distributed hash tables", Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks (LCN2004), pp.15~23 (2004)
- D. R. Karger, "Simple efficient load balancing algorithms for peer-to-peer systems", Proceedings of the 16th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA2004), pp.36~43 (2004)
- J. Byers, "Simple load balancing for DHTs", Proceedings of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS2003), pp.80~87 (2003)
- S. Bianchi, "Adaptive load balancing for DHT lookups", Proceedings of 15th International Conference on Computer Communications and Networks (ICCCN200), pp.411~418 (2006)
- H. Shen, "Elastic routing table with provable performance for congestion control in DHT networks", IEEE Transactions on Parallel and Distributed Systems, 21(2), pp.242~256 (2010)
- C. Harvesf, "Replica placement for route diversity in tree-based routing distributed hash tables", IEEE Transactions on Dependable and Secure Computing, 8(3), pp.419~433 (2011)
- "Keyword and search engines statistics"[URL]
- K. Shudo, "Overlay Weaver : an overlay construction toolkit", Computer Communications, 31(2), pp.402~412 (2008)