改良Kademlia在高度網路擾動下的搜尋成功率

Abstract

Kademlia是一種被廣泛使用的P2P分散式雜湊表技術，在高度網路擾動環境中仍存在資料搜尋失敗的問題。本文以模擬的方式對以Kademlia運作的P2P系統進行分析，整理出在Kademlia技術下資料搜尋失敗的原因，並提出改良方法以少量成本增長提升資料搜尋成功率。\n高度網路擾動會造成部分節點的路由表失效，同時使部份節點無法有效認識周遭節點。前者會導致儲存資料後資料難以被搜尋，或者搜尋資料時無法取得資料；後者會使資料儲存者與搜尋者找到的節點不一致，導致搜尋失敗。本文提出以紀錄長時間上線的節點，在路由表失效時向其連線以處理路由表失效的問題；及以向遠距離的節點詢問資料處理節點無法有效認識周遭節點的問題。實驗結果證實實施兩者後能使得資料搜尋成功率提升。\n相較於傳統上以超級節點支援的P2P網路，我們的方法能以較低的通訊成本達到相當的資料搜尋成功率。

Kademlia is a widely deployed P2P-Distributed Hash Table network, however there exists some search failure issue under high churn. This thesis analyzes the reasons for Kademlia search failure by simulating the Kademlia-based P2P system and proposed some methods to improve Kademlia search success rate with little extra cost.\nHigh churn causes Kademlia Routing Table to be invalid, and in such case, nodes would have insufficient acknowledge of surrounding nodes. Invalid Routing Tables not only make data hard to be found but also directly lead to search failure. Insufficient acknowledge of surrounding nodes would make the traversing nodes and data nodes different and cause search failure. To this end, we suggest that nodes can connect with long-stay nodes to handle the invalid Routing Table invalid problem, and nodes can ask the far nodes for information to avoid the problem for insufficient acknowledge of surrounding nodes. Simulation experiments confirm that the search success rate of Kademlia increases when the above two enhancements are implemented.\nFurthermore, we also compare the performance with traditional supernode supported P2P network. Simulation results also show that our method maintains the comparable search success rate but with less overhead.