Study on Load Management for Hierarchical Peer-to-Peer File Search

階層型ピア・ツー・ピアファイル検索のための負荷管理の研究

曹 琪

In a Peer-to-Peer (P2P) system, multiple interconnected peers or nodes contribute a portion of their resources (e.g., files, disk storage, network bandwidth) in order to inexpensively handle tasks that would normally require powerful servers. Since the emergency of P2P file sharing, load balancing has been considered as a primary concern, as well as other issues such as autonomy, fault tolerance and security. In a process of file search, a heavily loaded peer may incur a long latency or failure in query forwarding or responding. If there are many such peers in a system, it may cause link congestion or path congestion, and consequently affect the performance of overall system. To avoid such situation, some of general techniques used in Web systems such as caching and paging are adopted into P2P systems. However, it is highly insufficient for load balancing since peers often exhibit high heterogeneity and dynamicity in P2P systems. To overcome such a difficulty, the use of super-peers is currently being the most promising approach in optimizing allocation of system load to peers, i.e., it allocates more system load to high capacity and stable super-peers by assigning task of index maintenance and retrieval to them.

In this thesis, we focused on two kinds of super-peer based hierarchical architectures of P2P systems, which are distinguished by the organization of super-peers. In each of them, we discussed system load allocation, and proposed novel load balancing algorithms for alleviating load imbalance of super-peers, aiming to decrease average and variation of query response time during index retrieval process.

More concretely, in this thesis, our contribution to load management solutions for hierarchical P2P file search are the following:

• In Qin’s hierarchical architecture, indices of files held by the user peers in the bottom layer are stored at the super-peers in the middle layer, and the correlation of those two bottom layers is controlled by the central server(s) in the top layer using the notion of tags. In Qin’s system, a heavily loaded super-peer can move excessive load to a lightly loaded super-peer by using the notion of task migration. However, such a task migration approach is not sufficient to balance the load of super-peers if the size of tasks is highly imbalanced. To overcome such an issue, in this thesis, we propose two task migration schemes for this architecture, aiming to ensure an even load distribution over the super-peers. The first scheme controls the load of each task in order to decrease the total cost of task migration. The second scheme directly balances the load over tasks by reordering the priority of tags used in the query forwarding step. The effectiveness of the proposed schemes are evaluated by simulation. The result of simulations indicates that all the schemes can work in coordinate, in alleviating the bottleneck situation of super-peers.

• In DHT-based super-peer architecture, indices of files held by the user peers in the lower layer are stored at the DHT connected super-peers in the upper layer. In DHT-based super-peer systems, the skewness of user’s preference regarding keywords contained in multi-keyword query causes query load imbalance of super-peers that combines both routing and response load. Although index replication has a great potential for alleviating this problem, existing schemes did not explicitly address it or incurred high cost. To overcome such an issue, in this thesis, we propose 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 in order to decrease routing load in the super-peer layer, and distribute response load of an index among super-peers that stored the replica. The second scheme is a proactive pointer replication that places location information of an index, 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 super-peers. The result of simulations indicates that the proposed schemes can help alleviating the query load imbalance of super-peers. Moreover, by comparison it was found that our schemes are more cost-effective on placing replicas than other approaches.

電気工学 [ 540 ]

英語

Q. Cao and S. Fujita; Load Balancing Schemes for a Hierarchical Peer-to-Peer File Search System; International Journal of Grid and Utility Computing (IJGUC), vol. 2, no. 2, pp. 164-171, 2011. ～を参照している

Q. Cao and S. Fujita; Cost-effective Replication Schemes for Query Load Balancing in DHT based Peer-to-Peer File Search; Journal of Information Processing Systems (JIPS). (Accepted.) ～を参照している

Q. Cao and S. Fujita; Load Balancing Schemes for a Hierarchical Peer-to-Peer File Search System; In Proceedings the Fifth International Conference on P2P, Parallel, Grid, Cloud and Internet Computing (3PGCIC-2010), pp. 63-70, November, 2010. ～を参照している

[DOI] http://doi.org/10.1504/IJGUC.2011.040609 ～を参照している

[DOI] http://doi.org/10.3745/JIPS.03.0020 ～を参照している

[DOI] http://doi.org/10.1109/3PGCIC.2010.15 ～を参照している

広島大学