極不平衡的Kademlia路由表

在Kademlia的紙，節末段2.4的狀態，爲了妥善處理高度不平衡的樹木......極不平衡的Kademlia路由表

Kademlia網絡節點保持在大小的子樹的所有有效接觸的即使這需要拆分節點自己的 ID不駐留的桶。

然而，本文的前面部分似乎指出，如果一個k桶已經有k個要素，即任何進一步添加到該K桶需要除去stalest節點（第一偵測它，以查看是否它的存活）或以其他方式緩存該添加，直到在該k桶中可用的時隙爲止。

該論文似乎與這兩點相矛盾。

在什麼情況下應該拆分K桶，爲什麼？在路由表中保留「所有有效的聯繫人」似乎不太實際，因爲路由表會非常快地變得非常大。這個例子討論了一個樹，它有許多以001開始的節點和一個以000開頭的節點。以000開始的節點必須不斷地將其k-bucket拆分爲001以保存以001開頭的每個有效節點？在160位地址空間中，最終不會在000的路由表中存儲2^157個節點？

在所列出的塊中的措辭也很混亂......

「的子樹」 - 在路由表中的哪個子樹？

「至少有k個節點的大小」 - 我們使用什麼度量來確定子樹的大小？這種情況下的節點是指kademlia節點還是k桶或其他東西？

來源

2015-08-20 offbynull

但是，本文的前一部分似乎指出，如果一個k桶已經有k個元素，則該k桶中的任何進一步添加都需要移除最舊的節點（先ping它，看看是否它的存活）或以其他方式緩存該添加，直到在該k桶中可用的時隙爲止。

無論何時存在要插入的節點聯繫人但存儲桶不符合拆分條件，這就是如何維護存儲桶。

在什麼情況下應該拆分K桶，爲什麼？

作爲第一近似：拆分每當一個新的節點不能插入和桶的ID空間覆蓋的節點ID的桶。

這對於保持對您的鄰居的全面瞭解，同時對遠程密鑰空間部分只有模糊的認識是必要的。即爲地方。

要覆蓋不平衡樹的情況 - 如果節點ID不是（僞）隨機或者至少在葉桶中由於隨機分配時的統計錯誤而可能發生 - 該方法必須如下放寬：

當

試圖插入一個新的聯繫人ç在路由表
ç所屬到其中的桶滿
Ç比你的路由表中的ķ^第 -closest節點，其中ķ是桶大小

然後分裂剷鬥接近你節點ID。

在實踐中，這需要進一步修改，以便輕鬆分割用於響應，而未經請求的請求應該只使用嚴格分割，否則當啓動期間鬆散分割發生時，可能會得到一些奇怪的扭曲路由表。表尚未填充。

來源

2015-08-24 16:42:39 the8472

謝謝你的回答。過去一週我一直在努力理解這一點。你在這裏概述了什麼在原始文件中陳述了什麼？ – offbynull

疑難問題。我想說這是一種實施方法，相當於論文中各個段落的意圖。幾個月前，其他人在IRC上實際上提出了這個部分，我必須考慮相當長的一段時間，直到我真正瞭解它。我以前對Kademlia有過不正確的推理，所以我不願意爲我的解釋聲明正確性。也就是說，真實世界的實現往往不夠精確（只實現第一個近似），而且只要ID是均勻分佈的，似乎仍然有效。這隻會讓他們更喧鬧。 – the8472

我也在原稿紙上掙扎。這似乎與自己相矛盾。在一節中，它講述了160個基於距離的k個桶，另一個節段是基於密鑰的k個桶的二進制樹，其大小是動態的。網絡上有沒有什麼東西可以把那件事翻譯成簡單的英文？ – Sentinel

極不平衡的Kademlia路由表

回答

相關問題