Overlay Weaver の概要

[English | Japanese]
last-updated: April 17, 2009

Overlay Weaver はオーバレイ構築ツールキットです。 これを用いることで、オーバレイ設計者はたかだか数百ステップで structuredオーバレイのアルゴリズムを実装することができます。 また、計算機 1台の上で繰り返し試験を行って アルゴリズム実装の品質を向上させていくことができます。 どのアルゴリズム実装を使うかを実行時に決めることができ、 エミュレータを用いて数十万ノードの実験を行うことができるので、 設計者は新規、既存アルゴリズム間の比較を大規模かつ公正に行うことができます。 同時に、こうして実装したアルゴリズムはそのまま実ネットワーク上で動作するため、 アルゴリズム研究の成果が直接アプリケーションに結び付きます。

Table of Contents

ツールキット

このツールキットは、ランタイムと以下のツールから成ります。
ここで、括弧内の語は bin ディレクトリにあるコマンドの名前です。 また、以下のサンプルアプリケーションも提供しています。

ランタイム

図 1 はランタイムを構成するコンポーネント群を示しています。 図中のルーティング層 (routing layer) が、 Dabek らの提案 [1] にある key-based routing layer (図 2) に相当します。 Overlay Weaver の場合、ルーティング層は 3つのコンポーネントに分割されています。 すなわち、ルーティングドライバルーティングアルゴリズム、 および、メッセージングサービスの 3つです。 この分割によって、既存のいくつかのアルゴリズムを たかだか数百ステップで実装することが可能となりました。 本ツールキットは、ルーティングアルゴリズムとして Chord、Kademlia、Koorde、Pastry、Tapestry の実装を提供しています。 また、この分割によって、ルーティングドライバの側も どの実装を使うかを実行時に決められるようになりました。 iterative ルーティングと recursive ルーティング (図 3) [2] の実装が提供されています。

図 1: Overlay Weaver のランタイムを構成するコンポーネント群

図 2: Key-based routing (KBR) (論文 [1] より引用)

図 3: ルーティングの様式
他のコンポーネントにも、複数の実装があります。
例えば、メッセージングサービスには次の 4種類の実装があります。 ディレクトリサービスには、次の 3種類の実装があります。

高レベルサービスとサンプルアプリケーション

ルーティング層の上には、それを利用する高レベルサービスが実装されています。 通常、アプリケーションが直接利用するのは高レベルサービスです。 Overlay Weaver は、高レベルサービスとして、分散ハッシュ表 (DHT) に加えて、 マルチキャスト (Mcast)を提供しています。 Mcast はオーバレイ上のマルチキャストを行います。 このサービスを用いると、ID を指定してのグループへの参加、グループからの離脱、 グループ中のメンバに対するマルチキャストを行うことができます。 Mcast また、マルチキャストで用いられる配送木の形状を アプリケーションに直接通知することもできます。 このサービスを用いるサンプルアプリケーションである IPv4 マルチキャストルータが、この機能を利用しています。

DHT シェルMcast シェルは これら高レベルサービスを利用するサンプルアプリケーションです。 これらはキャラクタ端末やネットワーク越しにコマンドを受け取り、 それに従って高レベルサービスを制御します。 これらのシェルをエミュレータと共に用いることで、 オーバレイアルゴリズムの試験や比較を行うことも可能となります。

DHT シェルはまた、XML-RPC プロトコルの問い合わせも受け付けます。 このプロトコルは Bamboo [4] や OpenDHT と互換です。 そのため、Bamboo、OpenDHT と動作するアプリケーションなら Overlay Weaver と共に動作させることができます。

分散環境エミュレータ

Overlay Weaver は分散環境エミュレータを提供しています。 これを用いると計算機 1台で数万のノードをエミュレートできます。 オーバレイ設計者は自身のアルゴリズムをエミュレータ上で迅速に繰り返し試験して、 品質を向上させることができます。 エミュレータはまた、大規模かつ公正なアルゴリズム間の比較を可能とします。 同時に、こうして実装されたアルゴリズムは実ネットワーク上でも動作するため、 アルゴリズム研究の成果がアプリケーションに直接結び付きます。

図 4 はエミュレータの構造を示しています。 エミュレータの利用法は 2通りあり、 計算機 1台で動作させる方法の他に、 複数台の計算機を協調させてエミュレーションを行う方法があります。 どちらの場合でも、エミュレータは同一のシナリオファイルを読み込み、 その内容に従ってアプリケーションを起動して制御します。


図 4: エミュレータの構造

ツールキットはまた、簡単なエミュレーションシナリオ生成器を 提供しており、これを用いることでシナリオファイルを生成できます。 シナリオは、もちろん、手で記述してもよいですし、 既存アプリケーションを動作させてトレースを集めて、 それをシナリオに変換するという作成法も考えられます。

Overlay Visualizer

Overlay Visualizer は、ノード間の通信を実行時に可視化します。 通信状況の収集にもメッセージングサービス自身を用いるため、 エミュレータ上でも実ネットワーク上でも動作します。

図 5 にスクリーンショットを示します。 また、"スクリーンショットとデモ" のページ には他にも画像があります。 ノードは、円や直線などの上に、その ID に応じた位置に投影されます。 ノードが通信を行うと、ノード間に弧が描かれます。 Mcast が構築する配送木も、色付きの線として描画されます。


図 5: Overlay Visualizer のスクリーンショット

参考文献

[1] Frank Dabek, Ben Zhao, Peter Druschel, John Kubiatowicz and Ion Stoica, "Towards a Common API for Structured Peer-to-Peer Overlays", Proc. the 2nd International Workshop on Peer-to-Peer Systems (IPTPS'03), February 2003.
[2] Sean Rhea, Dennis Geels, Timothy Roscoe and John Kubiatowicz, "Handling Churn in a DHT", Proc. 2004 USENIX Technical Conference (USENIX '04), June 2004.
[3] "Berkeley DB Java Edition", http://www.oracle.com/database/berkeley-db/.
[4] "The Bamboo Distributed Hash Table", http://bamboo-dht.org/.

Return to Documents page
Return to Overlay Viewer main page