1

オーバレイ構築ツールキット Overlay Weaver
首藤一幸†,†† 田

中

良

夫†

関

口

智 嗣†

我々は，ネットワークオーバレイのアルゴリズム研究基盤として，オーバレイ構築ツールキット
Overlay Weaver を開発・配布している．これを用いることで，計算機 1 台上で繰り返し動作試験を行いながら，少ないコード量で structured オーバレイのアルゴリズムを実装できる．また，アルゴ
リズムの差し替え，および，計算機 1 台上での数千ノード規模のエミュレーションが可能であるため，アルゴリズム間の公正な比較を行うことができる．同時に，こうして実装したアルゴリズムはそのま
ま実ネットワーク上で動作するため，アルゴリズム研究の成果が直接アプリケーションに結び付く．
本ツールキットでは，アルゴリズムの実装を容易なものとするために，各アルゴリズムに共通する
ルーティング処理をアルゴリズム実装から分離した．本論文では，この分離を可能とする両者間のインタフェースを提案する．この分離によって，いくつかのアルゴリズムを，それぞれたかだか数百ス
テップで実装できた．ルーティング処理の側も，iterative および recursive の両ルーティング様式を差し替えられるようになった．

Overlay Weaver: An Overlay Construction Toolkit
Kazuyuki Shudo,†,†† Yoshio Tanaka† and Satoshi Sekiguchi†
We have been developing an overlay construction toolkit called Overlay Weaver as thegroundwork for future research on algorithms. Algorithm designers can implement structured
overlay algorithms in just hundreds of lines of code with the toolkit and improve these rapidly
by iterative testing them on a single computer. The toolkit enables designers to make fairand large-scale comparisons between of new and existing algorithms, since the implemented
algorithms are pluggable and the emulator provided by the toolkit can host thousands of virtual nodes. Furthermore, the implemented algorithms can work on a real network in addition
to the emulator. The toolkit enables algorithms developed through research to be used inapplications directly.
We decomposed the routing layer of software which constructs structured overlay into arouting process and a routing algorithm. In this paper, we propose a programming interface
between them. Decomposition enables an algorithm to be implemented in just hundreds oflines of code. The routing process also became pluggable by decomposition and the toolkit
can provide both iterative and recursive routing.

structured オーバレイに限定しても，これまで多く

1. は じ め にのアルゴリズム1)∼5) が提案されてきた．また，それら

大規模なインターネット上分散アプリケーションでは，ノード数が数万，数百万と増えてもなお性能と耐を実装したライブラリ6)∼9) やアプリケーション10)∼12)も現れている．

故障性を保つために，自律的・非集中的にアプリケー

アルゴリズムの設計・評価においては，可能であれションレベルのネットワークを構成することが不可欠

ば数百万という多数のノードを想定した実験が欠かせとなっている．ここで構成されるネットワークは，下ない．大規模な実験環境を用意することは容易ではな

位ネットワークの物理的トポロジとは独立したトポロ

いため，通常，アルゴリズムの動作と有用性はシミュジを持つためネットワークオーバレイと呼ばれ，検索レーションで確認される．その後，インターネット上やマルチキャストなどの機能を提供する．

の実環境で評価，応用するためには，実環境で動作するソフトウェアを，別途，実装する必要がある．この† 産業技術総合研究所
National Institute of Advanced Industrial Science andTechnology（AIST）†† 現在，ウタゴエ（株）
Presently with Utagoe, Ltd.

ため，提案時には実環境で動作する実装が伴わないア
ルゴリズムも多い．そこで提案されたアルゴリズムを
実環境向けに実装する開発者にとっては，シミュレー
ション時と寸分違わぬアルゴリズムとパラメータにし情報処理学会論文誌: コンピューティングシステム,
Vol.47, No.SIG12 (ACS 15), pp.358-367, 2006年9月

2
ない限り，自らの実装がどういう挙動を示すかは，実成できる．アルゴリズムは，分散ハッシュ表（DHT）のところ，明らかではない．オーバレイの挙動は，アとしては Chord と Pastry の実装を提供している．

ルゴリズムその他のパラメータ，例えば定期的な処理

アルゴリズムの記述に必要となるコードの分量は，MACEDON と本ツールキットで最大 1.5 倍程度の違の時間間隔に依存するためである．
我々は，この，アルゴリズム研究から応用までの距離

いであり，大きな差はない（5.1 節）．通信などのライを短縮するべく，オーバレイ構築ツールキット Overlay

ブラリ提供に加えて，MACEDON は専用の言語を導13),14)

Weaver を開発・配布している．structured オー
バレイのアルゴリズムを設計，実装する際に本ツールキットを用いることで，一度の実装で，インターネッ

入することで必要なコード量を減らしており，一方，本ツールキットはルーティング処理をアルゴリズムから分離することで同等の効果を得ている．

ト上実環境での動作と計算機 1 台上での数千ノード規

MACEDON はエミュレータ（4.2 節）を持たず，多模のエミュレーションの双方が可能となる．これによ

ノードでの試験は計算機 2〜50 台以上からなるイン

