« [Winny]Winnyの解析とそのセキュリティ脅威分析セミナー概要 | トップページ | [DHT]DHT勉強会ミニプレゼン講演者募集について »

2006.05.20

[DHT]DHTとホップ数の関係[その1]~直感的な方法

DHTの論文を見るとホップ数についての記述があるが、その計算根拠について書いてない場合が多い。
ここでは簡単な方法を使ってホップ数のオーダーを考えてみよう。
なお、次回以降には微分方程式・数列等を使うことにより、より詳細な考察を行う予定である。

今回はCANとChordについて書いてみることにする。

□CAN
CANについての概要は以下のサイトをご覧になってほしい。
P2Pと分散ハッシュテーブル~その1

今、2次元空間のCANを考える。縦、横ともnの大きさがあるとすると、ノード数はN=n^2である。ただし、^2は二乗を表すこととする。

ホップ数については、(0,0)というノードから(論理的に)一番遠いノードに対するホップ数とほぼ同じオーダーであろう。一番遠いノードは(n,n)である。
注※正確には(n-1,n-1)。ホップ数のオーダーにはあまり関係ないこと、見た目が複雑なので(n,n)で書いていく。

(0,0)から(n,n)までは2nホップかかる。ここでCANではリンクが縦または横にしかないことに注意!斜めにホップすることはできない。

結局ホップ数は 2n=2√(N)となる。つまりO(N^{1/2})である。

ちなみに同様な方法で計算すると、d次元の空間においてホップ数はO(N^{1/d})である。

□Chord
Chordの概要は以下のサイトをご覧になって欲しい。
P2Pと分散ハッシュテーブル~その2

今ノード数をNとして、n=log2Nとする。
ノードAからはリンクをnだけ出していることに注意。

Chordは2^p離れたノードに対してリンクをする。(pは0以上の整数)
つまり、1回リンクを辿ると、次にホップできる空間を1/2に絞ることができる。
するとホップ数qは、リンクを辿ることでホップできる空間があるノードに限定してしまう状態、つまり次にホップできる空間が1に辿りつくホップ数が分かれば良い。

結局N*(1/2)^q = 1であり、これを解いてq= n = log2 Nとなる。つまりq= O(log 2N)

次回は数列や微分方程式を使ってよりエレガントにホップ数を計算できる方法を提案したいと考えている。 

|

« [Winny]Winnyの解析とそのセキュリティ脅威分析セミナー概要 | トップページ | [DHT]DHT勉強会ミニプレゼン講演者募集について »

P2P」カテゴリの記事

コメント

コメントを書く



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


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



トラックバック

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

この記事へのトラックバック一覧です: [DHT]DHTとホップ数の関係[その1]~直感的な方法:

« [Winny]Winnyの解析とそのセキュリティ脅威分析セミナー概要 | トップページ | [DHT]DHT勉強会ミニプレゼン講演者募集について »