先進的計算基盤システムシンポジウム SACSIS 2011
Symposium on Advanced Computing Systems and Infrastructures

SACSIS2011
2011/5/25

柔軟な経路表：経路表空間上の順序関係に基づく
オーバレイネットワークルーティング方式
長 尾

也†

洋

首 藤

一

幸†

オーバレイネットワークにおけるルーティングアルゴリズムの構成手法である “柔軟な経路表（FRT）”
を提案する．FRT に基づくアルゴリズムは，経路表間の優劣を表す順序関係 ≤ID を定義し，それに従って経路表の改良を繰り返すことで，経路表構築の際に経路表の候補を限定することなくノード
ID を考慮することが可能となる．
FRT に基づく DHT アルゴリズム FRT-Chord を設計し，十分経路表が更新されるとき，経路長がノード数 N に対して O(log N ) になることを示した．また，FRT-Chord を実装し，FRT の経路
表更新手続きが意図したとおりに動作し，経路表を短縮することを確認した．

Flexible Routing Tables: Routing Algorithms
in Overlay Networks with Total Orders in Routing Table Space
Hiroya Nagao† and Kazuyuki Shudo†
We present “Flexible Routing Tables (FRT)”, a method of designing routing algorithm forstructured overlay networks. The algorithms based on FRT are able to consider node identifiers without restriction of candidates for routing tables, because they define orders “≤ID ”
of preferativity for node identifiers in tables, and repeat updating own tables based on theorder.
We design FRT-Chord, a DHT based on FRT and demonstate that it achieves O(log N )-hop
lookup performance. We also implement it and show that its method of constructing routing
tables works well and make path lengthes short.

方式は 100 万ノード超の大規模かつ不安定なアンダー

1. は じ め にレイネットワークを対象とし，オーバレイネットワー

オーバレイネットワークとは，実ネットワーク（アンク上を短い経路長でルーティングすることを目標のひダーレイネットワーク）上に構築した仮想的なネット

とつとして設計され，優れた負荷分散性能と耐故障性ワークである．この技術を用いてピュア Peer-to-Peerを持つ．このとき，各ノードが管理する経路表は非常型のネットワークを構成する場合，オーバレイネットに小さく，数エントリから数百エントリである．これワーク上でのルーティング方式は大きく二つに分類さは，大規模ネットワーク上において，全ノードが載っれる．一つは非構造化オーバレイと呼ばれ，ノード探た経路表の維持・管理が現実的ではないという判断に索クエリを再帰的に拡散させる方式である．この方式基づいている．しかし，適切なエントリの数は様々なは Gnutella や Freenet 等で利用された．もう一方は条件次第である．OneHop7) や EpiChord8) は，経路構造化オーバレイと呼ばれ，ノード探索クエリの転送

表を大きくとることで全ノードを経路表に載せる方式

方式が構造的に定められており，目的とするノードにであり，OneHop では，Gnutella ネットワークのノー確実に到達することが保証された方式である．構造化

ドの出入り頻度を仮定したとき，10 万ノード以下のオーバレイの方式に Distributed Hash Table（DHT）

OneHop ネットワークにおいて 99%の探索が正しくがある．

ルーティングされる．このように，必ずしも経路表を2000 年以降，DHT は盛んに研究され，Chord

1)を小さく保つ必要はなく，ノードの総数や参加・離脱のはじめとする多くの方式2)∼6) が提案された．これらの頻度などの条件に応じて自由にかつ動的に変更可能であるべきである．そして，元々大規模で不安定なネットワークを対象に構成された DHT は，その対象領域† 東京工業大学
Tokyo Institute of Technology

を広げ，新たな利用方法へ拡張されつつある．

117ⓒ 2011 Information Processing Society of Japan先進的計算基盤システムシンポジウム SACSIS 2011
Symposium on Advanced Computing Systems and Infrastructures

SACSIS2011
2011/5/25

拡張の基礎的な例として，通信遅延の考慮があげら出来る．

れる．ランダムに決定されるノード ID のみを考慮しエントリ情報の有効利用 従来の DHT は経路表に入て経路表を構成する従来の DHT に対して通信遅延のれたい都合の良いエントリ情報（ノード ID と IP考慮を追加した方式に LPRS-Chord9) や Coral10) がアドレスの組）のみを経路表に入れる構造を持つある．また，ノードグループの考慮を追加した方式にが，FRT は，あらゆる経路表のパターンを許容

Diminished Chord

11)

12)

や GTapがある．しかし，よするため，入手したあらゆるエントリ情報を無駄り複雑で強力な拡張を行うためには，克服すべき本質にせず，より良い経路表を構成できる．

的な問題がある．

高い状況適応性 常に経路表サイズを変更可能なため，経路表構築の基本は，ノード ID の考慮である．ここノード数やノードの安定性，要求の変化に応じたへ他の要素の考慮を追加することでアルゴリズムは拡

経路表を構成することが出来る．

張される．従来アルゴリズムは，この基本となるノー

