Monthly Archives: 11月 2008

MMO RPGとTCPのnagleアルゴリズム

昨今、Massively Multiplayer Online Role-Playing Game(MMO PRG)が好評を得ている。本屋でMMOの作り方の本(韓国語からの翻訳版?)が置いてあったのでチラ見したら、はじめの方にTCPとUDPに関する説明とnagleアルゴリズムについての解説があった。

ネットワークの実用的なプロトコルの中で最も制御の難しいものの1つにMMOのネットワークプログラミングがあると日ごろから考えている。その理由は以下の通りだ。

  • MMOは時間課金する場合があるため品質にシビア
  • アイテム課金する場合には、落ちているアイテムを誰が取得したのか等々
  • 格闘系やアクション、リアルタイムRPGならいかにラグを小さくするのか
  • UDPは使えない場合が多いのでTCPのみ?
  • 瞬断、パケットロス、無線などにどのように対応するか

これらの問題のうち、TCPに着目した場合、パケットロス、nagleアルゴリズムの問題は顕著だ。

課金やアイテム取得ではない、パケットロスしても良い素材情報の配信であればTCPよりもUDPの方が良い。しかしながらNATの関係上TCPにせざる得ない。TCPの場合、パケットロスした箇所が到着するまで、その先を送ることができない。

どうするべきか…と考えると、1つアイディアが浮かんだ。複数コネクション張れば片方でパケットロスが発生しても、片方で情報を伝えることは出来そうだ。しかし、これが有効かどうかは実験してみなければ分からない。

nagleアルゴリズムについては、MSSに満たないセグメントを生成するようなプログラムを書くと影響する。MMOのパケットをキャプチャしたことはないので分からないが、ほとんどがMMS以下のセグメントを生成しているのではなかろうか。その場合、nagleアルゴリズムによってACKが到着するまでは送信できなくなる。

MMOゲーマーのTIPSにはnagleアルゴリズムを無効化することでRTTが50ms〜100ms早くなったとする結果もあるようだ。

これらのMMOネットワークプログラムに対するTCPやUDPの振る舞いはMMOに限らずリアルタイム性を要求するアプリケーションに対して意味あるものだと考えられる。学術的にも、MMOが要求する品質とそれを満たすプロトコルの工夫についてより議論されていくべきではなかろうか。

# NGNの品質管理によるネットワークゲーム応用には期待していたりする。

モバイルもクラウド時代に、LTEとPHSとWiMAXとクラウドと

月刊テレコミュニケーションにてモバイルもクラウド時代にという記事のPDFがUPされている。

モバイルWiMAX、次世代PHS、LTEの比較が行われている。条件を同じにすると最大通信速度は、ほぼ同じとのこと。それぞれの特徴はLTEは音声重視、WiMAXはデータ重視、PHSは既存PHSとの親和性重視。

その他のキーワードは、マイクロセル、フェムトセル、UMPC、SaaS、リアルタイム対戦ゲーム、クラウド、周波数利用効率、ホワイトスペース、コグニティブ無線。

千葉大とNEC、無線LANを用いて映像など品質を向上

学術的に面白い記事があったので紹介する。

千葉大とNEC、無線LANを用いて通信される映像や音声の品質を向上させるダイナミック・パケット通信制御方式を開発

この方式はQoSを実現するにあたって802.11eに対応していない製品でも、QoSを実現しようという考えのもの。

通常802.11eは通常のデータトラフィックよりVoIPや映像のIFS(待ち時間)を短くすることによって優先度を与える。これにより、CSMA/CAを行った場合にVoIPのトラフィックが勝つ確率が大きくなるためにQoSが実現される。

今回の千葉大とNECの手法では、ブラウザなどのバックグラウンドデータのトラフィックのMACフレームをわざとAP側で損失したように見せかけ、ACKを返さないことで、送信端末側に指数バックオフを実行させ、バックグラウンドトラフィック側の優先度を下げようとするもの。これによってSTA側が11eに対応していなくてもAPのみの変更でQoSを実現することが可能だ。

問題は11eに比べてIFSの値がDIFSのため長くなってしまうため、わざとAP側でMACフレームを落としてしまうためにスループットが11eに比べて少しだけ落ちそうな点だが、QoSの優位性をつけたいだけであれば、まったく問題がない。

WRED(Weighted Random Early Detection)を連想させるような、この優先度のつけ方は思いつかなかった。非常に面白いし、既存の実装に影響を与えずにできる点が良い。アドホック系QoSでも絶賛検討すべき技術である。

「WPA」突破はTKIPのみ

無線LANセキュリティ規格「WPA」突破――その対策は? (1/2) – ITmedia News

RC4全般が全滅した模様。RC4チップのみしか搭載していない11b級の製品でかつ、AESのソフトウェア暗号を行おうとしないないベンダーの製品は危ないということになる。

AES-CCMPは大丈夫とのこと。AESを使っていないAP(心当たりあるな…)があったらAESに変更しておこう。

書き込みテスト

引越しした。

半月を移行期間として確保し、以前のドメインからリダイレクトを行う。

WPA1-TKIP終了のお知らせ

無線LANのセキュリティに危機?「WEP」に続いて「WPA」までも一部解読

ちなみに上記の記事におけるTKIP=WPA1の終了が正しいかどうかについてはどうですかね。WPA-AESがまだあるので。WPA対応ということはAESチップを持っているし。

RC4使う系が軒並みダメということ?

これホントの話なのかなぁ。

MPEG-2などの動きベクトル算出方法について

まるもさんの日記の動きベクトルについてが非常に分かりやすい。

ffmpegとx264を調べたところ以下の動きベクトル算出法が見つかった。

  • full motion estimation – full search(alias ‘esa’ – exhaustive search algorithm)
  • EPZS motion estimation (alias ‘dia’ – diamond search)
  • tesa motion estimation – transformed exhaustive search algorithm
  • log motion estimation
  • phods motion estimation – parallel hierarchical one-dimensional search algorithm
  • hex motion estimation – hexagonal search
  • umh motion estimation – uneven multi-hexagon search
  • iter motion estimaion – iterative search

ffmpegで通常使われるのはEPZSというアルゴリズムだが、このアルゴリズムはdiamond search→MVFAST→PMVFAST→EPZSと改善に改善の論文を重ねて作られている。ffmpegではdiamond searchのエイリアスでEPZSが選択される。

full searchやumhについてはffmpegの中には入っておらず、x264のソースコード内にて発見した。

SIMD化されたCPUで上手く動作するのだろうか、気になった。アセンブリで書かれているのはiDCTとDSPの部分をMMX, SSE化しているものが多かった。ffmpeg、x264ともにマルチスレッドや64ビット化には対応しており、ベンチマークしている方々がいらっしゃる。x264のcell化は無理だったのか、と、ふと思う。

このコード群をJAVAやRubyにしたら面白いかなーと思いつつ、別に面白くないやと思う今日の午後。

今月限りで11n.jp, 11s.jpを廃止する予定

ネタで取得した11n.jpおよび11s.jpの来期の契約が今月に迫っております。

不況のあおりを受け、経費削減が重要課題になりつつあります。

2008/11/31が期限ですが更新しない予定で検討してます(臨時収入がない限り)。

サーバも、これを期に一旦解約(〜2009/02/27)する方向で検討しています。

もし802.11n.jpや802.11s.jpなドメインでハァハァしたい無線LANな方がいらっしゃれば、お譲りできます。