構造化オーバレイにおける経路表の順序関係に基づく
ネットワーク近接性の考慮手法
宮

尾 武

裕†

長 尾

洋

也†

首 藤

一

幸†

Chord をはじめとする従来の分散ハッシュテーブル（DHT）では，経路表の管理をランダムに割り当てられたノード ID に基づき厳密に行っている．そのため，ノード間の通信遅延といったノード
ID 以外の情報を考慮することが難しい．そこで，本研究ではノード ID 以外を考慮しやすいルーティ
ングアルゴリズム設計手法である柔軟な経路表（FRT）に基づき，ネットワーク近接性を考慮したアルゴリズムを設計する手法（PFRT）を開発した．PFRT は，FRT における ID に関する経路表の順序関係 ≤ID を拡張した，ネットワーク近接性を考慮した経路表の順序関係 ≤ID+PR を用いる．
PFRT に基づくルーティングアルゴリズムは，この順序関係 ≤ID+PR に基づき経路表の改良を繰り返すことで経路表を構築していく．PFRT に基づく DHT アルゴリズム PFRT-Chord は，Chord
よりルーティングにおける平均所要時間が約 40% 減少し，PFRT の有効性を示すことができた．

Proximity-aware Structured Overlays
Based on an Order of Routing Tables
Takehiro Miyao,† Hiroya Nagao† and Kazuyuki Shudo†
Existing DHT algorithms such as Chord prescribe which nodes are held in a routing tablebased on the nodes’ ID. The ID restriction is a major obstacle to exploitation of network proximity. We designed Proximity-aware Flexible Routing Tables (PFRT), a routing algorithm
designing methodology by expanding Flexible Routing Tables (FRT). We define an order ofrouting tables ≤ID+PR for PFRT based on FRT’s basic order ≤ID . PFRT updates a routing
table repeatedly according to order ≤ID+PR . We designed PFRT-Chord, a DHT algorithm
based on PFRT. An experiment result shows that average routing latency in PFRT-Chord isabout 40% less than Chord.

1. は じ め にトワーク構築時のルールが一定の数学的ルールに従わずにネットワークを構築し，その技術は Gnutella やGnutella や BitTorrent などのさまざまな P2P ア

BitTorrent などのアプリケーションに用いられていプリケーションが存在する．P2P システムはスケーラ

る．逆に，構造化オーバレイネットワークでは一定のビリティや耐故障性などの点で優れている．P2P ネッ

数学的ルールに従いネットワークを構築する．

トワークのように，物理的に接続された実ネットワー

構 造 化 オ ー バ レ イ ネット ワ ー ク に は Chord1) ，ク上に独自のトポロジで構築されたアプリケーション

Kademlia2) ，Pastry3) などのアルゴリズムが存在し，レベルのネットワークをオーバレイネットワークと呼近年多くの研究がなされている．これらのアルゴリズ

ぶ．オーバレイネットワークによって，非集中であっムは分散ハッシュテーブル（Distributed Hash Table，ても多数のノードをうまく連携させることができる．

DHT）と呼ばれる．DHT とは連想配列を複数のノーオーバレイネットワークは二つに分類することがでドで管理する技術である．非構造化オーバレイネット

きる．一つは非構造化オーバレイネットワークであり，

ワークでは発見のためにフラッディング等が必要とな

もう一つは構造化オーバレイネットワークである．非るが，これらの DHT では，ノード数を N とすると構造化オーバレイネットワークでは，オーバレイネッ

O(log N ) の経路長で効率のよいルーティングを行うことが可能である．大規模な P2P システムではノー† 東京工業大学
Tokyo Institute of Technology

ドが世界中に存在するため，一対一でのノード間の通信遅延はさまざまなものとなる．しかし，従来の DHT

インターネットコンファレンス (IC2011) 論文集, ISSN 1341-870X, pp.41-48, 2011年10月

の多くではハッシュ関数で割り当てられたノード ID

持つデータもまた key に基づき ID が割り当てられ，に基づくルーティングを行うため，ネットワーク近接

ID 空間に配置される．ID 空間上でデータ ID から時性が考慮されていない．その結果，ルーティングにお計回りに進んだとき，一番最初に出会うノードを担当

いて通信遅延が大きなノードと通信を行うことが頻繁

ノードと呼び，担当ノードにそのデータを保存する．

に起こり，ルーティングにおける所要時間を小さくす

データを取り出すときは，目的のデータの key からることができないという問題がある．

ID を生成し，そのデータの担当ノードへたどり着く

ネットワーク近接性を考慮するための方針として，

Proximity Neighbor Selection（PNS），Proximity

