高效率非集中式之KAD同儕網路負載平衡策略

Abstract

KAD 同儕網路已被廣泛地應用在檔案分享軟體中，但這些同儕網路仍就被不平衡的發佈負載且被詢問負載所困擾，造成少量的節點處理大量的索引。這些高負載的節點會成為網路的瓶頸。因此，在本論文中，我們提出一個以同餘定理為基礎的方法 (KAD-mod) 以平衡網路中各節點的負載，我們給予每個節點一個同餘編號，並且設定一個門檻 (RFT) 用以限制一個節點可以負擔的相同索引數。模擬結果顯示，我們的方法的確可以將索引分佈的更平均。此外，針對我們的模擬環境，RFT = 6000 是最佳的設定。我們利用基尼係數來評估相關的負載平衡方法，在基尼係數中0為最平衡情況，1為最不平衡情況。由模擬結果得知，KAD-mod可以提升搜尋命中率至98.24%，在發佈負載平衡方面，KAD-mod， KAD-7及KAD 在基尼係數的表現上分別為0.23，0.80，0.93。而詢問負載平衡方面，KAD-mod， KAD-7及KAD 在基尼係數的表現上分別為0.33，0.67，0.83。評估結果顯示本方法的發佈及詢問負載皆比KAD及KAD-7更平衡。但它會增加8%的額外流量及平均需要額外的0.5 hop才可找到發布目標節點。當有節點失效時，本方法可藉由增加搜尋命中率加強搜尋的強韌性。此外，本方法可以很容易地被延伸應用至其他以DHT為基礎的同儕網路。

Kademlia (KAD) peer-to-peer (P2P) networks have become more and more popular. However, they have an unbalanced publish load problem. It causes a few peers to store a large number of indexes and these peers will become hotspots. Once become a hotspot, the peer must handle a large number of requests that result in high load, and it become a network bottleneck. To conquer this problem, we propose a modulo based method (called KAD-mod) to balance load in the KAD network. We give each peer a new ID (called mod ID) using modular arithmetic. A request forwarding threshold (RFT) is used to help decide if an index should be redirected to the same mod ID of peers in another zones. This method allows the same mod ID peers to share load. We used Gini coefficient (G, 0 ≤ G ≤ 1, 0: fully balanced) as a load balancing index to evaluate representative load balancing methods. Simulation results show that the proposed KAD-mod has the search hit rate close to 100%. The G’s of KAD-mod, KAD-7, and KAD for publishing load are 0.23, 0.80, and 0.93, respedtively. As to G for request load, KAD-mod is 0.33, KAD-7 is 0.67, and KAD is 0.83. We can see that the proposed KAD-mod is much more load balancing than the other methods. However, KAD-mod has 8% extra traffic and the hop count per publish increases from 2.5 to 2.9. By enhancing the search hit rate, KAD-mod can improve the search resilience of KAD P2P networks with failed peers. Furthermore, the proposed KAD-mod method can be easily extended to other DHT-based P2P networks.