り，大規模な動作試験をエミュレータ上で繰り返し行

ターネットエミュレータ ModelNet 上で行われていいながらアルゴリズムを設計，実装して品質を向上さる16) ．エミュレートされたノード数は最大でも 1000

せ，その結果得られた実装をそのまま実環境で用いるにとどまっており，そのノード数ではオーバレイの構ことが可能となる．

築（経路表が安定する様子の観察）しか行われていな

我々はまた，structured オーバレイ上のルーティン

い．これに対して本ツールキットは，計算機 1 台でグ処理をアルゴリズム実装から切り離すことを可能とング処理の実装はツールキット側が提供することで，4000 ノードのエミュレーションを達成している．
Mace18) は MACEDON の後継プロジェクトである． ただし，Mace release 0.7.1-20050919 で実装さアルゴリズムの実装が容易になった．これによって，れている structured オーバレイは Pastry と，それをする，両者間のインタフェースを提案する．ルーティ

1)

2)

3)

4)

Chord ，Pastry ，Tapestry ，Kademlia の各ア
ルゴリズムをそれぞれたかだか数百ステップで実装できた．同時に，ルーティング処理部の切り替えも可能となり，アルゴリズム実装には一切の変更なしで iterative ルーティングと recursive ルーティング6),15) からどちらかを実行時に選択できるようになった．
以降では，まず 2 章で関連研究を挙げる．3 章では，アルゴリズム実装とルーティング処理を切り離す方法を示し，両者間のインタフェースを提案する．続く 4

利用した Scribe および SplitStream に限られており，様々なアルゴリズムをサポートできることはまだ実証されていない．

P2 では，Prolog に似た宣言的オーバレイ記述言語
OverLog で，経路表といったノード状態の更新処理を記述する．オーバレイ記述はコンパイルされ，それを分散データフローエンジンが実行する．オーバレイのアルゴリズム記述は簡潔であり，例えば Chord の実装は，47 のルールと表の宣言 13 行，ステップ数で章では本ツールキットを構成する各コンポーネントと表すと 142 で済んでいる．本ツールキットではアルツールを説明し，それらがアルゴリズムの設計と実装，

ゴリズムは Java 言語で手続的に記述されるのに対し試験，比較をどうサポートするかを述べる．5 章では，て，P2 では専用言語で宣言的に記述される点が相違

各アルゴリズムを少ないコード量で実装できること，点である．提案間もない専用言語であるため，アルゴ

多ノードでの動作試験やアルゴリズム間比較が可能で

リズム記述の容易さや保守性はまだ明らかではない．

あることを示す．

また，P2 release 0.6 で実装されているアルゴリズム

2. 関 連 研 究は Narada と Chord，そのうち structured オーバレ

複数のアルゴリズムをサポートしているオーバレイ

ズムの記述可能性は未検証である．実験の規模は，計構築ソフトウェアには，本ツールキットの他に MACE-

算機 110 台を用いた 500 ノードにとどまっている．

16),17)

イは Chord のみであり，Mace 同様，多くのアルゴリ

18)

19)

DON
と Mace ，P2がある．
MACEDON では，C，C++に似た独自の専用言語
でオーバレイのアルゴリズムを記述し，それを MACEDON のコンパイラで処理することで動作する C++言MACEDON，Mace，P2 のどれも，アルゴリズム
記述は iterative/recursive ルーティングのどちらかに特化せざるを得ない．それに対して本ツールキットでは，アルゴリズム記述には変更なしで両様式を差し替

語のコードを得る．本ツールキットと同様に実環境でえて動作させることができる．

の通信は UDP，TCP で行う他，“partial support”16)

structured オーバレイのアルゴリズムを実装しているライブラリとしては，他にも Bamboo6),7) ，ながらネットワークシミュレータ ns 用のコードも生情報処理学会論文誌: コンピューティングシステム,
Vol.47, No.SIG12 (ACS 15), pp.358-367, 2006年9月

3い．また，もう一方であるアルゴリズム研究者にとっては，自身が設計するアルゴリズムを実装しやすいことに加えて，比較対象となる他のアルゴリズムが数多く提供されていることが望ましい．そのためには，
図 1 Key-based routing (KBR)（論文 22) の Figure 1）
Fig. 1 Key-based routing (KBR)（Figure 1 from Dabek etal.22) ）.

ツールキットにはアルゴリズムの実装が容易であることが求められる．しかし，ルーティング層の実装は，アルゴリズムの本質的な部分だけでなく，ノード間のChimera および Tapestry3),8) ，Khashmir9) などが入手可能となっている．それらはどれも単一のアルゴリズムを実装しており，複数のアルゴリズムを差し通信プロトコルの設計，実装から行う必要があり，容易とは言えない．
そこで我々は，ルーティング層から各種のルーティ

替えて使えるようにはなっていない．

ングアルゴリズムに共通する処理をくくり出し，各ア

p2psim20) は peer-to-peer プロトコルのシミュレータである．アルゴリズムとしては，Chord，Accordion，
Koorde，Kelips，Tapestry，Kademlia の実装を提供