具体的な FRT のアルゴリズムは，実際に FRT を利ド ID の考慮を，経路表に含めるノード ID の組合せ用して構成した DHT アルゴリズム FRT-Chord をを限定することで実現する．たとえば Chord1) は経用いて説明する．また，我々は FRT-Chord の実装・

i

路表に載せるノード ID を，2 先の担当ノード ID に実験を行い，ノード ID の考慮が正しく行われ，従来限定する．また，Kademlia4) は，XOR に基づく距離

同様の短い経路長が達成されることを確認した．

が [2i , 2i+1 ) になるノード ID がそれぞれ一定個以下

5 章において，将来の拡張を考慮した DHT に必要になる経路表に限定する．しかし，このようなノード

なアルゴリズムデザインについて論じ，FRT の拡張

ID の組合せを限定する方式には，ノード ID 以外の要可能性に言及する．

素を考慮する機会を奪ってしまう問題や，拡張の際に

2. 関 連 研 究

ノード ID に基づく限定をどのように緩和すべきかが明確でない問題，また，ノードが少ない場合に経路表

2.1 Chordに全ノードを載せることが出来ない問題などがある．

Chord は Chord リングと呼ばれるリング状の ID

これらはアルゴリズムの拡張を本質的に妨げる問題で

空間 [0, 2m ) を利用する DHT である．各ノードはラある．したがって，DHT の拡張性を向上させるためンダムに m ビットのノード ID を持ち，key の m ビッには，経路表を限定しない，あらゆるノード ID の組

トのハッシュ値から時計回りに進んで最初に出くわす

合せを対象とした，ノード ID を考慮する方式が必要

ノードを，key に対応する担当ノードと呼び，key に不可欠である．そしてその新たな方式が，今後のオー対応する value を保存する．

バレイネットワークの応用を促し，多数のマシンを高Chord は 3 つの経路表（successor list，predeces-

度に連携する方式へ続いていくと我々は信じる．

sor，finger table）を保持する．経路表の各エントリは，我々は，オーバレイネットワークにおけるルーティン

ノードの ID と IP アドレスの組である．successor list

グアルゴリズムの構成手法である柔軟な経路表（Flex-

は，自身のノード ID から Chord リング上を時計回り

ible Routing Table，FRT）を提案する．FRT にに進んだ先にある定数個のノードを，predecessor は，基づくアルゴリズムは，経路表間の優劣を表す順序関

反時計回りに進んだ先にある最初のノードをエントリ

係 ≤ID を定義し，それに従って経路表の改良を繰りとして保持する経路表である．この 2 つの経路表は，返すことで，経路表の候補を限定することなくノード

stabilize と呼ばれる通信を定期的に行うことで正しさ

ID を考慮した経路表構築が可能となる．

が担保され，あらゆる ID の担当ノードへの到達性を保FRT には次の特徴がある．

証する．この役割を担うエントリを Short Distance

拡張性の向上 FRT は，経路表に載るノード ID の組

Link(SDL) と言う6) ．Finger table は，自身のノー合せを限定せずに経路表を構築する．これにより，

ド ID から時計回りに 2i (i = 0, ..., m − 1) 進んだ ID

ノード ID 以外に基づくあらゆる制限に対して柔の担当ノードのエントリを保持する．これにより，1軟に対応した経路表構成が出来る．

回のフォワーディングで目的 ID までの距離を大きく

DHT の適用範囲の拡張 ネットワーク上のノード数短縮出来るようになり，経路長が短縮される．この役と経路表のサイズに応じて，経路表サイズが大き割を担うエントリを Long Distance Link(LDL)

い場合は経路長が O(1) になるフルメッシュ型，小と言う6) ．

さい場合にはマルチホップ型のルーティングとな

Chord は ID x から ID y への距離 d(x, y) を，時計る．また，これらの間を連続的に推移することが回りに進んだ距離として次のように定義する．

118ⓒ 2011 Information Processing Society of Japan先進的計算基盤システムシンポジウム SACSIS 2011
Symposium on Advanced Computing Systems and Infrastructures

SACSIS2011
2011/5/25

定義 2.1 (ID 間距離 d(x, y))d(x, y) =定しない方式を実現している．


 y − x,(x < y)2m ,(x = y)3. FRT-Chord y − x + 2m , (x > y)

FRT-Chord は，FRT に基づいて設計した DHT である．FRT-Chord は Chord リングを利用し，担当

そして，担当ノードの predecessor に辿り着くまで探ノードの決定方法も Chord と同様であるが，経路表索対象の ID t への距離 d(s′ , t) が最も小さくなるノーの構成手法に特徴がある．

ド s′ へフォワーディングを繰り返す．このように，ルーFRT-Chord は，successor list，predecessor，fin-

ティング先のノードに最も近いノードへのフォワーディ

ger table を区別せず，一つの経路表 E を保持する．経ングを繰り返すルーティングを greedy routing と路表 E は経路表エントリ ei の集合 {ei } である．各経言う．このとき，ネットワーク上のノード数 N に対路表エントリ ei はノード ID ei .id と，IP アドレスとして O(log N ) の経路長で到達する．

ポート番号の組 ei .addr を含む．ただし，ei .id を ei と略記することがある．{ei } は自ノード ID s からの時

