Symphony 25

分散ハッシュテーブル

Symphony

の

高速化と耐故障性向上について

平成

25

年度修了

三重大学大学院 工学研究科

博士前期課程 情報工学専攻

都築 礼

目次

はじめに

1

第

1

章

P2P

ネットワーク

[3]

2

1.1 オーバーレイネットワーク . . . 2 1.2 P2P ネットワークの構造と分類 . . . 3 1.2.1 ハイブリットP2P ネットワーク . . . 4 1.2.2 スーパーノード型 P2P ネットワーク . . . 4 1.2.3 ピュア P2P ネットワーク. . . 5 1.3 P2P ネットワークの抱える問題と解決策 . . . 6

第

2

章 分散ハッシュテーブル

(DHT)

8

2.1 構造型 P2P ネットワーク . . . 8 2.2 ハッシュテーブル . . . 9 2.3 分散ハッシュテーブル . . . 10

第

3

章

Symphony[1]

12

3.1 Symphony の概要 . . . 12 3.2 Symphony の経路表. . . 12 3.2.1 Short Link . . . 13

3.2.2 Long Distance Link . . . 14

3.2.3 Bidirectional Routing Protocol . . . 14

3.2.4 Lookahead List . . . 15

3.3 探索方法 . . . 16

3.4 Symphony の利点と欠点 . . . 16

第

4

章

Symphony

の高速化手法

18

4.1 Symphony のシミュレーションと考察 . . . 18

4.2.1 Short Link List . . . 19

4.2.2 Long Distance Linkの密集化 . . . 19

4.3 高速化手法の実験 . . . 20

4.3.1 実験の条件. . . 20

4.3.2 Short Link Listによる高速化の実験 . . . 21

4.3.3 Long Distance Linkの密集化による高速化の実験 . . . 22

4.3.4 併用手法の実験 . . . 23 4.4 高速化手法のまとめ . . . 26

第

5

章

Symphony

の耐故障性向上手法

27

5.1 安定化プロトコル . . . 27 5.1.1 経路表の修復機能 . . . 27 5.1.2 ハッシュテーブルの修復と複製機能. . . 28 5.1.3 コンテンツの複製機能 . . . 28 5.2 churn 状態を含むネットワークにおける探索方法. . . 29 5.2.1 経路表のノードが離脱していることによる探索クエリの送信失敗に対する処理 . . 29 5.2.2 特定のノード間の探索クエリのループへの処理. . . 29 5.2.3 ハッシュテーブルを管理するノードが離脱していたことによる探索失敗への処理 . 31 5.2.4 コンテンツの所有者が離脱していたことによる探索失敗への処理 . . . 31 5.3 局所的安定化による耐故障性の向上手法 . . . 31 5.4 耐故障性向上手法の評価実験 . . . 32 5.4.1 実験の条件. . . 32 5.4.2 局所的安定化によるネットワークの耐故障性の評価実験 . . . 33 5.4.3 耐故障性向上のまとめ . . . 35

おわりに

36

謝辞

37

参考文献

38

はじめに

近年インターネット上では，画像，音楽，動画などの高品質大容量なコンテンツの利用ニーズ が高まってきている．それに伴い，コンテンツの配信サーバや回線にアクセスが集中すること による障害やサービス管理維持コストの増大が問題になっている．そこで，インターネット上 のコンピュータ(以下ノード) が相互に通信を行うことによりサーバや回線の負荷を分散できる Peer-to-Peer(P2P)ネットワークが普及している．古典的なP2PネットワークであるNapsterや Gnutella等では大規模なネットワークになるほど探索が低速化したり，ノードやコンテンツの有 無が正確に把握できないことによる探索トラフィックの増加などの問題がある．そこで，このよう なP2P ネットワークの問題を解決するために考えられた手法として構造型 P2P ネットワークの

一つである分散ハッシュテーブル(DHT:Distributed Hash Table) が研究されている．従来の非

構造型P2P システムとは違い，DHT は，ネットワークに特定のトポロジを持たせることで，ト ラフィックを抑えつつ，ノードやコンテンツの所在を明かにすることにより，すべてのノードやコ ンテンツへの通信を保証するため，上記の問題を解決している． 本研究では，DHTの一手法であるSymphony[1] に着目する．Symphonyは他の DHTと比較 して各ノードへの負荷が小さく，ネットワークトラフィックを抑えることができるが，DHTで代 表的なChord[2] と比較すると，探索効率の面で劣る傾向にある．また，構造型 P2P ネットワー クでは，ノードがネットワークから頻繁に参加離脱を繰り返すchurn 状態において，ノードの参 加離脱によってネットワークのトポロジが崩れることで，すべてのノードやコンテンツへのアクセ スが維持できず，耐故障性が低下する可能性がある．そのため，各ノードは定期的にトポロジを維 持する処理として安定化プロトコルを行う必要がある．安定化プロトコルはノードの参加や離脱に よるハッシュ空間の変化を更新修復するための機能となる．安定化プロトコルを実行することによ り，ネットワークの耐故障性は維持できるがトラフィックを大量に消費することが大きな課題と なっている．

よって本研究では，探索の高速化手法として Short Link Listの実装とLong Distance Linkの

密集化を実装し，各ノードの通信を近距離に密集化させる手法を提案する．また，耐故障性の向上 手法として，局所的安定化を実装し，ノードの参加時に周辺ノードに安定化プロトコルを実行させ る手法を提案する．以上の二手法についてシミュレーションによる評価を行う．

本論文では，第1章では P2P ネットワークについて，第2章では分散ハッシュテーブルについ

第

1

章

P2P

ネットワーク

[3]

本章では，P2P ネットワークの構成について説明する．1.1でオーバーレイネットワークにつ いて，1.2で P2P ネットワークの構造と分類について，1.3で P2P ネットワークの抱える問題と その解決策について述べる．

1.1

オーバーレイネットワーク

オーバーレイネットワークとは，あるネットワーク上に構成された仮想のネットワークのことで あり，下位のネットワークのトポロジを意識せず通信することができる．多くのP2P ネットワー クはオーバーレイネットワークを利用している．図1.1は IP ネットワークの上位にP2P ネット ワークを構成したオーバーレイネットワークの例である．上位層であるP2P ネットワークのノー ドは下位層である IPネットワークの位置関係やルータの制御を意識することなく，上位層のネッ トワーク形態に従って通信を行うことで，それぞれのアプリケーションやサービスに合ったネット ワークを仮想的に構成できる． オーバーレイネットワークを利用した具体的な技術として，P2Pネットワーク，ファイル共有， IP電話，クラウドコンピューティングなどが挙げられる． 図1.1 オーバーレイネットワーク

1.2

P2P

ネットワークの構造と分類

