P2PMMOG ネットワークトポロジーによる遅延特性の評価
2007MI049 平山 佳典
指導教員

2007MI259 山原 雅也

河野 浩之
2.2 遅延問題における影響

1 はじめにゲームにおける遅延はパケットが送受信される間に生

現在, MMOG(Massively Multiplayer Online Game)

じる遅延時間以外にユーザの操作遅延なども含まれる

はクライアント・サーバモデルと Peer to Peer モデル

が, 本研究では通信における遅延についてのみ考える.

(以下 P2P モデル) の 2 種類のネットワークモデルで運営されている． 多くの MMOG はコンテンツ管理やセ遅延発生により影響を受けるゲームと受けにくいゲー

キュリティの確保・データの一貫性の確保の容易さからPerson Shooter) のような即時性を要求されるジャンルのものは, 遅延で大きな影響を受ける. Pantel らのムがある. FPS(First Person Shooter) や TPS(Third

クライアント・サーバモデルで運営が成されている. ク
ライアント・サーバモデルはサーバへの負荷が大きく,Real-Time Multiplayer Game[2] では遅延が及ぼす影イベント処理をするために遅延が発生する. 遅延が発響をプレイヤーの熟練度別に観測し, ユーザの体感に及生することにより, キャラクターの位置座標やキャラクぼす効果を調査した結果, 500ms 以上の遅延はゲームをターの位置座標の一貫性の欠如の問題が発生し, ゲーム遊ぶ上で許容することができないという結果に至ってが成立しなくなってしまう.

いる. 逆に, ターン制のような即時性を要求しないボー本研究ではソフトウェアシミュレータまたは, 実機をドゲームやシミュレーションは影響を受けにくいと言える.

利用したテストベッド, 仮想ノードを利用したテストベッドを利用して, 遅延を減らすための負荷分散を行え

実際に遅延が起こるとどのような現象が発生するのかるネットワークトポロジーのシミュレーションを行い,ということを FPS や TPS を用いて説明する．あるプ

それらの遅延特性を観測し, ネットワークトポロジー考レイヤーが他のプレイヤーに攻撃を当てた時，遅延が生察をするものとする.

じていない場合は見た目通りに当たり判定が生じる．し以 下, 2 章 で ま ず 現 状 の MMOG ネ ッ ト ワ ー ク モ

かし，遅延が発生している場合，相手に攻撃が当たった

デルと遅延による問題点を挙げる. 次に 3 章におい際に判定が生じずにしばらくした後に当たり判定が生じて,P2PMMOG のトポロジー提案を行い, 4 章でシミュるなど，場合によってはその攻撃の当たり判定自体がなレーションとその結果について考察し, 5 章でまとめとくなってしまう場合がある．このようなことが起こるとする.

本来なら倒せていたプレイヤーから攻撃を受けたり，当たったはずの攻撃が当たらなかったりなどゲームが成立

2 MMOG のネットワークトポロジーと遅延しなくなってしまう.

問題

既存の P2P を用いた MMOG と遅延によって出る影

2.1 ネットワークトポロジー

響を表 1 にまとめておく．

既存の MMOG の P2P 通信形態として, ハイブリッ

3 P2PMMOG に最適なトポロジーの提案

ド型 P2P を用いたものがある. その通信形態では, キャ

3.1 ネットワークシミュレータを用いたシミュレーラクター情報やロビー (ルーム) 情報, 経験値やアイテションの提案

ムの獲得などの重要な部分を占める情報はサーバで通信を行い, それ以外の相手キャラクターへのダメージ判定

本研究では MMOG を P2P を用いて作る場合，どのなどのゲームの対戦における部分は, プレイヤー同士でようなネットワークトポロジーを用いるのが一番最適で

P2P 接続を行っている.

あるかということを遅延とノードの関係から考えていプレイヤーの接続間のネットワークトポロジーにはく．これを行っていく手法としてゲーム領域を小領域にメッシュ型やリング型などが存在している．基本的な分割し, その領域ごとにサーバとなるマスターノードをネットワークトポロジーにはどれも利点・欠点が存在作成し, シミュレーションを行い, トポロジーの評価をし，大規模なネットワークや信頼性が求められるネットしていく. 領域を分割する方法として, ボロノイ分割をワークの場合, 複数のネットワークトポロジーを多層化用いる.

やハイブリッドにすることがある.

1

表 1 P2P 型ゲームの一覧

タイトル

ジャンル

人数

遅延による影響

アラド戦記

アクション RPG

8人キャラクターへの攻撃判定の遅れ

BlackShot

FPS

16 人

キャラクターへの攻撃判定の遅れ

SD GUNDAM
Capsule Fighter Online

TPS

8人

キャラクターの位置ずれ

3.2 ボロノイ分割

3.4 ネットワークシミュレーターの比較

ボロノイ分割とは, 施設などの最適配置を考える際に本研究はゲーム領域をボロノイ分割により領域分用いる分割方法である. ボロノイ分割の方法は, 複数個割し，負荷分散を行った場合の遅延をネットワークシの母点との距離に基いて領域を分割した図で, 隣り合うミュレーターを使用して計測を行う．今回の研究では母点間を結ぶ直線に垂直二等分線を引き, 各母点の最近

OverlayWeaver，OMNeT++，ns-2 の 3 つのシミュレー隣領域を分割したものである. 母点の配置の仕方により,ターを候補とした．

さまざまな領域に分割することができる.

OverlayWeaver は, アプリケーション開発やオーバレイのアルゴリズム設計などをサポートしているオーバレイ構築ツールキットである. このツールは, ルー
ティングアルゴリズムとして DHT(Chord, Kademlia,Koorde, Pastry, Tapestry) の実装を提供しており, 新規アルゴリズムの実装もすることができる. そして, 既存のアルゴリズムや新規に実装したアルゴリズムを試
験, 評価, 比較するためのエミュレータも提供している.
このエミュレータは数十万の仮想ノードを扱うことができ, 大規模エミュレーションによるアルゴリズム間の公正な比較を可能にする.

図 1 ボ ロ ノ イ 分 割 (引 用 元:南 山 大 学 情 報 シ ス テ

OMNeT++(Objective Modeler Network Testbed inC++) は, Andras Varga 等によって開発されたオブ

ム 数 理 学 科 ボ ロ ノ イ 図 http://www.ms.nanzan-u.ac.jp/dep/voronoi.html)

ジェクト指向の離散イベント型のネットワークシミュ
レータであり, Unix と Windows が対応 OS となってい

3.3 Area Of Interest
Area Of Interest(以下 AOI) とは, あるノードが他のる. C++ 言語のみで実装されているため, ユーザは提案手法を実装しやすいのが特徴である. さらに, GUI によノードとの通信を行う範囲のことを指す. 図 2 は★ノーるパラメータの設定, 確認などを行うことができるため,ドの AOI の範囲を円として表している. ★ノードの評価環境を容易に構築することができる．また，リアル

AOI 内の●ノード（AOIneighbor）は★ノードと通信を行いゲーム情報を交換し, そのゲーム情報をボロノイ

タイムでシミュレーション状況をアニメーション表示できることによって, 実装したプロトコルの動作把握やデ分割された領域内にいるプレイヤーにゲーム情報を送信バッグ処理が容易になるといったような特徴もある.

する.

ns-2(Network Simulator version 2) は，カルフォルニ
ア大学バークレイ校 (UCB/LBNL/VINT Project) によって開発された離散イベント型のネットワークシミュ
レータである．TCP, モバイルネットワークなどをサポートしており, インターネット上のプロトコル関連の研究に広く利用されている．
表 2 は以上のシミュレーターの実装環境や言語，特徴をまとめたものである．
本研究では, プレイヤーの Churn をパレートの法則を利用した ParetoChurn を利用するため, Churn の設
図 2 Area Of Interest

定やゲーム領域・ユーザ数・グループメンバーなどのパ2表2シミュレータの比較

OverlayWeaver

OMNeT++ns-2

OS

J2SE を持つプラットフォーム

Windows,Unix

Linux

言語

Java

C++

C++, OTcl

・提案手法が実装しやすい・TCP, モバイルネットワーク等の・多くのアルゴリズムを実装

・パラメータ設定のみで・多くのルーティング
特徴シミュレーションが可能

シミュレーションが可能

・イベントドリブン

・GUI によるパラメータ設定, 確認アルゴリズムを実装
・数十万のノードを扱える

・シミュレーション状況を・通信を実行時に可視化

・多くのネットワーク上の機能が実装されているアニメーション表示可能
・実行中にパラメータ設定変更不可

ラメータを容易に行うことができるため OMNeT++ を

ゲーム領域が分割されている数を表している．本研究で用いることにする.

はこの Group size を 5，10，15，20，25，30，35，40，3.5 シミュレーションを行う P2P 環境

45，50 と変更してシミュレーションを行う．
AOI Width は各ノードの AOI の大きさを表している．ここでは 50 とした．

本システムの実行環境は以下のような環境で行う．

表3

CPUtarget overlay terminalNum はシミュレーションに参加しているノード数のことを言い，本研究では 50 と実行環境

Intel(R) Core(TM)2

OS

Ubuntu 8.04

100 の場合で計測を行った．
Churn はノードの参加，離脱のことを表している．本
研究では Churn のモデルとして ParetoChurn を使用す

Memory4GBる．Pareto Churn は MMOG やファイル共有に適して

simulator

OMNeT++4.1

simulation model

OverSim

Quad CPUいるモデルであり，本研究に適したモデルである．

simulated time は 10000s に設定する．
4.2 シミュレーション結果
4.2.1 node50 でのシミュレーション結果

4 シミュレーション結果と考察
本研究では前章で延べた通り，OMNeT++ と Over-Sim を利用し，MMOG のゲーム領域をボロノイ分割して遅延を計測するシミュレーションを行っていく．

4.1 ネットワークシミュレーターのパラメーターの設定
本研究では OverSim のパッケージである Vast モデ
ルを利用し，シミュレーションを行っていく．設定する
パラメーターは以下のようにして行う．

area dimension はシミュレーションでのゲーム領域の大きさを表している．本研究では 1000m × 1000m，2000m × 2000m，5000m × 5000m，10000m × 10000mの 4 種類の大きさのゲーム領域に設定し，シミュレーションを行う．
次に movement speed とは移動体速度で各ノードの移動速度を表している．本研究では世界中のプレイヤー

図 3 node50 でのシミュレーション結果

数の 60 ％のシェアを誇る MMOG である”World ofWarcraft” で使用されている 5m/s を使用する．
Group size はゲーム領域内でのグループの数，つまり34.2.2 考察得た．

前節のグラフを見ると node50 でのシミュレーション

また，node の数値が大きいほど Delay の数値が大き

結果は Delay の数値が 0.06 から 0.11 の間の数値をとっくなると考えていたのだが，それぞれのグラフを見るており，2.2 で記述したように Pantel らの Real-Timeと node50 の時よりも node100 の時の方が Delay の数

Multiplayer Game[2] で述べられている 500ms 以上の遅延にはなっておらず，MMOG を行う際に問題は発生値が小さい傾向があることがわかる．さらには node がしないということがわかる．

は分割をしていない状態よりも分割をしている状態の方

50，100 の場合はゲーム領域の分割数が 15 から 25 の時が Delay の数値が小さくなるという結果を得ることがさらには破線は area dimension が 0 の時を表しており，どのゲーム領域の大きさでも分割数が 15 から 25できた．の時に分割を行っていない場合よりも Delay が小さく5 まとめなっている.

4.2.3 node100 でのシミュレーション結果

本研究では結果として，すべての数値がゲームを遊ぶ上で致命的な影響を及ぼすと言われている 500ms 以下の数値を示し，ボロノイ分割を行った場合，分割数が 15から 25 の時に分割を行わない状態よりも Delay が小さくなるという結果を得ることができ, ボロノイ分割が有用であると言うことができた．しかし，今回のシミュレーションでは実世界でのプレイヤーの距離や各ノードのスペックの違いを考えず，ゲーム内のみでのシミュレーションを行ったものである．
そこで今後の課題としてゲーム内のみではなく実世界の環境も考慮し，シミュレーションを行い，計測をする必要があると考えられる．それにより実際の環境により近いシミュレーション結果が得ることができると考えられる．また，本研究ではノード数を 50 と 100 のみで行っているのでノード数を大きくしていった時に同様の結果を得ることができるかということやシミュレーショ

図 4 node100 でのシミュレーション結果

ン回数を重ねても同様の結果が得ることができるのかということも今後の課題である．

4.2.4 考察
前節のグラフを見ると node100 でのシミュレーショ

参考文献

ン結果は Delay の数値が 0.07 から 0.11 の間の数値を[1] 宮地 利幸，三輪 信介，篠田 陽一， ネットワーク実
験の支援技術, マルチメディア, 分散, 協調とモバイ
ルシンポジウム, pp.797-807, 2009.

とっており，node50 の時と同様に 2.2 で記述したように

Pantel らの Real-Time Multiplayer Game[2] で述べられている 500ms 以上の遅延にはなっておらず，MMOG[2] Lothar Pantel, Lars Wolf， On the impact of delayon real-time multiplayer games. In Proceedings ofを行う際に問題は発生しないということがわかる．
さらには破線は area dimension が 0 の時を表しておthe 12th international workshop on Network andoperating systems support for digital audio andvideo, pp.23-29. ACM Press, 2002.

り、どのゲーム領域の大きさでも分割数が 15 から 25の時に分割を行っていない場合よりも Delay が小さくなっている.

4.3 node50 と node100 での考察
図 3，図 4 を見ると，Delay の数値のバラつきは area

[3] Michael Miller， P2P コンピューティング入門, 株式会社 翔泳社，pp.229-309, 2002.

dimension が大きくなるほど安定していく傾向を見ることができる．Delay の数値のバラつきは，node 数が50 の場合より 100 の場合の方が Delay の数値が大きく[4] 首藤 一幸, 田中 良夫, 関口 智嗣， オーバーレイ
構築ツールキット Overlay Weaver, 情報処理学会論文誌：コンピューティングシステム, Vol.47,No.SIG12(ACS 15), pp.358-367, 2006.

なると考えていたが，node50 の時よりも node100 の時の方が Delay の数値が小さい傾向があるという結果を4