修士進捗報告
オーバーレイ・ネットワークにおける 適応型アルゴリズムを用いたデータ
配置最適化手法
M2 （ 3 期目） kuro 親：斉藤さん
サブ親：重近さん
スケジュール確認
• MAUI （春学期）
– 4
月19
日•
研究を説明– 5
月31
日•
研究を発表– 7
月5
日（今学期最後のMAUI
）
今ココ•
題目申請に向けて– 7
月23
日•
修士題目申請2010/6/30 MAUI Project 2010
2
この MAUI でご相談したいこと
• 題目
–
主査・副査• 夏期休暇に向けて
–
今後の方針–
研究テーマ2010/6/30 MAUI Project 2010
3
修士論文題目申請
題目申請
• 日本語
–
オーバーレイ・ネットワークにおける適応型 アルゴリズムを用いたデータ配置最適化手法• English
– Data Placement Optimization
for Overlay Networks by an Adaptive Algorithm
• 主査・副査（敬称略）
–
主査:
村井 純–
副査:
斉藤 賢爾、江崎 浩（ICT
先端融合研究）2010/6/30 MAUI Project 2010
5
オーバーレイ・ネットワークにおける 適応型アルゴリズムを用いたデータ
配置最適化手法
研究目的
• 研究目的
–
オーバーレイ・ネットワークにおいてデータ転送パフォーマンスを高速化する
•
回線速度限界まで使ってデータ転送•
有限なネットワークリソースを効率的に利用• アプローチ
–
データ配置を最適化する•
データをオーバーレイ・ネットワーク上に事前配置する•
これまでのオーバーレイ・ネットワークには無い手法– CDN
などでは当たり前に使われている手法2010/6/30 MAUI Project 2010
7
実現手法
• 適応型アルゴリズムの使用
–
適切な位置をデータ自身が学習–
データは自律的に最適な位置へ移動する2010/6/30 MAUI Project 2010
8
データ自身の識別子 データが格納されるノード
Adaptive
Algorithm
データ配置 @ オーバーレイ・ネットワーク
• オーバーレイ・ネットワーク
–
様々な種類がある•
規模（扱うデータ）•
重要になるパラメータ• etc…
• 万能のアルゴリズムは無い
–
それぞれについて性質を理解する必要がある–
ネットワーク・アーキテクチャ、理念の違い•
変化させるパラメータの違い•
最適化するべき部分の違い2010/6/30 MAUI Project 2010
9
前回の MAUI でいただいたコメント
• 武藤研の学生が論文を書いている
–
（2007
年度 修士論文 ）望月洋介氏• NicoNet:
動画共有サービスに適したP2P
動画配信システム•
“本研究では、再生が集中している動画件数を除いた残り の動画群についてオーバーレイ技術を適用して～”–
配信サーバ＋P2P
ネットワーク–
確かにロングテール問題は重要だが…
•
本研究ではOut of Scope
• 評価手法について
–
シミュレーションで評価して欲しい•
様々なオーバーレイ・ネットワークを対象に実験可能•
アルゴリズムの開発がしやすい2010/6/30 MAUI Project 2010
10
というわけで、シミュレーションで
シミュレーション環境
•
パラメータ–
ノード•
数• Churn
•
回線速度–
データ•
数•
サイズ•
ニーズ•
展開の方法•
公開する時間•
オーバーレイの構造–
構造化–
非構造化•
結果–
ノードごとの転送速度• 1
リンクあたりの速度•
総転送量–
ストレージ使用量•
合計使用量2010/6/30 MAUI Project 2010
12
最適なアルゴリズムを発見
1 ST step
Winny と比較
Winny の構造
•
ノード–
クラスタリングキーワード （最大3
個まで）•
同じようなキーワードを持つノードへ優先的に接続–
回線速度（自己申告）•
データ–
ファイル名–
ハッシュ値•
データの展開1.
オリジネータがデータを公開（広告を開始）2.
広告・検索により他のノードに発見され転送開始•
データを取得したピアも同じようにデータを広告• 4%
の確率で中継が発生し、中継ノードもデータを取得・広告–
それぞれのピアには接続数が設けられている• Up: 2 / Down: 2
–
徐々にデータが広がっていくため、爆発的な要求には応えられない•
データの削除は行われずユーザが勝手に削除するまで理論上消えない2010/6/30 MAUI Project 2010
14
Winny の特徴
• オーバーレイ・ネットワーク
–
非構造化オーバーレイ–
クラスタリングされたノード群•
クラスタ中のノードのつながりは密に•
広告・検索により目的のデータが見つかりやすい• 理念
–
匿名性＋効率性の追求–
上流（回線の速い）ノードへデータを集める•
検索効率の向上＋中継データの転送速度向上2010/6/30 MAUI Project 2010
15
クラスタ間のつながりは疎
どこを変更するのか
• ノード
–
回線速度を自己申告
実測に–
その他のパラメータや網の組み方は変更しない• データ
–
リアクティブ型
プロアクティブ型へ•
適応型アルゴリズムを用いてデータを配置•
需要が無くなったデータは削除• シミュレーションでの動作
–
網の構成までは同一–
データの展開の時点で振る舞いを変更2010/7/1 MAUI Project 2010
16
変更点詳細
•
ノード–
クラスタリングキーワード （最大3
個まで）•
同じようなキーワードを持つノードへ優先的に接続–
回線速度（実測）•
データ–
ファイル名–
ハッシュ値•
データの展開1.
オリジネータがデータを他のノードへ配置2.
データを取得したノードはデータを広告、検索に応答3.
広告・検索により他のノードに発見され転送開始•
データを取得したピアも同じようにデータを広告–
それぞれのピアの接続数は回線速度に応じて決定–
予めデータが広がるため、爆発的な要求に対応可能•
リソースは余分に使用する2010/7/1 MAUI Project 2010
17
スケジュール
• 7 月
– 15
日Winny
のシミュレーション動作完成– 22
日 ネットワーク構成部分のシェイプアップ– 30
日 アルゴリズムの設計＋実装• 8 月
– 6
日 アルゴリズムの実装完了（予定）– 9
日～15
日 お盆休み（引き続き実装）– 20
日 アルゴリズムシミュレーション部分の完成– 31
日 シミュレータ完成• 9 月
– 10
日 アルゴリズムの検証2010/7/1 MAUI Project 2010