現在，インターネットに一般的に使用されているネットワークモデルとしてクライアントサーバ モデルがある．図1.2で示すように，サービスの利用者であるクライアントがサービスの提供者で あるサーバからコンテンツを取得するネットワークである．クライアントサーバモデルのネット ワークでは，人気のあるコンテンツを提供するサーバにアクセスが集中し，ネットワークやサーバ の負荷が増大する．このような負荷によるサービスの低下やサーバの故障が発生すると，クライア ントへ正常にサービスが提供できなくなるなどの問題がある．そのため，サーバや回線の強化が必 要となり，コストの増大が問題となる． 図1.2 クライアントサーバモデル 一方，オーバーレイネットワークの一種であるP2P ネットワークでは，サーバやクライアント といった役割分担をせず，ノードはすべて対等な立場(Peer)であり，時にはクライアントとして コンテンツを取得し，時にはサーバとしてコンテンツを提供することで通信を行うネットワークで ある．P2P ネットワークでは，人気のあるコンテンツとはネットワークに参加する多くのノード が同じコンテンツを保有していることと同意であり，コンテンツの提供者となるノードが故障し たとしても，代替となるノードからコンテンツを取得することができる．また，P2P ネットワー クを使用することで，複数のノードによって負荷が分散できるため，現実世界の一部の回線にトラ フィックが集中することを防ぐことができることから，クライアントサーバモデルの問題点を解決 できる． しかし，P2P ネットワークは，安易に理想的なネットワークを構築できる一方で，ネットワー

を管理する機能が必要となる．また，ノードの信憑性や，データの機密性を保証することが困難で あるため，認証を必要とするサービスを構築することが困難であることが課題となる． このような問題点から，ネットワークの一部でサーバを使用したP2Pネットワークや，管理者と して機能するノードを配置したP2P ネットワークなどが利用されている．このようなネットワー クを含めて，P2P ネットワークは大きく分けてハイブリットP2P ネットワーク，スーパーノード 型P2P ネットワーク，ピュア P2P ネットワークの三種類のネットワーク形式に分類される． 1.2.1 ハイブリットP2Pネットワーク ハイブリッドP2P ネットワークのイメージを図1.3に示す．ハイブリット P2P ネットワーク は，ネットワークの構成にサーバを含んだP2P ネットワークである．認証やコンテンツの探索は 中央のサーバが行い，コンテンツの交換はノード同士が直接行う．サーバが存在する限り，コンテ ンツの探索は保証される．また，サービスの提供者がサーバを所持することで，ユーザ認証サービ スを行うことが可能となる．代表的なアプリケーションとしてファイル共有サービスのNapster やWinMXのファイル探索機能，インターネット電話サービスのSkypeのユーザ認証部分にサー バを使用している． 図1.3 ハイブリッドP2Pネットワーク 1.2.2 スーパーノード型P2P ネットワーク スーパーノード型P2P ネットワークのイメージを図1.4に示す．スーパーノード型 P2P ネッ トワークは，ネットワークの構成にサーバを含まず，ノードだけでネットワークを構成した P2P ネットワークであるが，ハイブリッドP2P ネットワークにおけるサーバの役割であるコンテンツ

の探索などの機能を一部の高性能なノード(スーパーノード)に行わせる．スーパーノードがネッ トワーク内のノード数に応じて自律的にスーパーノードの数を調整でき，探索機能の冗長性を確 保できることから，故障や回線の負荷によるサービスの低下は発生しづらい．代表的なアプリケー ションとして，ファイル共有サービスの KaZaA やインターネット電話サービスのSkype のノー ド接続や探索機能が挙げられる．1.2.1で述べたように，インターネット電話サービスの Skypeは ハイブリッドP2P とスーパーノード型 P2P の両面を併せ持つことから，スーパーノード型ハイ ブリッドP2Pシステムとも位置づけることができる． 図1.4 スーパーノード型P2Pネットワーク 1.2.3 ピュアP2P ネットワーク ピュアP2Pネットワークのイメージを図1.5に示す．ピュアP2Pネットワークは，ネットワー クの構成にサーバを含まず，スーパーノード型P2P とも異なり，コンテンツの探索機能を始めと したネットワークの全機能をすべてのノード同士で対等な立場として解決するネットワークであ る．サーバを使用しないため，サーバの故障や回線の負荷によるサービスの低下は発生しづらい． ノード同士のマルチホップ通信によってコンテンツの探索を行い，コンテンツの交換もノード同 士で行う．探索のプロセスやコンテンツの管理などが分散されるため，各ノードに平等に負荷が 加算される．代表的なアプリケーションとして，ファイル共有サービスのGnutellaや Winny[4]， Shareなどが挙げられる．

図1.5 ピュアP2Pネットワーク

1.3

P2P

ネットワークの抱える問題と解決策

前節で述べたようなP2P ネットワークは，探索技術や維持管理のプロセスにおいて様々な問題 がある． ハイブリッド P2P ネットワークは，サーバがネットワークを管理するため，ネットワーク全体 を把握することが安易にできる．よって，探索効率は高いが，サーバに負荷が集中するため，回線 やサーバレスポンスの問題から大規模なネットワークにおいて性能が低下する可能性がある．ま た，故障などによりサーバがネットワークから離脱しサービスが維持できない可能性がある．実際 に，ファイル共有サービスのWinMXでは，2005年にインデックスサーバのネットワークが閉鎖 されたことにより，サービスの閉鎖が起こった事例がある． スーパーノード型P2Pネットワークでは，ハイブリッドP2Pにおけるサーバの役割をスーパー ノードが行うことで，ネットワークからサーバの切り離しと探索機能の冗長化が可能になった．し かし，スーパーノードはノード数に応じて適切な数を確保する必要があるが，負荷を請け負うスー パーノードを一般のノードから選出することになるため，ユーザがスーパーノードとしてネット ワークに参加することを好ましく思うかは定かではない．加えて，ネットワークが小規模な状態で はスーパーノードが不安定に配置されてしまうこともあり，スーパーノードの選出が課題になる． 2010年にインターネット電話サービスの Skype では，一部のスーパーノードが一斉にネットワー クから離脱したことに加えて，ネットワークの修復に負荷が集中したことにより，サービスが停止 する事例があった． ピュアP2P ネットワークでは，上述したようなサーバが欠落することによる障害や，スーパー ノードを利用したネットワークにおける問題点を解決している．ただし，サーバやスーパーノード

が管理していた情報をすべてのノードに分散管理させるため，ネットワークの全体像を把握しづら く，存在しないノードやコンテンツを探しつづけてしまうこともあり，探索のトラフィックが増大 してしまうことが問題となる．また，ピュア P2P ネットワークで一般的な探索技法はフラッディ ングと呼ばれるバケツリレー方式であり，図1.5で示すように隣接したノードに対して探索クエリ を送信する．この探索技術では，ネットワークの規模が大きくなると，探索クエリの送信回数が莫 大に増加する．これを防ぐために，クエリの転送回数や生存時間を制限することがある．そのた め，探索クエリがネットワーク全体に届かないことがある．このように，パケットがネットワーク 全体に届かないことにより，ノードが存在するかどうかが正確に把握できない問題がある． ピュアP2P ネットワークでは，上記の問題を解決するため，ネットワークに特定のトポロジを 持たせた構造型 P2P ネットワークの研究が行われている．次章では，構造型P2P ネットワーク の一つである分散ハッシュテーブル(DHT)について述べる．

第

2

章

分散ハッシュテーブル

(DHT)

本章では，構造型 P2P ネットワークの一つである分散ハッシュテーブルについて述べる．2.1 で構造型P2P ネットワークについて，2.2で，ハッシュテーブルについて，2.3で分散ハッシュ テーブルについて述べる．

2.1

構造型

P2P

ネットワーク