ルゴリズムに固有の処理との間のプログラミングイ

している．これらはすべて DHT，つまり structured

様々なアルゴリズムをたかだか数百ステップで実装すオーバレイである．Accordion の提案

21)

では Chord

ンタフェースを見出した．共通処理はツールキット側が提供することでアルゴリズムの実装が容易になり，ることが可能となった（5.1 節）．

との比較のために p2psim が使われており，最大で図 2 に，本ツールキットのランタイムを構成する

3000 ノードのシミュレーションが行われている．
シミュレーションには，再現可能なシミュレーション（図 1）22) におけるルーティング層に相当するのは，コンポーネント群を示す．図中で，Dabek らの提案

ム実装を実環境で動作させることはできない．また，

Routing Driver と，そこから直接利用される Routing Algorithm，Messaging Service である．このう
ち，Routing Driver が共通処理を行うコンポーネン
トである．Routing Algorithm は各種ルーティングア
ルゴリズムの実装であり，Routing Driver はここか

アルゴリズムを記述する際は遠隔呼び出し（RPC）をら必要な情報を得てルーティング処理を行う．

を行うことができる，という利点がある．本ツールキッ
トが行うような並行システムのエミュレーションは非決定的であり，結果に再現性はない．一方で，p2psim
はシミュレータであるため，p2psim 用のアルゴリズ

含む通信を直接書くことになるため必要となるコード

共通処理のくくり出しによって，アルゴリズム実装

量は少なくなく，本ツールキットや MACEDON の数だけでなく共通処理の側も，複数の実装を用意して実倍となっている（5.1 節）．

行時に選択することが可能となった．具体的には，本

3. ルーティング共通処理とアルゴリズムの分離
Dabek らは，あらゆる structured オーバレイに共通するルーティング処理を key-based routing（KBR）と呼んだ22) ．図 1 の通り，第 0 層と位置付けられる

KBR，つまりルーティング層の上には，より高位のサービスである DHT やマルチキャスト，エニーキャ
スト，メッセージ配送などを構築できる．
本ツールキットもこの抽象化に従い，ルーティング
層と，その上の DHT サービス，マルチキャストサー
ビスを分離している．この抽象化によって各層は交換可能となり，アプリケーションを変更することなく，様々なルーティングアルゴリズムを差し替えて利用することが可能となっている．
ツールキットの一方の利用者であるアプリケーション開発者にとっては，多くの選択肢から目的に合った
ルーティングアルゴリズムを選択できることが望まし

ツールキットは Routing Driver の実装として itera-tive ルーティングと recursive ルーティング6),15) の 2
種類を提供している（3.3 節）．そのどちらかを，アルゴリズム実装（Routing Algorithm）には一切の変更なしで，実行時に選択することが可能となった．
3.1 アルゴリズム側のインタフェース
Routing Driver から見た Routing Algorithm 側のプログラミングインタフェースを説明する．本ツール
キットの実装言語である Java 言語の形式で示す．
RoutingContext initialRoutingContext(

ID target)
ルーティング中，ノードからノードへ伝播する状態，
文脈の初期値を返す．文脈とは例えば Koorde であれ
ば，論文 5) の Figure 3 中の i（仮想ノードの ID）とkshif t である．ここで引数 target はルーティングのターゲットである．
IDAddressPair[] closestNodes(ID target,
int maxNumber, RoutingContext context)

情報処理学会論文誌: コンピューティングシステム,
Vol.47, No.SIG12 (ACS 15), pp.358-367, 2006年9月

4

図 2 Overlay Weaver のランタイムを構成するコンポーネント群
Fig. 2 Components organizing runtime of Overlay Weaver.

引数 target で表される ID に対して最も近い ID をようとする際のルーティングにおいて，経路上の全ノー持つノードを，最大 maxNumber ノード返す．Routing
Driver は，返されたノード群を，先頭から順にルー
ティングの次ホップ候補として扱う．返り値には，この処理が実行されているノード自身を含めてもよい．

ドに対して呼び出される．引数 joiningNode は参加し引数 context は，ノード間を伝播する文脈を必要としないアルゴリズムでは null が与えられる．アル
ゴリズム実装は，次ホップに伝播させる文脈を，返り値である IDAddressPair 型の値，つまり次ホップ候
補に付加して返すことができる．

ようとしているノード，lastHop は経路を 1 つ遡ったノードである．引数 isRootNode としては，root ノードに対して呼び出される際には true，そうでない場
合には false が与えられる．

void touch(IDAddressPair from)from から何らかのルーティング用メッセージを受信した際に呼び出される．
void forget(IDAddressPair node)

ここで，ID はルーティングのキーやノードの ID を

node を経路表から外すべき際に呼び出される．現表す型であり，IDAddressPair は ID と通信用アド実装では，node との通信に連続して一定回数失敗しレスの組である．通信用アドレスは，例えば UDP や
TCP では IP アドレスとポート番号の組となる．
IDAddressPair[] adjustRoot(ID target)

た場合に，このメソッドが呼び出される．