2.2 EpiChord
EpiChord は，Chord リング上を両方向にフォワー

計回りに整列されており，i < j ⇒ d(s, ei ) < d(s, ej )ディングする DHT であり，エントリ情報を次々にである．ここで，e1 は successor（successor list の先

キャッシュとして経路表へ追加することで，経路表が頭）に相当し，e|E| は predecessor に相当する．この8)大きいとき経路表に全ノードが載り，フルメッシュなとき，これらは stabilize (3.2 節) によって正しい状態

経路表になる．

に保たれていると仮定する．

Chord リングを slice と呼ばれる領域に分割し，slice

FRT-Chord は Chord と同様に，greedy routing をごとにキャッシュエントリの数が一定以上になるよう行うため，目的 ID t に対応するフォワーディング先に保つことで O(log N ) の経路長を保証する．しかし，E.forward(t) は d(ei , t) が最小になる ei (∈ E) となる．
3.1 ≤ID ：ID 集合間の順序関係

これは同時に経路表のパターンを限定してしまっている．FRT は EpiChord 同様，経路表に知り得たエン

FRT は，経路表に含まれるノード ID の組合せに基トリ情報を次々追加することでフルメッシュな経路表

づいて経路表空間上に順序関係 ≤ID を定義する．そして，≤ID に従って経路表の改良を繰り返すことで，を構成可能であるが，経路表の限定を必要としない．

より良い経路表へ推移させるアルゴリズムである．

2.3 Small-World Phenomenon

ここでは，FRT-Chord における ≤ID の設計につSmall-World Phenomenon13) は，2 次元空間上の格子点にノードがあり，それらの SDL が隣接する 4

いて述べる．

ノードを指し，1 つの LDL が各ノードからのマンハッ

3.1.1 最良経路表の定義

タン距離の 2 乗に反比例する確率密度分布に従って

自ノード ID を s，目的 ID を t としたとき，ある決まるノードを指すネットワークにおいて，経路長がフォワーディングに対する短縮倍率を，フォワーディ

O(log2 N ) になることを明らかにした研究である．1

ング後の残り距離 d(E.forward(t), t) をフォワーディ

次元の場合の Small-World Phenomenon を利用した

ング前の残り距離 d(s, t) で割った値と定義する．つまDHT に Symphony6) がある．Symphony は，Chord

り，値が小さいほど，残り距離を大きく短縮した優れリングにおいて，自ノードからの距離に反比例する確率たフォワーディングであることを表す．ここで，FRT-

密度関数に従いランダムに ID を生成し，その ID の担

Chord の ≤ID の定義において，predecessor を除く

当ノードを経路表エントリとする．これを k 回繰り返し

ei にフォワーディングする際の短縮倍率の最悪値（最k エントリの経路表を構築することで，O((log2 N )/k)大値）ri (E) に注目する．目的 ID が ei+1 のときに最の経路長を実現する．確率分布を用いることで，経路悪値をとるので，ri (E) は次のようになる．

表の制限を緩和しているが，ランダムに決定される ID

定義 3.1 (最悪短縮倍率 ri (E))

に従ってエントリを選択するため，結果として経路表

ri (E) =に入れるノード ID を限定してしまう．

d(ei , ei+1 ), (i = 1, ..., |E| − 1)d(s, ei+1 )FRT-Chord における優れた経路表の基準は，Sym-

ここで，任意の構成可能な経路表 E に対して Ẽ ≤ID E

phony の確率密度分布と一致する．しかし，FRT にが成立する経路表 Ẽ = {ẽi } を最良経路表と呼び，次基づきその確率密度分布と経路表との関係を ≤ID へのように定める．
定義 3.2 (最良経路表 Ẽ) 最良経路表 Ẽ = {ẽi }変換することにより，経路表に入れるノード ID を限119ⓒ 2011 Information Processing Society of Japan先進的計算基盤システムシンポジウム SACSIS 2011
Symposium on Advanced Computing Systems and Infrastructures

SACSIS2011
2011/5/25

は，max{ri (E)} を最小にする経路表である．

のアルゴリズムを，FRT の重要な構成要素である到

補題 3.1

達性保証操作，エントリ情報学習操作，エントリ厳選(
ri (Ẽ) = 1 −証明

d(s, ẽ1 )d(s, ẽ|Ẽ| )|E|−1
Πi=1 (1 − ri (E)))

操作に分けて説明する．

1|Ẽ|−1

3.2 到達性保証操作
FRT は，到達性を保証する経路表エントリの更新
操作を到達性保証操作と呼ぶ．

= d(s, e1 )/d(s, e|E| )(=一定) であるから，全項が等しいとき max{ri (E)} が

FRT-Chord は Chord と同様の stabilize 操作によ2

り，SDL を最新に保つ．これにより，経路表にいかな

定理 3.1 (最良経路表の経路長) |E| = O(log N )るエントリが載っていたとしても，Chord と同等の到最小となる．

において，最良経路表を保持するとき，経路長は達性が保証される．

O(log N ) となる．

3.3 エントリ情報学習操作

