オーバレイ構築ツールキットOverlay Weaver 首藤一幸、 田中良夫、関口智嗣 論文発表：さだ
概要 Overlay Weaverの提案 オーバレイネットワークのフレームワーク 一度実装すれば、シミュレータでの実験も、実環境での動作もできる ルーティング機能が予め提供されており、オリジナルのアルゴリズムの実装が容易 See http://overlayweaver.sourceforge.net/
1. はじめに 多くのStructured overlay networkに関する研究 多数ノードでの評価が欠かせない アルゴリズム：Chord, CAN, Tapestry, Kademlia ライブラリ：JXTA, Khashmir, Bamboo DHT など アプリケーション: BitTorrent 多数ノードでの評価が欠かせない これまでシミュレーション用、実環境用と分けて実装する必要があった
Overlay Weaverの提案 オーバレイネットワークのフレームワーク 一度実装すれば、シミュレータでの実験も、実環境での動作もできる ルーティング機能が予め提供されており、オリジナルのアルゴリズムの実装が容易 （Chord, Pastry, Tapestry, Kademlia のJava実装が手に入る）
2. 関連研究 MACEDON p2psim Cに似た独自の言語でアルゴリズム実装可能 ns用のコードも生成可能 これ自身はエミュレータを持たない ModelNetを使うと、最大1000ノードまで 後継のMaceもあるが、Pastryしか実装されていない p2psim C++でアルゴリズム実装可能 Chord, Tapestry, Kademlia, Koordeなどの実装がある シミュレータ専用
3. ルーティング共通処理とアルゴリズムの分離 Key-based routing (KBR) キーを用いた通信プロトコル Structured overlay network に共通の処理 層に分離→アルゴリズムが可換に
3.1アルゴリズム側のインタフェース Javaによる実装 IDAddressPair[] closestNodes(ID target, int maxNumber) Target に近いノードを複数返す IDAddressPair[] adjustRoot(ID target) Chord用, closestNodes void join(IDAddressPair[] route) Chord用 join void join(IDAddressPair joiningNode, IDAddressPair lastHop, boolean isRootNode) Pastry, Tapestry用 join、これらはjoin時に途中経路のルーティングテーブルを更新する必要があるため void touch(IDAddressPair from) ルーティング用メッセージを受け取った時に実行される void forget(IDAddressPair node) 経路表からnodeをはずす BigInteger distance(ID to, ID from) ID同士の距離を返す
3.2 各アルゴリズムによるインタフェースの実装 対応表
3.3 ルーティング共通処理 Routing Driverの実装（起動時に変更可） Iterative routing Recursive routing
4. ツールキットの構成 分散環境エミュレータ シナリオ生成器 メッセージカウンタ メッセージング可視化ツール
4.1 高レベルサービスとサンプルアプリケーション DHT Group Manager (マルチキャスト機能の提供) アプリケーション DHTシェル Group Managerシェル
4.2 エミュレータ シナリオをシナリオファイルに記述 起動するクラスと引数、その後の指示 アプリケーションはそれぞれスレッドとして起動する
4.3 メッセージカウンタ Messaging Service はメッセージ送受信をネットワーク越しに報告可能 それを数えるカウンタ
4.4 メッセージング可視化ツール
4.5 各アルゴリズムの実装とパラメータ 今回提供する実装 Chord Pastry Tapestry Kademlia
5 評価 5.1 アルゴリズム実装のコード量 5.2 4000ノードのエミュレーション 5.3 実ネットワークでの動作確認
5.1 アルゴリズム実装のコード量 ステップ数＝空行・コメントを抜いた実際のコード量 いずれも数百ステップで実装できた
5.2 4000ノードのエミュレーション ありふれたPCで、4000ノードのエミュレーション
5.3 実ネットワークでの動作確認 AISTのクラスタマシンを用い、約200台で動作確認
6 まとめ Overlay weaver の設計を述べた アルゴリズムの実装が容易 4000ノードのエミュレーションが可能 約200台での実環境での実験もできた