構造型P2Pネットワークは，ピュアP2Pネットワークにおいて特定のトポロジを持たせたネッ トワークである．ノードやコンテンツがネットワークに登録される際，特定の法則や構造に当ては めてネットワークを構成することで，探索にかかるトラフィックを低減するとともに，ネットワー クの全体像を把握することが可能となる． 具体的な構造として，図2.1で示すように，ノード同士の接続を円状の構造になるように配置し たリング型のネットワークや，網目のように配置したメッシュ型のネットワークなどが挙げられ る．リング型のネットワークを例にすると，あるコンテンツを探索する際に，隣接ノードへの探索 クエリの送信を繰り返せばネットワーク上にあるコンテンツが必ず見つかる．このように，ネット ワークの全体の把握が可能となり，従来の非構造型P2P ネットワークの問題点を解決できる． 構造型 P2P ネットワークの主な例として，ハッシュ関数を利用した分散ハッシュテーブル (DHT)がある． 図2.1 一次元リング型P2Pと メッシュ型P2P

2.2

ハッシュテーブル

P2P ネットワークにおけるハッシュテーブルは，コンテンツやノードの名前等の keyと keyを ハッシュ関数に与えたときの値 valueを格納した表である．ハッシュ関数とは，ある key を一定 長のデータに変換するための関数を指す． ハッシュテーブルの作成は，図2.2 で示すように， key をハッシュ関数に与えて得られる key,valueのペアを表として格納する．ハッシュ空間(valueの取れる値の集合)の小さいハッシュ 関数の場合，異なるkey から同じ値を得てしまうことがある．このように，valueの値が衝突した 場合は，value の値を一つずらす等の方法がとられる．通常のP2P ネットワークでは，MD5や SHA-1 等のハッシュ空間を大きいハッシュ関数が使われることが多く，ハッシュ値の衝突が起こ ることは極めて少ない． 図2.2 ハッシュ関数

MD5やSHA-1 を始めとするハッシュ関数では，入力 keyに対する出力valueは一様分布で決

定される．そのため，keyとして image1 とimage2 といった近似する文字列をハッシュ関数に入

力した場合でも，value は一様な値が出力される．よって，ハッシュテーブルによって管理される

データは値が一様に分散したデータベースとなる．

ハッシュテーブルを用いたデータベースを表2.1に示す．key = movie3 のsizeを探索する際，

逐次探索である線形探索の場合，最悪O(N ) (N : ハッシュ空間の大きさ) で探索されるが，ハッ

シュテーブルを用いたデータベースを用いた場合，key = movie3 をハッシュテーブルを作成した

ハッシュ関数に入力して value = 10 を取得し，hashtable[(value =)10].size を参照することで

表2.1ハッシュテーブルを用いたデータベース

key value size image9 1 100KB movie2 2 550KB movie1 3 500KB 4 5 image8 6 150KB image5 7 50KB 8 image7 9 200KB movie3 10 300KB

2.3

分散ハッシュテーブル

分散ハッシュテーブルは構造型 P2P ネットワークで広く使われる技術で，ピュア P2P ネット ワークのノードやコンテンツの管理を行うトポロジとして利用されている．2.2で述べたハッシュ テーブルをネットワークに参加するノードで分散管理する技術となる． 図2.3 分散ハッシュテーブル 図2.3は，ノードがハッシュテーブルを管理している一例である．自己のノードの管理外のハッ シュテーブルを参照する場合，各ノードの保持する経路表を用いて，目的のノードに探索クエリを 送信し，コンテンツの情報を取得する．

経路表とは，各ノードが管理する通信可能な関係を持つノードのことであり，ネットワークの規 模や構造によって経路表に指定するノードは異なる．経路表を用いることでネットワーク内のノー ド同士でルーティングが行われ，目的のノードに対する通信を確立する．ネットワーク内のすべて のノードを経路表に追加するとO(1)で探索可能となるが，ネットワークの規模が大きくなると経 路表の規模も大きくなり，経路表の維持のための負荷が大きくなる．そのため，少数のノードを経 路表に管理してルーティングによりハッシュテーブルを管理する方が現実的である．経路表のノー ドへの管理処理のため，ネットワーク全体のトラフィックが増大してしまうことから，ネットワー クの規模やノードの性能に応じた経路表を設定する必要がある．

DHT は，その構造やルーティングアルゴリズムによって Chord[2]，CAN[5]，Tapestry[6]，

Kademlia[7] など様々な手法が存在する．本研究では，DHTの中でも基本的な構造となる一

次元リング型の構造型 P2P ネットワークで使用される Symphony[1] に着目をする．次章で

第

3

章

Symphony[1]

本章では，DHTの一手法であるSymphony について述べる．3.1でSymphony の概要につい て，3.2で経路表について，3.3で探索方法について，3.4で Symphonyの利点と欠点について述 べる．

3.1

Symphony

の概要

本研究では，Mankuらによって提唱されたSymphonyに着目する．Symphonyは，他のDHT

に比べ，経路表を小さく持つことが特徴であり，ノードへの負荷を小さくネットワークが構成で きる． 図3.1に Symphony が構成するハッシュ空間を示す．Symphonyは，一次元リング型のハッ シュ空間で動作する．そのため，ハッシュ関数(MD5)の最小値 0 と最大値 2128− 1を連結して リング状のハッシュ空間を構成する．本論文では，便宜上時計回り方向をハッシュ値の増加方向と する．各ノードはハッシュ関数によって任意の値が与えられ，ハッシュ空間に配置される．また， ノードは (ハッシュ値/2128_{) を id として保持する．コンテンツの所有者ノードは，同様にハッ} シュ関数によってコンテンツのハッシュ値を取得する．所有者ノードはそのハッシュ値から時計回 りに最初に出会うノード(ハッシュテーブルの管理者ノード)を探索する．管理者ノードは，自身 のハッシュテーブルにコンテンツの情報と管理者ノードの情報(管理者ノードのIPやハッシュ値 など)を登録する．これにより，第三者のノードがコンテンツを取得する際，管理者ノードへの探 索を行いハッシュテーブルを参照することで，コンテンツの所有者ノードと通信ができる．

3.2

Symphony

の経路表

Symphonyは，Short Link，Long Distance Link，Bidirectional Routing Protocolの三種類の

経路表を保有する．また，経路表を用いたルーティング効率を向上させるため，Lookahead List

の機能を備える．経路表として保持するデータは，ノードの id ，ノードの所在 (IPアドレスな

ど)，ノードのハッシュ値を表に格納する．

図3.1 Symphonyのハッシュ空間

3.2.1 Short Link

図3.2はShort Linkの構造を示している．Short Linkはハッシュ空間において各ノードの増加

方向と減少方向に最近接のノードを経路表に登録する．これにより，Short Link をたどることで，

すべてのノードへのルーティングが可能となる．

3.2.2 Long Distance Link

図3.3はLong Distance Link の構造を示している．Long Distance Link は，ルーティングに おいて遠距離に位置するノードへのショートカットとして用いられる．ネットワークの規模に応じ てk(k :定数) 個保有する．

図3.3 Long Distance Link

Long Distance Linkに指定するノードの決定方法は，確率関数p = exp(log(N )∗(rand()−1.0))

によって与えられる[1/N, 1]の値を用いて，(id + p)∗2128のハッシュ値を管理するノードをLong

Distance Linkに指定する．N はノードの総数，rand()は [0, 1] の小数を出力する乱数関数を指

す．確率関数p は，図3.4で示すように[1/N, 1]の値のうち，0 に近い値を出力しやすい関数であ

