Tag D
7.1 G-Kad の評価
第 7 章
評価
本章では，6章で実装したG-Kadについて，Kademliaと比較を行い，どの程度性能 に下がるかを調べると共に，本論文の目的であるデータ展開について，評価を行った．
G-Kadについては，キーの検索にかかるメッセージの平均反復回数と，ノードの参加と
離脱にどの程度耐性があるかをシミュレーションにより調査した．ノードの参加と離脱 は，Churnと呼ばれ，Kademliaでは1時間内に50%のChurnが発生した場合にも動作 するように設計が行われている．また，データ展開については，ある1つのデータに着目 し，キャッシュノードを用いることなくデータ展開を行った場合と，キャッシュノードを 用いてデータ展開を行った場合で，どの程度完了時間に差が出るかを調査した．
について売り上げがわかっているため，タグの分布を考えた場合に，総売上数に占める割 合を仮想ノード数に反映できると考えたためである．さらに，タグのサンプルデータとし て，DVD Top 500の計 500個の商品それぞれについて，Amazon.co.jp[20] で検索を行 い，商品につけられているタグを取得した．Amazon.co.jpを用いた理由としては，それ ぞれの商品についてユーザが自由にタグをつけることが可能であるため，本研究の想定に 近いタグ付け手法を採っていると考えたためである．
評価に使用したデータと例を以下に示す．
• タイトル
例：崖の上のポニョ
• 売り上げ 例：841,203
• タグ
例：宮崎駿，スタジオジブリ，ポニョ，（他18個）
• 類似アイテム
例：となりのトトロ，魔女の宅急便，千と千尋の神隠し，（他13個）
7.1.2 評価環境
評価環境を表7.1に示す．
表7.1 評価環境
言語 C#
フレームワーク Microsoft .NET Framework 4.0.30319
OS Microsoft Windows 7 Ultimate (x64)
OSバージョン Version 6.1.7600 Build 7600
開発環境（IDE) Microsoft Visual Studio 2010 Ultimate Edition IDEバージョン Version 10.0.30319.1
コンパイラ Microsoft Visual C# 2010 Compiler Version 4.0.30319.1 Kademliaライブラリ Daylight 0.2
Kademlia ライブラリのDaylight[21] は，本来，実ネットワークで運用するように書
かれた構造化P2Pオーバーレイネットワークライブラリであるため，本論文ではシミュ レーション環境で動くよう，コードを一部書き換えている．
また，シミュレータはすべて独自に実装を行った．これは，G-Kadを評価する上で，
プロトコル自体の変更が必要になるためである．特に，構造化P2Pオーバーレイネット
ワークのインタフェースとして提供される，PUTメソッドとGETメソッドにも変更を 行う必要があるため，既存の実装をそのまま実装するのは限界があると判断した．した
がって，Kademliaに特化したシミュレータの実装を行った．
7.1.3 評価方法
評価は以下の手順で行った．
1. 仮想ノードの作成
指定された数のKademliaの仮想ノードを作成する．
G-Kadの場合：ノードのタグをDVD Top 500の分布に従って設定する．
2. 仮想ノードのネットワークへの参加
作成された仮想ノードをKademliaに参加させる．
3. 仮想ノードが保持する経路表の更新
仮想ノード同士がメッセージ交換を行い，保持する経路表の更新を行う．
4. キー・バリューペアの格納
• Kademliaの場合
キー・バリューペアをPUTする．
• G-Kadの場合
キー・バリューペアをタグと共にPUTする．
5. キー・バリューペアの取得
• Kademliaの場合 キーをGETする．
• G-Kadの場合
キーをタグと共にGETする．
また，キー・バリューペアの格納と取得において，Churn によって離脱するノード数 を，全体の10%，20%，30%，40%，50%の5つの場合を設定し，評価を行った．
7.1.4 評価結果
シミュレーションは，それぞれ 5回ずつ行い，平均メッセージ反復回数は最小値を，
GET成功数については最大値を結果として使用した．
平均メッセージ反復回数
KademliaとG-Kadの平均メッセージ反復回数を図7.1に示す．
図7.1において，x軸はChurn の確率，y軸はメッセージ反復回数である．Churn は PUT開始時からGET終了時までの間，発生させ，ノードが離脱した直後に別の新しい ノードを加入させているため，ノード数は一定である．
0.06 0.06 0.083 0.129 0.166 0.433 0.475
0.584
0.89
1.151
0 0.2 0.4 0.6 0.8 1 1.2 1.4
0.1 0.2 0.3 0.4 0.5
Average Try
Churn
Kademlia G-Kad
図7.1 平均メッセージ反復回数
図7.1より，Churnの確率が大きくなるにつれ，KademliaもG-Kadも平均メッセー ジ反復回数が多くなっていることがわかる．これは，Churnにより，ノードの離脱により キー・バリューペアが消滅してしまったために，本来のノードでバリューを発見できず，
より遠いノードへ検索を行っているためである．
また，Kademliaの平均メッセージ反復回数に対して，G-Kadの平均メッセージ反復回
数が多いのは，G-Kadがタグを用いた検索を行っているためである．G-Kadでは，検索 を行う際に，同じタグを持つノードへ優先的にメッセージを送ろうとするため，Kademlia でID的に遠い場合でも，タグが近ければメッセージを送り，ノードの候補を得る．そのた
め，Kademliaよりも多くのノードへメッセージを送る可能性がある．さらに，G-Kadに
おいて目的のバリューが発見できなかった場合には，タグを考慮せず，通常のKademlia の検索を行うことになる．したがって，上記2つの理由により，G-Kadの平均メッセー ジ反復回数はKademliaに比べて大きくなっている．
GET成功数
KademliaとG-KadのGET成功数を図7.2に示す．
図7.2において，x軸はChurnの確率，y軸はGET成功数である．Churnは7.1.4節 で述べた方法で発生させている．
図7.2より，Churnの確率が大きくなるにつれ，GET成功数が下がっていることがわ
かる．これは，7.1.4節で述べたように，ノードの離脱によりキー・バリューペアが消滅 してしまったために，バリューが発見できなかったためである．
Kademliaは経路表に柔軟性を持たせている反面で，PUT時に経路表に存在したノー
ドが，その後のメッセージのやりとりによって，GET時にいないといったことが起こる．
1424
1332 1378
1282
1175 1610 1600 1584
1502 1478
0 200 400 600 800 1000 1200 1400 1600 1800
0.1 0.2 0.3 0.4 0.5
GET Sucess
Churn
Kademlia G-Kad
図7.2 GET成功数
特に，今回の評価では，2000ノードという比較的少ないノード数で実験を行っているた め，ランダムに生成されるIDと自分のIDとの距離が，どのノードとも遠くなってしま うといったことが起きる可能性が高い．このような要因により，PUT時にk-bucketに存 在していたノードが，GET時にいなくなってしまうといったことが多く発生してしまっ たと考えられる．この問題は単にノード数が多ければ良いというわけではなく，ノード数 がある程度多い場合にも，同じような問題が起きることが指摘されている[22]．
また，図7.2において，Kademliaに比べてG-KadのGET成功数が多いのは，G-Kad の複製値が動的に決定されるためである．通常のKademliaは，2.2.3節で述べたように，
複製値は，k と規定されており，例えば20などの値になっている．しかし，G-Kadの場 合には，データについているタグ毎にPUTを行うため，1回の PUTでデータが格納さ れるノードは少ない反面で，タグが多くついていれば，その分だけPUTが実行され，結 果として多くのノードにデータが格納されることになる．したがって，このようにタグの 数に応じて動的に複製値が変化するため，今回用いたデータのように複数のタグがつけら れることが一般的なものは，G-Kadの方がGET 成功数が多くなる．このような性質に より，実際に運用を行う際にも，G-Kadはデータの人気などに合わせて効率的に資源を 配分することが可能となると思われる．