BigInteger distance(ID to, ID from)
引数として与えられた 2 つの ID 間の距離を返す．

ルーティングの最終段階で，ルーティングのターゲッ

厳密には，このメソッドが Routing Algorithm 側イ

トに最も近い ID を持つノードに対して呼び出される．

ンタフェースの一部である必要はない．Routing Driver

引数 target がターゲットである．自身が root，つまから呼び出されることはなく，アルゴリズムの実装内

りルーティングの目的地である場合には null または部で用いられるだけだからである．

空の配列を返す．そうでない場合は，root ノードの候

ここで BigInteger は多倍長整数型である．

補を返す．
void join(IDAddressPair[] route)
あるノードがオーバレイに参加しようとする際，
Routing Driver はそのノードの ID をターゲットと3.2 各アルゴリズムによるインタフェースの実装
本ツールキットが実装を提供しているルーティングア
ルゴリズムは Chord と Pastry，Tapestry，Kademliaである．表 1 は，これらの各アルゴリズムが Routing

してルーティングを行う．このメソッドは，ルーティ

Algorithm 側インタフェースが規定するどのメソッドに対して有効な実装を提供しているかを示したものである．表中の join(1)，(2) はそれぞれ，3.1 節に 2 度
現れる join に，現れる順番通りに対応している．
adjustRoot は Chord が必要とする（‡1）．他のアングが完了した後，参加しようとしているノードに対して呼び出される．引数 route としては，参加しようとしているノード自身から（参加前の）root ノードまでの経路が与えられる．

void join(IDAddressPair joiningNode,
IDAddressPair lastHop, boolean isRootNode)
このメソッドは，あるノードがオーバレイに参加しルゴリズムでは closestNode を呼び出して次ホップを順に辿り最も近いノードにたどり着けば，それがルーティングの目的地，つまり root ノードとなる．しかし情報処理学会論文誌: コンピューティングシステム,
Vol.47, No.SIG12 (ACS 15), pp.358-367, 2006年9月

5
表 1 アルゴリズム側インタフェースが規定するメソッドと各アルゴリズムの対応
Table 1 Correspondence between methods specified by
Routing Algorithm interface and routing algorithms.

Chord Pastry Tapestry Kademlia
closestNodes
adjustRootjoin(1)join(2)
touchforgetdistance

×
× ‡1
×

×
×

×

×

×
×
×
×

×
×
×
‡2

×

メッセージの送受信を表す．括弧内の数字は，通信が起こる順を表す．図の通り，iterative ルーティングではルーティングを始めたノードが経路上の各ノードに対して順に問い合わせを行い，recursive ルーティング
ではルーティング要求が経路に沿って転送されていく．
図 3 中の破線は，一般的な iterative/recursive ルー
ティングでは行われるとは限らない通信を表す．図 3
c の（5）と（6）は adjustRoot （3.1 節）の問い合
わせと返答を表す．本ツールキットが実装を提供して×××いるアルゴリズムのうちこれを必要とするのは Chordのみであり，他のアルゴリズムでは（5），（6）の通信は起こらない．
図 3 b 中の破線は，ルーティング要求メッセージに対する返答であり，到達確認メッセージを表す．これは，信頼性のない通信路でも確実にルーティングを完遂するために送受信している．ただし，経路上の各ノード
は，到達確認の返信よりもルーティング要求の転送を

a. Iterative ルーティング

b. Recursive ルーティング

優先して行う．このため，ルーティングに要する時間に対して通信遅延が支配的である場合には，iterative
よりも recursive ルーティングの方がルーティングに要する時間が短いことが期待できる．

1 回のルーティングに要するメッセージの数は次の通りである．Chord のように adjustRoot を必要とす
るアルゴリズムを除き，図 3 より，経路が n ホップのc. Iterative ルーティング（Overlay Weaver の場合）

場合 iterative ルーティングで 2n，recursive ルーティ
ングで 2(n + 1) である．adjustRoot を必要とするア

図 3 ルーティングの様式
Fig. 3 Routing styles.

ルゴリズムで iterative ルーティングを行う場合には，2(n + 1) となる．
Chord では，最も近いノードではなくその successor
が root ノードである．そのため，最も近いノードが4. ツールキットの構成

求まった後で，root ノードを求めるための補正が必要

本章では，本ツールキットを構成するランタイムととなる．adjustRoot メソッドはこの補正を行う．

各種ツールについて説明する．また，それらがルーティ

Tapestry はルーティングに ID 間距離を用いず，定められた手順に従って次ホップを決める．このため，ングアルゴリズムの設計と実装，試験，そしてアルゴ

Tapestry が distance を実装する必要はない（‡2）．
Pastry も Tapestry と同様に，routing table を参照してのルーティングには距離を用いない．しかし，ルー
ティングの最終段階で用いる leaf set を保守するため

リズム間の比較をどうサポートするかを述べる．
本ツールキットは，図 2 に示す各コンポーネントと，
次に挙げるツール群から構成される．

• 分散環境エミュレータ• シナリオ生成器

