[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)
次回は数列や微分方程式を使ってよりエレガントにホップ数を計算できる方法を提案したいと考えている。
| 固定リンク
「P2P」カテゴリの記事
- WebRTCを実現するためにSTUNだけでなくTURNも必要な理由(2015.01.08)
- [P2P]P2Pストリーミングのサーベイ文書について(2014.11.09)
- Winnyの開発者、金子 勇氏の急逝を悼んで(2013.07.07)
- 「分散ハッシュシステムでのNAT超えの考察」に対する質問について(2012.12.16)
- [P2P]Websocketでブラウザ間P2P通信は実現できるか?(その2)(2011.11.20)
この記事へのコメントは終了しました。
コメント