分散ハッシュテーブル Symphony の 高速化と耐故障性向上について

分散ハッシュテーブル 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

章では分散ハッシュテーブルについ て，第

3

章では

Symphony

について，第

4

章では

Symphony

の高速化手法について，第

5

章で

第 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

を参照することで

O(1)

で探索が可能となる．

表

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]

に着目をする．次章で

Symphony

の経路表と特徴について示す．

第 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

と最大値

2

¹²⁸

− 1

を連結して リング状のハッシュ空間を構成する．本論文では，便宜上時計回り方向をハッシュ値の増加方向と する．各ノードはハッシュ関数によって任意の値が与えられ，ハッシュ空間に配置される．また，

ノードは

(

ハッシュ値

/2

¹²⁸

)

を

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 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) ∗ 2

¹²⁸のハッシュ値を管理するノードを

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

点 ・

qd

︽v

n u w n v A U n u

︽U

即時率関数P

の 出 力 健

0.2 

。 。

0.1 

0.2  0.4  0.6 

r a n d O

の乱数値

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) ∗ log

²

(N ))

でコンテンツを探索可能であることを証明している．

N

はネットワーク内のノードの総数を，

k

は

Long Distance Link

の定数を示す．定数

k

は実験的に小さな自然数個で十分であり，

k = 8

以上 では探索効率に大きな変化は見られないとされる．

DHT

の中でも一般的で二分木探索に近い探索

図

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.2.2

で

Long Distance Link

の密集化について示す．

図

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

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

Long Distance Link

の密集化に付随して，密集化によって遠距離のノード情報が不足するこ

への経路表となる等分割リンクを実装した．

4.1

で示したように，ノード間の通信は近距離に密 集している．そのことから，ハッシュ空間を三分割する位置，つまり，

(id + 1/3) ∗ 2

¹²⁸ のハッ シュ値を管理するノードへの経路表を作成する．等分割リンクは，

Long Distance Link

と同様に

Bidirectional Routing Protocol

の経路表を作成することで，

(id + 2/3) ∗ 2

¹²⁸ のハッシュ値を管 理するノードへの経路表も作成される．この二つの経路表と自分自身のハッシュ値によってハッ シュ空間が三等分に近似される．

図

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.1

のシミュレーションと同様に，クエリの送信の大半が近距

図

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

，

Bidirectional Routing Protocol

である．

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

のシミュレーション実験で述べたように，近距離のノードの関係が探索において重要である と考える．そのため，より近距離のノード同士の経路表やハッシュテーブルに重点を置いて安定化 プロトコルを実行すことで耐故障性が向上するのではないかと考える．

経路表やハッシュテーブルが変化しやすい状況は，ノードの参加離脱時である．ノードの離脱は 他のノードへと離脱情報が知らされない無断離脱の可能性がある．本研究における実験では，ネッ トワークの最悪条件に近い状態で比較することを目指してネットワークから離脱するノードはすべ て無断離脱によりネットワークから切断されるものとする．よって，ノードの離脱時に耐故障性維 持の処理を行うことは困難となる．そのため，経路表やハッシュテーブルの変化を確実に判断でき るノードの参加時に処理を行うことで，耐故障性の向上ができるのではないかと考える．よって，

提案手法としてノードの参加時に周辺ノードに安定化プロトコルを実行させる局所的安定化の手法