3.3 ルーティング共通処理
Routing Driver，すなわちルーティング共通処理の実装として，本ツールキットは iterative ルーティン
グと recursive ルーティング6),15) の 2 種類を提供し• メッセージカウンタ• メッセージング可視化ツール
Routing Driver と Routing Algorithm 以外のコン
ポーネントも，複数種類の実装を実行時に差し替えて利用することが可能である．例えば Messaging Serviceている．そのどちらかを実行時に選択できる．

としては次の 3 種類を提供している．

に，distance を呼び出してノードをソートする．

図 3 は両様式で行われる通信を図示したものである．円はノードを表し，直線の矢印は破線を含めて• UDP 実装• TCP 実装

情報処理学会論文誌: コンピューティングシステム,
Vol.47, No.SIG12 (ACS 15), pp.358-367, 2006年9月

6

図 5 メッセージング可視化ツール
Fig. 5 Messaging Visualizer.
図 4 エミュレータの構成
Fig. 4 Structure of Emulator.

• 単一プロセス内のスレッド間で通信をエミュレー
トする実装（エミュレータ用）

4.1 高レベルサービスとサンプルアプリケーション
3 章で説明したルーティング層の上に，アプリケー
ションが直接利用する高レベルサービスが実装される（図 2）．本ツールキットは高レベルサービスとして，

Messaging Service が行う．
シナリオファイルにはまず，起動するクラスの指定，起動する際の引数，起動の指示を記述する．Scenario
Sequencer はそれを読み込み，アプリケーションをスレッドとして起動する．シナリオには続いて，アプリ
ケーションに対して与える指示を記述できる．1 つの指示は，指示内容と相手先，指示を与える時刻から成る．指示は標準入力を通して与えられるため，アプリ

DHT に加えて Mcast を提供している．Mcast はマル
チキャスト機能を提供する高レベルサービスである．
これを用いることで，ID で識別されるグループへの参加，離脱，また，グループに参加している全ノードへのマルチキャストを行うことができる．

4.3 メッセージカウンタ
Messaging Service には，メッセージ送受信をネット
ワーク越しに逐一報告させることができる．メッセー

サンプルアプリケーションとして，それぞれ DHT

ジカウンタは，この報告を受信してメッセージ数を数

ケーションが受け付ける文字列ならどういった指示でも与えることが可能である．

シェル，Mcast シェルを提供している．これらを用いえるツールである．

ることで，両サービスを起動して，キャラクタ端末もこれらシェルをエミュレータ（4.2 節）と組み合わせ

4.4 メッセージング可視化ツール
Messaging Visualizer は，メッセージ送受信の様子を実行中に可視化するツールである．可視化結果を図 5て利用することで，ルーティングアルゴリズムの動作に示す．ノードは，円環や直線などの上に，その ID

試験や比較を行うことができる．5 章では，こういっに応じた位置に描画される．通信は，発生した時点でた比較が可能であることを示す．

送信元と送信先ノードの間に弧が描かれる．Mcast が

しくはネットワーク経由で直接制御することができる．

4.2 エミュレータ
本ツールキットは分散環境エミュレータを提供してマルチキャストのために構築する配送木も描画される．

おり，数千ノードを計算機 1 台上でエミュレートでき観的に把握できる．動作試験に有用であるだけでなく，る．これを用いることで，ルーティングアルゴリズム

アルゴリズムの実演説明に用いることもできる．

を設計，実装する際に動作試験をエミュレータ上で繰り返し行いながら品質を向上させることができる．まこのツールを用いることでアルゴリズムの動作を直4.5 各アルゴリズムの実装とパラメータ
本ツールキットが提供する Chord，Pastry，Tapes-

ズム研究の成果が直接アプリケーションに結び付く．

try，Kademlia 実装について，その詳細と，5 章の実験で用いるパラメータを述べる．
Chordstabilization を行う通常のアルゴリズムに加えて，
論文 1) の Figure 6 に示されている，オーバレイ参加

た，同一のシナリオを異なるアルゴリズムで実行することでアルゴリズム間の公正な比較を行うことができる．なおかつ，その結果得られた実装をそのまま実際の分散環境で動作させることができるため，アルゴリ
エミュレータの構成を図 4 に示す． 起動されたア

時に経路表を完成させてしまうアルゴリズムについて

プリケーションインスタンスには仮想ホスト名が割も実装を提供している．こちらのアルゴリズムは，以り当てられ，仮想ホスト間の通信をエミュレータ用

降「Chord (Figure 6)」と表記する．

情報処理学会論文誌: コンピューティングシステム,
Vol.47, No.SIG12 (ACS 15), pp.358-367, 2006年9月

7
手続き stabilize を呼び出す間隔は，はじめは 10

3000

秒だが，経路表に変更がなかった場合には徐々に延ば2500

していき，最長 120 秒まで広げる．fix fingers の呼

s
p
1500
te
s

び出し間隔は，ﬁnger table の埋まり具合いに応じて

5 秒から 600 秒の間の値をとる．
PastryID は 4 ビットを 1 つの digit とした（b = 4）．Pastry，Tapestry 実装ともに，この値は実行時に指定できる．leaf set のサイズは 8 とした（|L| = 8）．

