オーバレイ構築ツールキット 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 ﻩ ﻩ ﻩ ﻩ ﻩ 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台での実環境での実験もできた
© Copyright 2024 ExpyDoc
