2769


[Kademliaの論文](http://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-
lncs.pdf)を読んでいて、`k-bucket`の説明に関してよく分からない箇所がありました。

2.2 の **Node state** では、

> For each 0≤i<160, every node keeps a list of < IP address, UDP port, NodeID
> > triples for nodes of distance between 2i and 2i+1 from itself. We call
> these lists k-buckets.

各ノードに160個のk-bucketがあり、ノードとのIDの距離によってルーティング情報が各k-bucketに割り当てられていると読めます。

しかし、後の2.4 **Routing table** のセクションでは、

> Initially, a node _u_ ’s routing tree has a single node — one k-bucket
> covering entire ID space. When u learns of a new contact, it attempts to
> insert the contact in the appropriate k-bucket. If that bucket is not full,
> the new contact is simply inserted. Otherwise, if the k-bucket’s range
> includes _u_ ’s own node ID, then the bucket is split into two new buckets,
> the old contents divided between the two, and the insertion attempt
> repeated.

初期状態では各ノードに1つのk-bucketしかなく、距離ではなくIDそのものを基準として割り当てを行うことになっています。

このように、k-bucketに関する説明が2箇所で異なっている理由が読み取れず混乱しているのですが、この２つのk-
bucketはDHT上で別の役割をしているということなのでしょうか。それとも単なるテーブルの実装方法の違いということなのでしょうか。


CC BY-SA 3.0
2014-12-27T11:11:49.560
2693
2015-01-01T08:28:22.367
2015-01-01T08:28:22.367
3639
3639
question
network
Kademlia DHTのk-bucketについて


論文を今読んだだけの理解レベルですが:

2.4 Routing Table は、k-bucketを動的に増やす実装の一例である、と考えればよいと思います。

[Goによる実装例を解説した記事](http://blog.notdot.net/2009/11/Implementing-a-DHT-in-Go-
part-1)では、初めから全てのk-bucketを持っておくという実装になっています
(`Update`関数)。そして、ノードを探索する時点で、そのノードが入っているはずのk-bucketから徐々に近傍のk-
bucketに探索対象範囲を広げるということをしています (`FindClosest`関数)。

> 2.2 の **Node state** : 各ノードに160個のk-bucketがあり、ノードとのIDの距離によってルーティング情報が各k-
> bucketに割り当てられていると読めます。

その通りだと思います。これは、k-bucketの概念を説明するため、仮にルーティング情報が全充填された場合の状態を説明したものと思います。

出だしの一文で「ノード探索用の通信をルーティングするため、各ノードに既知のノード情報を保存する」("Kademlia nodes store contact
information about each other to route query messages.") とあるので、2.2
の説明内容はルーティングに使うものであると読めます。つまり 2.4 Routing Tableと同じ用途のものであると考えられます。

> 2.4 **Routing Table** : 初期状態では各ノードに1つのk-bucketしかなく、

ここでは、あるノードが初期状態からルーティングテーブルを段々埋めていく手順を説明しています。初期状態では、既知のノードは自分自身しかないので、初めはk-
bucketを1つだけ持っておけば十分、という実装です。

[code]

    初期状態:                        自分
    |--------------------------------o| <- 全ノードの空間 (右にいくほど近い)
              仮k-bucket [2^0-2^160)
    
    とても遠いノードを追加:
    |-------o--------|---------------o|
     k-bucket(i=159)   仮k-bucket [2^0-2^159)
    
[/code]

初期状態のk-bucketを「仮」としたのは私の個人的解釈で、論文ではそう書かれてはいません。2.2 節で「各k-bucketは距離 2i から 2i+1
の範囲を担当する」としているのとダイレクトに矛盾するので、説明不足なのだと思います。

> 距離ではなくIDそのものを基準として割り当てを行うことになっています。

Kademliaでは、ノード間の距離がIDによって決まるので、「ID空間 (ID
space)」を距離空間と同じ意味で使っているように思います。この節の冒頭の段落で:

> Each _k_ -bucket contains nodes with some common prefix of their IDs.  
>  各k-bucketに含まれるノードは、IDの前半部分が一定の長さで共通したものになる。

とあるように、ノードのIDを見れば、どのk-bucketに入れればいいかが決まります。というのも、

  * IDの高次ビットが共通している場合、
  * → その共通部分は XOR の結果がゼロになる
  * → そのノードとの距離は一定の範囲内に限定される: 最大値は共通部分から下のビットが全て 1 になる場合、最小値は共通部分の次のビット以外が全て 0 になる場合
  * → 割り当てるべき k-bucket が決まる (各k-bucketが担当する距離の範囲は 2i ~ 2i+1、と2.2で定義されている)

からです。ノード自身のIDとの比較なので、どのIDがどのk-bucketに入るかはノードによって違うということにはなります。

[code]

    self     0 1 0 0 ..(160個).. 1 0 1 0
    other    0 1 1 1 ..(160個).. 0 0 0 0
    -------------------------------------
    XOR      0 0 1 1 ..(160個).. 1 0 1 0 = 距離 = 2^157~2^158
    
    k-bucket u u u u ..(160個).. u u u u
                 ^このk-bucketにotherが入る
    
[/code]


CC BY-SA 3.0
2014-12-29T05:20:36.647
2769
2015-01-01T08:20:47.497
2015-01-01T08:20:47.497
30
30
2693
answer