Speedは2台のコンピュータがネットワークを通じてリアルタイムで動作します。そこで問題となる点が、同時出しのときにどちらが早いのかが公平にできるかという点です。実際に起こりうる事例をみてみると、場に数字が３のカードが置いてあり、お互いの手の中に４のカードを持っていてそれを同時に出したときに、どちらが早いのか、ということにあたります。
そのために、時間の概念を取り入れることにしました。具体的には相手との接続が確立し、ゲームがスタートしてから何秒たったのかが分かる、いわゆるタイマーです。しかしタイマーを開始させるにあたり、非常に遅延が生じているネットワーク環境でも、２台のコンピュータが正確に同タイミングでタイマーが開始できるのか、という問題があります。そこで、NTPという時刻を同期するためのプロトコルを使い、遅延の生じているネットワーク環境でもタイマーが同時に開始できるようなシステムを作成しました。
そしてそのタイマーを使うことによって、お互いがカードを操作した正確な時間を測定することができ、どちらが早いのかを判断することができます。ですが、ユーザによってカード情報が更新されたとき、それが相手に受け入れられたかどうかを判定するには、お互いのメッセージが「出しっぱなし」では困るわけで、そのメッセージが受け入れられるものなのかを返答する必要があります。そのためには、要求を出してそれが受け入れられたかを知るまでは、次の要求を出すことができません。そこで相手との通信のやりとりの中で、「更新権」を持たせることにして、その権利を持っているときのみ、更新できるという方法をとりました。更新権は一つしかなく、それがお互いがキャッチボールをするように移動します。イメージとしては次のような図です。
そして最後に、その結果を調査するためにに、、パケット情報が見れるデバック画面を作成しました。以上をまとめると次のようになり、順に説明します。
タイマーを使わないプログラムを考えてみると、開始から終了まで常にＣＰＵは休むことなく連続処理をしています。そこに時間というものを取り入れる事によって、様々な動作が可能になります。例えば、一定時間毎に処理を行いたいとき、処理時間を計りたいとき、処理を遅らせたいとき、等の用途があります。規模が大きいプログラムを作成すれば、必ず必要になってくるものではないかと思います。
今回はWindowsで使う事を目的としますが、タイマーの種類はいくつかあるので、用途によって使い分けてください。１[s]ごとに更新を行いたい場合と、1[ms]とでは精度が異なるように、まずは希望する精度に伴ったタイマーを使用する必要があります。
アメリカの規格です。time.hをインクルードすることによって使用できます。これは西暦年・月・日・時間・分・秒が取得でき、１日単位や大まかな時間を扱う場合など便利です。ただ、１秒に満たない細かな時間を扱う処理には向きません。
Windowsで使用することのできるタイマーで、0.001[s]単位で指定することができます。通常一定時間毎に処理を行いたい場合に使います。ただし0.001秒単位でできても、実際には0.054までしか扱えないので注意。
確実に1[ms]を確認できるタイマーです。OSが起動してからの時間を32[Bit]で保持してあり、正確な時間を割り出すことができます。今回作成しているSpeedでもこのタイマーが使用されています。ただ、32[Bit]ですので扱える時間に限界があり、計算してみると
232[ms] = 4294967296[ms] = 4294967.296[s] / 3600 = 1193[h] / 24 = 49.7[Day]
Sが起動して50日たったPCで使用すると、正常に動作しないようです。サーバ機など常時起動状態にあるPCでの使用は避けた方が良いでしょう。
この命令は時間ではなく、CPUのクロック数を数えるものなのでCPUの性能により異なります。取得できる値が時間ではないので、余分な計算をしなければなりませんが、1[GHz]のCPUであれば0.000,000,001(１ナノ秒)まで計測することができます。これはWindowsの機能を使用せず直接CPUに命令するものなので、どのOSでも使用することができます。ちなみに値は64[Bit]で、計算すると・・・
264[ns] = 18446744073709551616[ns] = 5124095[h] = 213503[Day]
OSが起動してから584年間は問題ありません。
今回使用したタイマーが1[ms]まで計ることが出来るマルチメディアタイマーですので、その仕様と記述方法を説明します。まずは機能を使用するための準備をするので、mmsystem.hをインクルードし、winmm.libとリンクする必要があります。これでtimeGetTimeという関数が使えるようになり、この関数はOSを起動してからの[ms]時間の値をDWORD型で返します。DWORD型がまさに32[Bit]の型で、この値をunsigned longとして使用します。時間を取得するだけなら、下記のような簡単な文でできます。
#include <stdio.h>
#include <windows.h>
#include <mmsystem.h>
#pragma comment(lib,"winmm.lib")
int main ( void )
{
DWORD dwTime; // 変数宣言
dwTime = timeGetTime(); // 時間を取得
printf("%lu", dwTime); // 時間を表示
return 0;
}
 |