り，Long Distance Link は，自分のハッシュ値に増加方向へ近いノードを選びやすい特徴を持つ．

3.2.3 Bidirectional Routing Protocol

Bidirectional Routing Protocolは，図3.5で示すように，経路表を双方向のリンクに拡張する

プロトコルである．3.2.2で示した Long Distance Link では，ハッシュ空間の増加方向のみ経路

表に指定していたが，Bidirectional Routing Protocol によって経路表を双方向に拡張すること

で，減少方向にも経路表を確保することが可能になる．減少方向の経路表をLong Distance link

と同様に指定するよりも既に確立された接続を拡張することで，経路表を作成する際のトラフィッ クを軽減することができる．

図3.4 確率関数pの軌跡

図3.5 Bidirectional Routing Protocol

3.2.4 Lookahead List Lookahead Listは，ルーティングの効率向上機能であり，経路表の構築時や更新時に経路表に 登録されているノードの経路表をあらかじめ取得することで，ルーティングの経路決定の先読みと して使用できるリストとなる．Lookahead List を使用したルーティングの概要は3.3の探索方法 で説明する． p 0.9 。 。 ， ， e 。， S 点 “・ q d ︽ v n u w n v A U n u ︽ U 即 時 率 関 数 P の 出 力 健 0.2

。

_。

0.1 0.2 0.4 0.6 randOの乱数値 0.8

3.3

探索方法

図3.6に，Symphonyの経路表を用いたコンテンツの探索の一例を示す．ノードX がコンテン ツを取得する際，ノードX はコンテンツの keyをハッシュ関数に入力し，コンテンツのハッシュ 値を取得する．ノードX は自己の経路表を参照し，ハッシュ値が最近接のノードC へ探索クエリ を送信する．ノードCは同様に経路表からノードDへ探索クエリを送信し，最終的にハッシュ値 を管理するノードE へ探索クエリが到達すると，ノード E はハッシュテーブルを参照し，コンテ ンツの所有者(ノードF )の情報をノードX へ返す．これにより，ノードXとノード Fによるコ ンテンツの交換が可能になる． 図3.6 経路表を用いたルーティング方法

Symphonyでは，上記の探索方法にに加えて，3.2.4で示したLookahead List による探索効率

の向上手法がある．図3.7に Lookahead Listを用いた探索の図を示す．Lookahead List を用い

た探索では，事前に経路表内のノードの経路表を取得することで，図3.6で示した経路に比べ，よ

り効率的な探索が可能となる．ただし，Lookahead Listのノードに直接探索クエリを送信するの

ではなく，自己の経路表のノードへ探索クエリを送信する．

3.4

Symphony

の利点と欠点

文献[1]では，上記のSymphony を P2P ネットワークに実装することで O((1/k)∗ log2_{(N ))}

でコンテンツを探索可能であることを証明している．N はネットワーク内のノードの総数を，kは

Long Distance Linkの定数を示す．定数 kは実験的に小さな自然数個で十分であり，k = 8 以上

図3.7 Lookahead Listを用いたルーティング方法

方法を行うChordでは，O(log(N ))で探索されることから，Symphonyは探索効率の面では劣る

傾向にある．しかし，経路表の大きさで比較をすると，Chordはハッシュ空間の大きさによって

経路表の大きさが変化すが，Chordの長距離リンクに限定して最大 log(M )(M : ハッシュ空間の

大きさ) 個，平均 log(N ) 個の経路表を管理する必要がある．対するSymphony の利点は，長距

離リンクに限定して2k(k :最大8程度の定数) 個の経路表の管理で探索可能であることに加えて，

Bidirectional Routing Protocol で決定している経路表 k 個については受動的に決定している経

路表のため，経路表の決定に必要なプロセスやトラフィックが削減できることがSymphony の大

きな利点となる．

以上から，Symphony の各ノードへの負荷やネットワークトラフィックの小さい点を活かしつ

第

4

章

Symphony

の高速化手法

本章では，Symphonyの探索高速化手法を提案し，シミュレーションによる実験と考察を行う． 4.1では Symphony のシミュレーションと考察，4.2で検索の高速化手法，4.3で高速化手法の実 験，4.4で 高速化手法のまとめについて述べる．

4.1

Symphony

のシミュレーションと考察

前章で述べた経路表を実装し，シミュレーションを行った．ノード数1000，各ノード毎にコン テンツを一つ保有したネットワークで100個のコンテンツを探索する実験を行った．各ノードの

管理する経路表はShort Link の2ノードとLong Distance Link をk = 8 として16ノードの計

18ノードを管理する．また，Lookahead Listは使用する．ネットワークは，理想的な状態でノー ドとコンテンツが配置されているものとして，すべてのノードがSymphony の経路表を構成して いる．また，ノードの参加や離脱は発生せず，ノード数，コンテンツの総数は変化しない．図4.1 は以上の環境における探索クエリの送信されたときのノード間の距離と探索回数の関係を示すグ ラフである．x 軸は，探索クエリ送信時の自己の id と経路表で選択されたノードの id の差分を 0.05刻みで示す，つまり，ハッシュ空間を[0, 1]の空間としたときの探索クエリの送信元ノードか ら送信先ノードへの距離を示す．y 軸はその回数を示す．100個のコンテンツ探索にあたり，308 回の探索クエリが送信された．また，ネットワークはリング状なので，探索クエリの送信距離は最 大0.5 となる． 図4.1により，探索クエリは近距離の通信が多いことが分かる．これは，コンテンツの探索にあ たり，遠方のノードへの探索クエリ送信は探索の序盤で数回だけ行われ，ハッシュテーブルの管 理ノードを決定する探索の終盤に近距離のノードへの探索クエリの送信が多いことを示している． よって，コンテンツの探索にあたって，より近距離の経路表に重点をおくことで，探索効率が向上 するのではないかと推測した．

4.2

Symphony

の検索の高速化手法

4.1の結果から，近距離の経路表に重点をおいた経路表作成手法として，Short Link Listの実装

と Long Distance Link の密集化の二手法を提案する．以下4.2.1で Short Link List について，

図4.1 送信元ノードから送信先ノードへの距離

4.2.1 Short Link List

Symphony の経路表における Short Linkの拡張リンクとなる．Symphony の Short Link で

は，ハッシュ空間上で増加方向と減少方向の最近接のノードを1つずつ経路表のノードに指定して

いたが， Short Link List では，増加方向と減少方向にn ノードずつ計 2n 個のノードを経路表

に追加した．他のDHTの Chordや，既存研究[1][8]においてSuccessor Listが提案されている

が，Successor Listでは増加方向のノードのみ指定している．これは，経路表の増加を防ぎ，ネッ トワークトラフィックやノードの負荷などのコストを抑えるために取られた措置であると予想され

るが，本手法では，Symphony の Bidirectional Routing Protocolと同じ手法を取ることで，そ

れらのコストは抑えられると考え，減少方向のノードを追加することによる探索効率向上のメリッ トに重きを置く．

4.2.2 Long Distance Linkの密集化

Symphonyの経路表における Long Distance Link の拡張リンクとなる．Long Distance Link

に指定するノードをより近距離に密集化させるため，Long Distance Link の指定先のノードへの

距離にしきい値を設定し，Long Distance Link の密集化を行った．実際には，確率関数 p の平

均値がしきい値を越えた場合，確率関数を再出力させ，しきい値に収まる値になった際に Long

