Kademlia 拡張（ G-Kad ）概要

本研究では，Kademliaにグループ化の概念を導入し，タグ毎に仮想的な経路を構成で きるようにした，G-Kad を実装した．G-KadはKademliaの拡張であるため，基本的な 動作や基盤などはKademliaと共通である．したがって，本節ではKademliaとG-Kad の変更点のみを説明する．

k-bucketsの拡張

G-Kadでは，k-bucketsに格納するノード情報を以下のように拡張した．

• IPアドレス

• UDPポート番号

• ^ノードID

• 属性（ノードタグ）

この拡張により，G-Kadでは，すべてのメッセージにおいて，ノードタグが交換され るようになる．

Kademliaプロトコルの拡張

G-Kad では，4 つの Kademlia プロトコルのうち，3 つに関して属性を扱うための

拡張を行った．具体的には，STORE，FIND NODE，FIND VALUEに関して，引数

を追加し，キーとバリューの他に属性を扱えるように拡張を行った．そのため，上の RPC では，属性を持つノードが優先して選ばれるようになり，属性を持たない場合 や属性に合致するノードが居なかった場合にのみ，Kademlia の動作を行うようにな る．また，FIND NODE，FIND VALUEに関しては，属性を用いた検索が失敗した場

合に，Kademliaの検索を行うための処理を関数内に追加した．さらに，データ展開の

ためのプロトコルとして，FIND NODE BY ATTRIBUTE という RPC を定義した．

FIND NODE BY ATTRIBUTEでは，複数個の属性を引数として受け取り，1個以上の

同じ属性を持つノード情報を返すRPCである．

属性の処理

G-Kadでは，属性を追加したために，属性の比較や一致に関して考慮する必要がある．

本項では，G-Kadの属性の処理について説明を行う．

まず，属性の比較については，基本的に文字列として扱っているため，単純な文字列比 較を行うだけである．ただ，自然言語であるために，揺らぎや表現の違いが発生すること を考え，揺らぎを許容するように実装を行った．属性比較処理を行うソースコードをソー スコード6.1に示す．

ソースコード6.1 属性比較処理

1 public bool AttributeEquals(string a, string b)

2 {

3 System.Globalization.CompareInfo ci = System.Globalization.CultureInfo.

CurrentCulture.CompareInfo;

4

5 if (a.Length >b.Length)

6 {

7 if (ci.IndexOf(a, b, System.Globalization.CompareOptions.IgnoreCase|

8 System.Globalization.CompareOptions.IgnoreKanaType |

9 System.Globalization.CompareOptions.IgnoreNonSpace|

10 System.Globalization.CompareOptions.IgnoreSymbols|

11 System.Globalization.CompareOptions.IgnoreWidth) >0)

12 {

13 return true;

14 }

15 }

16 else

17 {

18 if (ci.IndexOf(b, a, System.Globalization.CompareOptions.IgnoreCase|

19 System.Globalization.CompareOptions.IgnoreKanaType |

20 System.Globalization.CompareOptions.IgnoreNonSpace|

21 System.Globalization.CompareOptions.IgnoreSymbols|

22 System.Globalization.CompareOptions.IgnoreWidth) >0)

23 {

24 return true;

25 }

26 }

27 return false;

28 }

属性比較処理では，2つの文字列を受け取り，文字列長の比較を行う．そして，文字列 長の長い方の文字列の中に，文字列長の短い方の文字列が含まれているかどうかを判断す る．その際，大文字や小文字，カタカナとひらがな，発音区別府，記号，半角・全角は無 視するように実装した．

次に，属性の優先度の計算については，上述した属性比較処理を用いて，実装を行った．

属性優先度計算を行うソースコードをソースコード6.2に示す．

ソースコード6.2 属性優先度計算

1 public classAttribute

2 {

3 public string Tag{ get; set; }

4 public int Frequency{ get; set; }

5 }

6

7 public int CalculatePriority(List<Attribute> ourTags, List<Attribute>targetTags)

8 {

9 intpriority = 0;

10 foreach (Attribute ourTag in ourTags)

11 {

12 foreach (Attribute targetTag in targetTags)

13 {

14 if(AttributeEquals(ourTag.Tag, targetTag.Tag))

15 {

16 priority += targetTag.Frequency;

17 }

18 }

19 }

20 return priority;

21 }

優先度計算処理では，2つの属性リストを受け取り，優先度を計算する．文字列リスト は総当たりで比較を行い，属性比較処理において一致した場合には優先度に出現頻度を足 すことで，単なる一致度ではなく，ノードにおけるある属性の重要度を反映した優先度の 計算ができるようになっている．

6.2 まとめ

本章では，4章で述べた，データ展開におけるキャッシュノードの動的な選択手法につ いて，5章の設計に基づき，実装を行った．次章では，シミュレーションを用いてG-Kad の性能を既存のKademliaと比較し，その性能について定量的な評価を行うと共に，本論 文の目的であるデータ展開について，高速化が実現できるのかどうか，定量的・定性的な 評価を行う．

第 7 _章

評価

本章では，6章で実装したG-Kadについて，Kademliaと比較を行い，どの程度性能 に下がるかを調べると共に，本論文の目的であるデータ展開について，評価を行った．

G-Kadについては，キーの検索にかかるメッセージの平均反復回数と，ノードの参加と

離脱にどの程度耐性があるかをシミュレーションにより調査した．ノードの参加と離脱 は，Churnと呼ばれ，Kademliaでは1時間内に50%のChurnが発生した場合にも動作 するように設計が行われている．また，データ展開については，ある1つのデータに着目 し，キャッシュノードを用いることなくデータ展開を行った場合と，キャッシュノードを 用いてデータ展開を行った場合で，どの程度完了時間に差が出るかを調査した．