証明 一 般 に N が 大 き い と き 十 分 高 い 確 率 でFRT はエントリ情報の学習をエントリ情報学習操d(s, e1 ) > 2m /N 2 が成立し14) ，距離の定義から

作と呼ぶ．FRT はエントリ情報の具体的な学習方法

d(s, e|E| ) < 2m が成立する．したがって，補題 3.1

を制限せず，知り得たあらゆるエントリ情報を有効活より，任意の i = 1, ..., |Ẽ| − 1 について

用できる．

(
ri (Ẽ) < 1−d(s, ẽ1 )2m)1|Ẽ|−1

(

1
< 1−
N

)

学習方法には，たとえば，参加時に他のノードから

2|Ẽ|−1

経路表全体をコピーする方法や，ノードの探索時等に通信した相手のエントリ情報を取得する方法，エントが成立する．|Ẽ| = 1 + 2 log N とすると，残り距離を

リ情報を学習するために探索を行う方法（能動学習探m

2 /N 以下にするまでに必要な経路長は，最悪でも索と呼ぶ）がある．

FRT-Chord における能動学習探索は Symphony に11
logri (Ẽ)< log
= log N
2
1
|
Ẽ|−1
N
N
1−( N )

類似する方法であり，最良経路表に含まれるノード IDとなり，O(log N ) である．このとき predecessor への分布を確率分布とみなし，その確率分布に従うようのフォワーディングを考慮していないが，predecessorに生成したノード ID への探索を行う．確率分布は自にフォワードした場合は自身が担当ノードでありフォ

ノード s からの距離の逆数に比例する分布とし，そのワーディングが終了するからである．また，残り距離

累積分布関数 F (x) は次の通りである．

が 2m /N 未満のとき，自ノードから 2m /N 先までにO(log N ) 個となることが知られており1) ，その経路

ln(d(s, x)/d(s, e1 ))(1)ln(d(s, e|E| )/d(s, e1 ))0 以上 1 未満の乱数 rnd を用いて探索対象 ID は次の長は O(log N ) となる．以上より，経路全体の経路長ようにして生成することが出来る．

F (x) =

存在するノードは，N が大きいとき十分高い確率では O(log N )．

{

2

}rnd

最良経路表に “近い” 経路表を優れた経路表とみなd(s, e|E| )s + d(s, e1 )(2)d(s, e1 )FRT-Chord では，参加時と探索時にエントリ情報

し，その “近さ” を表す指標 ≤ID を次のように定義の学習を行う．また，学習を促進する目的で必要があする．

れば能動学習探索を行う．

3.1.2 ri (E) による ≤ID の定義

定義 3.3 (≤ID ) {ri (E)} を 降 順 に 並 べ た 列 を

FRT は新たに学習したエントリ情報を経路表 E へ{r(i) (E)} としたとき，E ≤ID F ⇔ {r(i) (E)} ≤dic

次々と追加する．エントリ学習操作が繰り返されるこ{r(i) (F )}．

とで，より短縮倍率の優れたフォワーディングが可能

ここで辞書式順序 ≤dic とは，となる．一方で追加を繰り返すことで経路表に含まれ{ai } <dic{bi }⇔ ak < bk (k = min{i|ai ̸= bi })るエントリ数 |E| は増加し続けるため，エントリ数に{ai } =dic{bi }⇔ ai = bi

最大値 L を設け，無制限な経路表エントリの増加を防{ai } ≤dic{bi }⇔ ({ai } <dic{bi })∪({ai } =dic{bi })ぐ．ここで，L は遅延やマシン性能，ノードの離脱頻である．

度などに応じて決めることが出来る，保持可能な経路定理 3.2 (≤ID の正当性) Ẽ ≤ID E
証明 補題 3.1 より明らか．

表エントリ数に応じて柔軟にかつ動的に変更可能な値

2

である．

このようにして定義した ≤ID を用いた FRT-Chord

ネットワーク内のノードが安定している場合など，

120ⓒ 2011 Information Processing Society of Japan先進的計算基盤システムシンポジウム SACSIS 2011
Symposium on Advanced Computing Systems and Infrastructures

SACSIS2011
2011/5/25

L がノード数 N より大きく設定されるとき，全ノーと変化しない．

ドのエントリ情報を保持するフルメッシュな経路表がE
ここで，i∗ の決定方法から，SiE∗ −1 + SiE∗ ≤ Si−1
+ SiE

達成され，経路長は O(1) となる．

が成立するので，k ∗ ≥ k ．したがって，i = 1, ..., k −E−{ei∗ }3.4 エントリ厳選操作

E−{e }= S(i) i が成立し，かつE−{ei }
S(k)が成立する．したがって，補

1 において S(i)E−{e ∗ }S(k) iFRT は，L < N において，|E| が L を越えようと≤するとき，現在の経路表に含まれるエントリ情報と，

題 3.2 より E − {ei∗ } ≤ID E − {ei } が成立する． 2

新たに取得したエントリ情報の合計 |E| + 1 の中からE
ここで，{Si−1+ SiE } を昇順にしておくことで i∗

