| 題名 | 非均質なネットワークにおける均質なWebコンテンツ提供方式の検討 |
| 著者 | *門脇 恒平 (同志社大学大学院工学研究科知識工学専攻), 小板 隆浩 (同志社大学工学部情報システムデザイン学科), 佐藤 健哉 (同志社大学大学院工学研究科知識工学専攻) |
| Page | pp. 396 - 402 |
| Keyword | P2P, Web, ネットワーク |
| Abstract | 近年，日本やアメリカなど，先進国と呼ばれる国々においてネットワークの広帯域化が急速に進行している．一方，発展途上国と呼ばれる国々の中には，未だ広帯域化が実現されていない国が多く存在する．その結果，先進国と発展途上国において利用可能なネットワークの帯域幅に格差が生まれている． 利用可能なネットワークの帯域幅が異なる複数地域の人々が，ある一つのWebサーバにおいて提供されるSNS（ソーシャルネットワーキングサービス）などのWebコンテンツを利用し，互いにコミュニケーションを行う状況を考える．本研究では，このようなネットワーク環境を「非均質なネットワーク」と表現する．非均質なネットワークにおいては，地域間において，Webコンテンツを構成するファイルの取得速度に差異が生じる．結果として，各地域の人々に対して均質にWebコンテンツを提供することができず，地域間における人々のコミュニケーションを妨げてしまう可能性がある． 本研究では，非均質なネットワークにおいて均質にWebコンテンツを提供するために，利用可能帯域幅が広い地域のファイル取得速度を低下させることなく，利用可能帯域幅が狭い地域のファイル取得速度を向上させるシステムを提案する．また，研究対象として，各地域の人々が地域に存在する拠点（学校など）に集まり，拠点に存在するPCを用いてWebコンテンツを利用する状況を考える． 各拠点では，拠点のローカルエリアネットワークに存在するPCを相互接続することによりP2Pネットワークを構築し（以下イントラクラスタネットワーク），その上に分散ファイルシステムを展開する．イントラクラスタネットワークでは，各ノードの性能やローカルエリアネットワークの使用状況に応じて，拠点ごとに一つのクラスタヘッドノードを動的に選出する．クラスタヘッドノードは，Webコンテンツを提供するWebサーバと接続し，拠点・Webサーバ間の通信路における利用可能帯域幅をすべて消費しファイルを取得し続ける．クラスタヘッドノードが取得したファイルは，自ノードが属する分散ファイルシステムに随時格納される．これにより，イントラクラスタネットワークに属する各ノードは，Webサーバから直接ファイルを取得する場合と比較して，高速に目的のファイルを取得することが可能になる． しかし，クラスタヘッドは，拠点・Webサーバ間の通信路における利用可能帯域幅が非常に狭い，あるいは，遅延が非常に大きい場合，自ノードが属するイントラクラスタネットワーク全体で要求されるすべてのファイルをWebサーバから取得できない可能性がある．そこで，提案システムでは，拠点を一つのノードとみなし，複数の拠点を相互接続することによりP2Pネットワークを構築する（以下インタークラスタネットワーク）．イントラクラスタネットワークにおけるクラスタヘッドノードは，自ノードが属する拠点とインタークラスタネットワークに属する他拠点間，および，Webサーバ間の通信路における利用可能帯域幅と遅延を定期的に計測する．クラスタヘッドノードはこれらの情報を利用し，最も短時間でファイルを取得できると考えられる拠点またはWebサーバからファイルを取得する．これにより，クラスタヘッドノードは，拠点・Webサーバ間の通信路の一部に帯域幅が極度に狭い区間が存在する場合においても，その時点で最適なファイルの取得先を選択し，Webサーバからファイルを直接取得する場合と比較して高速にファイルを取得することが可能になる． 本稿では，提案システムに適用するアルゴリズムとして，インタークラスタネットワークのノード間における通信路の利用可能帯域幅・遅延測定アルゴリズム，および，イントラクラスタネットワークにおける分散ファイルシステム構築アルゴリズムの検討を行う． |
| 題名 | 分散配列: 連番アイテムに適したP2P分散データ構造 |
| 著者 | *福地 大輔, Christian Sommer, 清 雄一 (東京大学), 本位田 真一 (国立情報学研究所/東京大学) |
| Page | pp. 403 - 415 |
| Keyword | P2P, オーバーレイネットワーク, 分散データ構造, DHT, Chord |
| Abstract | P2P環境で多数のアイテムを扱う場合，分散ハッシュテーブル（DHT）を用いることでアベイラビリティを保つことができる． しかし，その上で連番アイテムに関する操作を行う場合，DHTは十分な性能ではない． DHTはアイテム間の関連を考慮してつくられてはおらず，連番アイテムはハッシュ関数によって乱数的にネットワーク内に配置される． そのようなアイテム配置では，連番アイテムに関する有用な操作である，シーケンシャルアクセス，範囲アクセス，最大インデクス探索を効率良く実行することが困難である． 我々はそれらの操作を高速化するために分散配列を構築する． まず，ビット列を逆読みする写像によって，DHTのスケーラビリティを損わぬように連番アイテムを規則的に配置する． 次に，連番アイテムに関する操作のアルゴリズムとDHTのオーバーレイネットワークをその規則に合わせて改良する． 結果，連番アイテムに関する操作に必要なメッセージホップ数のシステム内のノード数への依存度は低下し，多くの場合，ホップ数は大きく減少する． これを理論と実験の両面から示す． |
| 題名 | データ検索効率化のためのP2Pネットワークトポロジ変更方法の検討 |
| 著者 | *川本 絵茉, 門脇 恒平 (同志社大学大学院工学研究科情報工学専攻), 小板 隆浩 (同志社大学理工学部情報システムデザイン学科), 佐藤 健哉 (同志社大学大学院工学研究科情報工学専攻) |
| Page | pp. 416 - 423 |
| Keyword | P2P, トポロジ, 自己組織化, コンテンツ検索 |
| Abstract | 近年，P2Pファイル共有システムの普及に伴い，ファイルの検索効率の向上を目的とした研究が注目されている．ピュアP2P型で用いられる代表的なコンテンツ検索方式には，分散ハッシュテーブルを用いるものとクエリをフラッディングするバケツリレー方式がある．分散ハッシュテーブルはStructured型のP2Pネットワークで用いられ，この方式は高速ではあるが，単一のキーワードからしかハッシュ値が求められないので，条件比較などの柔軟な検索が行えない欠点がある．一方，バケツリレー方式はUnstructured型のP2Pネットワークで用いられ，コンテンツを検索したいノードはクエリを発行し，そのクエリをタイムアウトが生じるまで連鎖的にブロードキャストすることで，ネットワーク上のノードに自分の要求するコンテンツを所有するかを聞きまわる．このようにバケツリレー方式では，クエリを用いて個々のノードに問い合わせるので，分散ハッシュテーブル方式と異なり，柔軟な検索が行え，さらに，探索動作は完全に分散した形で進行するため，探索対象のコンテンツ数に対するスケーラビリティ性，アドホック性，耐障害性に優れているという利点がある．しかし，TTL という値で何ホップ先までクエリを伝播するのか制限されるので，目的のノードにクエリが届かないという問題に遭遇する場合がある．TTL を増やすことで，コンテンツ発見確率を上げることはできるが，その分，クエリのトラフィック量が増加するというトレードオフの問題が発生する． 本研究では，柔軟な検索に対応可能なバケツリレー方式を対象に，類似コンテンツを保持するノード同士が論理ネットワーク上において近くに配置されるようにネットワークのトポロジを再構築するアルゴリズムを提案する．そこで，類似するコンテンツを保持するノード同士が近くに配置されるように随時，論理ネットワーク上のリンクの繋ぎ換えを行い，Unstructured型P2Pネットワークのトポロジを再構築する．バケツリレー方式の情報検索を適用することで，単一のキーワードのみならず，複数のキーワードを組み合わせてAND・OR検索が行え，さらに否定条件を加えられるので，ユーザが求めるコンテンツをピンポイントで検索することが可能となり，よりユーザのニーズに応えるサービスが提供できる．なお，提案するアルゴリズムは，ユーザが要求するコンテンツに嗜好性があり，ユーザは何時も類似した内容・種類のコンテンツを検索することを前提に動作する．そこで，各々のノードにおいて，どの隣接ノードからどの隣接ノードにレスポンスが流れたのかを各ノードが持つトラフィック履歴テーブルに記録することで，周囲のノードが要求するコンテンツの傾向や検索頻度を計測する．そして，一定時間内において，あるノードからあるノードへのレスポンス数がある閾値を超えている場合，２つのリンクのうちレスポンスのトラフィックが小さい方のリンクを不要とみなし切り離し，代わりに，その２つのノード間に新しいリンクを張る．このことで，レスポンスの転送頻度が高い経路において類似ノード間の中継ノードをスキップできるので，ホップ数削減に繋がる．しかし，ノードが保持できるリンク数を制限せずにリンクを張り換えると，あるノードにリンクが集中する，あるいは，あるノードの全リンクが切り離される可能性があるので，リンクの張り換えと同時に，ノードが保持できるリンク数を2〜6 本に収まるように制御する．このようにリンク数を制御しながらノードが保持するコンテンツに沿って組織化された論理ネットワークを形成することができれば，検索精度の高い検索を実現できるだけでなく，トポロジ変更後でもネットワーク上のリンク数は一定に保たれる．その上，ノードの要求するコンテンツを保持するノードに少ないホップ数で到着できるので，TTLを増やすことなく目的のノードを発見することができ，その結果，クエリの氾濫を抑制することができる． 提案手法の有効性を検証するため，P2PシミュレータのPeersimを使って提案手法のシミュレーションを行った．シミュレーションでは，ユーザが検索するコンテンツに嗜好性を持たせるために，それぞれのノードに１種類のコンテンツを保持させ，毎回，類似した種類のコンテンツに対してリクエスト要求を出させた．評価では，レスポンス取得率と組織化の度合いを測定し，結果，トポロジ組み換え前と比べたとき，コンテンツ検索の効率が向上することが分かった． |
| 題名 | Bloom filterを利用したSemantic Overlay Network構築手法の検討 |
| 著者 | *高木 健士, 遠藤 伶 (慶應義塾大学大学院理工学研究科), 重野 寛 (慶應義塾大学理工学部) |
| Page | pp. 424 - 429 |
| Keyword | P2P, オーバレイネットワーク, セマンティック, Bloom filter |
| Abstract | 現在，ピアが持つ特徴を利用することで意味的な検索を可能とする，Semantic Overlay Networks(SONs)に関する研究が注目されている．SONではピアからSemanticsを抽出することで，関連したピア同士を接続し意味的なクエリ検索を可能としている． しかし，既存のSONsではピアの頻繁な参加・離脱(churn)に対応できるものはほとんどない．また，Unstructuredオーバレイにおいてはピアがネットワーク全体のトポロジの知識を持たないために，クエリの転送効率が低下するという問題もあった． そこで本稿では，churn状態においても効率的な意味検索が可能なSONs構築手法を提案する．本提案手法では，SONs構築のためにBloom filterを利用する．そして，2つピアのBloom filterのXORをピア間の距離と定義し，Bloom Filter Table(BFT)と呼ぶピアとBloom filterとの対応表を利用することで意味的な検索を実現する．また，Bloom filter間の距離に応じてピア同士を接続することでネットワークの柔軟性を高め，churn状態に対応している． 本提案手法をシミュレーションにより評価した結果，churn状態においても，検索効率および検索成功率は十分に低い値を示すことを確認した． |