« [VoIP]VoIP Conference開催のお知らせ | トップページ | [DHT]第2回DHT勉強会懇親会 »

2006.09.10

[DHT]DHTとホップ数の関係[その2]~Chordの平均ホップ数を考えよう

前回は直感的な方法でDHTのホップ数について推定した。今度はChordに絞ってホップ数を調べる事でより理解を深める事にしよう。

□Chordのリンク数からホップ数を推定

まず、Chordのノード参加数をN=2^xとしよう。2^xとは2のx乗を表す事とする。ここで1ノード当たりのリンク数はlog(N)=xである事に注意。

平均ホップ数を計算するときに発想を転換しよう。今1ノードxあたりのリンクがある。すると、P回ホップ数すると、ホップ可能な総ノード数LはだいたいL=x^Pとなる。x^P=Nであれば、P回ですべてのノードにアクセスできると大体考えられる事ができる。つまり、平均ホップ数P=log(N)/log(x)=log(N)/log(log(N))~O(log(N))となる。
最後の近似はやや荒っぽい。計算がlog(N)より小さく出たのはホップ時に到達するノード数の仮定が甘いからである。

□もう少し解析的にホップ数求める方法

今度は違った見方をしてみよう。この手法によるホップ数算定はこのBlogが初発表になるはずだ。

今ノード0からのリンクを考えると、総ノード数を2^xとして距離2^0、2^1・・・2^{x-1}のノードとリンクを張るはずだ。
ところで、ハッシュ空間にすべてノードが埋まっている場合、あるノードへ到達する際に次ホップする距離はホップ毎に単調減少するはずだ。(この証明は読者にお任せする。)
つまり、次ホップまでの距離をR、ホップ数をtとするとR(t+1)<R(t)である。
ところが、R(t)として取れる数は、{2^0、2^1・・・・2^{x-1}}というlog(N)個しかない。つまり、最大ホップ数はO(log(N))より超える事がないはずである。

ここで問題なのは、O(log(N))というステップ数で本当に2^xの空間のすべてのノードに到達できるかということである。

そのために補題を作る。
補題:
2^{x-1}+1≦P<2^x となる整数Pは、集合S{2^0、2^1、・・・2^{x-1}}の和で表される。ただし、この和において、集合Sの各元は高々1回しか現れないとする。

証明:帰納法により証明可能。

この補題により、O(log(N))のステップ数以内に、任意のノードに必ず到達できることが証明できた。
今はハッシュ空間にすべてのノードが参加していることを仮定した。ノードが部分的に参加してない場合の証明については読者にお任せする。

|

« [VoIP]VoIP Conference開催のお知らせ | トップページ | [DHT]第2回DHT勉強会懇親会 »

P2P」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/18781/11844144

この記事へのトラックバック一覧です: [DHT]DHTとホップ数の関係[その2]~Chordの平均ホップ数を考えよう:

« [VoIP]VoIP Conference開催のお知らせ | トップページ | [DHT]第2回DHT勉強会懇親会 »