修士進捗報告
オーバーレイ・ネットワークにおける 適応型アルゴリズムを用いたデータ
配置最適化手法
M2 （ 3 期目） kuro 親：斉藤さん
サブ親：重近さん
スケジュール確認
• MAUI （春学期）
– 4
月19
日•
研究を説明– 5
月31
日•
研究を発表– 7
月5
日（今学期最後のMAUI
）
今ココ•
題目申請に向けて– 7
月23
日•
修士題目申請2010/7/1 MAUI Project 2010
2
この MAUI でご相談したいこと
• 題目
–
主査・副査• 夏期休暇に向けて
–
今後の方針–
研究テーマ2010/7/1 MAUI Project 2010
3
修士論文題目申請
題目申請
• 日本語
–
オーバーレイ・ネットワークにおける適応型 アルゴリズムを用いたデータ配置最適化手法• English
– Data Placement Optimization
for Overlay Networks by an Adaptive Algorithm
• 主査・副査（敬称略）
–
主査:
村井 純–
副査:
斉藤 賢爾、江崎 浩（ICT
先端融合研究）2010/7/1 MAUI Project 2010
5
オーバーレイ・ネットワークにおける 適応型アルゴリズムを用いたデータ
配置最適化手法
研究目的
• 研究目的
–
オーバーレイ・ネットワークにおいてデータ転送パフォーマンスを高速化する
•
回線速度限界まで使ってデータ転送•
有限なネットワークリソースを効率的に利用• アプローチ
–
データ配置を最適化する•
データをオーバーレイ・ネットワーク上に事前配置する•
これまでのオーバーレイ・ネットワークには無い手法– CDN
などでは当たり前に使われている手法2010/7/1 MAUI Project 2010
7
要求から取得までの時間の短縮
• データ発見＋データ取得
–
どちらも高速でなければならない1. データ発見の高速化
–
検索アルゴリズムの改良•
分散ハッシュテーブル、グループ化など–
クエリへの応答を高速化•
オーバーレイ上で近くにノードを配置する2. データ取得の高速化
–
高速な回線を持っているノードを選択–
複数のノードから同時に転送を行う2010/7/1 MAUI Project 2010
8
ノード配置・データ配置
• ノードの配置（網の組み方）
–
要求が行われるノードの近くにいる–
リソース（ネットワーク・ストレージ）に余裕がある• データの配置
–
これまで（リアクティブ型）•
データの要求元から計算・計測
最適なノードを見つけることが可能–
配置を行う場合（プロアクティブ型）•
データを持っているノードから計算・計測•
要求がどこにあるかわからない2010/7/1 MAUI Project 2010
9
オーバーレイ・ネットワークの性質
• オーバーレイ・ネットワーク
–
様々な種類がある•
規模（扱うデータ）•
重要になるパラメータ• etc…
• 万能のアルゴリズムは無い
–
それぞれについて性質を理解する必要がある–
ネットワーク・アーキテクチャ、理念の違い•
変化させるパラメータの違い•
最適化するべき部分の違い2010/7/1 MAUI Project 2010
10
解き方
• オーバーレイ・ネットワーク毎に検討する
–
モデル化を行う•
ノードの配置方法（網の組み方）–
リンク（回線速度）–
ストレージ•
データの配置方法（プロアクティブ・リアクティブ）–
識別子（名前、ハッシュ）–
サイズ–
性質–
適応型アルゴリズムの適用• GTYPE
• PTYPE
2010/7/1 MAUI Project 2010
11
0 1 1 0 1 0 1 0 1 1
データの型
• データには型があるはず
–
同じような性質のデータを示す•
人間が理解できるもの•
例）カテゴリ、ジャンル、etc…
–
適応型アルゴリズム使用時の種• GTYPE
は型を代表することになる• 問題点
–
どうやって型を抽出するのか–
データの型の例•
データについている名前を解析•
あらかじめキーを指定する2010/7/1 MAUI Project 2010
12
1 ST step
Winny と比較
Winny の特徴
• オーバーレイ・ネットワーク
–
非構造化オーバーレイ–
クラスタリングされたノード群•
クラスタ中のノードのつながりは密に•
広告・検索により目的のデータが見つかりやすい• 理念
–
匿名性＋効率性の追求–
上流（回線の速い）ノードへデータを集める•
検索効率の向上＋中継データの転送速度向上•
川の流れアーキテクチャ2010/7/1 MAUI Project 2010
14
クラスタ間のつながりは疎
Winny のモデル化
•
ノードの配置方法–
クラスタリングキーワード•
同じようなキーワードを持つノードへ優先的に接続–
回線速度（自己申告）•
データの配置方法–
ファイル名–
ハッシュ値•
データ発見＋データ取得1.
オリジネータがデータを公開（広告を開始）2.
広告・検索により他のノードに発見され転送開始•
データを取得したピアも同じようにデータを広告• 4%
の確率で中継が発生し、中継ノードもデータを取得・広告2010/7/1 MAUI Project 2010
15
Winny のデータの型
• クラスタリングキーワード
–
自分の嗜好に合わせて設定–
指定しない場合はファイル名が設定される•
ダウンロードリストにあるファイル名–
文字列の部分一致により判定• GTYPE の抽出方法
–
クラスタリングキーワードをハッシュ–
得られたハッシュ値をGTYPE
として指定– GTYPE
の類似度により同じデータをグループ化2010/7/1 MAUI Project 2010
16
データを配置するノードの決定
• オーバーレイの性質
–
クラスタリングによるグループ化が行われる• キャッシュを置くべきノードの抽出
– GTYPE
•
クラスタリングキーワード•
ファイル名（キー）– PTYPE
• 1
リンクあたりの平均回線速度–
最終的に得られるノード•
データの検索・取得に適したノード2010/7/1 MAUI Project 2010
17
まとめ
まとめ
• 題目申請
• データ配置最適化
–
データ発見の高速化–
データ取得の高速化–
ノードの配置・データの配置• オーバーレイ・ネットワークに合わせた配置
–
モデル化–
適応型アルゴリズム2010/7/1 MAUI Project 2010
19
スケジュール
• 7 月
– 15
日Winny
のシミュレーション動作完成– 22
日 ネットワーク構成部分のシェイプアップ– 30
日 アルゴリズムの設計＋実装• 8 月
– 6
日 アルゴリズムの実装完了（予定）– 9
日～15
日 お盆休み（引き続き実装）– 20
日 アルゴリズムシミュレーション部分の完成– 31
日 シミュレータ完成• 9 月
– 10
日 アルゴリズムの検証2010/7/1 MAUI Project 2010
20
おわり