1 つを捨て，エントリを厳選し，|E| ≤ L に保つ．この探索は O(1) で完了し，経路表の変更時に行われるれをエントリ厳選操作と呼ぶ．FRT は順序関係 ≤ID

更新も O(log N ) で終了する．

に基づきエントリ厳選操作を行うことで経路表の改良

FRT-Chord のエントリ情報学習操作とエントリ厳を繰り返し，経路長を短縮する．こうして FRT は経選操作を繰り返すことで，学習したエントリと削除す

路表の可能なパターンを限定することなくノード ID

るエントリが常に一致し，経路表の改良が停止するこを考慮する．また，このエントリ厳選操作に ID 以外とが考えられる．このときの経路表 E を収束した経の要素を導入することでアルゴリズムを見通しよく拡路表と呼び，次が成立する．

張できる．

定理 3.4 (厳選操作の非停止性) ノ ー ド 数 N のFRT-Chord の場合，新しく学習したエントリ情

ネットワークにおいて，全ノードが収束した経路表

報を一時的に追加した経路表 E = {ei } において，E を持つとき，|E| = O(log N ) の条件下で経路長はE
i = 2, ..., |E| − 1 から Si−1
+ SiE が最小の i = i∗ をO(log N ) である．

探索し，ei∗ を削除する．このとき，i ≠ 1, |E| である

証明 Chord リング上の領域 (ei , ei+1 ) にノードのは，それらが successor，predecessor に相当し，削が存在する i の集合を J ，存在しない i の集合を K

除の対象としないからである．ただし，SiE は正規化と定義する．このとき，収束した経路表の定義から，間隔であり次のように定義される．

Ej ∈ J, i = 2, ..., |E| − 1, SjE ≤ Si−1
+ SiE が成立する

定義 3.4 (正規化間隔 SiE )SiE= log d(s,ei+1 ) −から，j を固定してこの不等式の和をとることにより，

log d(s,ei ), (i = 1, . . . , |E|−1)

次が成立する．

∑|E|−1

E
降順に並べた正規化間隔の列を {S(i)} とすると，次SjE ≤が成立する．

i=2

E
(Si−1
+ SiE )
|E| − 2∑|E|−1

補題 3.2 (正規化間隔と ≤ID の関係)
EF
E ≤ID F ⇔ {S(i)} ≤dic {S(i)
}

=

2(

i=1

∑|E|−1証明

ri (E) =≤d(s, ei )d(s, ei+1 )−d(s, ei )= 1−d(s, ei+1 )d(s, ei+1 )

= 1−2

− log

d(s,ei+1 )d(s,ei )2(ESiE ) − S1E − S|E|−1|E| − 2

SiE )
= log
|E| − 2i=1(d(s, e|E| )d(s, e1 )2) |E|−2

また，補題 3.2 より，定理 3.1 の証明と同様にして，E= 1−2−Si()

4

定理 3.3 (削除の最適性) FRT-Chord のエントリ

1 |E|−2(3)Nmである．ここで，残り距離を 2 /N 以下にするため厳選操作により作成される経路表を E − {ei∗ } とするに必要な経路長の上限を考える．フォワーディング先とき，任意の削除対象エントリ ei (i = 2, ..., |E| − 1)が ek (k ∈ K) のとき，ek と ek+1 の間にノードが存在について E − {ei∗ } ≤ID E − {ei } が成立する．

しないため，担当ノードは ek+1 であり，ルーティン

よって，ri (E) と SiE の大小が一致する．

rj (E) < 1 −2

証明 削除後の経路表に関して正規化間隔を考グが終了するため，フォワーディング先は ej (j ∈ J)

E
える．k ∗ = min{j|SiE∗ −1 + SiE∗ > S(j)} とするの場合のみを考慮すればよい．このとき，式 1 が成} の先頭から k∗ + 1 番目までは立するので，定理 3.1 の証明と同様にすれば経路長は

E
E
E
E
E
S(1)
, ..., S(k∗ −1) , (Si∗ −1 + Si∗ ), S(k∗ ) となる．このとO(log N ) である．また，残り距離が 2m /N 以下につき，k − 1 番目までは削除前と変化しない．同様に，

