基於強韌搜尋之KAD同儕網路負載平衡方法

A Load Balancing Scheme for Resilient Search in KAD Peer-to-Peer Networks

吳岱庭(Tai-Ting Wu)

指導教授 ： 王國禎

國立交通大學/資訊學院/網路工程研究所/碩士(2009年)

https://doi.org/10.6842/NCTU.2009.00534

摘要

KAD 同儕網路已被廣泛地應用在檔案分享軟體中，但這些同儕網路仍就被不平衡的發佈負載所困擾，造成少量的節點處理大量的索引。這些高負載的節點會成為網路的瓶頸。因此，在本論文中，我們提出一個多次雜錯方法 (KAD-N)以平衡網路中各節點的負載，其中 N 是一個由成本效益係數所決定的參數，它代表雜錯的最大次數。一個關鍵字經過 r 次的雜錯後，可以產生出一個發佈用的金鑰，而 r 是一個介於 1 與 N 之間的隨機數。模擬結果顯示，我們的方法的確可以將索引分佈的更平均。此外，針對我們的模擬環境，N = 7 (KAD-7)是最佳的設定。我們利用標準差來評估所提出的負載平衡方法。由模擬結果得知，KAD-7可以使搜尋命中率接近100%，其標準差也比KAD (即KAD-1)少了44%。這表示本方法的發佈負載比KAD更平衡，但它會增加 7% 的額外流量。當有節點失效時，本方法可藉由增加搜尋命中率加強搜尋的強韌性。此外，本方法可很容易地被延伸至其他以DHT為基礎的同儕網路。

關鍵字

負載平衡 ； KAD ； 同儕網路 ； 強韌搜尋

並列摘要

Kademlia (KAD) peer-to-peer (P2P) networks have been widely used in file sharing applications. However, these P2P networks suffer from the unbalanced publishing load problem. It causes a few peers handling large numbers of indexes. Those peers with high loads may become the bottlenecks of the network. Therefore, we propose a multiple hash method (called KAD-N) to balance peer loads in the KAD network. Note that N is the maximum hash times, determining by a cost-effectiveness factor. This method hashes the keyword of an object r times to produce a key for publishing objects, where r is a random number and 1 ≤ r ≤ N. Simulation results show that the distribution of indexes is more balanced using the proposed KAD-N method. We found out that N = 7 (KAD-7) is the optimal setting in our simulation environment. We used a standard deviation to evaluate the proposed load balancing method. Simulation results show that KAD-7 has the search hit rate close to 100% and the standard deviation is 44% less than that of the KAD (i.e., KAD-1), which means the proposed method is more load balanced than the KAD. However, KAD-7 has 7% extra traffic overhead. By increasing the search hit rate, KAD-N improves the search resilience of KAD networks with failed peers. Furthermore, the proposed KAD-N method can be easily extended to other DHT-based P2P networks.

並列關鍵字

Load balancing ； KAD ； peer to peer network ； resilient search

參考文獻

[1] D. Kundur, Z. Liu, M. Merabti, and H. Yu, “Advances in peer-to-peer con tent search,” in Proceedings of the IEEE International Conference on Multimedia and Expo, pp. 404-407, July 2007.

[2] Y.J. Joung, L.W. Yang, and C.T. Fang, "Keyword search in DHT-based peer-to-peer networks," IEEE Journal on Selected Areas in Communications, vol. 25, pp. 46-61, January 2007.

[3] P. Maymounkov and D. Mazieres, “Kademlia: A peer-to-peer informatiion system based on the XOR metric”, in Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS), pp. 53-65, March 2002.

[6] Rowstron and P. Druschel, “Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems,” in Proceedings of the 2001 IFIP/ACM International Conference on Distributed Systems Platforms, vol. 2218, pp. 329-350, November 2001.

[8] “eMula Project,” [Online]. Available: http://www.emule.com/.