Document

P2Pネットワークにおける同期の
最適化機構
NAGELの提案
ECN (B3) ichiriki
親 mika
研究背景
• 昨今のインターネットを利用したオンライン
ゲームの普及
• 従来はクライアント・サーバ型
• 最近ではP2P型のゲームの登場
P2Pでのコンテンツ検索機構の分類
• Hybrid P2P (WinMX)
– サーバがコンテンツの所在を管理
• Pure P2P (Winny)
– コンテンツの所在を逐次的に検索
P2P論理ネットワークトポロジの分類
• フルメッシュ型
– ノードから全てのノードへ1ホップ接続
• 非メッシュ型
– 発見時の接続経路を維持し、マルチホップし
て拡大していく
P2Pネットワークゲームの現状
• コンテンツの検索はHybrid P2Pで参加ノー
ドを決定
• 論理ネットワークトポロジ形態はフルメッ
シュ型P2P
P2Pネットワークゲームの問題
• 同期(ゲーム状態の一貫性)
– 同期が取られないと…
同期の問題とは
• 多くのノードが参加すると…
– 通信経路の回線速度にばらつきが出る
– 同期できる頻度が少なくなる
• 同期の種類
– イベントベース…ユーザーの操作で同期
– タイムベース…一定時間で同期
NAGELの提案
• 各ノードがゲーム状態を最も遅延の短い
経路で送受信するシステム
• タイムベースで同期
想定環境
• リアルタイム性が必要なゲーム
• ゲームはイベントベースで実装されたもの
• 既存のHybrid P2P上でメッシュを構成
システム構成図
遅延計測
ノード階層化
通常ノード
マスターノード
Master
遅延報告
ルートノード
Root
同期確立
同期確立
動的経路最適化
遅延計測しノード階層化
遅延計測
ノード階層化
通常ノード
マスターノード
Master
ルートノード
Root
各ノードで遅延計測
最大遅延4
平均遅延3
ルート
遅延
B-A
4
B-C
4
B-D
1
A
4
B
最大遅延5
平均遅延4.3
5
ルート
遅延
A-B
4
A-C
5
A-D
2
最大遅延5
平均遅延3.6
2
D
1
4
ルート
遅延
C-A
5
C-B
4
C-D
4
4
C
最大遅延4
平均遅延2.3
ルート
遅延
D-A
2
D-B
1
D-C
4
マスターノードの選出
遅延情報パケット
最大遅延5
マスター発動パケット
A
最大遅延4
平均遅延3
B
4
平均遅延3.6
マスター起動
5
2
D
1
4
最大遅延5
平均遅延4.3
4
最大遅延4
平均遅延2.3
C
ルートノードの選出
遅延情報パケット
ルート発動パケット
A
ルート起動
3
B
4
1
D
1
3
3
C
各ノードごとの機能説明
遅延計測
ノード階層化
通常ノード
マスターノード
Master
遅延報告
ルートノード
Root
同期確立
同期確立
動的経路最適化
【通常ノード】
遅延計測
ノード階層化
通常ノード
マスターノード
Master
遅延報告
ルートノード
Root
同期確立
同期確立
動的経路最適化
【通常ノード】で
マスターに遅延報告
ルート
遅延
B-A
4
B-C
4
B-D
1
A
4
B
5
ルート
遅延
A-B
4
A-C
5
A-D
2
2
D
1
4
ルート
遅延
C-A
5
C-B
4
C-D
4
4
C
Master
リンク
遅延
A-B
4
B-C
4
C-D
4
A-C
5
B-D
1
A-D
2
【マスターノード】
遅延計測
ノード階層化
通常ノード
マスターノード
Master
遅延報告
ルートノード
Root
同期確立
同期確立
動的経路最適化
【マスターノード】で
動的な最適通信経路の構築
Dの収集した通信経路の情報
リンク
遅延
A-B
4
B-C
4
C-D
4
A-C
5
B-D
1
A-D
2
4
4 B
A
5 C
2 D
1
C
D
4
4
D
C
4 B
4 D
1
D
1
B
1 B
4 C
4
C
4
B
A→B より A-D-B の方が効率的
【マスターノード】
各ノードに最適通信経路の通知
A-D-B
A
4
B
5
ルート
遅延
ルート
遅延
A-B
4
A-D-B
3
A-C
5
A-C
5
A-D
2
A-D
2
2
D
1
4
4
C
Master
リンク
遅延
A-B
4
B-C
4
C-D
4
A-C
5
B-D
1
A-D
2
【マスターノード】
同期確立
ゲーム状態の情報
A
4
B
5
2
D
1
4
Master
4
C
イベントベースのずれをタイムベースで修正
【ルートノード】
遅延計測
ノード階層化
通常ノード
マスターノード
Master
遅延報告
ルートノード
Root
同期確立
同期確立
動的経路最適化
【ルートーノード】
同期確立機能
T ゲーム状態の情報+
通常ノードへの送信A
開始時間
1分後に送信実行
B
T
4
1分後に送信実行
T
5
2
D
1
4
Root
4
T 1分後に送信実行
C
イベントベースのずれをタイムベースで修正
Root
同期確立機能
Master
• ルートノードはゲームの状態を定期的にマ
スターに送信
– マスター間の同期を指示する
• マスターノードは通常ノードに送信
Master
Master
Game-State
Game-State
Master
Root
Game-State
Game-State
Master
実装
•
•
•
•
アプリケーションレイヤーで実現
既存のHybrid P2P機構に実装
ゲームプログラムにNAGEL-APIを提供
ゲームはイベントベースで実装する
Game Application
NAGEL
P2P Architecture
Network Protocol
評価方法
• 通常ノードとマスターノードの情報を集計
–
–
–
–
時間単位当たりの遅延平均
各ノードの最終遅延平均
通信経路変更ログ
総合送受信メッセージ数・サイズ
• 従来のP2Pメッシュと比較
• 最適なマスターノード選出数を出す
本日のまとめ
• P2Pネットワークゲームで同期が問題
• 解決のためのNAGELの提案
– 各ノードでゲーム状態を最も遅延の短い経路
で通すシステム
– タイムベースで同期するシステム
終わり
NAGEL動作手順
Server
ノード検索
Master
メッシュ形成
既存のHybrid P2Pによりメッシュを構築
システム構成図
NAGEL
ノードの階層化機能ノード状態情報
遅延計測機能
遅延テーブル
同期確立機能
動的リンク変更機能
リンク情報テーブル
遅延報告機能
遅延計測
ノードの階層化機能
ノード状態情報
遅延テーブル
遅延報告機能
遅延計測機能
同期確立機能
動的リンク変更機能
リンク情報テーブル
Network

Download Report