Distance Linkの候補ノードの探索を始める．

への経路表となる等分割リンクを実装した．4.1で示したように，ノード間の通信は近距離に密

集している．そのことから，ハッシュ空間を三分割する位置，つまり，(id + 1/3)∗ 2128 _のハッ

シュ値を管理するノードへの経路表を作成する．等分割リンクは，Long Distance Link と同様に

Bidirectional Routing Protocolの経路表を作成することで，(id + 2/3)∗ 2128 のハッシュ値を管 理するノードへの経路表も作成される．この二つの経路表と自分自身のハッシュ値によってハッ シュ空間が三等分に近似される．

図4.2 ハッシュ空間の等分割リンク

4.3

高速化手法の実験

上述した高速化手法をシミュレーション実験により評価を行う．4.3.1で実験の条件について，

4.3.2でShort Link Listによる高速化の実験について，4.3.3で Long Distance Link の密集化に

よる高速化の実験について，4.3.4で二手法の併用手法の実験について述べる．

4.3.1 実験の条件

探索の高速化についてシミュレーションによる評価実験を行う．実験にあたり，以下の条件で実 験を行う．

• 初期ノードの参加処理が終えた時点から探索が開始される • ノードは新規参加処理，故障などの離脱処理は行わない • 各ノードはユニークなコンテンツを一つずつ所有する • コンテンツの複製や消失は行われない • 探索はネットワーク内に存在するコンテンツのうち100個を無作為に選び探索する • 探索クエリがハッシュテーブルを管理するノードへ到達するまでの探索クエリの平均送信回 数を比較する • 各ノードの管理する経路表の大きさは確率により変化するが，平均18個になるように設定 する(従来手法k = 8を基準とする) また，高速化手法の実装によって経路表を多く持つことになる．経路表を多く持つことで探索効率 は向上するが，各ノードへの負荷が増大する．よって，本実験では各ノードの負荷を同じ条件で実

験を行い比較するため，高速化手法によって経路表が増加する場合，Long Distance Link の定数

kを減らすことで，各ノードの持つ経路表の平均サイズを統一する．

以上の条件で，ノード数が変化したときに探索クエリの平均送信回数がどのように変化するかを グラフにより出力する．

4.3.2 Short Link Listによる高速化の実験

図4.3にノード数を1000から 16000に増加させたときの実験結果を示す．また，各手法のパラ

メータを表4.1に示す．実験においては，Symphony をSYM，Short Link Listによる高速化手

法を手法Aとして表記する．

表4.1 Short Link Listによる高速化実験のパラメータ

SYM SYM+手法A Short Link List 隣接1ノードずつ 隣接3ノードずつ の大きさ (n = 1) (n = 3) Long Distance Link

の大きさ(k) k = 8 k = 6

図4.3から分かるように，従来手法と Short Link Listによる高速化手法の双方においてノード

数の増加によって探索クエリの送信回数が増加していることが分かる．また，Short Link Listに

よる高速化手法の方が，従来手法に比べ，5%ほど探索クエリの送信回数が減っていることに加え

て，ノード数が多いほど効果が大きく現れていることが分かる．ノード数が増えることで，探索に

図4.3 Short Link Listによる高速化手法の比較

したことにより，より効率よく通信できたのではないかと考えられる．

4.3.3 Long Distance Linkの密集化による高速化の実験

Long Distance Linkの密集化による高速化の比較実験を行った．図4.4にノード数を 1000か ら 16000に増加させたときの実験結果を示す．また，各手法のパラメータを表4.2に示す．実験

においては，Long Distance Link の密集化による高速化手法を手法Bとして表記する．

表4.2 Long Distance Linkの密集化による高速化実験のパラメータ

SYM SYM+手法B Short Link List 隣接1ノードずつ 隣接1ノードずつ の大きさ (n = 1) (n = 1) Long Distance Link

の大きさ(k) k = 8 k = 7

密集化のしきい値 0.15

等分割リンク 2ノード

図4.4において，従来手法と Long Distance Linkの密集化による高速化において大きさな差は

見られなかったが，全体では，1%ほどの探索効率の向上が見られた．高速化手法として大きな変

化が見られなかった原因として，Long Distance Linkの密集化による高速化において，密集化と

12.00 11.00 10.00 9.00 主張 回 8.00 雌 監 7.00 ー-SYM 宮 俳 6・00 ー-SYM+A 5.00 4.00 3.00 2.00 1000 2000 4∞口 8000 16000 ノード数

図4.4 Long Distance Linkの密集化による高速化手法の比較

等分割リンクの二つを実装したことから，Long Distance Link全体の距離関係は差し引きで大き

な変化がなかったためだと考えられる．図4.5で示すように，密集化と等分割リンクの別々で実装

した結果は，僅差ではあるが従来手法の方が探索効率が良い結果となった．つまり，密集化と等分

割リンクの双方を実装することで，Long Distance Link は近距離に密集化され，等分割リンクで

は遠距離に対応することで，4.1のシミュレーションでもあまり使用傾向のなかった中距離への経

路表が排除されたことが探索の向上につながったのだと考えられる．

4.3.4 併用手法の実験

4.3.2と4.3.3で行った二手法は，Symphonyの経路表のShort LinkとLong Distance Linkの 独立した経路表の改良を行っているため，二手法は併用して実装することが可能となる．よって， 二手法を併用した手法A+Bについて同様に実験を行う．図4.6にノード数を1000から16000に 増加させたときの実験結果を示す．また，各手法のパラメータを表4.3に示す．実験において，併 用手法は手法A+Bと表記する． 図4.6から分かるように，二手法の併用手法A+Bは，どの手法よりも探索クエリの送信回数が 少ないことが分かる．ただし，ノード数が 16000 の時に性能が低下している．この原因として，

Long Distance Link の定数k が小さくなってしまっているため，全体の経路表に対する Long Distance Linkの割合が半数を割ってしまっていることから，Symphonyの経路表が正しく構築で

きていないことが原因として考えられる．そこで，定数kを増加させることで Symphony 本来の 12.00 11.00 10.00 9.00 主張 回 8.00 雌 監 7.00 ー-SYM 宮 俳 6・00 ー-SYM+B 5.00 4.00 3.00 2.00 1000 2000 4000 8000 16000 ノード数

図4.5 Long Distance Linkの密集化と等分割リンクの比較 図4.6 二手法の併用手法による高速化の比較 12.00 11.00 10.00 9.00 訴 8・00 回 控 艇 7.00 吾、6.00 修ト 5.00 4.00 3.00 2.00 1∞o 2000 12.00 11.00 10.00 9.00 掛_固 8.00 雌 騒 7.00 宮 俳 6・00 5.00 4.00 3.00 2.00 1∞口 2000 4∞o 8000 ノード数 4∞口 8000 ノード数 16000 1

旬

。

。

ー-SYM ーー・SYM+DIVID - SYM+THRE ー-SYM - SYM+A - SYM+畠 ー-SYM+A+B

表4.3 二手法の併用手法による高速化実験のパラメータ

SYM SYM+手法A+B Short Link List 隣接1ノードずつ 隣接3ノードずつ の大きさ (n = 1) (n = 3) Long Distance Link