まで，各ノードが所持している経路表に基づきノードへの転送（ホップ）を繰り返す．

Route Selection（PRS），Proximity Identifier Se-

Chord には，successor list，predecessor，finger

lection（PIS）が提案されてきた4) ．PNS は経路表構

table の 3 つの経路表がある．ID 空間上で自ノー

築時に，PRS は経路選択時に，PIS はノード ID 決

ドから時計回りに進んだとき，最初に出会うノードを定時にそれぞれネットワーク近接性を考慮する方法でsuccessor と呼び，successor list とは時計回りに進んある．本研究では，PNS に基づいてネットワーク近で出会うノードのノード情報（エントリ）を順番に一接性を考慮する．

定数 c だけ保持する経路表である．反時計回りに進ん

Chord，Kademlia といった従来の DHT では，ノーだとき，最初に出会うノードを predecessor と呼び，

ド ID のみによって経路表に追加するノードを厳密にそのノードをエントリとして経路表に保持する．finger

選択しているので，PNS に基づいてネットワーク近接

table とは自ノード s から 2i（i = 0, 1, ..., m − 1）の性を考慮することが難しい．そこで，ノード ID 以外を距離だけ離れた ID の担当ノードを i 番エントリとし考慮しやすいルーティングアルゴリズム設計手法であて保持する経路表である．ノード x からノード y のる柔軟な経路表（Flexible Routing Tables, FRT）5)

ID 距離 d(x, y) を次のように定義する．

{

を利用する．FRT では，ID に関する経路表の順序
関係 ≤ID に基づき経路表の改良を繰り返す．FRT にd(x, y) =おける ID に関する経路表の順序関係 ≤ID を拡張し

y − x,(x < y)y − x + 2m ,(y ≤ x)(1)て，ネットワーク近接性を考慮した経路表の順序関係

Chord は，successor によってルーティングにおけ≤ID+PR を定義し，≤ID+PR に基づき経路表の改良をる目的ノードへの到達性を保証し，finger table によっ

繰り返すネットワーク近接性を考慮した柔軟な経路表てルーティングにおけるノードの転送回数（経路長）（Proximity-aware Flexible Routing Tables，PFRT）を減少させる．これらの経路表により，Chord はノーを提案する．

ド数を N とすると，ルーティングにおける経路長がPFRT に基づく DHT アルゴリズムである PFRT-O(log N ) で目的ノードへ到達することが可能となる．

Chord の実装・評価を行った．PFRT-Chord は FRT

2.2 LPRS-Chordに基づく DHT アルゴリズムである FRT-Chord を素LPRS-Chord6) はネットワーク近接性を考慮する

直に拡張した DHT アルゴリズムである．そのため，

ように Chord を拡張した DHT アルゴリズムである．

FRT-Chord の経路表サイズの変更可能などの特長を

LPRS-Chord では，PNS に基づく拡張，つまり経路継承している．

表構築時にネットワーク近接性を考慮している．

PFRT-Chord では，ルーティングにおける平均所要Chord の 3 つの経路表のうち finger table をネッ

時間が Chord より約 40% 減少した．よって，PFRT

トワーク近接性を考慮するように拡張する．つまり，はネットワーク近接性を考慮したルーティングアルゴ

successor によってルーティングにおける目的ノード

リズムの設計手法として有効であることを示すことがへの到達性を保証しつつ，拡張した finger table によできた．

り Chord と同等の経路長を達成し，またルーティン

2. 関 連 研 究グにおける 1 回の転送（1 ホップ）あたりの平均所
要時間を減少させる．その結果，LPRS-Chord にお本研究の関連研究を次に示す．

けるルーティングにおける平均所要時間が減少する．

2.1 Chord

LPRS-Chord の拡張した finger table は次の通りで

Chord

1)

は DHT アルゴリズムのひとつである．m

ビットのリング上の ID 空間にハッシュ関数により IDが割り当てられたノードを配置する．key と value を

ある．

(1)

他のノードと通信を行ったとき，ノード間の通信遅延を計測する．

インターネットコンファレンス (IC2011) 論文集, ISSN 1341-870X, pp.41-48, 2011年10月

(2)2i ≤ d(s, n) < 2i+1 を満たすノード n のうち，知りえたエントリをすべて経路表に追加する．エント

自ノード s との通信遅延の最も小さいノードをリ情報学習操作は次の場合にエントリを学習する．

finger table の i 番エントリとして保持する．

• ネットワーク参加時に他のノードから経路表の全

2.3 柔軟な経路表

エントリを学習する．

柔軟な経路表（Flexible Routing Tables，FRT）5)• ノードの探索時等において通信したノードのエン