いても同様に経路長は O(log N ) であり，経路全体のE−{ei∗ }とき，{S(i)∗E−{e }
EE
k = min{j|Si−1+SiE > S(j)} とするとき，{S(i) i }E
E
Eの先頭から k + 1 番目までは S(1), ..., S(k−1), (Si−1+EESi ), S(k) となる．このとき，k − 1 番目までは削除前

経路長は O(log N ) となる．

2

削除の候補を i = c + 1, ..., |E| − 1 に変更すると，長121ⓒ 2011 Information Processing Society of Japan先進的計算基盤システムシンポジウム SACSIS 2011
Symposium on Advanced Computing Systems and Infrastructures

SACSIS2011
2011/5/25

自ノードからの距離（対数）（ = log d(s, ei )）さ c の successor list が実現され，stabilize 操作が行われることで，正しい successor と predecessor が保持される．また，このときも定理 3.3 と同様，≤ID に基づいて最も経路表を改善する選択となり，更新を繰り返すことで経路長が短縮される．このように，FRT
は，経路表に載せるかどうかの条件に対して柔軟に対応することが可能である．

160
158
156
154
152
150
148
146
144

最良経路表
参加時コピー有り，
確率分布に従う探索
参加時コピー有り，
ランダムな探索参加時コピー無し，確率分布に従う探索

e1

e11

e21

e31 e41 e51
経路表エントリ

e61

e71

参加時コピー無し，
ランダムな探索

図 1 25 回探索後の経路表エントリ ID(縦軸対数)
Fig. 1 Entries after 25 lookups (semilog graph).

FRT では，エントリ厳選操作において削除の候補にしない successor list や predecessor などのエント
自ノードからの距離（対数）（ = log d(s, ei )）リのことを sticky entry と呼ぶ．Sticky entry という例外を設けることで，順序関係 ≤ID の構成をシンプルに行うことが出来る．こうするとき，FRT-Chord
におけるエントリ厳選操作は次のように記述できる．

(1)

C⇐E

(2)

C から sticky entry を取り除く．

(3)

E
C から Si−1+ SiE が最小となるエントリを削

最良経路表
参加時コピー有り，
確率分布に従う探索
参加時コピー有り，
ランダムな探索参加時コピー無し，確率分布に従う探索

e1

e11

e21

e31 e41 e51
経路表エントリ

e61

e71

参加時コピー無し，
ランダムな探索図 2 100 回探索後の経路表エントリ ID(縦軸対数)
Fig. 2 Entries after 100 lookups (semilog graph).

除する．

4. 評

160
158
156
154
152
150
148
146
144

価

図 1 より，参加時にコピーせずにランダムに探索

オーバレイネットワーク構築ツールキット Overlay

した場合が最も最良経路表から離れている．これは，Weaver15)16) 上に FRT-Chord を実装し，エミュレー

ランダムの探索において，エントリ同士の間隔が狭い

ションにより評価を行った．実験には Overlay Weaver

自身から近いエントリへのフォワード回数が相対的に0.9.11 を用い，OS は Windows 7 64bit，CPU は Core

少なくなり，自身から近い領域にあるエントリの学習

2 Duo E8400 3.00 GHz，メインメモリは 8.00GB の回数が少なくなってしまうからである．一方，同じコマシン上で JRE 6 Update 20 を用いた．

ピー無しであっても，確率分布に従った乱数による探4.1 エントリ厳選操作とエントリ情報学習操作方式

索を行った場合は，そのようなフォワード回数の偏り

FRT-Chord のエントリ厳選操作を繰り返すことで，が解消されており，最良経路表に大幅に近づいている．

経路表が最良経路表に近づくことを明らかにする．まこれらから，確率分布に従った探索は，エントリ情報

た，各エントリ情報学習操作の特徴を調べる．

の学習効果が高いと言える．また，ランダムに探索をN = 104 のノードが参加を行い，ランダムに選択行っていても，参加時に経路表をコピーした場合は最したノードからランダムに選択した ID への探索を 10

良経路表に近い経路表となっている．このことから，万回実行した後，新たに 1 ノードを参加させて，その参加時の経路表コピーはエントリ情報の学習効果が高ノードからの探索を 100 回行った．経路表エントリのいと言える．

最大数 L は 80 とした．

以上から，エントリ厳選操作は，参加時のコピーと参加時に successor から経路表をコピーするかどう

確率分布に従って探索することで効率よく行われるこかおよび，ランダム ID への探索により学習するか能とが分かった．そのため FRT-Chord では，参加時の動学習操作により学習するかの計 4 通りのエントリ情

コピーを行う．一方で能動学習探索は，経路表を構成

報学習操作を行い，最後に参加したノードの経路表にするための探索でありコストを伴うため，経路のエン含まれるノード ID を記録した．探索回数を 25 回おトリと直接通信しない再帰方式のフォワーディングをよび 100 回とし，条件ごとに自ノードから各エントリ行う際など，経路表の学習頻度が少ない場合に行うこまでの距離の対数 log d(s, ei ) をプロットした（図 1，ととする．

図 2）．また，最良経路表を参考のために表示してお4.2 エントリ厳選操作と経路長の関係

り，最良経路表に近いほど，より改良された経路表で全ノードを参加させた後，ランダムに選択したノーある．探索を繰り返した結果，どの条件においても最ドからランダムに選択した ID への探索を 50 万回行

良経路表に近づき，エントリ厳選操作が有効にはたらう実験を行った．ノード数 N を 102 ，103 ，104 とし，

いていることが分かる．

経路表サイズの上限 L は 20，40，80，160，successor

122ⓒ 2011 Information Processing Society of Japan先進的計算基盤システムシンポジウム SACSIS 2011
Symposium on Advanced Computing Systems and Infrastructures

9

L=20

8

L=40
L=80

SACSIS2011
2011/5/25

平
均
経
路
長

N=104

7
L=160
平 6
均
経 5
路
長 4

L=20

3

L=20

10
8
6
4
2
0

L=40
L=80

FRT-Chord(L=20)
FRT-Chord(L=40)
FRT-Chord(L=80)
10^2

N=103

10^3

10^4

ノード数