の大きさ(k) k = 8 k = 5 密集化のしきい値 0.15 等分割リンク 2ノード 経路表を維持しつつ実験を行うことで，探索クエリの送信回数がどのように変化するか検証した． 表4.4に定数k を大きく設定した時のパラメータを示す．また，図4.7にその結果を示す． 図4.7 定数k = 16における高速化手法の比較 図4.7から分かるように，定数k を大きく設定すると，ノード数の増加にともなう探索クエリ送 信回数の増加が抑えられていることが分かる．また，二手法の併用手法A+Bの高速化の影響がよ り大きく現れていることも見て取れる．これにより，定数kの値を大きく取り，Symphony の経 路表の特徴を維持できる環境であれば，本手法により探索の高速化が可能であることが分かった．

表4.4 定数k = 16における高速化手法の実験パラメータ

SYM SYM+手法A+B Short Link List 隣接1ノードずつ 隣接1ノードずつ の大きさ (n = 1) (n = 1) Long Distance Link

の大きさ(k) k = 16 k = 13 密集化のしきい値 0.15 等分割リンク 2ノード

4.4

高速化手法のまとめ

4.3の実験から，本研究で提案した二手法双方で探索効率の向上が見られた．また，二手法は経 路表の構築に必要なノードへの負荷を同条件に近い状態にして比較しているため，本手法はノード への負荷を従来とは変わらずにコンテンツを高速に探索できる手法であることが示された．

ただし，本手法の問題点として，二手法を併用させるためにLong Distance Link の定数kが小

さくなってしまっていることから，ノード数の増加によって高速化の効果が小さくなる可能性が考 えられる．そのため，大規模なネットワークが予想される状況において，ノードの性能が期待でき

る環境であれば，定数kを大きく持つことで，より効率の良い探索の高速化が可能になると考えら

第

5

章

Symphony

の耐故障性向上手法

前章でSymphony の探索の高速化手法について考察したが，いずれの実験も，ノードが参加や 離脱が起こるchurn 状態について考慮しない理想的なネットワークにおける実験であり，現実の ネットワークではノードが予期せずにネットワークから離脱し，二度とネットワークに復帰しない 可能性がある．離脱したノードが所持していたコンテンツも同時に取得できなくなる．また，経路 表の指定先ノードがネットワークから離脱した場合，目的のノードへの経路が構築できなくなる． このような事態を防ぐため，DHTでは，耐故障性に関する研究が進められている．[8][9][10] 本章では，ネットワークの不測の事態に対応するための耐故障性について説明する．5.1では安 定化プロトコルについて，5.2ではchurn状態を含むネットワークにおける探索方法について，5.3 では局所的安定化による耐故障性の向上手法について，5.4では耐故障性の向上手法の評価実験に ついて述べる．

5.1

安定化プロトコル

安定化プロトコルは，DHTにおけるノードの離脱や故障への対策機能である．本研究の実験に おいてシミュレータに実装した安定化プロトコルは，経路表の修復機能，ハッシュテーブルの修復 と複製機能，コンテンツの複製機能の三つである．安定化プロトコルはネットワークに参加する ノードが定期的に実行する． 5.1.1で経路表の修復機能，5.1.2でハッシュテーブルの修復と複製機能，5.1.3でコンテンツの 複製機能について示す． 5.1.1 経路表の修復機能 経路表に指定されたノードがネットワークから離脱した場合，経路表によって予測された理 想的な経路で探索クエリを送信することができなくなる．また，最悪の場合は，経路表すべての ノードへ探索クエリが送信できないことから，探索の失敗となる．それを防ぐために，各ノード は定期的に自己の管理する経路表のノードに対して通信を行い，ノードの生存確認を行う．返答 が無く，タイムアウトしたと判断されたノードは経路表から削除され，ノードは代替となる接続

先を探す．Symphony において修復が必要となる経路表は，Short Linkと Long Distance Link，

Short Linkは探索においてすべてのノードへの接続を保証する経路表となるため，Short Link

の修復はネットワークの維持に重要なプロセスとなる．最も容易な Short Link の修復手法とし

て，近隣のノードから周囲のハッシュテーブルの状況を取得し，適切な隣接ノードを探し出す方法

が用いられる．ChordなどではSccessor List のノードを用いて修復が行われる．よって，本研究

では，高速化手法で実装したShort Link Listから情報を取得し，修復を試みる．Short Link List

の前後情報からノードの配置情報を修復する．また，離脱によって不足したShort Link List を生

存するShort Link List のノードから取得する．

Long Distance Link の修復については特別なプロセスは必要とせず，初期の経路表作成と同様

に確率関数pを用いて代替のノード選択し，登録する． 5.1.2 ハッシュテーブルの修復と複製機能 ノードが離脱することにより，そのノードが分散管理していたハッシュテーブルがネットワーク から失われてしまう．ハッシュテーブルには，コンテンツのハッシュ値と所有者の情報が格納され ているため，ハッシュテーブルを損失するとそのハッシュ値を持つコンテンツの所有者の情報が取 得できず，コンテンツの探索ができなくなる．それを防ぐために，安定化プロトコルの機能として ハッシュテーブルの修復と複製機能を実装する． 事前に，分散管理しているハッシュテーブルが失われないように各ノードが管理するハッシュ

テーブルを複数のノードに複製する．ハッシュテーブルの複製先のノードは Short Link Listの

ノードを使用する．また，隣接するノードは隣接するハッシュテーブルを管理するため，Short

Link Listを使用することにより，ハッシュテーブルの修復においても安易に修復が可能となる．

ハッシュテーブルの修復方法は，Short Linkのハッシュ空間減少方向へのノードの離脱が確認

された時に事前に複製として取得していたハッシュテーブルを自己の管理するハッシュテーブルと

して追加する．その際，再度ハッシュテーブルの複製を作成し，Short Link Listのノードへ複製

する．また，探索において，自己に複製したShort link List のハッシュテーブルを利用すること

で，探索クエリの送信回数を減らすことが可能になる．

5.1.3 コンテンツの複製機能

コンテンツの所有者がネットワークから離脱した場合，コンテンツの交換が不可能になる．新規 に作成されたコンテンツや所有者の少ないコンテンツはネットワーク内に複製を作成し，冗長化さ せる必要がある．

コンテンツの複製方法として，コンテンツの所有者ノードのShort Link Listのノードに複製を

配布する．コンテンツを取得したノードは，そのコンテンツの所有情報をハッシュテーブルに登録 処理をする．そのため，コンテンツの所有者ノードはコンテンツのハッシュ値を管理するハッシュ

テーブルの管理者ノードへ通信を行い，所有情報をハッシュテーブルに記録する．その際，ハッ

シュテーブルの管理者ノードは，5.1.2のプロセスとしてハッシュテーブルの複製を行い，ハッシュ

テーブルの管理者ノードのShort Link Listのノードに複製を配布する．

5.2

churn

状態を含むネットワークにおける探索方法