これにより、通信開始からどのくらい経ったか知ることができ、相手との通信速度も図ることができるようになります。ですが、通信速度を計測するには、お互いのタイマーを正確に同期させなければなりません。通信速度は時と場合により変動するので、常にタイマーを合わせる処理を行う必要があります。またコンピュータの時計がずれてしまうように、環境によっても多少時間の進み具合が違うかもしれません。 |
２台のコンピュータが、通信にランダムな遅延があるなかで、同時にタイマーをスタートさせなければなりません。そこで私はNTPを利用し、２台のコンピュータの時刻を合わせて、お互いがある特定の時間になったときにタイマーをスタートさせようと考えました。２台のコンピュータが、「○○分○○秒になったらタイマーをスタートして。」という約束事を交わすことと同じです。
具体的な動作は、Speedが相手との接続が確立したら、次に相手との最大送信時間を計算します。パケットを10往復させ、その往復の中で、一番時間がかかった時間を２で割った数値が、送信して相手に届くまでの最大時間とします。（これは後に、更新権の移動サイクルとしても使われ、最大送信時間は更新される場合もあります。）ここで、２台のコンピュータの時計が合っていると仮定したときに、現在の時刻＋最大通信時間＋３秒をした時間にタイマーをスタートさせるというメッセージを送り、２台のコンピュータがその時間になるまで待ち、時刻になったと同時にタイマーが開始する仕組みになっています。
それでは時刻を同期させるプロトコル、NTPについて説明をしたいと思います。
NTPはNetwork Time Protocolの略で、インターネットを通じて時刻の同期を計るためのプロトコルです。NTPは様々な能力のクライアントとサーバを、広い範囲の遅延とジッタ特性（通信時に起こるゆらぎ）を持ったネットワーク越しに使うために設計されています。しかしNTPの動作は非常に複雑で、RFCが100ページ以上になってしまう程でした。そこでNTPを簡略化したSNTP(Simple Network Time Protocol)を利用することにしました。SNTPの最新のバージョンはVersion4で、SNTP Version4は、現在定義されているNTP Version3やNTPVersion4に基づいて単純化されていて、NTPとSNTPは共存するように設計されているので、SNTP Version4は既存のプロトコルに影響を与えません。つまり、NTPやSNTPクライアントはNTPサーバにもSNTPサーバにも問題なく要求を出せるということになります。SNTPメッセージはUDPを利用しています。SNTPに割り当てられているポート番号は123で送信元ポートとしても送信先ポートとしても使用されます。SNTPにはヘッダ領域の中に以下の４つのタイムスタンプがあり、それを元に時刻を計算します。
| Reference Timestamp 基準タイムスタンプ |
64ビットタイムスタンプ形式で、ローカル時計がサーバにリクエストを出す以前に最後に設定あるいは修正された時刻が入ります。 |
| Originate Timestamp 基点タイムスタンプ |
64ビットタイムスタンプ形式で、クライアントがサーバに要求を出した時刻が入ります。 |
| Receive Timestamp 受信タイムスタンプ |
64ビットタイムスタンプ形式で、クライアントのリクエストがサーバに届いた時刻が入ります。 |
| Transmit Timestamp 送信タイムスタンプ |
64ビットタイムスタンプ形式で、サーバがクライアントに対し応答データを出した時刻が入ります。 |
〔用語説明〕
ユニキャストモード １対１
マルチキャストモード １対多（クライアント側が多）
エニーキャストモード 多対１（サーバ側が多）
SNTPクライアントはユニキャストモード、マルチキャストモード、エニーキャストモードのいずれかで動作できます。エニーキャストモードはブロードキャストアドレスに要求を出し、最初に返ってきた返答のサーバとユニキャストモードとして通信を行うので、アドレスの選択方法以外はユニキャストとエニーキャストモードの動作は同じです。マルチキャストモードでは、リクエストを送信せずに使用するマルチキャストサーバからのブロードキャストを待ちます。
ユニキャスト又はエニーキャストクライアントはNTPメッセージヘッダを初期化し、サーバへリクエストを送信し、その応答のタイムスタンプフィールドから日時を割り出します。
クライアントは、タイムスタンプを利用してdとtを計算します。そのタイムスタンプと計算方法を記します。
| タイムスタンプ | 記号 | 生成された時刻 |
| Original Timestamp | T1 | クライアントが要求を生成した時刻 |
| Receive Timestamp | T2 | サーバによって要求が受信された時刻 |
| Transmit Timestamp | T3 | サーバによって応答が送信された時刻 |
| Destination Timestamp | T4 | クライアントによって応答が受信された時刻 |
SNTPは送受信の遅延時間が同一であるとして計算されていますが、遅延時間の誤差が小さければ問題ないと考えられます。よって、ネットワーク的に一番近いサーバが選択する事が推奨されます。一方NTPは統計的な揺らぎを考慮することで精度を高めています。
更新権の説明と同時に、Speedが相手との接続を完了してからの詳細な動作を説明したいと思います。Speedは相手との接続に成功すると、次の動作に移ります。（サーバの例を記述しますが、クライアントも動作の内容は同じです）
以上のことを守ると、CT=50[ms]だった場合の更新権の移動は理想的には表は次のようになります。
パケットの送信は更新権が移動する時にしかできないので、お互い同じ条件で更新ができるといえるます。もし、CTの50[ms]を越えてから相手のパケットが到着した場合は、下の図のようにCTの改正を行うことによって、通信の遅れによる不平等さから守ります。下の図は、150[ms]までに到着するはずであったパケットが送れて165[ms]に到着した場合の例です。ですが、この部分のプログラムは完成するに至りませんでした。
基本的には、更新権と共に送られてきたメッセージを了解できれば # OKメッセージを出し、了解できなければ # NG メッセージを出すという単純なものです。要求を出したユーザは、# OK メッセージを受信するまでは、カードと画面の更新は行えません。# OK を出したユーザはCT秒待った後にカードと画面を更新することによって、若干の誤差はありますが、両方のユーザがほぼ同時に更新されます。
CT=50[ms]で1000[ms]の時に更新した例
# UPDATE メッセージの中にはユーザが更新した時間が入っており、950〜999[ms]までの値が入るはずです。実際のメッセージは
# UPDATE 984 5 C5S4H4D8D4SCDA…
であり意味は、ユーザが 984秒に５番目のメッセージとして更新した。その内容はクラブの５、スペードの４…
といったメッセージになります。そして相手はそのメッセージを受け取り、その984秒以前に何も更新作業をしていなければ、そのまま # OK と返答し、カードと画面の更新処理をします。
研究室内はローカルエリアネットワーク内なので、通信を行った場合、遅延がほとんどありません。従ってお互いを同期させるプログラムを作成してもその動作を確認する事が困難になります。そこで通信を任意の時間もしくはランダム時間遅らせることのできる遅延ソフトを作成しました。それがDelay Simulatorであり、UDPで行われる通信を任意に遅らせる事ができます。
Delay Simulator（以後DSと記述）の基本的な動作を説明します。DSは２台のコンピュータのIPアドレスを所持していて、常に２台からの接続を待機します。タイムアウトは無いので、DSを終了しない間はずっと待ち続けます。そして両方の接続が成功すると同時に、両方のコンピュータからのメッセージの転送処理を開始します。２台のコンピュータをＡ、Ｂとおくと、ＡのメッセージはＢへ、ＢのメッセージはＡへ転送されます。なお、Speedは切断するときに、SHUTDOWNという命令文を出します。DSがそのメッセージを受信したとき、２台のコンピュータとの通信が終了し、再び接続待ち状態になります。
DSの遅延時間はランダム値にすることもできるので、どちらが早いのかを的確に判断できているかの実験ができるようになります。
従来の通信は、２台のコンピュータで以下のように通信されていました。
Delay Simulatorを使用すると以下のような通信になります。
 |