Chord

L=160

図 5 経路表サイズと平均経路長の関係
Fig. 5 Correlation between number of routing table size
and average path lengths.

L=40
2
L=80
1

N=102

L=160
0

10

20

30

40

探索回数(万回
探索回数 万回)
万回

Fig. 3

FRT-Chord(L=160)

20

FRT-Chord(L=20)

最 15
大
10
経
路 5
長 0

図 3 探索回数と平均経路長の変化
Changes of average path length along with thenumber of lookups.

FRT-Chord(L=40)
FRT-Chord(L=80)
10^2

9

L=20

8

L=40
L=80

N=104

L=160
L=20

均
経 5
路
長 4

10^4

FRT-Chord(L=160)
Chord

図 6 ノードあたりの探索回数と平均経路長の関係
Fig. 6 Correlation between number of routing table size
and max path lengths.

7
平 6

10^3

ノード数

L=40
L=80

N=103

ノード数と経路表サイズを変更しながら，経路長がどL=160のように変化するかを計測する．ノード数 N を 102 ，

L=20

3

L=40
2
L=80
1

N=102

103 ，104 と変化させたときの平均経路長と最大経路長を測定した（図 5，図 6）．ここから，定理 3.4 で示

L=160
0

10

20

30

40

1ノードあたりの探索回数
ノードあたりの探索回数(回
ノードあたりの探索回数 回)

した経路長の O(log N ) 性が確認できる．また，L と

図 4 ノードあたりの探索回数と平均経路長の変化
Fig. 4 Changes of average path length along with thenumber of lookups per node.

経路長のトレードオフを自由に変更できることが確認できた．そして，経路表サイズがノード数より大きい
とき（N = 102 ，L = 160），経路表がフルメッシュとlist の長さは 4 である．フォワーディングは，探索をなっており，経路長が O(1) になることが確認できた．

行うノードが次のフォワーディング先の問い合わせを繰り返す反復方式で行った．

5. 拡

探索時の経路長を 1 万回ごとに集計し平均を求めた

張ものが図 3 であり， どの条件でも，探索を繰り返す

FRT は高い拡張性を提供する．これは，FRT が経ごとに平均経路長が短縮されていることが分かる．こ路表空間のあらゆる部分集合に対して，ノード ID にれは，探索によってエントリ情報を学習し，厳選操作関する優劣を定義するからである．

が繰り返し行われることで，経路表が優れた状態へ推ノード ID 以外の要素を考慮するように DHT の経移した結果であると考えられる．

路表を拡張することは，すなわち，経路表に対して何N 回ごとに平均経路長を求めることで横軸をノー

らかの制限を加えることである．従来のアルゴリズム

ドあたりの探索回数としたものが図 4 である． このは，構築可能な経路表をたとえば経路長が O(log N )図と図 3 を比較すると，1 ノードが行う探索回数が同になるクラスの部分集合になるように限定し，ノード

じであれば，平均経路長が短縮される速さは同程度でID を考慮する．これを拡張することは，ノード ID にあると分かる．したがって，各ノードがそれぞれ一定

基づき限定した経路表の中からの選択を行うに過ぎな

回の探索を行い経路表を更新することは，ノード数 N

い．その部分集合に含まれなかった経路表が O(log N )に依らない経路表更新効果が得られると言える．このにならないとは限らず，また，そもそも経路長はルー

ことから，FRT-Chord のエントリ学習操作はノード

ティングの性質の一面しか表しておらず，ノード ID

数に対してスケールすると言える．

に基づく限定は，将来の拡張に対して強すぎる制限を

4.3 ノード数，経路表サイズ，経路長の関係与えている．これに対して FRT は，ノード ID 以外

十分に経路表厳選操作が行われた経路表を用いてのあらゆる要素に関する条件を満たす経路表集合の中

123ⓒ 2011 Information Processing Society of Japan先進的計算基盤システムシンポジウム SACSIS 2011
Symposium on Advanced Computing Systems and Infrastructures

SACSIS2011
2011/5/25

で，どの経路表がより優れているかを表明することに参より，ノード ID の考慮を行うことを可能にする．この点が従来 DHT と最も異なる点であり，DHT の適用範囲拡大に伴う，将来の拡張を見据えたアルゴリズ
ムに必要な特徴であるといえる．
また，安定した環境や比較的ノードが少ない場合に経路表に全ノードを載せ，O(1) の経路長を実現できることは，Web サービスやクラウドの構築などにおいて，DHT の特徴を活かした低い管理コストかつ可用性の高いシステムの構成に効果的であると考えている．しかし，実用にはアンダーレイを考慮した様々な最適化を施す必要がある．
アンダーレイを考慮する一例として，FRT の拡張性を利用し，FRT-Chord をノードグループを考慮するように拡張したアルゴリズムに LFRT-Chord17) がある．LFRT-Chord では，経路表に同じグループに属するノードを優先的に載せるという制限のもとでノード

ID を考慮する．これにより，経路長の伸びを抑えつつ，グループをまたぐ経路の削減を実現している．たとえば ISP やデータセンタなどをグループとすることで，それらをまたぐ通信量を削減でき，従来の DHTの持つデメリットを抑えることが出来る．