安定化プロトコルにより，ネットワークの修復は行われるが，コンテンツの探索時に必ずしも安 定化プロトコルが完了していることは保証されない．そのため，churn 状態の影響を受けたまま目 的のノードまで探索クエリを送信することとなる．そのようなネットワークにおける探索では以下 の問題が発生する可能性がある． • 経路表のノードが離脱していることによる探索クエリの送信失敗 • 特定のノード間の探索クエリのループ • ハッシュテーブルを管理するノードが離脱していたことによる探索クエリの送信失敗 • コンテンツの所有者が離脱していたことによる探索クエリの送信失敗 このような問題によって探索クエリがタイムアウトする可能性があり，探索クエリの探索クエリ の送信失敗を以って探索の失敗と判断する場合，探索成功率は著しく低下する．そのため，シミュ レーションに以下の処理を追加し，上述の問題への処理を追加した． 5.2.1 経路表のノードが離脱していることによる探索クエリの送信失敗に対する処理 経路表の候補のノードへの探索クエリがタイムアウトした場合，次の候補へ探索クエリを送 信する処理を加える．図5.1のように 経路表から候補のノードを挙げ，優先順位を決定する．

Lookahead Listを含むネットワークの場合は，自身の経路表のノード毎にLookahead Listのノー

ドへの距離を比較して優先順位を決定する．Lookahead List 経路表のノード一つあたり複数ある

場合がほとんどだが，送信先ノードは経路表のノードへ送信するため，図5.1のNode D やNode

Aのように，Lookahead Listが最短の経路表に対して優先順位を決定する．Lookahead listを使

用しないネットワークの場合は，経路表のノードへの距離を比較して優先順位を決定する．耐故障 性の評価のため，候補のノードへの探索クエリの送信が失敗した場合も探索クエリの送信回数に加 算する． 5.2.2 特定のノード間の探索クエリのループへの処理 図5.2は特定のノード間の探索クエリのループが発生したイメージである．以下の手順が起こる ことで特定のノード間で探索クエリがループする．

図5.1 候補ノードへの優先順位の決定方法 2. ノード Bはより近接なノードC へのクエリを送信するがノードCへの送信が失敗する 3. ノード Bは次の候補となるノード Dへ探索クエリを送信する 4. ノード DはノードCへと探索クエリを送信するが失敗する 5. ノード Dの次の候補となるノードとして ノードA が選ばれる 6. 1 へループする この問題への対処として，探索クエリに経路情報を記録する処理を加える．これにより，探索クエ リが過去に送信されたノードへは送信されなくなり，ループは解消される． 図5.2 特定のノード間の探索クエリのループによる探索失敗例

5.2.3 ハッシュテーブルを管理するノードが離脱していたことによる探索失敗への処理 上述した経路表のノードが離脱していることによる探索失敗に対する処理と特定のノード間の探 索クエリのループへの処理によって，ハッシュテーブルを管理するノードが離脱していた場合，目 的のハッシュテーブルを探すためにその周囲で無意味な探索クエリが送信され続けることが起こり 得る．そのため，探索クエリにTTL(Time to live)を加え，一定値以上の回数の送信があった場 合，探索失敗と判断する． 5.2.4 コンテンツの所有者が離脱していたことによる探索失敗への処理 ハッシュテーブルを管理するノードまで探索クエリが到達した際，所有者情報を探索クエリの送 信元ノードへ返す．所有者は安定化プロトコルの処理によって複数登録されていることが予測され るが，すべての所有者へのコンテンツ交換要求が失敗した場合，探索失敗として処理する． 以上の処理により，耐故障性を最低限確保したネットワークを構成することができる．ただし， 安定化プロトコルの機能は大量のネットワークトラフィックが使用されるため，ノードが常に安定 化プロトコルを実行することは現実的には不可能である．よって，安定化プロトコルは各ノードが 一定間隔毎に定期的に行われる． 以上の処理を基準として，耐故障性向上手法の評価実験を行う．

5.3

局所的安定化による耐故障性の向上手法

本研究では，ノードの参加時に周辺ノードに安定化プロトコルを実行させる手法となる局所的安 定化を提案する． 4.1のシミュレーション実験で述べたように，近距離のノードの関係が探索において重要である と考える．そのため，より近距離のノード同士の経路表やハッシュテーブルに重点を置いて安定化 プロトコルを実行すことで耐故障性が向上するのではないかと考える． 経路表やハッシュテーブルが変化しやすい状況は，ノードの参加離脱時である．ノードの離脱は 他のノードへと離脱情報が知らされない無断離脱の可能性がある．本研究における実験では，ネッ トワークの最悪条件に近い状態で比較することを目指してネットワークから離脱するノードはすべ て無断離脱によりネットワークから切断されるものとする．よって，ノードの離脱時に耐故障性維 持の処理を行うことは困難となる．そのため，経路表やハッシュテーブルの変化を確実に判断でき るノードの参加時に処理を行うことで，耐故障性の向上ができるのではないかと考える．よって， 提案手法としてノードの参加時に周辺ノードに安定化プロトコルを実行させる局所的安定化の手法

局所的安定化の処理は以下のプロセスとなる．

1. 新規参加ノードの参加処理を終える

2. 新規参加ノードのShort Link List のノードに対して局所的安定化プロトコルの要請を行う

3. 局所的安定化プロトコルの要請を受けたノードはShort Link List とハッシュテーブルに関

する安定化プロトコルの処理を行う

4. 新規参加ノードの安定化プロトコルの実行

Short Link Listに対する安定化プロトコルには，ハッシュテーブルの更新も含まれるため，周 囲のハッシュテーブルも最新の状態に更新できる．また，周囲のノードが気づいていなかった隠れ 離脱ノードを発見し，新規参加ノードを正しいネットワーク状況で参加させることができると考 える．

5.4

耐故障性向上手法の評価実験

ノードの参加時に周辺ノードに安定化プロトコルを実行させる局所的安定化の評価実験を行う． 5.4.1で実験の条件について，5.4.2で局所的安定化による耐故障性の評価実験について，5.4.3で 実験の考察について述べる． 5.4.1 実験の条件 耐故障性の評価実験として，通常の安定化プロトコルを実装した Symphonyと局所的安定化を 用いたSymphony について比較を行う．実験にあたり，ネットワークの最悪条件を想定とするた め，以下のプロセスを1 サイクルとしてシミュレーションを行う． 1. 1000ノードをネットワークに参加させ，Symphonyのアルゴリズムでネットワークを構成 させる 2. 各ノードはユニークなコンテンツを一つ所有する 3. 全ノードで安定化プロトコルを実行する 4. 一定数の新規ノードが参加処理を行う(新規ノードはユニークなコンテンツを一つ所有する) 5. 耐故障性向上手法では局所的安定化が行われる 6. 一定数のノードが通知を行わずにネットワークから切断される 7. コンテンツを100個探索し，成功率を算出する 8. 任意の一定数のノードが安定化プロトコルを実行する 9. 4に戻る

安定化プロトコルとして実行されるプロセスは5.1で述べたように，経路表の修復機能，ハッ シュテーブルの修復と複製機能，コンテンツの複製機能の三つである．ネットワークから切断され たノードやコンテンツは二度と復帰しないものとする．また，以下の条件の場合探索失敗として処 理する． • 探索クエリが20ステップを越えた場合 • ハッシュテーブルに記録されたコンテンツの所有者がすべて離脱していた場合 • ノードの持つ経路表のすべてのノードが離脱していた場合 • 経路表のノードがすべて探索クエリにすでに登録されたノードである場合 新規参加ノードが新規登録したコンテンツも探索対象になる．コンテンツの要求者となるルート ノードはネットワーク内に生存する任意のノードから選ばれる．また，コンテンツの探索以外の参 加処理などに必要な探索は必ず成功するものとする． 5.4.2 局所的安定化によるネットワークの耐故障性の評価実験 図5.3に従来手法と局所的安定化の耐故障性の比較実験の結果を示す．また，各手法のパラメー タを表5.1に示す． 図5.3 局所的安定化によるネットワークの耐故障性の評価 局所的安定化では，通常の安定化プロトコルのプロセスに加えて，ノードの参加時にも安定化プ

