ノード性能を考慮した非対称DHTの提案

特別研究報告
題目
ノード性能を考慮した非対称 DHT の提案
Asymmetric-DHT based on node capabilities
指導教員
植田 和憲 講師
報告者
1115066
川田 量久
平成 21 年 3 月 19 日
高知工科大学 電子・光システム工学コース
目次
第 1 章 序論
1
第 2 章 関連研究
3
2.1
2.2
P2P ネットワークモデル . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.1.1
Unstructured P2P . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.1.2
Structured P2P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
DHT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.2.1
技術概要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.2.2
DHT ルーティングアルゴリズム . . . . . . . . . . . . . . . . . . . . .
9
2.2.3
探索様式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.2.4
Kademlia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2.2.5
Overlay Weaver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
第 3 章 提案手法
3.1
3.2
14
非対称 DHT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
3.1.1
ルーティングテーブル . . . . . . . . . . . . . . . . . . . . . . . . . .
15
3.1.2
ルーティング . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
非対称 Kademlia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
3.2.1
ルーティングテーブル . . . . . . . . . . . . . . . . . . . . . . . . . .
17
3.2.2
ルーティング . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
第 4 章 評価
23
4.1
評価項目と環境 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
4.2
Kademlia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
i
4.3
4.4
4.2.1
系の性能評価 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
4.2.2
負荷分散 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
非対称 Kademlia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
4.3.1
系の性能評価 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
4.3.2
負荷分散 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
4.4.1
get 失敗問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
4.4.2
負荷分散 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
第 5 章 まとめ
32
謝辞
33
参考文献
34
ii
第 1 章 序論
現在、P2P 技術は研究から実用まで多岐にわたって注目を集めている。ファイル共有が
行える Gnutella[1]、Winny[2]、BitTorrent[3]、インターネット通話が行える Skype[4]、地震
情報を伝える P2P 地震情報 [5] などのアプリケーションがすでに実用化されている。また、
DNS など新たな応用分野へ向けての研究も盛んに行われている。
P2P の中でもピュア P2P と呼ばれるモデルはサーバなどの集中管理機構を必要とせず、
ネットワークを構成するノード群がそれぞれ自律的に振舞うことで、維持コストを抑えつつ
ノード数に対して高いスケーラビリティを実現している。ピュア P2P は更に Unstructured
P2P と Structured P2P の二種類に分類できる。研究分野においては、Structured P2P の中で
も特に DHT（分散ハッシュテーブル）の研究が盛んである。Structured P2P は Unstructured
P2P と比べ、検索と負荷分散に対して高い利点がある。しかし、構造的なネットワークを維
持するための通信を必要とするなどの欠点も持っている。
既存 DHT ルーティングアルゴリズムは共通して、ノードが対称的な動作を行うよう設計
されている。しかし、現実にネットワークを構成するノード群の性能は必ずしも均一ではな
く、差があると考えることが普通である。高性能ノードと低性能ノードが同じ働きをし、高
性能ノードが帯域や処理能力などのリソースを余らせ、有効活用できなければ系に対し不利
益である。
そこで本研究では、ノードの性能差に応じた負荷分散と系の通信量削減を目的として、ノー
ドの性能差を考慮してノードの動作を非対称化した非対称 DHT を提案する。非対称 DHT
は既存 DHT ルーティングアルゴリズムに共通しているルーティングテーブルとルーティン
グの働きをノードの性能差に応じて非対称化したものである。高性能ノードは既存 DHT と
あまり変わらない働きだが、低性能ノードは既存 DHT と比べ限られたルーティングテーブ
ルを持ち、その制限を補うため高性能ノードに積極的に働きかける設計になっている。
非対称 DHT は既存 DHT ルーティングアルゴリズムに共通して適用できる規格である。
1
そこで、既存 DHT ルーティングアルゴリズムの一つである Kademlia の設計を非対称 DHT
に基づいて変更した非対称 Kademlia を実装した。また、非対称 Kademlia と Kademlia をエ
ミュレーションによって比較し、通信量と検索性効率、負荷分散について評価した。
2
第 2 章 関連研究
2.1
P2P ネットワークモデル
一極集中型のクライアントサーバモデルに対し、サーバが存在せず、各ノードが自律的に
振舞うネットワークモデルをピュア P2P と呼ぶ。ピュア P2P には、隣接ノードをどのノー
ドにするかの制約が緩い Unstructured P2P と、隣接ノードをどのノードにするか制約があ
る Structured P2P の二種類に大きく分類できる。
P2P を構成するノードはネットワーク全体の知識を持たないため、ノード単体では自分の
知識にないノードに到達する手段を持たない。そのため、P2P には何らかのルーティング機
能が必要になる。
また、新規ノードは既に P2P に参加しているノード（以下ランデブーノード）を経由する
ことで P2P に参加できる。しかし、一般にランデブーノードを探す仕組みを P2P は提供せ
ず、別の手段を用いる必要がある（例えば web ページがランデブーノードのリストを公開す
るなど）。
なお、サーバが存在するネットワークモデルも存在するが、本稿では扱わない。
2.1.1
Unstructured P2P
Gnutella や Winny に代表される、隣接ノードをどのノードにするかに大きな制約が無い
P2P を Unstructured P2P と呼ぶ。ただし、このモデルに厳密な定義があるわけでは無く、一般
に Structured P2P 以外の P2P を Unstructured P2P と指す場合が多い。一般に Unstructured
P2P は検索範囲が限られるが、柔軟な検索が可能な場合が多い。
3
Gnutella
Gnutella[1] は P2P の中でも初期の P2P アプリケーションである。隣接ノードをどのノー
ドにするかに大きな制約が無く、そのネットワークトポロジーは次数にスケールフリー性を
持つことが確認されている [6]。
ルーティングにはフラッディングを使用している。フラッディングとは、隣接ノード全て
にクエリを送信し、クエリを受信したノードも同様に隣接ノードにクエリを送信する処理を、
クエリの TTL が 0 になるまで続けるルーティングである。TTL を大きくすることで確実な
検索が可能であるが、トラヒックが非常に増加するという欠点がある。
Gnutella はそのトポロジーとルーティングから、スケーラビリティに限界があると言われ
ている。
Winny
Winny[2] は Gnutella より後期に登場した日本製の P2P アプリケーションである。隣接ノー
ドをどのノードにするかに一定の制約があり、階層型のネットワークトポロジーとユーザの嗜
好を基にしたクラスタを構成している。そのため Winny は半構造型 P2P とも呼ばれている。
階層上位のノードは下位のノードのインデックスを管理することで、あるクラスタのファイ
ル情報はそのクラスタ階層上位のノードに問い合わせるだけで得ることができる。ルーティ
ングは、階層上位のノードにクエリを転送する「深さ優先探索」を行う。階層上位のノード
はクエリを同じ層のノードのみに転送することで、トラヒックを軽減しつつ検索性能を維持
している。
Winny は階層構造とクラスターによって、限られた検索範囲でも高いスケーラビリティ
を実現している。Winny ネットワークを調査した NetAgent によると、2008 年 12 月 27 日∼
2009 年 1 月 4 日に平均 24 万ノードでの動作が確認されている [7]。
2.1.2
Structured P2P
隣接ノードをどのノードにするかに厳密な制約がある P2P を Structured P2P と呼ぶ。Struc-
tured P2P には DHT と、範囲検索が可能な Skip Graph[8] がある。本稿では特に DHT を第
4
DHT
（P2Pで形成）
コンテンツを取得
（get）
コンテンツを格納
（put）
コンテンツα
コンテンツβ
ユーザA
ユーザB
図 2.1: DHT 概要図
2.2 節で解説する。
2.2
DHT
DHT（分散ハッシュテーブル）とは、P2P において複数のノードがコンテンツを分散管理
するための技術である。DHT は put、get と呼ばれる手続きを規定している。 put はコンテ
ンツを DHT に格納する手続き、get は DHT からコンテンツを取得する手続きである。すな
わち、DHT は例えば巨大なネットワークストレージと見なすこともできる。
DHT の性能は、put、get 手続きの信頼性、システムの維持コスト、負荷分散などで評価
することができる。put、get をより早く、より軽く、より確実に行うため、現在 DHT の研
究が注目を集めている。
図 2.1 に DHT の概要図を示す。図 2.1 のユーザは同時に DHT を形成するノードである場
合が多いが、必ずしもそうである必要はない。
2.2.1
技術概要
DHT では、ノードの ID とコンテンツを同一のハッシュ関数から生成されるハッシュ値（以
下 key）で表現し、同一のハッシュ空間にマッピングすることが基本的なアイディアになる。
これにより、put、get のコストがノード数に対して高いスケーラビリティを実現している。
5
後
前
：ノード
：コンテンツ
：ノードの担当空間
N2 N N3
1
図 2.2: ノードの担当空間
ノードの担当空間
ノードとコンテンツがハッシュ空間にマッピングされた場合、各ノードは自 ID の近くに
いる他ノードの場所によって自分の担当空間が定まる。担当空間内にマッッピングされたコ
ンテンツの value は、そのノードが管理することになる。これにより任意のコンテンツの検
索は、そのコンテンツがマッピングされた空間を担当する ID のノードを検索することと等
しい。
「遠い」といった距離は OSI 参照モデルにおける下位レイ
ここで、DHT における「近い」
ヤと無関係で、DHT ルーティングプロトコル（第 2.2.2 節）によって表現方法が異なる。
図 2.2 に、ハッシュ空間を一次元の円状で表現し、ノードとコンテンツをマッピングした
場合のノードの担当空間の例を示す。この場合、各ノードは自分の一つ後ろにいるノードま
での空間が担当空間になる。また、ノード N1 に最も近いノードは前にいるノード N2 、最も
遠いノードは後ろにいるノード N3 になる。
前述した DHT における put、get は、どちらも「コンテンツの key を管理するノードの検
索」という操作によって実現可能である。すなわち、put はコンテンツの管理ノードにその
コンテンツの key と value（コンテンツ自身か、コンテンツ所持ノードのアドレス）のペア
を格納し、get はコンテンツの key から value を得ることである。次項で put、get に必要な
6
後
前
N1
図 2.3: ノード N1 のルーティングテーブルに格納されるノードの分布
ルーティングテーブルとルーティングについて述べる。
ルーティングテーブル
ノードのルーティングテーブルには、自分以外のノードの ID とアドレス（IP アドレスな
どの位置情報）の対応表が格納されている。ルーティングテーブルには自ノードの ID から
見て近い ID を持つノードほど密に、遠くなるほど疎に格納されている。具体的には、自ノー
ドの ID から見て距離が指数的に離れた他ノードがルーティングテーブルに格納される。
例えばハッシュ空間が 160bit で、自 ID から見て距離が 2k だけ離れたノードをルーティ
ングテーブルに格納する場合、最大で 160 台までノードを格納できる。しかし、ハッシュ空
間上でノードの存在が非常に疎であるため、実際に使用されるルーティングテーブルの数は
O(log N) ほどになる。
図 2.3 にノード N1 のルーティングテーブルに格納されるノードの分布例を示す。ノード
N1 が指し示すノードがノード N1 のルーティングテーブルに格納される。
7
後
(2)
前
(3)
(1)
(4)
C
N1 N3
図 2.4: ノード N1 からノード N3 までの経路
ルーティング
ルーティングには key を使用し、ノードとコンテンツを区別なく検索することが可能であ
る。検索元ノードは自分のルーティングテーブルの中から検索対象の key に最も近いノード
を選択し、クエリを転送する。クエリ転送先ノードでも同様の処理を繰り返し、検索対象を
管理するノードにクエリが転送されるまで続ける。一般に、クエリを一回転送する毎に検索
範囲（検索元ノード ID から key までの距離）を 1/d(d 2) に絞ることができる。そのため
N 台のノードに対して logd (N) のコストで検索が可能である
図 2.4 にルーティングの例を示す。ノード N1 がコンテンツ C を要求した場合、ノード N1
はコンテンツ C の key で検索を行い、コンテンツ C を管理しているノード N3 までクエリが
到達すれば検索が終了する。
DHT は Unstructured P2P と比べ非常にスラービリティが高く、理論上はノードが数億台
以上でも O(log N) のコストでネットワーク全体を検索可能である。しかし、Unstructured
P2P のような柔軟な検索は得意とせず、一般にハッシュ関数による完全一致検索しか行えな
い。他にも負荷分散やノードの参加離脱耐性など、課題は多い。
8
経路
経路
2
2
1
(4)
(2)
(5)
(3)
1
3
(2)
(3)
3
(4)
(6)
(1)
(1)
0
0
反復探索
再帰探索
図 2.5: 探索様式
2.2.2
DHT ルーティングアルゴリズム
過去に発表された DHT ルーティングアルゴリズムの多くは共通して、これまで述べてき
た特徴が挙げられる。
対して相違点は、ハッシュ空間における距離の表現方法などにある。距離が一次元の Chord[9]、
Symphony[10]、多次元の CAN[11]、key の prefix が何文字一致したかで定まる Pastry[12]、
Tapestry[13]、Kademlia[14] などが知られている。
2.2.3
探索様式
Dabek ら [15] によると、各種 DHT ルーティングアルゴリズム（第 2.2.2 節）では実際にク
エリを転送する手続きが共通している。この手続きには反復探索と再帰探索がよく知られて
いる。首藤ら [16] はこれらを総じて探索様式と呼び、遅延、効率、耐攻撃性についてエミュ
レーションにて比較している。
図 2.5 に反復探索と再帰探索の例を示す。図中の経路の求め方は各種 DHT ルーティング
アルゴリズム（第 2.2.2 節）によって異なる。そして求めた経路までクエリを転送する手段
が探索様式によって異なる。
9
反復探索
問い合わせ元ノードが経路上の各ノードに対して自ら問い合わせを行う。クエリの転送は
行わない。
再帰探索
問い合わせ元ノードから経路上の各ノードに対してクエリを順に転送する。再帰検索には
問い合わせ元ノードへの返答の仕方によって 2 通りの通信パターンがあるが、本稿ではこの
解説は省略する。
2.2.4
Kademlia
距離を二つのハッシュ値の XOR とおき、ハッシュ空間を二分木で表現した DHT ルーティ
ングアルゴリズムである。例として 4bit ハッシュ空間にノードをマッピングした様子を図 2.6
に示す。
ノード N 台に対する検索コストは他の DHT ルーティングアルゴリズムと同様に O(log N)
である。ノードの参加離脱に強く、実装が比較的容易といった特徴があるため、多くの P2P
アプリケーション (BitTorrent、LimeWire など) に採用されている。
距離とルーティングテーブル
Kademlia では、距離は XOR によって定義されている。ハッシュ空間が m bit の場合、各
ノードは自 ID と距離が [2i , 2(i+1) ) (0 ≤ i < m) となるノードのリストを所持する。すなわ
ち、距離はハッシュ値 (2bit) が前方から何ビット一致するか、という prefix の一致度と同義
である。
prefix の一致度を距離と定義しているルーティングアルゴリズムとして他に Pastry と Tapestry
がある。Kademlia がハッシュ値を 2bit で表現する事に対し、Pastry と Tapestry は 2 の累乗
bit で表現している。
Kademlia では上述のノードのリストを k -bucket と呼び、ルーティングテーブルとして使
用している。各ノードは k -bucket をハッシュ空間のサイズ m と等しい数だけ所持する。そ
10
4 bit ハッシュ空間にノードをマッピング
1111
0
二分木で表現
：ノード有
1
1
1
1
0
0
0 1
0
1
0 1
1
0
0 1
1
0
1
0
0 1
：ノード無
0
1
0 1
0
0 1
0
図 2.6: Kademlia ノードのマッピング
れぞれの k -bucket は k 個（標準で k = 20）のノードを格納できる。ただし、ハッシュ空間
の中でノードは非常に疎になるため、実際に使用される k -bucket は平均して O(log N) 個で
ある。
図 2.7 にノード [ID=0110] の k -bucket を示す。図は 4bit ハッシュ空間であるで、k -bucket
の数は 4 個になる。
ルーティングテーブルの更新
他ノードから何らかのメッセージを受信した場合、送信ノード (以下エントリーノード) の
ID に該当する k -bucket にエントリーノードを格納するかを判断する。このアルゴリズムを
図 2.8 に示す。
図 2.8 に従うと、k -bucket に優先して格納されるノードは古くからネットワークに存在す
る、古株ノードになる。これは、Gnutella ネットワークの解析によって、ネットワークに新
規参加したノードよりこれまでオンラインだったノードの方が今後もオンラインであり続け
る確率が高いという結果に基づいている [17]。
11
1
1
1
1
0
0
0 1
0
1
0 1
：ノード[0110]
1
0
0 1
i=3
0
1
0
0
1
0 1
i=0
1
0 1
i=1
0
0 1
0
i=2
k-bucket
図 2.7: Kademlia におけるノード [ID=0110] の k -bucket
• エントリーノードが既に該当 k -bucket に格納されている場合
エントリーノードを該当 k -bucket の末尾に加える
• エントリーノードが該当 k -bucket に格納されていない場合
– 該当 k -bucket に空きがある場合
エントリーノードを該当 k -bucket の末尾に加える
– 該当 k -bucket に空きが無い場合
該当 k -bucket の先頭ノードに ping を送信し、オンラインか否かを確認する
∗ オンラインなら
先頭ノードを該当 k -bucket の末尾に移動し、エントリーノードは加えない
∗ オンラインでなければ
エントリーノードを該当 k -bucket の末尾に加える
図 2.8: Kademlia における k -bucket 更新アルゴリズム
12
ルーティング
検索元ノードは key の該当 k -bucket（無ければその周囲の k -bucket）から最大α（標準で
α = 3）個のノードを選択する。α個のノードに対して同時に非同期な反復探索（第 2.2.3
節）を行う。
2.2.5
Overlay Weaver
Overlay Weaver[18] は、Dabek ら [15] の抽象化に従って設計されたオーバレイ構築ツール
キットである。既存 DHT ルーティングアルゴリズムに共通するルーティング処理をアルゴ
リズムから分離することで、容易にアルゴリズムを実装することが可能となった。また、大
規模なエミュレーション機能によって、容易にアルゴリズムの性能評価やアルゴリズム間の
比較を行うことができる。
13
第 3 章 提案手法
既存 DHT ルーティングアルゴリズムは共通して、ノードが対称的な動作を行うよう設計
されている。しかし、現実にネットワークを構成するノード群の性能は必ずしも均一ではな
く、差があると考えることが普通である。高性能ノードと低性能ノードが同じ働きをし、高
性能ノードが帯域や処理能力などのリソースを余らせ、有効活用できなければ系に対し不利
益である。そこで本研究では、ノードの性能差に応じた負荷分散と系の通信量削減を目的と
して、ノードの性能差を考慮してノードの動作を非対称化した非対称 DHT を提案する。
なお、本手法におけるノードの性能とは、ノードの処理能力や回線速度などである。具体
的に何を性能と考えるかはアプリケーションの実装者に委ねる。
非対称 DHT は既存 DHT ルーティングアルゴリズムに共通しているルーティングテーブ
ルとルーティングの働きをノードの性能差に応じて非対称化したものである。高性能ノード
は既存 DHT とほぼ同様の働きであるが、低性能ノードは既存 DHT と比べ限られたルーティ
ングテーブルを持ち、その制限を補うため高性能ノードに積極的に働きかける設計となって
いる。
そこで、既存 DHT ルーティングアルゴリズムの一つである Kademlia の設計を非対称 DHT
に基づいて変更した非対称 Kademlia を実装した。
本章はまず、非対称 DHT の設計を第 3.1 節に示す。次に、非対称 Kademlia の設計を第 3.2
節に示す。
3.1
非対称 DHT
まず、ノードを性能に従って「高性能ノード」と「低性能ノード」の二種類に分類する。
それぞれのノードによって、ルーティングテーブルとルーティングの扱いが異なる。また、
両ノードの比（全ノードに対する高性能ノードの割合）を示す値 p と、低性能ノードのルー
14
ティングテーブルサイズに関係する値 tableSize（後述、変数名は変更予定）、二つの提案手
法固有のパラメータを規定する。
3.1.1
ルーティングテーブル
DHT は構造化されたネットワークを維持するために通信を行っている。例えば Chord で
は定期的な通信を行い、Kademlia では普段の通信を契機に維持のための通信を行う。ネッ
トワークを維持するための通信とは、ノード毎のルーティングテーブルを維持するための通
信と同義である。
非対称 DHT はこの通信量を削減するため、ノードの性能差に応じてルーティングテーブ
ルのサイズに差をつける。具体的な手法を以下に示す。
ルーティングテーブル更新
ルーティングテーブルに空きが無い状態で新規のノード（以下、エントリーノード）を加
えるかどうかの判断は、ノードの性能を基準にする。すなわち、ルーティングテーブル内に
エントリーノードより性能が低いノードが格納されていた場合、そのノードとエントリー
ノードを入れ替える手続きを行う。これ以上の詳細なアルゴリズムは、実装先のルーティン
グアルゴリズムに合わせて設計する。
高性能ノード
既存 DHT と同様に、ハッシュ空間全体の疎密なルーティングテーブルを所有する。
低性能ノード
ノードから見てネットワークの距離が近傍なルーティングテーブルを所有する。これは既
存 DHT の疎密なルーティングテーブルと比較して、「密」な部分だけのルーティングテー
ブルになる。ノードから見てどれだけ離れた距離のルーティングテーブルを所有するかは、
ルーティングテーブル内に高性能ノードが tableSize 個格納されるまで、とする。
15
後
前
N２
：低性能ノード
：高性能ノード
：ノードのルーティングテーブル
N１
図 3.1: 非対称 DHT ルーティングテーブル
従って、低性能ノードのルーティングテーブルのサイズは、ハッシュ空間中に配置される
高性能ノードの場所に依存し、ノード毎に異なる。全ノードに対する高性能ノードの割合が
低いほど、低性能ノードのルーティングテーブルのサイズは大きくなる。
図 3.1 に一次元円状ハッシュ空間における非対称 DHT のルーティングテーブルの例を示
す。この例では高性能ノードは１台だけである。高性能ノード N1 のルーティングテーブル
はハッシュ空間全体を網羅しているが、低性能ノード N2 のルーティングテーブルは高性能
ノード N1 が格納されるまでであるため、小さいサイズとなる。
3.1.2
ルーティング
前節で低性能ノードのルーティングテーブルサイズを小さくしたため、ハッシュ値に従っ
た既存のルーティング手法ではルーティングが完結しない可能性がある。そこで非対称 DHT
はルーティングにも変更を加える。具体的な手法を以下に示す。
16
低性能ノード
key までの距離がルーティングテーブル内に収まる場合、既存 DHT と同様に key に従った
ルーティングを行う。しかし、key までの距離がルーティングテーブルの範囲を超える場合、
ルーティングテーブルの中で性能が高いノードを優先したルーティングを行う。
図 3.2 に一次元円状ハッシュ空間における非対称 DHT のルーティング例を示す。この例
では高性能ノード N1 と低性能ノード N2 が同様のコンテンツ C を要求している。図 3.2.a は
高性能ノードの例を示し、これは既存 DHT と同様である。図 3.2.b は低性能ノードの例を示
し、クエリを最初に高性能ノードに転送し、それ以降の転送は高性能ノードと同様である。
図に示すように、本手法では低性能ノードの場合、最初の転送で key までの距離を大きく
縮めることはなく、検索は付近の高性能ノードに依存する形になる。
すなわち、クエリが低性能ノードに転送されたとき、key が付近にあれば既存 DHT と同
様のルーティングを行う。しかし、key が付近に無ければルーティングテーブルにある高性
能ノードにクエリを転送することになる。
高性能ノード
既存 DHT と同様に、key に従ったルーティングを行う。すなわちクエリの転送先は、ルー
ティングテーブル内で key に最も近いノードとなる。
3.2
3.2.1
非対称 Kademlia
ルーティングテーブル
Kademlia では k -bucket（第 2.2.4 節）と呼ばれるノードのリストをルーティングテーブル
として使用している。そのため、本節では k -bucket を非対称 DHT に従って変更した設計を
示す。
17
後
(2)
C
(3)
N3
前
(1)
：N1からN3までの経路
N２
a.
高性能ノードのルーティング
N１
後
(3)
C
(4)
N3
前
(1)
(2)
：N２からN3までの経路
N２
b.
低性能ノードのルーティング
N１
図 3.2: 非対称 DHT ルーティング
k -bucket 更新
Kademlia のアルゴリズム (図 2.8) と比較して、エントリーノードが該当 k -bucket に格納
されておらず、該当 k -bucket に空きが無い場合の処理が異なる。この時、エントリー候補
ノードが高性能ノードで、かつ該当 k -bucket の先頭ノードが低性能ノードである場合、両
ノードを交換する。それ以外は Kademlia と同様である。
すなわち、Kademlia では古株優先の更新を行うが、本手法では性能優先の更新を行う事
18
になる。
高性能ノード
上記の k -bucket 交換アルゴリズムに従う。
k -bucket の範囲は、Kademlia と同様にハッシュ空間全体をとる。
低性能ノード
まず該当 k -bucket の使用可否を判断する。使用可能なら上記の k -bucket 交換アルゴリズム
に従う。使用不可なら、k -bucket の先頭ノードとエントリー候補ノードを強制的に交換する。
k -bucket の使用可否の判断は、最も自分に近い k -bucket から見て高性能ノードが tableSize
個格納されるまで、とする。すなわち、i が小さい k -bucket のみを管理し、そうでない k -
bucket は維持のための通信を行わない。
図 3.3 に、4bit ハッシュ空間にノードが 8 台（高性能ノード 2 台）配置されている場合
（図 3.3.a）、幾つかのノードが使用できる k -bucket を示す。なお、tableSize=1 である。図
3.3.b が高性能ノード [ID=0011] の k -bucket、図 3.3.（c,d）が低性能ノード [ID=0000,1100]
の k -bucket になる。図に示すように、高性能ノードはネットワーク全体 k -bucket を、低性
能ノードは高性能ノードが格納されるまでの k -bucket を使用できる。また、低性能ノードの
k -bucket の数は高性能ノードがハッシュ空間中に配置される場所によって異なる。
3.2.2
ルーティング
高性能ノード
Kademlia と同様のルーティングを行う。
低性能ノード
key の該当 k -bucket が使用可能なら、Kademlia と同様のルーティングを行う。そうでな
ければ、使用可能 k -bucket 群の中から高性能ノードを優先的に選択する。ここで、k -bucket
19
群からノードを選択する性能以外の基準、すなわち一つの k -bucket に複数の高性能ノードが
格納されている場合や、複数の k -bucket に高性能ノードが格納されている場合、どのノード
を選択するかを本アルゴリズムでは規定しない。
図 3.4 にルーティングの様子を示す。それぞれ、ノードのクエリの転送先を示している。
図 3.4.a は高性能ノードの場合を示し、k -bucket がハッシュ空間全体をカバーしているため
key の該当 k -bucket にクエリを転送している。図 3.4.b は低性能ノードの場合を示し、key の
該当 k -bucket が使用できるため高性能ノードの場合と同様である。図 3.4.c も低性能ノード
の場合を示しているが、図 3.4.b と異なり key の該当 k -bucket が使用できないため、使用で
きる k -bucket の中で高性能ノードを選択している。
20
a.
1
0
ノード8台
1
0
（高性能ノード2台）
をハッシュ空間に 1
0
1
0
マッピング
1
0 1
0 1
0 1
0
1
0
1
1
0
0 1
1
0
0 1
0 1
0
高性能ノード（ID:1000、0011）
b.
1
高性能ノード
[ID=0011]
のk-bucket
1
1
1
0
0
0
0 1
1
1
0 1
0
0 1
1
0
1
0
0 1
i=3
c.
1
1
1
0 1
0 1
0 1
i=0
1
1
0 1
0
0
0 1
1
0
1
0
0 1
1
低性能ノード
[key=1100]
のk-bucket
1
1
1
0 1
0
0 1
1
0 1
i=1
i=0
1
1
0 1
0
i=0
0
0
0
i=1
0
i=1
d.
0
0
0
0
1
i=2
1
低性能ノード
[ID=0000]
のk-bucket
0
0
0 1
1
0
1
0
0
0 1
i=2
図 3.3: 非対称 Kademlia ルーティングテーブル
21
1
0 1
0
0 1
0
a.
1
高性能ノード
[ID=0011]
のルーティング
1
1
1
0
0
0
0 1
1
1
0 1
0
0 1
0
1
0
1
0
0 1
i=3
1
0
0 1
i=2
0 1
i=0
0
i=1
key
b.
1
低性能ノード
[ID=1100]
のルーティング
1
1
1
0
0
0 1
i=1
0
1
1
0 1
0
0 1
i=0
0
1
0
1
0
0 1
1
0 1
0
0 1
0
i=2
key
c.
1
低性能ノード
[ID=1100]
のルーティング
1
1
1
i=1
0
0
0 1
i=0
0
1
1
0 1
0
0 1
1
0
1
0
0
0 1
1
0 1
0
0 1
i=2
key
図 3.4: 非対称 Kademlia ルーティング
22
0
第 4 章 評価
提案手法の有効性を確認するため、Kademlia（第 2.2.4 節）と比較したエミュレーション
を行った。また、提案手法は固有のパラメータ tableSize と、エミュレーション環境 p（高性
能ノード数の割合）を変化させた。なお、エミュレーションには Overlay weaver（第 2.2.5
節）を使用した。
4.1
評価項目と環境
Kademlia と非対称 Kademlia で送受信メッセージ数と検索成功率を比較した。また、非対
称 Kademlia に限り、高性能ノードと低性能ノードの負荷の差（送受信メッセージ数の差）を
比較した。
エミュレーションは 10000 ノードで行い、参加・離脱が無い環境を想定した。エミュレー
ションの具体的なシナリオを以下に示す。
1. 10000 ノードを起動する
2. 1 台のランデブーノード（第 2.1 節）に対し、残り全てのノードが順にネットワークに
参加する
3. ランダムなノードが順に 10000 種類のコンテンツを put する
4. ランダムなノードが順に 10000 種類のコンテンツを get する
送受信メッセージ数と、高性能ノードと低性能ノードの負荷は手順 3 から終了まで計測し
た。検索成功率は手順 4 の get 成功率を計測した。また、以下の全ての計測は同一の環境で
5 回行い、その平均をとった。
23
表 4.1: 1 ノード辺りの平均送受信メッセージ数と検索失敗回数
平均送受信メッセージ数
544
検索失敗回数
40.8
手順 1,2 の期間を計測しない理由は、現実の P2P ネットワークにおいて全てのノードが短
い期間にまとまって参加する振る舞いが不自然であるからである。
提案手法も同一のシナリオを使用し、ノードを割合 p に従って高性能ノード、低性能ノー
ドの二種類に分類した。ただし、ランデブーノードは低性能ノードとおいた。両ノードは第
3.2 節に従って異なる振る舞いをするが、エミュレーション上での性能、処理能力などに違
いは無い。
4.2
4.2.1
Kademlia
系の性能評価
1 ノード辺りの平均送受信メッセージ数と検索失敗回数を表 4.1 に示す。平均送受信メッ
セージ数は、エミュレーションシナリオの手順 3 以降で全ノードの送受信メッセージ数を計
測し、ノード一台辺りの平均を算出したものである。検索失敗回数は、get を 10000 回行い
失敗したものを計測したものである。
次節で述べる非対称 Kademlia の評価は表 4.1 の結果と比較したものである。
4.2.2
負荷分散
ノード毎の送受信メッセージ数を図 4.1 に示す。この結果は 5 回行った実験うち 1 回目の
結果であるが、残り４回も同様の結果を示した。
図 4.1 の縦軸は表 4.1 の平均送受信メッセージ数を 1 とした対数軸で、横軸は縦軸を降順
で並び替えたノード台数を表している。また、図 4.1 において最もメッセージ数が多いノー
ドはランデブーノードであった。
24
図 4.1: Kademlia ノード毎の送受信メッセージ数
図 4.2: 非対称 Kademlia における Get 失敗数比、送受信メッセージ比（p=10%）
4.3
4.3.1
非対称 Kademlia
系の性能評価
非対称 Kademlia の性能評価を図 4.2、図 4.3、図 4.4、図 4.5、図 4.6 に示す。全ノード台数
に占める高性能ノード台数の割合 p が 10%、5%、1%、0.5%、0.1%の 5 通りの場合において、
提案手法固有のパラメータ tableSize を変化させたときの系の性能を評価したものである。
図の縦軸は、表 4.1 の値に対する送受信メッセージ数と Get 失敗数の割合である。横軸は
提案手法固有のパラメータ tableSize である。
25
図 4.3: 非対称 Kademlia における Get 失敗数比、送受信メッセージ比（p=5%）
図 4.4: 非対称 Kademlia における Get 失敗数比、送受信メッセージ比（p=1%）
図 4.5: 非対称 Kademlia における Get 失敗数比、送受信メッセージ比（p=0.5%）
26
図 4.6: 非対称 Kademlia における Get 失敗数比、送受信メッセージ比（p=0.1%）
4.3.2
負荷分散
第 4.3.1 節で評価した全ノード台数に占める高性能ノード台数の割合 p が 10%、5%、1%、
0.5%、0.1%の 5 通りの場合において、高性能ノードにかかる負荷を図 4.7 に示す。
ここで高性能ノードにかかる負荷とは、高性能ノードの送受信メッセージ数の平均値であ
る。図 4.7 の縦軸は、それぞれの系における低性能ノードの送受信メッセージ数に対する高
性能ノードの送受信メッセージ数率（高性能ノード送受信メッセージ数が低性能ノード送受
信メッセージ数の何倍か）である。横軸は本提案手法固有のパラメータ tableSize である。
また、割合 p とパラメータ tableSize を変化させた時でも、それぞれの系におけるノード
毎の送受信メッセージ数の傾向は図 4.1 の場合と近い形を示した。
送受信メッセージ数の多いノードは、図 4.7 の結果から明らかなように高性能ノードが多
くを占めた。しかし、最も送受信メッセージ数が多いノードは kademlia と同様にランデブー
ノードであった。
27
図 4.7: 高性能ノードの負荷
28
4.4
4.4.1
考察
get 失敗問題
第 4.3.1 節より、系の通信量削減は達成できた。しかし、get 失敗回数は状況によって Kadem-
lia と大きな違いが生じた。この原因を考察する。
まず、tableSize が小さければ、高性能ノードの割合 p が 0.1%の時を除いて非常に大きな失
敗回数を示している。この原因は、tableSize が小さいことにより低性能ノードが自分の周囲
で非常に近い距離のルーティングテーブルしか所持しないことにある。あるルーティングの
終了間際、クエリがこの低性能ノードに転送された時、最終的なルーティングを絞り込めな
いためと考えられる。p が 0.1%の時では、高性能ノードが非常に少ないため、tableSize が小
さくとも低性能ノードが十分な大きさのルーティグテーブルを確保したものと考えられる。
図 4.2、図 4.3、図 4.4 では、tableSize が大きいときでも get 失敗回数に大きな変化がある。
まず、図 4.3、図 4.4 では tableSize がある値の範囲で、get 失敗回数が大きく増加している。
このとき、直接的な原因は get 失敗ではなく、put 時のコンテンツ格納に失敗していること
が分かっている。put 失敗とは、コンテンツの key と距離が大きくはなれたノードにコンテ
ンツを格納してしまうことである。すなわち、格納には成功しているが格納ノードの ID が
適切ではないということである。
put 失敗の原因も、直接的にはルーティングテーブルが不完全でルーティング性能が落ち
たことにある。しかし、この問題の本質は tableSize がある範囲の時になぜルーティングテー
ブルが不完全になってしまうことにある。
図 4.2 では逆に tableSize がある範囲で get 失敗回数が大きく減少しているが、この問題も
解明する必要がある。
4.4.2
負荷分散
4.2、4.3 節より、Kademlia と非対称 Kademlia のどちらの系にも、高負荷ノードと低負荷
ノードが発生することがわかる。 Kademlia を含む既存 DHT ルーティングアルゴリズムは
29
ノードを区別しないため、任意のノードが高負荷ノードと低負荷ノードのどちらになるかを
選ぶことはできない。しかし、非対称 Kademlia はノードを高性能ノードか低性能ノードに
分類することで、高性能ノードを高負荷ノード、低性能ノードを低負荷ノードにすることが
可能である。
この結果から、非対称 DHT を現実のネットワークアプリケーションに適用した場合を考察
する。性能をノード側からの申告（ノードのユーザが自発的に申告するか、アプリケーショ
ンが自動的に判断するかはここでは問わない）すれば、系に有効であることは自明である。
また、帯域制御などの技術を応用する例として、プロバイダなどが特定のノードの帯域を確
保し、そのノードを高性能ノードと申告するなども考えられる。
コンテンツの人気度に依存した負荷
非対称 DHT で制御可能な負荷はネットワークを維持するための通信である。そのため、
DHT に格納されたコンテンツの人気度に依存した負荷を直接制御することはできない。間
接的に制御する手法としては、人気コンテンツを所持するユーザが明示的に高性能ノードと
申告すればよい。しかし、この手法を使用するためにはノードが格納しているコンテンツの
人気度をユーザが把握する必要がある。これではユーザに負担を強いる事になる。ユーザの
負担を軽減するためには、コンテンツの人気度をシステム側が把握し、性能の申告を自動化
する手法を確立する必要があると考えられる。
ランデブーノードの負荷
Kademlia、非対称 Kademlia のどちらも、最も負荷が高いノードはランデブーノードであっ
た。ランデブーノードはエミュレーションの参加時に全てのノードから接続されるため、全
てのノードのルーティングテーブルに一度は格納されることになる。
Kademlia では k -bucket に古株ノードを優先して格納する。ランデブーノードは他のどの
ノードから見てもネットワークに最も古くから参加している古株ノードになる。そのため高
負荷になったと考えられる。
30
非対称 Kademlia では、ランデブーノードは低性能ノードとエミュレーション時に定めた
たが、それでも他の高性能ノードより高い負荷だった。これは、非対称 Kademlia の高性能
ノードに高い負荷をかけ、低性能ノードの負荷を軽減するという能力がランデブーノードま
で及ばないということを示している。
31
第 5 章 まとめ
現在、P2P の中でも DHT（分散ハッシュテーブル）と呼ばれる技術が注目を集めている。
DHT は厳密に構造化されたネットワークを形成し、検索と負荷分散などの性能が高い。し
かし、ネットワーク維持の通信が必要だという欠点も持っている。
既存 DHT は共通して、ノードが区別されず対称的に動作している。しかし、現実にネッ
トワークを構成するノードの性能は必ずしも均一ではないと考えるのが普通である。高性能
ノードが低性能ノードと同じ働きをし、帯域や処理能力などのリソースを余らせることは系
に対し不利益である。
そこで本研究では、系の通信量削減を目的として、高性能ノードに負荷が集中するよう
ノードの動作を非対称化させる非対称 DHT を提案した。非対称 DHT は既存 DHT に共通し
ているルーティングテーブルとルーティングの設計をノードの性能差に応じて非対称化した
ものである。
そこで、既存 DHT ルーティングアルゴリズムの一つである Kademlia の設計を非対称 DHT
に基づいて変更した非対称 Kademlia を実装した。また、非対称 Kademlia と Kademlia をエ
ミュレーションによって比較し、通信量と検索性効率、負荷分散について評価した。
エミュレーションは 10000 ノードでの put、get を参加離脱が無い状況で行った。系の性能
として通信量と get 成功回数の二つを観測した。また、系の負荷分散の様子としてノード毎
の通信量を観測した。これらの要素を Kademlia と非対称 Kademlia とで比較した。
エミュレーションの結果から、本研究の目的である通信量を削減することに成功した。し
かし、get 失敗の原因解明が必要である。
32
謝辞
本研究に際して、様々なご指導を頂きました植田和憲講師に深謝いたします。植田和憲講
師には、研究の方向性から実験方法まで、研究全般に対して並々ならぬお力添えを頂きまし
た。ここに重ねて感謝申し上げます。
研究において他分野からの貴重なご意見を頂いた山本真行准教授に感謝いたします。また、
山本准教授には本論文の副査をして頂いたこと、重ねて感謝申し上げます。お忙しい中、副
査を引き受けて下さいました岩下克教授に感謝申し上げます。
また、研究への様々なサポートを快く引き受けてくれた高橋武尊氏、北野雅士氏、畠中紀
行氏、大久保拓哉氏、勝浦大貴氏に感謝いたします。共に助け合って研究に取り組んだ石川
尚志氏、江波友則氏、進藤遼氏、川崎隆裕氏、神矢健一氏、三村健氏、山本恵大氏に感謝い
たします。
33
参考文献
[1] “Gnutella - a protocol for a revolution,” available at http://rfc-gnutella.
sourceforge.net/, (accessed 2009-02-10).
[2] 金子 勇，Winny の技術，株式会社アスキー，2005.
[3] “Bittorrent,” available at http://www.bittorrent.com/, (accessed 2009-02-10).
[4] “Skype,” available at http://www.skype.com/intl/ja/, (accessed 2009-02-10).
[5] “Jisin,” available at http://www11.plala.or.jp/taknet/p2pquake/, (accessed 200902-10).
[6] L. Adamic, R. Lukose, A. Puniyani, and B. Huberman, “Search in power-law networks,”
Physical Review E, vol.64, no.4, p.46135, 2001.
” ，available at http://forensic.netagent.
[7] NetAgent，“Winny ノード数の推移分析，
co.jp/winny node.html, (accessed 2009-01-23).
[8] A. James, and S. Gauri, “Skip graphs,” Proc. of the 14th Annual ACM-SIAM Symp.
on Discrete Algorithms. Philadelphia: Society for Industrial and Applied Mathematics,
vol.384, p.393, 2003.
[9] I. Stoica, R. Morris, D. Karger, M. Kaashoek, and H. Balakrishnan, “Chord: A scalable
peer-to-peer lookup service for internet applications,” Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, pp.149–160, 2001.
34
[10] G. Manku, M. Bawa, and P. Raghavan, “Symphony: Distributed hashing in a small
world,” Proceedings of the 4th USENIX Symposium on Internet Technologies and Systems, pp.127–140, 2003.
[11] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Schenker, “A scalable contentaddressable network,” Proceedings of the 2001 SIGCOMM conference, vol.31, no.4,
pp.161–172, 2001.
[12] A. Rowstron, and P. Druschel, “Pastry: Scalable, Decentralized Object Location, and
Routing for Large-Scale Peer-to-Peer Systems,” Lecture Notes In Computer Science,
vol.2218, pp.329–350, 2001.
[13] B. Zhao, J. Kubiatowicz, and A. Joseph, “Tapestry: An infrastructure for fault-resilient
wide-area location and routing,” Technical Report UCB//CSD-01-1141, UC Berkeley,
2001.
[14] P. Maymounkov, and D. Mazieres，“Kademlia: A peer-to-peer information system
” Proceedings of the 1st International Workshop on Peerbased on the XOR metric，
to-Peer Systems (IPTPS ’02)，vol.258，pp.53–65，2002.
[15] F. Dabek, B. Zhao, P. Druschel, J. Kubiatowicz, and I. Stoica, “Towards a Common API
for Structured Peer-to-Peer Overlays,” LECTURE NOTES IN COMPUTER SCIENCE,
pp.33–44, 2003.
[16] 首藤一幸，加藤大志，門林雄基，土井裕介，“構造化オーバレイにおける反復探索と再
帰探索の比較 (OS-1: ネットワーク, 2006 年並列/分散/協調処理に関する 『高知』サ
マー・ワークショップ (SWoPP 高知 2006)-研究会・連続同時開催-)，
” 情報処理学会研究
報告.[システムソフトウェアとオペレーティング・システム]，vol.2006，no.86，pp.9–16，
2006.
[17] S. Saroiu, P. Gummadi, S. Gribble, et al., “A measurement study of peer-to-peer file
sharing systems,” Proceedings of Multimedia Computing and Networking, vol.2002,
2002.
35
[18] 首藤一幸，田中良夫，関口智嗣，“オーバレイ構築ツールキット Overlay Weaver，
” 情報
処理学会論文誌: コンピューティングシステム，vol.47，pp.358–367，2006.
36