は，ID に関する経路表の順序関係 ≤ID に基づき経路表の改良を繰り返すことで経路表を構築するルーティ

トリを学習する．

• 能動学習探索を行い，通信したノードのエントリ

ングアルゴリズム設計手法である．

を学習する．
能動学習探索は，現在の経路表より ID に関する経

2.3.1 FRT-Chord
FRT-Chord5) は FRT に基づき設計された DHT

路表の順序関係 ≤ID に基づき優れた経路表を構築す

アルゴリズムである．Chord と同様に m ビットのリるために，必要なエントリを学習するルーティングでング上の ID 空間を持ち，担当ノードの決定法も同じある．現在の経路表から計算された ID へのルーティであるが，経路表の構築方法が異なる．FRT-Chord

ングを行う．

には，Chord の successor list，predecessor，finger

table の 3 つの経路表を 1 つに統合した経路表 E が2.3.1.4 エントリ厳選操作
FRT-Chord では，経路表 E のエントリ数 |E| が経
路表サイズ L を超えるとき，|E| ≤ L になるように経ある．
経路表 E はエントリ ei の集合 {ei } である．自ノー

路表のエントリを厳選する操作をエントリ厳選操作とド s の経路表エントリ ei はノード ID ei .id および呼ぶ．エントリ厳選操作では，次の式を満たすエント

IP アドレス ei .address を保持している．d(s, ei ) <リ er の削除を行う．

d(s, ei+1 )(i = 1, 2, ..., |E| − 1) を満たしている．このとき，e1 は successor，{ei }i=1,2,...,c は successor list，

E − {er } ≤ID E − {e}2.3.1.1 ≤ID ：ID に関する経路表の順序関係

SiE = log

≤ID は ID に関する経路表の優劣を表す順序関係である．順序関係 ≤ID に基づき優れた経路表ほどルー

FRT-Chord では，自ノード s が経路表エントリ ei
へフォワーディングを行った際，残り ID 距離の短縮
倍率の最悪値を ri (E) とする．

{ri (E)} を降順に並べた列を {r(i) (E)} とすると，次のように ID に関する経路表の順序関係を定義する．

の式を満たす経路表 Ẽ を最良経路表と呼ぶ．

for ∀EE+ SiE が最小となるエントリ
削除エントリは Si−1

効率よく削除エントリ探索することができる．

FRT-Chord では，Chord における successor list
entry と呼び，エントリ厳選操作による経路表からのエントリ削除を行わない．FRT-Chord におけるエントリ厳選操作は次の通りである．

(1)

(4)

2.3.1.2 到達性保証操作
FRT-Chord では，ルーティングにおける目的ノードへの到達性を保証するための操作を到達性保証操作

削除候補のエントリ集合 C に経路表 E の全エントリを追加する．

(3)

ただし，≤dic とは辞書式順序である．このとき，次Ẽ ≤ID E(6)および predecessor にあたる経路表エントリを sticky(i = 1, 2, ..., |E| − 1)(2)

E ≤ID F ⇐⇒ {r(i) (E)} ≤dic {r(i) (F )}d(s, ei+1 )d(s, ei )E
ei である．Si−1+ SiE を昇順に保持しておくことで，ティングにおける経路長が短くなる．

d(ei , ei+1 )d(s, ei+1 )(5)に正規化間隔 SiE を定義する．

e|E| は predecessor を表している．

ri (E) =for ∀e ∈ E

削除エントリを効率よく見つけるために，次のよう(2)C から sticky entry を除外する．

(3)E
C のエントリの中で Si−1
+ SiE が最小となるエントリ ei を経路表から削除する．

3. PFRT：ネットワーク近接性を考慮した柔軟な経路表と呼ぶ．これは Chord の stabilize 操作にあたる操作

ネット ワ ー ク 近 接 性 を 考 慮 し た 柔 軟 な 経 路 表である．この操作により successor を常に最新に保ち，（Proximity-aware Flexible Routing Tables，PFRT）

Chord と同等の到達性を保証する．

は，ネットワーク近接性を考慮した経路表の順序関係

2.3.1.3 エントリ情報学習操作≤ID+PR に基づき経路表の改良を繰り返すことで経路

FRT-Chord では，エントリを学習する操作をエン表を構築するルーティングアルゴリズム設計手法であトリ情報学習操作と呼ぶ．この操作により，ノードがる．ただし，≤ID+PR は，FRT の ID に関する経路表

インターネットコンファレンス (IC2011) 論文集, ISSN 1341-870X, pp.41-48, 2011年10月

の順序関係 ≤ID をネットワーク近接性を考慮するよ