Overlay Weaver
MACEDONMace
p2psim

2000
1000
500
0

Chord

PastryTapestry

Kademlia

図 6 各アルゴリズム実装のステップ数
Fig. 6 Lines of code for each routing algorithm.

経路表維持のためには，Pastry の最初の提案2) と多い Pastry でも 900 ステップ弱である．これは，ルーは異なるが，論文 23) の Section 2.2 に記述されていティングに共通する処理をアルゴリズム実装から分離

る periodic routing table maintenance を行う．そのしたこと（3 章）の成果である．

間隔は 60 秒とした．

オーバレイのアルゴリズムを記述するための専用言語を用意している MACEDON と比較しても，Chord

Tapestry
ID は，論文 3) を通して行われている通り，16 進数の 1 桁を 1 つの digit として扱う（β = 16）．Pastryと同じパラメータである．
現実装は backup links を用意しない（c = 1）．また，backpointer を保持しない．
Kademlia
k-bucket の長さは論文 4) の通り 20 とした（k =20）．ルーティング中に保持するターゲット ID への
最近接ノードの数も論文 4) の通り 20 としたが，問い合わせを受けたノードが返す最近接ノードの数は 20

テップ数は本ツールキットの方が少ない．p2psim ではアルゴリズム実装自身が通信や RPC といった低レベルの処理を行うため，コードの量が多くなっている．

MACEDON の Chord 実装は，本ツールキットとは異なり，論文 1) に記述されているアルゴリズムのサブセットであることを追記しておく．ID は 160 ビッ
トではなく 32 ビットであり，保持できる successor は
ただ 1 つである．

5.2 4000 ノードのエミュレーション
エミュレータ上で大規模な動作試験が可能であるこではなく 5 とした．
並行クエリ（3.3 節）の並行性（concurrency）は，論文の通り 3 とした（α = 3）．

5. 評

でたかだか約 1.6 倍のステップ数であり，Pastry のスとを示すために，計算機 1 台で 4000 ノードをエミュレートした結果を示す．この実験の目的はアルゴリ
ズムの比較やパラメータの評価それ自体ではなく，本価

ツールキットを用いることで公正な比較や評価を行い

本研究の目標は，アルゴリズムの設計と実装を容易得ることを示すことである．

にしてその成果を直接アプリケーションに結び付ける

実験は，3.4 GHz Pentium 4（Prescott）と 1 GBことである．そこで，次の 4 点について本ツールキッのメモリを搭載した PC で行った．OS は Linux 2.6.15
である．本ツールキットの実行に用いた Java 実行系

トを評価する．

• アルゴリズムの実装が容易であること

は，Java 2 Standard Edition（J2SE） 5.0 Update• 多ノードのエミュレーションでアルゴリズム実装の動作を確認できること• アルゴリズム間の比較を公正に行えること• アプリケーションが実ネットワークで動作すること6 である．
図 7，図 8 に，4000 ノードのエミュレーションを行った際の，1 秒および 1 ノードあたりのメッセージ数を示す．メッセージ数は 10 分間の平均値である．エ5.1 アルゴリズム実装のコード量
アルゴリズム実装の容易さを示すために，図 6 に，現実装が提供しているアルゴリズム実装のステップ数
を MACEDON16),17) ，Mace18) ，p2psim20) と比較して示す．ここでステップ数とは，空行とコメントを除

ミュレーションシナリオの内容は，6 秒おきに 4000
ノードがオーバレイに参加した後，100 秒間の休みをおいて，2 秒おきに DHT への put を 4000 回繰り返
し，再び 100 秒間の休みをおいて，2 秒おきに DHT
からの get を 4000 回行うというものである．put とget を行うノードは，シナリオを生成器を用いて生成いた後のコードの行数である．
本ツールキット上では，どのアルゴリズムもたかだ
か数百ステップで実装できている．最もステップ数がする際に乱数で決めている．
アルゴリズムを評価，比較するためには，調べたい

情報処理学会論文誌: コンピューティングシステム,
Vol.47, No.SIG12 (ACS 15), pp.358-367, 2006年9月

8
Chord
Chord (Figure 6)
Kademlia
PastryTapestry

0.2

0.15
0.1

0.05

e
M

0

10000

20000
30000
Time (seconds)

図74000 ノードのエミュレーションシナリオでの 1 秒・1 ノー
ドあたりのメッセージ数（Iterative ルーティングの場合）
Fig. 7 Number of messages per second per node passed
between emulated 4000 nodes (iterative routing).

Chord
Chord (Figure 6)

0.2

PastryTapestry

0.15
0.1

0.05

e
M

0

0.3
0.2
0.1

0

1000

2000
Time (seconds)

0

10000

20000
Time (second)

30000

40000

図8

3000

図 9 実機 197 台での 1 秒・1 ノードあたりのメッセージ数（Iterative ルーティングの場合）
Fig. 9 Number of messages per second per node passed
between real 197 computers (iterative routing).

0.5

0.25