表5.1局所的安定化によるネットワークの耐故障性実験のパラメータ

SYM SYM+局所的安定化

Short Link List 隣接6ノード 隣接6ノード の大きさ (n = 3) (n = 3) Long Distance Link

の大きさ(k) k = 16 k = 16 1サイクルあたりの参加ノード数 1ノード , 5ノード 1ノード, 5ノード 1サイクルあたりの離脱ノード数 1ノード , 5ノード 1ノード, 5ノード 1サイクルあたりの安定化ノード数 200 100 来手法は1サイクル毎に200ノード，局所的安定化手法では1サイクル毎に100ノードが安定化 プロトコルを行うように設定する． 図5.3におけるx軸はシミュレーションのサイクル数，y軸は探索成功率を示している．参加離 脱ノード数 5 の時は500 サイクル終了時に合計5000 ノードのネットワークへの参加や離脱が発 生していることを示す．頻繁な churn を繰り返すと探索成功率は極端に低下することが分かる． また，500サイクル以降も探索成功率は下降傾向にあった．局所的安定化では探索成功率の低下が 緩やかであることがわかる．また，参加離脱ノード数1 の穏やかな churn において探索成功率は 90%を上回り，耐故障性を維持できていると考えられる． 図5.4 耐故障性実験におけるノードの通信回数

図5.4は同じ実験におけるノード間の通信回数を示している．サイクル数が経過する毎に通信回 数は増加する．これは，探索の失敗が増加していることが原因のもので，ハッシュ値を管理する ノードが発見できず，1つの探索クエリの転送回数が既定値を越えたことによる失敗が多数を占め ていた．探索が成功する場合は高々10回ほどの通信回数で探索クエリが目的ノードに到達できる が，探索失敗の場合は20回の通信回数を要していることが通信回数を増加させている要因となっ た．また，安定化プロトコルによる送信回数は全体の80% を越えたが，1サイクル毎に安定化を 行うノードは一定値であり，また，1サイクルに200ノードが安定化する場合は5サイクルですべ てのノードが安定化を行うため，経路表の修復などによる通信回数は極端に変化することは少ない 傾向にあった． 以上の図5.3と図5.4から，本研究で提案した耐故障性向上手法は，より少ない安定化処理かつ より少ない転送回数でコンテンツ探索の成功率を維持できた．これにより，ハッシュ空間の変化の 段階において，その周辺ノードへ早期に安定化を行わせることで探索効率を維持できることが分 かった． 5.4.3 耐故障性向上のまとめ 実験の結果から，従来の定期的な安定化プロトコルを実行することに加えて，新規ノードの参加 の直後に近隣のノードに安定化を行わせることで，より少ない安定化処理でネットワークを維持で きることが分かった． しかしながら，安定化プロトコルを行っている状態においても，図5.3のように，サイクル経過 毎に探索成功率は徐々に減少している．安定化プロトコルの実行頻度を上げて実験を行ったが，通 信回数が大幅に増加する一方で，探索成功率は大きな向上は見られなかった．実験中のノードの動

作を確認したところ，ハッシュテーブルの管理ノードが他のノードのShort Link List に登録され

ていないことによるネットワークからの孤立状態になっている探索失敗が多数を占めていた．安定

化プロトコルが行われる前にShort Link Listの周辺ノードが大きく変化してしまったことや，安

定化プロトコルによって修復された情報が間違ったまま周囲のノードに共有されてしまった可能性 が考えられる．そのような孤立状況やノードの正確な位置を判断できる機能の実装が今後の課題と なる．

おわりに

本研究では，分散ハッシュテーブルの一種である Symphony のコンテンツ探索を Symphony の経路表をハッシュ空間上近距離に密集化させる手法を用いて拡張する手法を提案した．さらに， churn状態における耐故障性の向上手法として，ノードの参加時に周辺ノードに安定化プロトコル を実行させる手法を提案した．提案手法の有用性を調べるため，シミュレーションによる評価実験 を行った． 高速化手法では，従来手法に比べ，10% の高速探索が可能となり，ネットワークトラフィック 低減にもつながった．耐故障性向上手法では，高速化手法で実装した経路表を応用することで安定 化プロトコルの機能を定義し，高速化手法で応用した経路表が近距離に密集化する特徴を用いて， ハッシュ空間上に近距離に位置するノードの安定化プロトコルを重点的に行うことでより少ない ネットワーク負荷で探索成功率の維持が可能となった． シミュレーションの結果から，穏やかな churn 状態においては高い探索成功率を長期間で維持 できることが示された．また，激しいchurn 状態では，従来手法に比べ探索成功率の減少を抑え ることは可能ではあったが，長期間で激しいchurn が起こった場合は探索成功率が著しく低下し てしまう状態が目立った． 今後の課題として，激しい churn 状態においても長期間で探索成功率を維持できるようにネッ トワークにおけるノードの正確な位置を補完できる手法の導入が求められる．

謝辞

日ごろから多くの御指導を頂きました太田義勝教授，鈴木秀智准教授，テープウィロージャナポ ン・二ワット助教に深く感謝いたします．そして，日頃何かとお世話になりました落合美子事務員 に感謝いたします．また，本論文作成にあたって特にお世話になりました太田義勝教授に深く感謝 いたします．最後に，日頃から熱心に討論して頂いた研究室の諸氏に感謝いたします．

参考文献

[1] Gurmeet Singh Manku， et al.，“Symphony: distributed hashing in a small world”，

Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems USITS 03，2003

[2] Ion Stoica; Robert Morris，David Karger，M. Frans Kaashoek，Hari Balakrishnan，“Chord: A scalable peer-to-peer lookup service for internet applications”，ACM SIGCOMM Com-puter Communication Review (New York，NY，USA: ACM Press) 31 (4): 149 - 160 ，

2001

[3] 江崎 浩，「P2P 教科書」，インプレスR&D，2008 [4] 金子勇，「Winnyの技術」，アスキー，2005

[5] S.Ratnasamy，P.Francis，M. Handley，R.Karp，and S.Shenker: “A Scalable Content-Addressable Network”，In Proc. of ACM SIGCOMM 2001，pp.161-172，2001

[6] B.Zhou，D.A.Joseph，and j.Kubiatowicz，“Tapestry: a fault tolerant wide area network infrastructure.”，In Sigcomm，pp. Tech.Report UCB/CSD-01-1141，2001

[7] P. Maymounkov and D.Mazieres，“Kademlia: A Peer-to-peer Information System Based on the XOR Metric”，In Proc. of IPTPS 2002，pp. 53-65，2002

[8] 福本聡，寺田夢人，新井雅之，“構造化P2P ネットワークの耐故障性に関する考察”，電子情 報通信学会技術研究報告. DC，110(333)，pp.15-20，2010 [9] 首藤一幸，“下位アルゴリズム中立なDHT実装への耐churn手法の実装”，情報処理学会論文 誌コンピューティングシステム，Vol.49，No.2，pp.1-9，2008 [10] 岩尾隆弘，“Chordにおけるchurn状態での耐故障性の向上手法について”，修士論文，三重 大学，2010