3.1.2 到達性保証操作

うに拡張した順序関係である．

FRT-Chord の到達性保証操作と同じである．
3.1.3 エントリ情報学習操作

3.1 PFRT-Chord
PFRT-Chord は PFRT に基づき設計された DHT

PFRT-Chord ではエントリの学習を行うために，

アルゴリズムである．FRT-Chord を素直に拡張して

FRT-Chord のエントリ情報学習操作を拡張した操作いるため，経路表を構築する方法以外は FRT-Chordを行う．PFRT-Chord では，経路表エントリ ei にのアルゴリズムを用いている．自ノード s の経路表エei .latency を追加しているので，エントリを学習する

ントリ ei は ID および IP アドレスの他にノード s と際に，ei .latency を記録する．通信遅延が自然に得ら

ei との間の通信遅延 ei .latency を保持している．

れない場合，自ノードとの通信遅延を計測する．エン

3.1.1 ≤ID+PR：ネットワーク近接性を考慮した経路表の順序関係PFRT では，経路長を短くするために ID を考慮す

トリ情報学習操作は次の通りである．

(1)

エントリ情報学習操作を行う．

(2)

手順 (1) で経路表に追加したエントリを最新追るだけでなく，1 ホップあたりの所要時間を小さくするために自ノードとの通信遅延も考慮する．そこで，
まず自ノードとの通信遅延に関する経路表の順序関係≤PR を定義する．次に，≤ID および ≤PR を用いることで，ネットワーク近接性を考慮した経路表の順序関係 ≤ID+PR を定義する．

加エントリ enew として記憶する．
最新追加エントリ enew はエントリ厳選操作において利用される．

3.1.4 エントリ厳選操作
PFRT-Chord ではエ ントリを厳選する ために，
FRT-Chord のエントリ厳選操作を拡張した操作を行

3.1.1.1 ≤PR ：自ノードとの通信遅延に関する経路表の順序関係

う．≤ID は全順序関係であるため，FRT-Chord では最善の削除エントリ er を決定することができた．しか≤PR は自ノードとの通信遅延に関する経路表の優し，≤ID+PR は半順序関係であるため，PFRT-Chord

劣を表す順序関係である．順序関係 ≤PR に基づき優では一般に最善の削除エントリ er を決定することがれた経路表ほどルーティングにおける 1 ホップあた

できない．そこで，まず経路表エントリのうち，順序りの平均所要時間が小さくなる．自ノードとの通信遅関係 ≤ID+PR および最新追加エントリ enew を用いて

延に関する経路表の順序関係 ≤PR を次のように定義削除エントリの候補集合 Cr に絞る．

Cr = {e ∈ E | E−{e} ≤ID+PR E−{enew }}(10)する．

E ≤PR F ⇐⇒ l(E) ≤ l(F )(7)ただし，l(E) は経路表 E の各エントリ ei と自ノー

次に，Cr の中で順序関係 ≤ID に基づき削除するエ
ントリ er ∈ Cr を決定する．

E − {er } ≤ID E − {e}ドとの通信遅延 ei .latency の平均値であり，次のよう

1 ∑ei .latency
|E|

(11)

存在する．er を削除した経路表は，最新追加エントリ|E|l(E) =for ∀e ∈ Cr

enew ∈ Cr より Cr ̸= ϕ である．つまり，er は必ずに定義される．

(8)i=1

3.1.1.2 ≤ID+PR の定義

enew を追加する前の経路表よりネットワーク近接性を考慮した経路表として優れているか，または同じ経路表である．

≤ID+PR はネットワーク近接性を考慮した経路表のエントリ厳選操作の手順は次の通りである．ただし，優劣を表す順序関係である．順序関係 ≤ID+PR に基づ

sticky entry のうち successor list サイズを c とする．

き優れた経路表ほどルーティングにおける所要時間が(1)小さくなる．経路長が減少し，1 ホップあたりの所要削除候補のエントリ集合 C に経路表 E の全エントリを追加する．

時間が減少するとき，ルーティングにおける所要時間(2)

C から sticky entry を除外する．

は確実に減少する．そこで，≤ID+PR を次のように定(3)ノード間の通信遅延の閾値となるエントリを閾義する．

値エントリ et とすると，

 ec+1 ,E ≤ID+PR F ⇐⇒ (E ≤ID F )∩(E ≤PR F )(9)E ≤ID F および F ≤PR E の両方を満たす経路表

et =E, F が存在するとき，経路表 E, F を順序関係 ≤ID+PR

newに基づき比較することができない．つまり，≤ID+PR
は半順序関係である．

e

|E|−1

 e ,

(4)