6. ま と め
本論文では，オーバレイネットワーク上のルーティ
ングアルゴリズム構成手法である柔軟な経路表（FRT）
および，FRT に基づいて構成した DHT である FRT-

Chord を提案した．
従来の DHT は経路表の候補を限定することで経路表構築のために必要なノード ID の考慮を行う．FRT
は，経路表間の順序関係 ≤ID を定義することで，経路表のパターンを限定しない，従来とは異なるノード

ID の考慮方式を実現した．
FRT-Chord の諸性質を明らかにするとともに，
FRT-Chord の実装・実験を行い，FRT に基づく経路表の更新が経路長を短縮することおよび，N に依らない回数の探索を各ノードが行うのみで経路表が十分更新されることを明らかにした．また，経路表の最大エントリ数がノード数より大きいとき経路長が O(1)になる状態へ移行可能であることを示した．
本論文では，FRT-Chord を提案したが，今後は，FRT に基づく他のアルゴリズムや，それらを拡張した実用性の高い応用手法を構成していく．
謝辞 提案手法の分析方法について議論して頂いた大西真晶様に感謝致します．本研究は科研費

考

文

献

1) Stoica, I., Morris, R., Karger, D., Kaashoek,
M. F. and Balakrishnan, H.: Chord: A Scalable Peer-to-peer Lookup Service for Internet
Applications, Proc. ACM SIGCOMM ’01 , pp.
149–160 (2001).
2) Zhao, B. Y., Huang, L., Stribling, J., Rhea,
S. C., Joseph, A. D. and Kubiatowicz, J. D.:
Tapestry: A Resilient Global-scale Overlay for
Service Deployment, IEEE Journal on Selected
Areas in Communications, Vol. 22, No. 1, pp.
41–53 (2004).
3) Rowstron, A. I. T. and Druschel, P.: Pastry:
Scalable, Decentralized Object Location, andRouting for Large-Scale Peer-to-Peer Systems,
Proc. IFIP/ACM Middleware 2001 , pp. 329–
350 (2001).
4) Maymounkov, P. and Mazières, D.: Kademlia: A Peer-to-Peer Information System Basedon the XOR Metric, Proc. IPTPS ’02 LNCS
2429 , pp. 53–65 (2002).
5) Kaashoek, M. F. and Karger, D. R.: Koorde: A
Simple Degree-Optimal Distributed Hash Table, IPTPS , pp. 98–107 (2003).
6) Manku, G. S., Bawa, M. and Raghavan,P.: Symphony: distributed hashing in a small
world, Proc. USITS’03 , pp. 10–10 (2003).
7) Fonseca, P., Rodrigues, R., Gupta, A. andLiskov, B.: Full-Information Lookups for Peerto-Peer Overlays, IEEE Trans. Parallel Distrib.
Syst., Vol. 20, pp. 1339–1351 (2009).
8) Leong, B., Liskov, B. and Demaine, E. D.:
EpiChord: Parallelizing the Chord lookup algorithm with reactive routing state management, Comput. Commun., Vol. 29, pp. 1243–
1259 (2006).
9) Zhang, H., Goel, A. and Govindan, R.:
Improving lookup latency in distributedhash table systems using random sampling,
IEEE/ACM Trans. Netw., Vol. 13, pp. 1121–
1134 (2005).
10) Freedman, M. J. and Mazières, D.: Sloppy
Hashing and Self-Organizing Clusters, IPTPS ,pp. 45–55 (2003).
11) Karger, D. R. and Ruhl, M.: Diminished
Chord: A Protocol for Heterogeneous Subgroup
Formation in Peer-to-Peer Networks, IPTPS ,pp. 288–297 (2004).
12) Zhang, Y., Li, D., 0002, L.C. and Lu, X.: Flexible Routing in Grouped DHTs, Peer-to-Peer
Computing, pp. 109–118 (2008).
13) Kleinberg, J.: The Small-World Phenomenon:（22680005）の助成を受けたものである．

124ⓒ 2011 Information Processing Society of Japan先進的計算基盤システムシンポジウム SACSIS 2011
Symposium on Advanced Computing Systems and Infrastructures

SACSIS2011
2011/5/25

An Algorithmic Perspective, Proc. ACM STOC
2000 , pp. 163–170 (2000).
14) Cordasco, G. and Sala, A.: 2-Chord Halved,
Proc. HOT-P2P ’05 , Washington, DC, USA,IEEE Computer Society, pp. 72–79 (2005).
15) Shudo, K., Tanaka, Y. and Sekiguchi, S.:
Overlay Weaver: An overlay construction
toolkit, Computer Communications, Vol. 31,
No. 2, pp. 402–412 (2008).
16) 首 藤 一 幸: Overlay Weaver: An Overlay
Construction Toolkit, http://overlayweaver.
sourceforge.net/.
17) 長尾洋也, 首藤一幸: オーバレイネットワークにおけるグループ間通信抑制手法, 情報処理学会研究報告，2010-OS-115 (2010).

125ⓒ 2011 Information Processing Society of Japan