標題: 基於強韌搜尋之KAD同儕網路負載平衡方法
A Load Balancing Scheme for Resilient Search in KAD Peer-to-Peer Networks
作者: 吳岱庭
Wu, Tai-Ting
王國禎
Wang, Kuo-Chen
網路工程研究所
關鍵字: 負載平衡;KAD;同儕網路;強韌搜尋;Load balancing;KAD;peer to peer network;resilient search
公開日期: 2008
摘要: KAD 同儕網路已被廣泛地應用在檔案分享軟體中,但這些同儕網路仍就被不平衡的發佈負載所困擾,造成少量的節點處理大量的索引。這些高負載的節點會成為網路的瓶頸。因此,在本論文中,我們提出一個多次雜錯方法 (KAD-N)以平衡網路中各節點的負載,其中 N 是一個由成本效益係數所決定的參數,它代表雜錯的最大次數。一個關鍵字經過 r 次的雜錯後,可以產生出一個發佈用的金鑰,而 r 是一個介於 1 與 N 之間的隨機數。模擬結果顯示,我們的方法的確可以將索引分佈的更平均。此外,針對我們的模擬環境,N = 7 (KAD-7)是最佳的設定。我們利用標準差來評估所提出的負載平衡方法。由模擬結果得知,KAD-7可以使搜尋命中率接近100%,其標準差也比KAD (即KAD-1)少了44%。這表示本方法的發佈負載比KAD更平衡,但它會增加 7% 的額外流量。當有節點失效時,本方法可藉由增加搜尋命中率加強搜尋的強韌性。此外,本方法可很容易地被延伸至其他以DHT為基礎的同儕網路。
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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT079656532
http://hdl.handle.net/11536/43490
Appears in Collections:Thesis


Files in This Item:

  1. 653201.pdf