(enew ∈ {ei }i=1,2,...,c ),(enew = e|E| )otherwiseet ∈ C ならば C から {e ∈ C | e.latency <インターネットコンファレンス (IC2011) 論文集, ISSN 1341-870X, pp.41-48, 2011年10月(12)累積分布関数

0.8
0.6
0.4

0.2
0
0

200

400

600

800

1000

ルーティングの平均所要時間(ms)

1

3500
3000
2500
2000
1500
1000

500
0
Chord

ノード間の通信遅延(ms)

図 1 ノード間の通信遅延の分布
Fig. 1 CDF of communication latency

LPRS-Chord

FRT-Chord

PFRT-Chord

DHTアルゴリズム

図 2 各 DHT アルゴリズムの平均所要時間
Fig. 2 Average elapsed time for routing of Chord, LPRSChord, FRT-Chord and PFRT-Chord

et .latency} を除外する．
(5)E
C のエントリの中で Si−1
+ SiE が最小となる

ルにより，実ネットワークのトポロジをシミュレート

エントリ ei を経路表から削除する．

した．TS モデルはトランジットノードとスタブノー最新追加エントリ enew が sticky entry の場合はドの 2 種類のノードで構成されている．トランジット

enew を削除することができないので，enew を追加す

ノード間，トランジット・スタブノード間およびスタることで sticky entry からあふれたエントリを閾値エ

ブノード間の通信遅延を 100 ms，20 ms，5 ms とし，ントリ et にする（手順 (3)）．経路表サイズを変更し一対一でのノード間の通信遅延を決めた．その結果，たいとき，エントリ厳選操作を連続して実行する場合

ノード間の通信遅延の分布は図 1 となり，通信遅延のがある．その場合，enew が経路表から削除されたこと

平均値は 470 ms，最大値は 1000 ms となった．

により，経路表内に存在せず，enew = et ̸∈ C が起こ
りうる．このとき，自ノードとの通信遅延に基づく C
からのエントリ除外を行わない（手順 (4)）．

4.2 実 験 結 果
4.2.1 節でネットワーク近接性を考慮した DHT ア
ルゴリズムとして PFRT-Chord が有効であることを手順 (1)，(2) および (5) は FRT-Chord のエント示し，4.2.2 節で想定した通りに経路表の改良がされ

リ厳選操作である．PFRT-Chord により拡張した手ていることを示す．また，4.2.3 節で PFRT-Chord のE
順は手順 (3) および (4) である．Si−1+ SiE を昇順に

経路表サイズを変化させたときのルーティングにおけ保持し，上から閾値エントリ et の通信遅延以上である平均所要時間と平均経路長を調べる．これらの実験

るかを調べることで，削除エントリの探索をすることに使用したパラメータは次の通りである．

ができる．経路表サイズを L としたとき，削除エント• ノード数：N = 10000

リの探索は O(L) で終了する．

• 探索回数：1 ノードあたり 100 回

4. 評

価

オーバレイ構築ツールキットである Overlay Weaver7)8)• successor list サイズ：c = 4
4.2.1 PFRT の有効性
図 2 に，PFRT-Chord と他の DHT アルゴリズム

上に，PFRT-Chord を実装した．一台のマシン上でのルーティングにおける平均所要時間を示す．他のシミュレーションによる実験・評価を行った．ルーティ

DHT アルゴリズムと平均所要時間を比較することで，ングにおける所要時間は，全ホップの通信遅延の総和

PFRT-Chord の有効性を示す．比較対象は Chord，である．実験に使用したマシンは次の通りである．

LPRS-Chord および FRT-Chord である．

• Overlay Weaver 0.10.1

Chord および LPRS-Chord では finger table のサ• OS：Windows 7 Professional 32 bit

イズは変更できない．そこで，経路表サイズの変更可• CPU：Intel 2.67 GHz Core 2 Quad Q9400

能な FRT-Chord および PFRT-Chord の経路表サイ• メモリ：4 GB

ズを Chord および LPRS-Chord の経路表に載るエ• Java SE 6 Update 22

ントリ数に合わせた．finger table に載るエントリ数

4.1 ノード間の通信遅延の設定

は log N と計算できるので，約 13 である．succes-

ノード間の通信遅延を設定するために，Transit-

sor list および predecessor を加えると Chord およびStub モデル（TS モデル）9) を利用した．TS モデ

LPRS-Chord の経路表に載るエントリ数は約 18 とな

インターネットコンファレンス (IC2011) 論文集, ISSN 1341-870X, pp.41-48, 2011年10月

8
6
4

FRT-Chord
PFRT-Chord

2
0
0

20

40

