コンピュータの発展・普及に伴い,膨大なデータやコンピュータを扱えるシステムの重要性がますます増している.P2Pシステムは,発展・普及したコンピュータを構成ピアとして取り込むことによって,そのようなシステムになれる可能性を持つ.しかし,不安定なピアからなるP2P環境を克服するためには,安定な環境とは異なる手法が必要となる.その1つがP2P環境でデータを安定に管理するためのアドレッサブルネットワークである.アドレッサブルネットワークでは,データ管理用のアドレスがピアに割り当てられ,ピア間が適切につながれる.さらに,ピアの新規参加・離脱に対応するための手続きが定期的に実行され,冗長性を確保するための方針も与えられる.このアドレッサブルネットワークでは,メモリのような指定したアドレスへの一意なアクセスが可能であり,これを利用すれば,P2P環境において,安定で効率の良いデータ管理を実現できる可能性がある.しかし,通常のメモリとは違い,ピア間で負荷を分散するように,データの配置アドレスを散らさなければならない.また,目的のアドレスへのアクセスは,そのアドレスを割り当てられたピアまでP2Pネットワーク内をたどることにより実現する.したがって,複数データへのアクセスコストを抑えるためには,データ配置がネットワーク構造に合っていなければならないし,アクセスアルゴリズムもそのデータ配置やネットワーク構造に合っていなければならない.

また,配列は広く利用されており,時系列データの保存など,P2P環境でも有用である.しかし,P2P環境で効率良く配列を管理する仕組みはこれまで無かった.

本研究により,アドレッサブルネットワークを利用してP2P環境で配列を効率良く分散管理できるようになる.本システムはアドレッサブルネットワークの特徴である高い耐故障性とスケーラビリティを持ち,既存のアドレッサブルネットワークでのデータ管理手法とも組み合わせられる.これは大規模なデータ管理や計算処理の実行などを統合したP2Pプラットフォームの実現へ向けた一歩となる.

本研究では,代表的なアドレッサブルネットワークであるChordネットワークに変更を加えた改造Chordネットワークを基盤に,均等配置規則という配列の要素の配置規則を提案し,添字番号の範囲を指定した一斉アクセスと二分探索のような探索のアルゴリズムを与える.均等配置規則は添字番号が連続する配列要素を均等に近い形に分散させる.また,その間隔がChordネットワークにおけるピア間接続の間隔と合致する.そのため,アクセスする配列要素の数が1つ増えた場合のホップ数の増分を,最適なオーダーであるに抑えられる.分散ハッシュテーブルと呼ばれるアドレッサブルネットワークでのデータ配置にハッシュ関数を用いる既存手法では,この増分は,をピア数として,になる.よって,ピアの多い,より大規模なシステムほど,本システムの有用性が大きい.また,本研究では,配列要素間でのアクセスや添字番号順でのアクセスを含めて,本システムの効率の良さの仕組みの詳細を,分散ハッシュテーブルと対比しつつ,明らかにする.

P2Pシステムは,インターネットに結合された無数のコンピュータを構成ピアとして取り込むことによって,膨大なデータを扱うできるシステムである.P2Pシステムでデータを安定に管理するための手法の1つに,アドレッサブルネットワークがある.アドレッサブルネットワークでは,データ管理用のアドレスがピアに割り当てられ,ピア間の接続が定義される.さらに,ピアの新規参加・離脱に対応するための手続きが定期的に実行され,冗長性を確保するための方針も与えられる.アドレッサブルネットワークでは,メモリのごとく指定したアドレスへの一意なアクセスが可能であり,これを利用すれば,P2P環境において,安定で効率の良いデータ管理を実現できる.P2P環境では,ピア間で負荷を分散するように,データの配置アドレスを適切に分散させることが望まれる.また,目的のアドレスへのアクセスは,そのアドレスを割り当てられたピアまでP2Pネットワーク内を何度もたどることにより実現しなければならないので,その効率化が望まれる.

