何かのやり方や、問題の解決方法をどんどんメモするブログ。そんな大学院生の活動「キャッシュ」に誰かがヒットしてくれることを祈って。
2011-10-12 Wed 18:59 |
P2P、特にDHTの前提知識が無い状態から、オリジナルDHTアルゴリズムを実装・評価できるようになるまでの学習方法と参考資料をまとめました。
基本的なアルゴリズムの仕組みから、実装評価に用いるツールキットの使い方までを短期間で学習することが出来ます。
﹁P2Pに関する卒論を書こうと思っている人﹂や﹁P2Pアプリケーションの開発前に、アルゴリズムをテストしたい人﹂、﹁なんとなくP2Pアルゴリズムに興味が出た人﹂などにぴったりだと思います。また、研究室での後輩教育用資料にするのも良いと思います。実際に使いましたし。
ここで紹介する資料一覧は以下の通りです。
●
資料1‥﹁ChordアルゴリズムによるDHT入門﹂
●
資料1ーオプション1‥﹁DHTアルゴリズムSymphonyの解説﹂
●
資料1ーオプション2‥﹁Mercuryではじめる範囲検索のできるDHT﹂
●
資料2‥﹁Chordの論文﹂
●
資料3‥﹁Overlay Weaver の使い方﹂
●
資料3-オプション1‥﹁マニュアル: DHT シェル﹂
●
資料3-オプション2‥﹁Eclipseを使う︵Windows︶|Javaプログラミングの始め方﹂
●
資料4‥﹁Overlay Weaverの使い方(2) ログから経路情報を読み取る方法編﹂
●
資料5-1‥﹁Overlay Weaver で新しいルーティングアルゴリズムを作る方法(1/3)﹂
●
資料5-2‥﹁Overlay Weaver で新しいルーティングアルゴリズムを作る方法(2/3)﹂
●
資料6‥﹁Overlay Weaver で新しいルーティングアルゴリズムを作る方法(3/3)﹂
大部分がこのブログの記事です。記事一覧が無かったので、学習の流れを新たに書き、その参考資料としてまとめました。まず学習の流れの概要を紹介し、その次に学習の各ステップで一覧に示した資料がどう役立つかを説明します。
学習の流れ概要
学習の流れはこんな感じ。
(一)
有名DHTアルゴリズム﹁Chord﹂のエッセンスをさくっと学習する
(二)
Chordの論文を読む︵オプション︶
(三)
DHT構築フレームワークの導入・実行方法を学び、既存アルゴリズムを動かしてみる
(四)
アルゴリズムの動作ログの取得・解析方法を学習する
(五)
フレームワーク上にオリジナルアルゴリズムを実装する方法を学ぶ
(六)
実際にオリジナルアルゴリズムを動かして、動作ログを取り、分析・評価する
ほぼ全てのステップに関して、今までに書いた資料が存在するので、それを参考にすれば、何もない状態から比較にならないほどスムーズに基礎知識を身につけて、アルゴリズムを考える部分に注力できるようになるはずです。
資料の概要
以上の流れに沿った学習を手助けしてくれる"資料"の概要は以下の通りです。
1.有名DHTアルゴリズム﹁Chord﹂のエッセンスをさくっと学習する
資料1‥﹁ChordアルゴリズムによるDHT入門﹂
まずは、DHTの基礎知識と、超有名なDHTアルゴリズムのエッセンスを学びます。
いきなり論文を読むのは敷居が高く、どうせ読むなら全体像を把握してから読んだ方が効果的だと思うので、まずは解説を読むと良いと思います。
他のアルゴリズムはこちら↓
資料1ーオプション1‥﹁DHTアルゴリズムSymphonyの解説﹂
資料1ーオプション2‥﹁Mercuryではじめる範囲検索のできるDHT﹂
2.Chordの論文を読む︵オプション︶
資料2‥﹁Chord: A scalable peer-to-peer lookup service for Internet applications︵論文︶﹂
ただ実装したいだけならば論文を読む必要は無いかもしれません。一方、卒論を書くとかなら論文を読んだほうがよいでしょうす。エッセンスが学習済みなので、だいぶ読みやすいと思います。
3.DHT構築フレームワークの導入・実行方法を学び、既存アルゴリズムを動かしてみる
資料3‥﹁Overlay Weaver の使い方﹂
この資料では、DHTを構築できるフレームワークである﹁Overlay Weaver﹂をEclipseを用いて実行する方法を詳細に解説をしています。
資料の大まかな流れは次のようになっています。
●
ソースコードの取得方法︵eclipseを用いたsourceforgeレポジトリからのインポート︶
●
シナリオファイル︵ノードの動作を記述する設定ファイル︶の書き方
●
実行結果を見やすくする方法
●
Eclipseでの起動設定の見本
●
起動方法
この資料を読めば、1台のマシン上でエミュレータを起動し、10、100、1000ノード以上のDHTネットワークを用いた実験ができるようになります。より高度な実験をするためには、この資料を読んだ後に次の公式資料をチェックすると良いでしょう。
資料3-オプション1‥﹁マニュアル: DHT シェル︵シェルのコマンド︶←リンク先の下半分と資料3を見比べる﹂
もし、Eclipseの環境が準備できていない場合は、たとえば次の資料を参考にしてください。
資料3-オプション2‥﹁Eclipseを使う︵Windows︶|Javaプログラミングの始め方﹂
4.アルゴリズムの動作ログの取得・解析方法を学習する
資料4‥﹁Overlay Weaverの使い方(2) ログから経路情報を読み取る方法編﹂
資料3を読むだけでもアルゴリズムの動作ログが出力されるのですが、読み取れる情報がかなり限定されてしまいます。資料4では、探索経路や経路長、経路表やノードの内部状態といった、分析・評価するための重要な情報を取得するstatusコマンドの使い方と、出力されたログファイル︵テキストファイル︶の読み方を解説しています。
5.フレームワーク上にオリジナルアルゴリズムを実装する方法を学ぶ
資料5-1‥﹁Overlay Weaver で新しいルーティングアルゴリズムを作る方法(1/3)﹂
資料5-2‥﹁Overlay Weaver で新しいルーティングアルゴリズムを作る方法(2/3)﹂
いよいよオリジナルのアルゴリズムを実装する方法です。
資料5-1では、最低限どんなパッケージ・クラスを作成する必要があるかおよび、それぞれのクラスの役割や継承すべきインターフェースなどを解説しています。
資料5-2では、作成すべきクラスのうち、最も重要なクラスの全メソッド解説を行っています。
これらの資料は基礎の基礎ですが、たくさんのソースコードを読んでこの基礎を見つけ出すのはかなり苦労します。まずはこの基礎の基礎を理解し、必要に応じてすでに学習したChordがOverlay Weaverでどう実装されているかを参考にすればスムーズに実装できるはずです。
6.実際にオリジナルアルゴリズムを動かして、動作ログを取り、分析・評価する
資料6‥﹁Overlay Weaver で新しいルーティングアルゴリズムを作る方法(3/3)﹂
この資料では、新しく作成したオリジナルアルゴリズムをOverlay Weaver本体から呼び出すための具体的な準備方法を解説しています。この準備をすることで、すでに学習した﹁既存アルゴリズムの動かし方﹂と同じようにオリジナルアルゴリズムを動かすことが出来るようになります。
まとめ
より高度なことをするためにはいろいろ調べたり、Overlay Weaverのいろいろな箇所のソースコードを見る必要が当然出てきますが、それは必要が出てきてからで十分であって、まずは基礎知識と実装・実験方法のエッセンスを学ぶことが一番だと思います。ただし、これを何も知らない状態から学ぼうとするとかなり大変です。
その大変なところをこの資料で出来るだけ軽くして、浮いた時間を"オリジナルアルゴリズム"を考える作業やデバッグ作業にまわしていきましょう-。
ちなみに、Overlay Weaver上でうまくアルゴリズムが実装できると、ネットワークエミュレータ上で動いたアルゴリズムをそのまま実マシンのネットワークで動かすことも出来るので、なかなか楽しいですよ。
コメントの投稿 エントリの新旧に関わらず、極力18時間中に返信します。
アクセスカウンタ
アクセスランキング
人気エントリ
新ブログ人気記事
最新記事
月別アーカイブ
プロフィール
カテゴリ
タグ