起動するとタスクバー上に現れます。この時点ではメッセージの転送はされませんので、Speed側ではまだ待っていて下さい。アイコンをクリックするとメニューが出て遅延設定で、設定画面に入ります。設定が終わり次第、転送開始を押してからSpeedをスタートしてください。 |
 |
通信を行う２台のコンピュータのIPアドレスかドメイン名を入力してください。不親切ですが、左のエディットボックスに入力したコンピュータが50001番ポートを使用し、右側が50002番を使用する事になりますので、Speed側でも設定を確認して下さい。転送にかかる時間は左図の設定だと、300[ms]は必ずかかり、プラス0〜700[ms]のランダム時間遅延させます。つまり、300〜1000[ms]です。 |
 |
＜Speed側での設定＞ まず対戦者IPをDelay Simulatorが動いているPCにします。対戦者を待つ時間は同じで構いません。使用ポートは通常は50001で構いませんが、Delay Simulatorで右側のエディットボックスに書かれていた場合は必ず50002にして下さい。50001でも通信をしようとはしますが、誤動作になります。 |
公平性を保っているかを確認するために、以下の実験項目を立ててみました。なお、Speedのバージョンは0.4と0.5の２通りを使用します。バージョン0.4と0.5で出来ることは次のようになっています。
| Version4 | Version5 | |
| タイマーを同時にスタートする処理 | × | ○ |
| 更新権を利用してメッセージを出す | × | ○ |
| メッセージが了承されたかの返答を出している | × | ○ |
Speedが送信するメッセージの平均バイト数である128[Byte]を付加させたパケットを数回送信し、その時間を計測する。
次に、高画質のストリーミング映像を再生してネットワークに負荷をかけながら、同じように128[Byte]のメッセージを送信し、その影響をみる。
次に、Speedが送信するメッセージのバイト数を、1, 2, 4, 8, 16, 32, …, 16384[Byte]と変化させながら送信し、パケットの往復時間に変化があるかを見る。
Delayサーバを経由しない場合と、経由した場合を比較し、Delayサーバが正常に動いているかを見る。
Delayサーバを経由した場合、タイマーの開始にどれだけ影響が出るかをSpeed Ver0.4で確認する。 と同時に、 Ver0.5ではタイマーの開始に影響が出ないことを調べる。
Speed Ver0.4とVer0.5でDelayサーバを経由した場合に、自分と対戦相手が同時にカードを出したときに正しい判断ができているのかを調べる。
128[Byte]のメッセージを送信したときに往復にかかる時間は、約7[ms]でした。同じメッセージをネットワークに負荷をかけた状態で送信したときは、約9[ms]となり、約2[ms]の違いが生じました。このことにより、その他のソフトウェアによる通信が、通信に影響を与える可能性があることが分かりました。
メッセージのバイト数を1〜16384[Byte]に変化させて送信したときの往復時間の結果はグラフにしてみました。
2048[Byte]あたりからが、比較的往復に時間がかかりだすという結果になりました。
Delayサーバを経由した場合は、理想どおりの500〜1000[ms]遅れた時間となり、Delayサーバが正常に動作していることが分かりました。
左のウィンドウが、WindowsXPで動いている画面で、右のウィンドウが遠隔操作をすることができるソフトウェアVNC Serverを使用してWindows2000上で動いている画面です。誤差は18766-18737 = 29[ms]程と出ました。これはSNTPの誤差と、VNCServerが情報を送信する時間の誤差も含まれるので、正確なものではありませんが、Delay Simulatorの遅延時間である１秒の誤差が出ていないことから、プログラムが正常に機能していると見てよいといえます。
Delay Simulatorの遅延時間を１秒に設定し、ゲームをスタートさせ、次のような状況になりました。場にスペードの５が置いてあり、自分の手元にはダイアの６があり、場に出せます。また相手もクラブの４があり場に出せます。遅延時間を１秒に設定しているので、通常だとお互いが同時に出そうとしたときに衝突が起こるはずです。ここで、自分にも分からないくらいに同時出しをしては結果が合っているのか分からないので、上のカードを操作しているＰＣの方を、若干早く操作してみました。
下側のカードを操作しているＰＣの要求はどうなったのかを、デバック画面を見てチェックしてみました。
結果は図にある通り、上のカードを操作しているＰＣの要求がのまれました。更新権と遅延時間の関係で、処理が非常に遅くなってはいますが、遅延が生じていても早いほうを判定できることができました。以上で実験を終えます。一見成功しているかのように見えますが、実際には様々なバグがありますので、その詳細を４−２の今後の改善点で記します。
まず実験１では通信を行う際に、他のソフトウェアでも通信をしている場合、影響が出るのかを調査しました。結果は、何も負荷がかかっていない状態よりも、負荷がかかっている方が1〜2［ms］程度遅いという結果になり、微かながら影響を与えることが分かりました。このことで、２台のコンピュータが通信をしている最中に、他の処理により通信の揺らぎが発生する可能性が十分にあることがいえます。揺らぎが起こる原因の一つに、多数のプログラム上でソケットを作成していることがあたります。ソケットはいくつも作成でき、各プログラムで同時に送受信を行えますが、TCPやUDPの一つ下の層のネットワーク層層は、一本の管のようになっていて、一つづつパケットを送信しています。よって他のプログラムで大量のデータを送受信している場合は、遅延が生じるということです。
次に、送信するメッセージのサイズを1,2,4,8,・・・,16384［Byte］と変化していった場合に、それぞれの通信時間にどれだけ差が出るのかを調べた結果、2048［Byte］以降に若干の遅れを確認することができました。これは、TCPとUDPの最大セグメントサイズが関係していると思われます。TCPとUDPには、MSS（Maximum Segment Size）というものが存在し、イーサネットを使用するとき、通常1500オクテット（１オクテット＝８ビット）という数値が使用されます。これにはIPのヘッダと、TCP・UDPのヘッダも含まれるので、実際のデータ長は1460オクテットとなります。つまり、トランスポート層で送信しようとするメッセージのサイズ1460バイトを超えてしまった場合は、複数に分けて送信されることになります。よって、大量のメッセージのやり取りを行う際には、一つのメッセージサイズを1460以下にすることで、効率よく送受信ができるといえます。実験の結果ではグラフで見ても分かる通り、1460［Byte］の以前と以降では差が確認できます。ですが、16384［Byte］のメッセージを往復させたときの時間がそれほど大きくないことが疑問点として残りました。
実験３では、1秒の遅延が生じている環境で同時出しをしました。要求を出してから相手に届くまでが少なくとも１秒はかかるので、確実に衝突が起こります。このときどちらが早いかの判断処理を施していない場合は、送信したデータがそのまま反映するので、２台のコンピュータがそれぞれ、自分が先に置いたものとして考えてしまいます。衝突を考慮してあるVer0.5で試した結果、早くマウスの左ボタンを離した方の結果が反映していたので、正常に処理が行われたといえます。ここまではよかったのですが、次にカードの更新を行うときにカード情報が、同時出しを行う以前の状態に戻ってしまうというバグが発生していました。カードを更新するときには必ず、szStackMsg［RECV_UDP］という変数にカード状態を保持しておくのですが、この情報がどこかで復活している可能性が高いです。残念ながらこのバグは直すには至りませんでした。