e
d
o
n
/
d
n
o
c
e
s
/
s
e
g
a
s
s

0.4

0

40000

Messages / second / node

0

Chord
Chord (Figure 6)
Kademlia
PastryTapestry

0.5
Messages / second / node

0.25

e
d
o
n
/
d
n
o
c
e
s
/
s
e
g
a
s
s

Chord
Chord (Figure 6)
PastryTapestry

0.4
0.3
0.2
0.1
0
0

1000

2000
Time (seconds)

3000

4000 ノードのエミュレーションシナリオでの 1 秒・1 ノー
ドあたりのメッセージ数（Recursive ルーティングの場合）
Fig. 8 Number of messages per second per node passed
between emulated 4000 nodes (recursive routing).

図 10 実機 197 台での 1 秒・1 ノードあたりのメッセージ数（Recursive ルーティングの場合）
Fig. 10 Number of messages per second per node passed
between real 197 computers (recursive routing).

内容についてのログを出力させて，エミュレート後にして PING，ACK の送受信を行う．このため，約集計すればよい．ノード単独で算出できる値，例えば24000 秒経過以降の put/get 時に，put/get に必

DHT でのデータ保持量や経路表の収束具合いであれ
ば，この方法で済む．一方，複数ノードが関わる値については，時刻情報を付けてログを出力しておいて後で集計するか，メッセージカウンタ（4.3 節）を使っ要となるより多くのメッセージを送受信している．
ありふれた PC を用いて 4000 ノードをエミュレー
トし，アルゴリズムの挙動を調べることができた．また，アルゴリズムの公正な比較を行うためのデータ採て集計すればよい．図 7 と図 8 を作成するためのデー取方法を述べ，そのうち，メッセージカウンタを用い

タ採取はメッセージカウンタを用いて行った．

る方法を行って結果を示した．

図 7 と図 8 からは，各アルゴリズムの以下の挙動を読み取ることができる．

• Chord と Pastry はオーバレイ保守のために定期的な通信を行うため，Kademlia，Tapestry 実装と比較して，定常状態でのメッセージ数が多い．
• Chord (Figure 6) は，オーバレイ参加時に，経路表を完成させるために多くのメッセージを送受信する．
• Kademlia は，通信相手ノードを経路表に加えるか否かを判断するために，経路表中のノードに対

5.3 実ネットワークでの動作確認
本ツールキットが実ネットワークで動作することを示す．実験は，AIST スーパークラスタ（ASC）の一部である 3.06 GHz Xeon 搭載 PC 196 台に加えて，
5.2 節で用いた PC 1 台の合計 197 台で行った．PC のネットワークインタフェースはすべて Gigabit イーサ
ネットであり，ASC の 196 台は同一のスイッチに接続されている．ASC と残る 1 台の間には 3 台のルータがあるが，帯域幅は 1 Gbps が確保されている．196
台の OS は Linux 2.4.24 であり，Java 実行系は J2SE

情報処理学会論文誌: コンピューティングシステム,
Vol.47, No.SIG12 (ACS 15), pp.358-367, 2006年9月

9
5.0 Update 6 である．DHT シェルを各 PC に 1 つず
つ起動し，ネットワーク越しに制御した．
図 9 と図 10 は 1 秒および 1 ノードあたりのメッ
セージ数を示したものである．メッセージ数は 1 分間の平均値である．集計にはメッセージカウンタを用いた．制御シナリオは，8 秒おきに 197 ノードがオーバ
レイに参加した後，100 秒間の休みをおいて，2 秒おきに DHT への put を 500 回繰り返し，30 秒間の休みをおいて，2 秒おきに DHT からの get を 500 回行
うというものである．put，get を行うノードはやはり乱数で決めた．
約 200 台という規模の実ネットワークで本ツールキットが動作することを確認できた．

6. ま と め
本論文では，ネットワークオーバレイのアルゴリズ
ム研究基盤として開発しているツールキット Overlay

Weaver の設計を述べた．これを用いることで，既存のよく知られたルーティングアルゴリズムをたかだか
数百ステップで実装できること，また，計算機 1 台上
で 4000 ノードという規模のエミュレーションを行ってアルゴリズムの挙動，性質を調べられることを示した．約 200 台の実環境での動作も示した．
同時に，アルゴリズムの実装をルーティング処理の実装から分離する両者間のインタフェースを提案した．
アルゴリズム実装の容易さはこの分離の成果である．

参

考 文

献

1) Stoica, I., Morris, R., Karger, D., Kaashoek,
M. F. and Balakrishnan, H.: Chord: A Scalable
Peer-to-peer Lookup Protocol for Internet Applications, Proc. ACM SIGCOMM 2001 , pp.
149–160 (2001).
2) Rowstron, A. and Druschel, P.: Pastry: Scalable, decentralized object location and routing
for large-scale peer-to-peer systems, Proc. Middleware 2001 (2001).
3) Zhao, B. Y. et al.: Tapestry: A Resilient
Global-Scale Overlay for Service Deployment,
Journal on selected area in communications,Vol. 22, No. 1, pp. 41–53 (2004).
4) Maymounkov, P. and Mazières, D.: Kademlia: A Peer-to-peer Information System Basedon the XOR Metric, Proc. IPTPS’02 (2002).
5) Kaashoek, M. F. and Karger, D. R.: Koorde:
A simple degree-optimal distributed hash table, Proc. IPTPS’03 (2003).
6) Rhea, S., Geels, D., Roscoe, T. and Kubiatowicz, J.: Handling Churn in a DHT, Proc.

