FIND NODE 時の検索コスト

次に，FIND NODEを行った場合の平均コストについて説明する．FIND NODE を

行った場合，複数のノードに問い合わせることになる．そのため，ここでは1ノードあた りの平均コストについて議論する．

ただし，その前に，k-bucketsが保持しているノードの数と，FIND NODE終了までに 必要な問い合わせの回数について議論を行う．

ノード数とk-bucketsの高さ

今，木構造でルーティングテーブルを管理した場合の木の高さをk-bucketsの高さと呼 ぶとする．例えば，図 4.1の(d)ではk-bucketsの高さは3である．この時，Kademlia のネットワークに参加しているノードの数が N であり，各々のノードが持つIDが一様 ランダムに分布していたとしたら，k-buckets の高さは平均してlogN となる．これは，

先程の議論と同じく，自身のID = 0^{とした場合，}1∗ · · · ∗^のIDを持つノードは，全体の 50[%]を占め，01∗ · · · ∗^のIDを持つノードは，全体の25[%]を占めるからである．

図4.4はk-bucketsの高さの理論値と，実測値を表したものである．実測値は，ランダ ムに IDをノード数だけ生成したときの，k-bucketsの高さの平均値であり，ここでは生 成した全てのノードのk-bucketsの高さをサンプルとしている．なお，ここではk = 1と して計測を行った．この結果より，理論通りk-bucketsの高さの平均はlogN となること がわかる．

FIND NODE終了に必要な問い合わせ回数

FIND NODEに必要な問い合わせ数は，k-bucketsのk の数に依存する．これは，k の数が多いほど，bucket中の最大共通プレフィクス長が確率的に大きくなるからである．

いま，FIND NODEを行うごとに平均して L(k) ビットずつマッチしていくとすると，

FIND NODE終了に必要な問い合わせの平均回数は，参加しているノードの数をN ^とす

ると，logN

L(k) ^{回となる．}

0 5 10 15 20

1 10 100 1000 10000 100000

depth of k-bucktes

#NODES

theoretical experimental

図4.4 k-bucketsの高さ

図4.5は，kを1から30まで変化させたときの，FIND NODE終了に必要な問い合わ せ回数をシミュレーションにて導出したものである．これより，問い合わせ回数はlogN に比例して変化していることが分かる．また，kが大きいほど，必要な問い合わせ回数が 減ることもわかる．

図 4.6は，図 4.5で求めた結果から，最小二乗法を用いてL(k)の値を概算した結果で ある．これより，k ^{が大きいほど}L(k)の値が大きくなっていくことがわかる．しかしな がら，k が30と40の場合では，L(k)にはほとんど変化が見られなかった．この結果よ り，実用的には，Kademliaではkの値は5から30程度が有用な値であると言える．

配列の場合におけるFIND NODE時の検索コスト

配列の場合は，ルーティングテーブルの検索コストは1である．従って，FIND NODE 終了に必要な問い合わせ回数は logN

L(k) ^{であるので，合計で，}

logN

L(k) ^{の検索コストが必要} となる．また，これは平均して1となる．

0 2 4 6 8 10

100 1000 10000 100000

#FIND NODE

#NODES k = 1

k = 5 k = 10 k = 20 k = 30

図4.5 FIND NODE終了に必要な問い合わせ回数

木構造の場合におけるFIND NODE時の検索コスト

木構造の場合は，FIND NODEを行うごとに平均して L(k)だけの検索コストが発生 する．これは，L(k)が木を辿るべき高さを意味しているからである．また，k-bucketsの 高さはlogN となるため，FIND NODEを行う際に発生するルーティングテーブル検索 コストの合計は，平均して

i·L(k)∑<logN

i=1

i·L(k) + logN (4.6)

となる．なお，平均検索コストは，FIND NODE終了に必要な問い合わせ回数の logN L(k) で割ったものになる．

図 4.7は木構造のときの，FIND NODEに必要な合計コストの平均を，式 4.6から導 出したものである．配列の場合は，FIND NODE終了に必要な問い合わせ回数と同じな ので，合計コストの平均は図 4.5と等しくなるが，100,000ノードの場合を比較すると10 倍以上の差がある事がわかる．

0 1 2 3 4 5 6 7

0 5 10 15 20 25 30 35 40

L(k)

k L(k)

図4.6 L(k)の概算