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

Abstract

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.