Overlay Weaverコミュのホップ数

1,000 ノードで 1,000 回 GET したときのホップ数の分布です。
アルゴリズムごとの性質がよく見えます。

コメント(13)

最初
全て
最新の40件

4,000 ノード版

楽しく拝見させていただいています。

1000 ノード版を見て Kademlia はさすがだなぁ、と思っていたのですが、4000 ノード版では省かれてしまったのでしょうか？

可能でしたら、4000 ノードにおける Kademlia の評価も拝見できれば、と思うところです。

[3] mixiユーザー 05月24日 23:22

Kademlia をグラフに含めていたこと自体がミスリーディングでした。
1,000 ノード版グラフに示したホップ数も、実のところ正しくない値でした。
ごめんなさい。

Kademlia の場合、「ホップ数」という概念がそぐわないです。
一回の (DHTの) get で 20かそれ以上のノードに対してコンタクトします。
ただし、複数のノードに対して並行して問い合わせを行うので、20ノードに逐次で問い合わせるよりは早いはずです。

[4] mixiユーザー 05月26日 11:54

なるほど、了解です。ありがとうございます。

[5] mixiユーザー 05月26日 14:20

4,500 ノード版です。
4,000 ノード版と変わり映えしません。

[6] mixiユーザー 10月26日 19:35

楽しく拝見させていただいています。
4000ノード版を見て、思ったのですが、
Chordは最悪 log N ホップで検索が終了するはずですが、
12ホップ以上にも値が存在するのは何故でしょうか？？

[7] mixiユーザー 10月30日 12:28

御質問ありがとうございます。
得られた数字の妥当性を考えるのは、楽しいです。

「最悪 log Nホップ」という情報のソースはどちらでしょうか。

ノードとキーのIDがランダム（に散らばっている）場合に、ホップ数は高い確率で O(log N) になる、と理解してます。

ノード数に近いホップ数を要してしまうような状況を恣意的に作ることもできますし。（→「最悪 log N ホップ」ではない。）

[8] mixiユーザー 10月31日 01:47

大変お忙しい中、質問にお答えいただきありがとうございます。

「最悪 log N ホップ」というのは、私が初めてChordについて書かれた論文を読んだ際に勝手に思い込んでいたものでした。

まだ私はChordについての理解が足りていないようで、やはり log N ホップ以上かかる状況をイメージ出来ませんが、もう一度論文を読み直してみます。

今回の質問で、「最悪 log N ホップではない」という今まで考えなかった見解をもてました。
本当にありがとうございました。

[9] mixiユーザー 11月07日 19:36

楽しく読ませてもらっています。

4000ノード版について、私も疑問に思いました。

図は論文からの転載なのですが、私は図のようにfinger tableが構成されれば、finger tableを一回参照するたびに、目的ノードが存在し得る区間を約半分に絞ることが出来ると考えています。

このためホップ数は必ず対数オーダーになると思うのですがいかがでしょうか？（直感的な質問ですみません）

もしよろしければ上記の「ノード数に近いホップ数を要してしまうような状況」の具体的な状況を教えていただけると非常にうれしいです。

[10] mixiユーザー 11月08日 15:40

> ノード数に近いホップ数を要してしまうような状況を恣意的に作ることもできますし。

これは、例えば図のような状況を恣意的に作ることができるということです。
全体でわずか5ノードなのに、2 or 3 ホップでは済まず 4ホップかかります。

[11] mixiユーザー 11月08日 15:46

4,000 ノードで 4,000回 put、4,000回 get、合計で 8,000回の lookup についてホップ数を集計したものです。
（5月に載せたこれまでのグラフでは、合計 4,000回の lookup (get) についての頻度でした。今回は lookup 回数が倍になってます。）

Chord については 11/7 のグラフと 11/8 のグラフ、２つがあります。11/8 のものの方がホップ数が小さくなってます。これは、finger table に入れるノードの決め方を若干変更した結果です。この変更は OW 0.5.2 に入る予定です。

それ以前に、11/7 のグラフでも、5月のものよりホップ数の分布が小さい方に寄ってるようです。これの原因は定かではありませんが、successor list の長さを 4から 8に変更したせいかもしれません。

[12] mixiユーザー 11月08日 17:48

忙しい中、素早い返信大変ありがとうございます。

今まで図のような状況を想像できなかったです、
とても勉強になりました、ありがとうございます。

OW0.5.2 楽しみにしています

[13] mixiユーザー 11月09日 00:14

> Chord については 11/7 のグラフと 11/8 のグラフ、２つがあります。11/8 のものの方がホップ数が小さくなってます。これは、finger table に入れるノードの決め方を若干変更した結果です。この変更は OW 0.5.2 に入る予定です。

困ったことに、この変更によって、churn 状態での get 成功率は、逆に微妙に下がって（悪くなって）しまうような感触です。
うーん...

ログインすると、みんなのコメントがもっと見れるよ