60

80

100

1ノードあたりのクエリ数

エントリとの平均通信遅延(ms)ルーティングの平均経路長

10

500
400
300
200

FRT-Chord
PFRT-Chord

100
0
0

20

40

60

80

100

1ノードあたりのクエリ数

図 3 実行クエリ数と平均経路長の関係
Fig. 3 Correlation between number of lookups andaverage route length

図 4 実行クエリ数と経路表エントリの平均通信遅延の関係
Fig. 4 Correlation between number of lookups andaverage communication latency to entry node

る．PFRT-Chord が有利にならないようにするため化を確認する．図 3 および図 4 に，各クエリ実行回に，FRT-Chord および PFRT-Chord では経路表サ数に対する平均経路長および平均通信遅延を示す．1

イズ L = 16 とした．

ノードあたり 10 クエリ実行する毎に平均経路長およPFRT-Chord でのルーティングにおける平均所要び平均通信遅延を測定した．

時間は 1930 ms であった．まず，Chord と比較する．

まず，図 3 からルーティングにおける平均経路長のChord の平均所要時間は 3180 ms であることから，変化を確認する．PFRT-Chord では，実行したクエ

PFRT-Chord により約 40 % 減少した．この結果か

リ数が増加するにつれて，平均経路長が減少している．

ら，PFRT-Chord はネットワーク近接性を考慮した

よって，エントリ厳選操作によって平均経路長が減少

DHT アルゴリズムとして有効であるといえる．

していることがわかる．また，10 番目のクエリを実次に FRT-Chord と比較する．FRT-Chord の平均

行するまでの間に平均経路長が大きく減少し，それ以所要時間は 2930 ms であることから，約 35 % 減少

降のクエリでは緩やかに減少し続け，100 番目のクエした．この結果から，PFRT は FRT に基づく DHT

リを実行するときにはほとんど減少していない．つまアルゴリズムをネットワーク近接性を考慮するように

り，PFRT-Chord の経路表は収束していないが，少拡張する手法として有効であるといえる．

ないクエリ数で収束後の経路表に大きく近づくことが最後に LPRS-Chord と比較する．LPRS-Chord のできる．さらに，FRT-Chord とほぼ同じ変化である

平均所要時間は 1780 ms であることから，約 8 % 増ので，PFRT-Chord に拡張することによる平均経路加した．しかし，平均所要時間の差は約 150 ms であ長の損失がほとんどないといえる．

り，これはノード間の通信遅延の平均値の 3 分の 1 以

次に，図 4 から平均通信遅延の変化を確認する．

下に過ぎない．また，LPRS-Chord の経路表は finger

PFRT-Chord では，実行したクエリ数が増加するにtable であり，経路表サイズは変更できないが，一方つれて平均通信遅延が減少している．このことから，

PFRT-Chord は FRT の特長を引き継ぎ，経路表サ

エントリ厳選操作によって平均通信遅延が減少していイズの変更が可能なので，経路表サイズを大きくする

ることがわかる．また，10 番目のクエリを実行する

ことで平均所要時間を短縮することも容易である．さまでの間に平均通信遅延が大きく減少し，それ以降のらに，PFRT-Chord は他にも FRT の特長を引き継クエリでも減少を続けている．つまり，PFRT-Chord

いでいるため，LPRS-Chord より優れた DHT アルの経路表は平均通信遅延が収束するために，平均経路

ゴリズムであるといえる．

長が収束するよりたくさんのクエリを実行する必要が4.2.2 PFRT-Chord の経路表改良の効果あるが，少ないクエリ数で収束後の経路表に大きく近PFRT-Chord では，≤ID+PR に基づき経路表の改づき，クエリ数を増やすことでより経路表をより改良

良を繰り返しているので，経路表を改良するごとにすることができる．さらに，FRT-Chord より常に平ルーティングにおける平均経路長が減少し，各エント

均通信遅延が小さく，100 番目のクエリを実行するとリの自ノードとの通信遅延の平均値（以下，平均通信

きに約 50 % 減少しているので，PFRT-Chord に拡遅延）が小さくなると想定している．そこで，経路表張することで大きく減少させることができるといえる．

を改良するごとに平均経路長および平均通信遅延の変PFRT-Chord では，経路表を改良するごとに，ルーインターネットコンファレンス (IC2011) 論文集, ISSN 1341-870X, pp.41-48, 2011年10月

6

ルーティングの平均経路長

ルーティングの平均所要時間(ms)

3000
2500
2000
1500

FRT-Chord
PFRT-Chord

1000

500
0

5
4
3

FRT-Chord
PFRT-Chord

2

1
0

0

20