本研究は,P2Pネットワーク上で配列を効率的に扱うための手法を構築したものである.ここで配列は,添字によってデータがアクセスされるもので,添字を順にアクセスする,添字の一定の範囲をアクセスする,二分探索のような探索を行う,などのアクセスパターンが利用されるものを想定している.配列のこのような利用方法は極めて一般的なものであり,時系列データの保存など,P2P環境でも有用である.しかし,P2P環境において,これらの代表的なアクセスパターンに対して最適化された手法はこれまで提案されていなかった.本研究では,代表的なアドレッサブルネットワークであるChordネットワークに変更を加えた改造Chordネットワークを基盤に,均等配置規則という配列の要素の配置規則を提案し,上記のアクセスを効率的に行うことを提案する.また提案手法の理論的解析およびシミュレーションによる実験により,提案手法の効率の高さを実証する.

本論文は以下に概略を示す9つの章からなる.

1章ではまず背景としてP2Pネットワークや分散ハッシュテーブルが論じられる.つぎに,本研究の貢献と応用について概論され,さらに関連研究として分散システム,P2Pネットワーク,アドレッサブルネットワークについて論じられている.

2章では,基盤となる改造Chordネットワークが論じられている.十分広い2べきのアドレスを持つアドレス空間を定義し,ピアがその上に配置される.各ピアからは,正方向におよそ2べき離れたピアに接続が定義される.オリジナルのChordネットワークでは2べきよりも少し先のピアに接続されているが,本論文の改造Chordネットワークでは2べきよりも少し手前のピアに接続される.この接続を利用して,各ピアから別のピアへのアクセスが定義される.改造した接続により,アクセスコストが縮小される.

3章では,配列要素のアドレッサブルネットワークへの配置規則である均等配置規則が論じられる.まず均等配置規則と呼ばれる性質を定義し,その性質を満たす配置の一般形を示す.また,均等配置規則一般に対して成立する性質を論ずる.均等配置規則は添字番号が連続する配列要素を均等に近い形に分散させる.また,その間隔がChordネットワークにおけるピア間接続の間隔と合致する.均等配置規則を満たす具体的な配置も論じられる.

4章では,配列中のある要素の次に別の要素がアクセスされる場合のコストを論じている.そのコストは論文中で s' と書かれる量で抑えられ,これが小さい場合は,ランダムに配置される分散ハッシュテーブルに比べてアクセスコストが低く抑えられる.このコストは静的な条件では理論により分析され,ピアの出入りを含む動的な挙動はシミュレーションにより実証されている.

5章では,配列要素が添字順に逐次的にアクセスされる場合のコストを分析・検証している.提案手法では,アクセスする配列要素の数が1つ増えた場合のホップ数の増分がO(1)に抑えられる.ランダムに配置する既存手法では,この増分は nをピア数としてO(log n)になる.よって,ピアの多い大規模なシステムほど,提案手法の有用性が大きい.

6章では,添字の範囲を指定して,その範囲の要素すべてをアクセスする場合のコストを分析・検証している.本研究では逐次アクセスとマルチキャストを用いる並列アクセスが論じられている.さらに,それぞれについてアクセスコストを減らすためにアクセス方式を最適化した方式が示されている.

7章では,二分探索に代表される探索のコストを分析・検証している.特に,特定の均等配置規則の性質を利用した,ピア内で初期探索空間を限定するためのアルゴリズムも示されている.

8章は,以上の検証に用いられている実験条件の詳細である.

9章は,論文全体とまとめ,今後の課題について論じている.

本研究で提案されている均等配置規則を満たす配置方式のひとつは,van der Corput 列に対応する.すなわち,本研究の配置規則はvan der Corput列を一般化してアドレッサブルネットワークに応用するものと言える.本研究により,アドレッサブルネットワークを利用してP2P環境で配列を効率良く分散管理できるようになる.これは大規模なデータ管理や計算処理の実行などを統合したP2Pプラットフォームの実現へ向けた一歩となる.

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる.