本章では，構造化P2Pオーバーレイネットワークにおいて，グループ化を行っている 研究について紹介を行い，その特徴について述べる．
8.1 LFRT-Chord
LFRT-Chord[23]は，構造化P2Pオーバーレイネットワークの構成手法の一つである
“柔軟な経路表（Flexible Routing Tables）”をベースとした，Chordのグループ化手法で ある．
LFRT-Chordでは，FRTを拡張し，各ノードに設定されている“ラベル（Label）”に基 づき，同じラベルを持つノード群を“ノードグループ”と見なす．グループ分けの方法は 任意であり，構造化P2Pオーバーレイネットワークの利用者，もしくは利用するアプリ ケーションが設定する．論文では，ISP間の通信を減少させるために，ノードグループを またぐ通信を抑制するというアプローチが紹介されている．
LFRT-ChordをChordと比較した結果を論文より引用し，図8.1と図8.2に示す．
図 8.1: 平均経路長 図 8.2: 経路長分布
図8.1と図8.2より，グループ間通信が抑制されている一方で，経路長のトレードオフ が小さく抑えられていることがわかる．
また，各グループごとに構成される構造化P2Pオーバーレイネットワークについて比 較した結果を論文より引用し，図8.3と図8.4に示す．
図8.3と図8.4より，平均経路長や最大経路長，経路長分布など経路長の特性の変化が小 さく抑えられており，複数の構造化P2Pオーバーレイネットワークを一つの構造化P2P オーバーレイネットワーク分の経路長維持コストで実現していることがわかる．
8.2. DIMINISHED CHORD 第 8章 関連研究
図 8.3: 平均経路長 図 8.4: 経路長分布
8.2 Diminished Chord
Diminished Chord[24]は，Chordをベースとした構造化P2Pオーバーレイネットワー クのグループ化手法である．
グループを構成する手法として，ツリー型・埋め込みツリー型・スパースリング型な ど，複数のグループ化手法が紹介されている．構造化P2Pオーバーレイネットワークの グループ化は，所属するグループに関する情報を各ノードが管理することで行われる．
また，Diminished Chordでは，グループ化を行う際に，独自のリングなどを形成する ことなく，Chordが提供するリングを利用することで経路制御を行うことが可能である．
そのため，k個のノードが各グループに存在する場合，独自にリングを形成する場合には，
O(klogk)のストレージを使用するが，Diminished Chordでは，O(k)の使用量に抑える ことが可能である．
8.3 Flexible Routing in Grouped DHTs
Flexible Routing in Grouped DHTs（GTap）[25]は，Tapestryをベースとした構造化 P2Pオーバーレイネットワークのグループ化手法である．
経路制御手法として，宛先を指定する他に，経由するノードを指定した経路制御を行う ことが可能である．経由するノードを指定した経路制御を利用することで，各ノードの特 性（計算機資源やネットワーク資源など）を考慮した通信が可能である．
また，GTapでは，グループを構成する構造化P2Pオーバーレイネットワークのため の経路表と，グループを発見するためのGroup Membership Rendezvous（GMR）木を用 いる．
GTapの評価結果を論文より引用し，図8.5と図8.6に示す．
図8.5は，GTapとTapestryおよびAutonomous DHT（ADHT）の平均経路表サイズを 示している．図8.5より，GTapの平均経路表サイズは他の構造化P2Pオーバーレイネッ トワークと比べて，大きくなっていることがわかる．また，グループ数が64の場合と256
– 45 –
8.4. まとめ 第 8章 関連研究
N N N N N
1XPEHURIQRGHV
5RXWLQJWDEOHVL]H
*7DS *7DS
$'+7 7DSHVWU\
図 8.5: 平均経路表サイズ
N N N N N
1XPEHURIQRGHV
$YHUDJHQXPEHURIKRSV
*7DS *7DS
図 8.6: 経由ノード指定経路制御における平 均経路長
の場合でほぼ変化しないことから，グループ数に関わらず一定の経路表サイズとなること がわかる．
図8.6は，GTapにおける経由ノード指定経路制御の際の平均経路長を示している．図 8.6より，グループ数が減少すると，経路長が増加している．これは，グループ数が減少 すると，一つのグループあたりに所属するノード数が増加するためである．
図8.5と図8.6より，複数の構造化P2Pオーバーレイネットワークを一つの構造化P2P オーバーレイネットワークとほぼ変わらないコストで実現していることがわかる．
8.4 まとめ
本章では，構造化P2Pオーバーレイネットワークにおいて，グループ化を行っている 研究について紹介を行い，その特徴について述べた．紹介した関連研究は，すべて本研究
で用いたKademlia以外の構造化P2Pオーバーレイネットワークを使用していたが，これ
らの構造化P2Pオーバーレイネットワークは，本来備えている経路表が，Kademliaと比 べ決定的であるという特徴がある．そのため，決定的である経路表に柔軟性を持たせるた め，大きく経路表の構造やアルゴリズムを変更することで，グループ化を実現している．
しかし，経路表の構造やアルゴリズムを変更する場合には，構造化P2Pオーバーレイ ネットワークの構造が複雑になる可能性があるため，実際に運用する際には，慎重に検討 する必要がある．一方で，本研究で使用しているKademliaは，本来備えている経路表自 体に既に柔軟性があるため，経路表の構造やアルゴリズムの変更を最小限にすることが可 能である．特に，本研究で実装したG-Kadは，属性を保持しない状態では，Kademliaと 同様の動作をするように設計・実装されているため，本来備えている構造を失うことなく グループ化を実現することが可能である．
本研究では，そのような他の関連研究が気づけていなかったKademliaの特徴に着目し，
最大限にその特徴を活かすことでグループ化を実現した．また，ネットワークのグルー プ化という意味でも，Kademliaが備えている柔軟性を利用することで，8.1節で述べた
LFRT-Chordのように，下位層を考慮したグループ化や他の利用者やアプリケーションが
要求するようにグループを構成することも容易である．