USENIX ’04 (2004).
7) The Bamboo Distributed Hash Table.
http://www.bamboo-dht.org/.
8) Chimera and Tapestry. http://p2p.cs.ucsb.
edu/chimera/.
9) Khashmir. http://khashmir.sourceforge.net/.
10) Azureus: Java BitTorrent Client. http://azureus.sourceforge.net/.
11) The Oﬃcial BitTorrent Home Page. http://
www.bittorrent.com/.
12) eMule-Project.net - Oﬃcial eMule Homepage.
http://www.emule-project.net/.
13) Overlay Weaver: An Overlay Construction
Toolkit.
http://overlayweaver.sourceforge.
net/.
14) 首藤一幸, 田中良夫, 関口智嗣: オーバレイ構築
ツールキット Overlay Weaver, 先進的計算基盤シ
ステムシンポジウム（SACSIS2006）論文集, pp.
183–191 (2006).
15) 首藤一幸, 加藤大志, 門林雄基, 土井裕介: 構造化
オーバレイにおける反復探索と再帰探索の比較,
情報処理学会研究報告, 2006-OS-103-2 (2006).
16) Rodriguez, A., Killian, C., Bhat, S. andKostić, D.: MACEDON: Methodology for Automatically Creating, Evaluating, and Designing Overlay Networks, Proc. NSDI’04 , pp.267–
280 (2004).
17) The MACEDON project. http://macedon.
ucsd.edu/.
18) The Mace project. http://mace.ucsd.edu/.
19) Loo, B. T., Condie, T., Hellerstein, J. M.,
Roscoe, P. M. T. and Stoica, I.: Implementing
Declarative Overlays, Proc. SOSP ’05 (2005).
20) p2psim: a simulator for peer-to-peer protocols.
http://pdos.csail.mit.edu/p2psim/.
21) Li, J., Stribling, J., Morris, R. and Kaashoek,
M. F.: Bandwidth-eﬃcient management of
DHT routing tables, Proc. NSDI’05 (2005).
22) Dabek, F., Zhao, B., Druschel, P., Kubiatowicz, J. and Stoica, I.: Towards a Common API for Structured Peer-to-Peer Overlays,
Proc. IPTPS’03 (2003).
23) Castro, M., Costa, M. and Rowstron, A.: Debunking some myths about structured and unstructured overlays, Proc. NSDI’05 (2005).
(平成 18 年 1 月 26 日受付)
(平成 18 年 5 月 23 日採録)

情報処理学会論文誌: コンピューティングシステム,
Vol.47, No.SIG12 (ACS 15), pp.358-367, 2006年9月

10
首藤 一幸（正会員）関口 智嗣（正会員）

1996 年早稲田大学理工学部情報学

1959 年生．1982 年東京大学理学科卒業．1998 年同大学メディアネッ

部情報科学科卒業．1984 年筑波大学

トワークセンター助手．2001 年同大学院理工学研究科修了．同年電子大学大学院理工学研究科情報科学専

技術総合研究所入所．以来，データ駆攻博士後期課程修了．同年産業技術

動型スーパーコンピュータ SIGMA-

総合研究所入所．2006 年ウタゴエ (株) 取締役最高技
ラミング言語処理系，情報セキュリティ等に興味を持

1 の開発等の研究に従事．2001 年独立行政法人産業技術総合研究所に改組．2002 年 1 月より同所グリッド
研究センターセンター長．並列数値アルゴリズム，計つ．SACSIS2006 最優秀論文賞．日本ソフトウェア科

算機性能評価技術，グリッドコンピューティングに興学会，IEEE–CS，ACM 各会員．

味を持つ．市村賞，情報処理学会論文賞受賞．グリッ術責任者．博士（情報科学）．分散処理方式，プログド協議会会長．日本応用数理学会，ソフトウェア科学
会，SIAM，IEEE，つくばサイエンスアカデミー各会
田中 良夫（正会員）

員．

1965 年生．1995 年慶応義塾大学
大学院理工学研究科後期博士課程単位取得退学．1996 年技術研究組合新情報処理開発機構入所．2000 年通産
省電子技術総合研究所入所．2001 年
4 月より独立行政法人産業技術総合研究所．現在同所
グリッド研究センター主幹研究員．博士 (工学)．グ
リッドにおけるプログラミングミドルウェア，グリッドセキュリティ，およびテストベッド構築に関する研究に従事．IC’99，HPCS2005，SACSIS2006 論文賞．
ACM 会員．

情報処理学会論文誌: コンピューティングシステム,
Vol.47, No.SIG12 (ACS 15), pp.358-367, 2006年9月