修士進捗報告
オーバーレイ・ネットワークにおける 適応型アルゴリズムを用いたデータ
配置最適化手法
M2 （ 3 期目） kuro 親：斉藤さん
サブ親：重近さん
スケジュール確認
• MAUI （春学期）
– 4 月 19 日
•
研究を説明– 5 月 31 日
•
研究を発表– 7 月 5 日 （今学期最後の MAUI ） 今ココ
•
題目申請に向けて– 7 月 23 日
•
修士題目申請2010/7/4 MAUI Project 2010
2
この MAUI でご相談したいこと
• 題目
– 主査・副査
• 夏期休暇に向けて
– 今後の方針
– 研究テーマ
修士論文題目申請
題目申請
• 日本語
– オーバーレイ・ネットワークにおける適応型 アルゴリズムを用いたデータ配置最適化手法
• English
– Data Placement Optimization
for Overlay Networks by an Adaptive Algorithm
• 主査・副査（敬称略）
– 主査 : 村井 純
– 副査 : 斉藤 賢爾、江崎 浩（ ICT 先端融合研究）
オーバーレイ・ネットワークにおける 適応型アルゴリズムを用いたデータ
配置最適化手法
ばらまいて刈り込む
↓
最初から良さそうな位置に配置するぜ！
背景
• オーバーレイ・ネットワーク
– 大容量化するデータ
•
品質の向上、メディアの進化、・・・– On-demand 配信の限界
•
アクセスの集中、ノードの性能限界、・・・– これからは配置（ Pre-load ）が重要に！
•
パフォーマンスの向上、安定した供給• 問題
– どこに配置すればいいのかわからない
•
ノードとデータのマッチングが取れない•
ノードもバラバラ、データもバラバラ分析
• データを配置する場所
– 要求が生まれるところ
•
データを配置する意味がある•
理想：「ダウンロードしようと思ったらもうあった！」• クラスタリングがデータ主体になっていない
– ノード主体
•
緩いクラスタリング•
どこが最適かわからない– データ主体
•
厳密なクラスタリング•
最適な場所がわかる2010/7/5 MAUI Project 2010
8
ノード主体のクラスタリング 緩いクラスタリング
目的
• オーバーレイ・ネットワークにおいて
データが適切な位置に配置されるようにする
– 欲しかったデータがすぐそこに！（ここに！）
• アプローチ
– プロファイルを作成する
•
ノードプロファイル–
過去の履歴から予測•
データプロファイル–
データの性質を抽出– データのクラスタリング ノードのクラスタリング
•
より細かい粒度のクラスタリングが可能にプロファイルの作成
• プロファイルの抽出
– 過去にダウンロードしたデータの名前を処理
– 自然言語処理により抽象度の高いデータを取得
•
例）カテゴリ、タイトル、タイプ、etc…
• Node Profile Table （ NPT ）に記録する
– 判定ビット
•
強く支持
支持
支持しない
削除•
一定期間or
ダウンロード時に評価を行う– 判定ビット・ダウンロード量 接続ノードを決定
•
厳密なクラスタリングが可能になる2010/7/4 MAUI Project 2010
10
プロファイル（
Hash
） ダウンロード量（Byte
） 判定ビット（2bit
）データ配置
• ノードプロファイルとの比較
– 適応型アルゴリズムを使用
• GTYPE
– データプロファイルに適合するノード
• NPT
にエントリが存在&&
支持ビットが立っている• PTYPE
– エントリ数が少ないノード
• ○データに対する要求が高い（適切なノード）
• ×オーバーレイ上に長くいない
𝐹𝑖𝑡𝑛𝑒𝑠𝑠 =
全ノードのエントリ数合計 全ノード数考えなければならないこと
• オーバーレイ・ネットワーク
– 様々な種類がある
•
規模•
扱うデータ– 想定する環境によって状況は異なる
• プロファイルに使用するデータ
– 目的のデータが取得できるようにする必要がある
•
自然言語処理アルゴリズム–
ニューラルネットワーク？•
メタデータ（タグ）の使用2010/7/4 MAUI Project 2010
12
評価
• シミュレーションを用いて行う
1.
オーバーレイ・ネットワークを構築•
ノードのクラスタリングアルゴリズムを複数実装–
データプロファイル–
キーワード、etc…
2.
データ公開（＋配置）3.
ダウンロード• Point-to-Point
で行う• 評価パラメータ
–
オーバーレイ・ネットワーク上でのホップカウント•
目的のデータまでn
ホップ–
クラスタリングの正確さ•
オーバーレイ・ネットワークを再構成したとき
隣接ノードがどの程度の確率で変化するのか（ノード数）まとめ
まとめ
• 題目申請
• データ配置最適化
– 問題
•
オーバーレイ・ネットワーク上にデータを配置する際
どこに配置すればいいのかわからない– オーバーレイ・ネットワークにおいて
データが適切な位置に配置されるようにする
•
ノードのクラスタリングを厳格に行う•
データプロファイルによるクラスタリングの提案– 評価
•
シミュレーション2010/7/4 MAUI Project 2010
15
スケジュール
• 7 月
– 15 日 オーバーレイ・ネットワークの構成部分完成 – 22 日 ネットワーク構成部分のシェイプアップ
– 30 日 アルゴリズムの設計＋実装
• 8 月
– 6 日 アルゴリズムの実装完了（予定）
– 9 日～ 15 日 お盆休み（引き続き実装）
– 20 日 アルゴリズムシミュレーション部分の完成 – 31 日 シミュレータ完成
• 9 月
– 10 日 アルゴリズムの検証
2010/7/4 MAUI Project 2010
16
おわり
前回の MAUI でいただいたコメント
• 武藤研の学生が論文を書いている
– （ 2007 年度 修士論文 ）望月洋介氏
• NicoNet:
動画共有サービスに適したP2P
動画配信システム•
“本研究では、再生が集中している動画件数を除いた残り の動画群についてオーバーレイ技術を適用して～”–
配信サーバ＋P2P
ネットワーク– 確かにロングテール問題は重要だが …
•
本研究ではOut of Scope
• 評価手法について
– シミュレーションで評価して欲しい
•
様々なオーバーレイ・ネットワークを対象に実験可能•
アルゴリズムの開発がしやすい2010/7/4 MAUI Project 2010
18