40

60

80

100

120

140

160

0

20

経路表サイズ

図 5 経路表サイズと平均所要時間の関係
Fig. 5 Correlation between averageelapsed time forrouting and size of routing table

40

60

80

100

120

140

160

経路表サイズ

図 6 経路表サイズと平均経路長の関係
Fig. 6 Correlation between average route length and sizeof routing table

ティングにおける平均経路長および平均通信遅延が減

サイズが 20 のときは PFRT-Chord の平均所要時間

少していることから，≤ID+PR に基づき想定通りに経は FRT-Chord に比べ約 30 % 減少していたが，経路路表が改良されていることを確認することができた．

表サイズが 100 のときは約 10 % の減少である．よっ

4.2.3 経路表サイズの変更て，経路表サイズを大きくするにつれて，FRT-Chord

PFRT-Chord は FRT の特長を継承しているため，を PFRT-Chord に拡張することによるルーティング

経路表サイズの変更が可能である．そこで，図 5 およにおける平均所要時間の短縮効果が小さくなっている．

び図 6 に，経路表サイズを変化させたときのルーティ

図 6 から，PFRT-Chord および FRT-Chord のルー

ングにおける平均所要時間および平均経路長を示す．

ティングにおける平均経路長を比較する．経路表サイ

FRT-Chord および PFRT-Chord の経路表サイズをズが変化しても，PFRT-Chord の平均経路長は FRT-

20 から 160 まで変化させ，平均所要時間および平均

Chord とほとんど同じ変化をしていることがわかる．

経路長を測定した．

よって，経路表サイズを変化させても，FRT-Chord

図 5 より，PFRT-Chord は経路表サイズが 25 のとき，ルーティングにおける平均所要時間が 1760 ms

を PFRT-Chord に拡張することによる平均経路長の損失がない．

であることがわかる．4.2.1 節で実験を行った LPRS-PFRT-Chord および FRT-Chord の経路表サイズ

Chord は 1780 ms であるため，PFRT-Chord は経路を大きくしたとき，平均経路長の差がほとんどないに

表サイズが 25 を超えると LPRS-Chord より平均所もかかわらず，平均所要時間の差が小さくなっている

要時間が小さくなる．LPRS-Chord では，finger ta-

ことがわかる．つまり，経路表サイズが大きくなるに

ble に載るエントリが約 13 であっても，配列といっ

つれて，PFRT-Chord の 1 ホップあたりの平均所要

た単純な実装では 160 エントリ分のメモリを消費す

時間が増加しているといえる．これには 2 つの原因

る．一方，PFRT-Chord では，経路表サイズが 25 のが存在する．1 つ目の原因は，平均経路長が短くなる

ときは 25 エントリ分だけメモリを消費する．つまり，ことにより，目的ノードに到達するために successor

平均所要時間が同等なとき，PFRT-Chord の方がメ

list にあるノードへの転送回数が経路長全体に対してモリの消費量が小さいといえる．また，FRT-Chord

増加するからである．successor list は自ノードとのが LPRS-Chord と同等の平均所要時間になるために通信遅延を考慮していないノードをエントリとしては，経路表サイズが 140 必要である．このことからも保持しているため，1 ホップあたりの平均所要時間はFRT-Chord を PFRT-Chord に拡張することによる

FRT-Chord および PFRT-Chord ともに等しい．2

ルーティングにおける平均所要時間の短縮効果が確認

つ目の原因は，PFRT-Chord は自ノードとの通信遅できる．

延だけでなく，ノード ID も考慮して経路表を構築しPFRT-Chord および FRT-Chord のルーティングているので，経路表サイズが大きくなることにつれ，における平均所要時間を比較する．経路表サイズを大自ノードとの通信遅延の大きいノードをエントリとしきくするにつれて，FRT-Chord および PFRT-Chordて保持することが増えるからである．そのため，経路の平均所要時間は小さくなるが，FRT-Chord の減少

表エントリの自ノードとの通信遅延の平均値の増加し，量に比べ，PFRT-Chord の減少量が小さい．経路表

1 ホップあたりの平均所要時間が増加する．

インターネットコンファレンス (IC2011) 論文集, ISSN 1341-870X, pp.41-48, 2011年10月

5. ま と め
ノード ID 以外を考慮しやすいルーティングアルゴリを定義することが可能である．このような，単独または複数の ID 以外の情報を考慮するように柔軟な経路表を拡張することが課題である．

ズム設計手法である柔軟な経路表（FRT）を拡張した，

謝辞 本研究は科研費（22680005）の助成を受けた

ネットワーク近接性を考慮した柔軟な経路表（PFRT）

