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
© Copyright 2024 ExpyDoc