ものである．また，本研究成果の一部は，独立行政法を提案した．PFRT は，ネットワーク近接性を考慮し

人情報通信機構（NICT）の委託研究「新世代ネット

た経路表の順序関係 ≤ID+PR に基づき経路表の改良

ワークを支えるネットワーク仮想化基盤技術の研究開を繰り返すことで経路表を構築するルーティングアル

発」により得られたものです．

ゴリズム設計手法である．また，PFRT に基づき設計された DHT アルゴリズムである PFRT-Chord を提案し，実験・評価を行った．

PFRT-Chord は FRT に基づき設計された DHT ア
ルゴリズムである FRT-Chord の素直な拡張であるため，FRT-Chord の特長（たとえば，経路表サイズの変更可能など）を継承している．また，拡張を行うことによるデメリットを最小限に抑えている．そのため，ルーティングにおける平均経路長は FRT-Chord よりほとんど増加しない．

PFRT-Chord はルーティングにおける平均所要時
間が Chord より約 40 % 減少し，FRT-Chord より
約 35 % 減少した．また，LPRS-Chord よりわずかに増加した．LPRS-Chord と同等の平均所要時間にするためには，PFRT-Chord の経路表サイズを 25 にする必要がある．LPRS-Chord では，finger table に載るエントリ数が約 13 であっても，配列といった単純な実装では 160 エントリ分のメモリを消費するが，

PFRT-Chord では設定した経路表サイズ分だけのメモ
リが消費されるため，PFRT-Chord は LPRS-Chord
よりメモリ消費量が少ない．

PFRT-Chord ではネットワーク近接性を考慮した
経路表の順序関係 ≤ID+PR に基づく経路表の改良，つまり ID に関する経路表の順序関係 ≤ID および自ノー
ドとの通信遅延に関する経路表の順序関係 ≤PR の両方において優れている経路表に改良している．しかし，順序関係 ≤ID または ≤PR のどちらか一方のみが優れている経路表に改良した場合でも，ルーティングにおける平均所要時間が減少することが考えられる．それらの経路表への改良が行われないことによる損失を分析することで，さらに良い順序関係 ≤ID+PR を定義することができる．
本研究では，順序関係 ≤PR を用いることで経路表エ

参

考

文

献

1) Stoica, I., Morris, R., Karger, D., Kaashoek,
F. and Balakrishnan, H.: Chord: A Scalable
Peer-to-peer Lookup Service for Internet Applications, Proc. ACM SIGCOMM ’01 , pp. 149–
160 (2001).
2) Maymounkov, P. and Mazieres, D.: Kademlia:
A Peer-to-peer Information Systems Based on
the XOR Metric, Proc. IPTPS 2002 , pp. 53–65(2002).
3) Rowstron, A. and Druschel, P.: Pastry: Scalable, Decentralized Object Location, and Routing for Large-scale Peer-to-peer Systems, Proc.
IFIP/ACM Middleware 2001 , pp. 329–350(2001).
4) Gummadi, K., Gummadi, R., Gribble, S., Ratnasamy, S., Shenker, S. and Stoica, I.: The Impact of DHT Routing Geometry on Resilienceand Proximity, Proc. ACM SIGCOMM ’03 ,pp. 381–394 (2003).
5) Nagao, H. and Shudo, K.: Flexible Routing Tables: Designing Routing Algorithms forOverlays Based on a Total Order on a Routing Table Set, Proc. IEEE P2P ’11 , pp. 72–81(2011).
6) Zhang, H., Goel, A. and Govindan, R.: Incrementally Improving Lookup Latency in Distributed Hash Table Systems, Proc. ACM SIGMETRICS ’03 (2003).
7) 首藤 一幸: Overlay Weaver,
http://overlayweaver.sourceforge.net/.
8) Shudo, K., Tanaka, Y. and Sekiguchi, S.:
Overlay Weaver: An Overlay Construction
Toolkit, Computer Communications, Vol. 31,
No. 2, pp. 402–412 (2008).
9) Zegura, E. W., Calvert, K. L. and Bhattacarjee, S.: How to Model an Internetwork, Proc.
IEEE INFOCOM ’96 , pp. 592–602 (1996).

ントリの自ノードとの通信遅延を考慮し，ネットワー
ク近接性を考慮した経路表の順序関係 ≤ID+PR を定義したが，ID 以外の情報（たとえばネットワークに生存している時間）を考慮するために，順序関係 ≤EX を用いて本研究と同じ方式で経路表の順序関係 ≤ID+EX

インターネットコンファレンス (IC2011) 論文集, ISSN 1341-870X, pp.41-48, 2011年10月