ゲーム開発者向けのネットワークプログラミング。 パート4：UDPでの信頼性、順序付け、および過負荷の回避

翻訳者から：Javaの非ブロックモードでのUDPソケットの動作を理解し、それに基づいてネットワーク接続を操作するための独自のクラスを作成する必要がありました。 残念ながら、私はこのテーマに関する理にかなったロシア語のドキュメントを見つけませんでした。 しかし、UDPを介した信頼性の高い接続の作成というテーマを明らかにしようとするhabrのいくつかの試みにつまずきました。 ユーザー bvasilyevが 作成したGlenn Fiedlerによるいくつかの記事の翻訳を含む 。 そして、記事ではゲームで使用するためのそのような接続の作成について説明します（私が必要とするものではありません）。 残念ながら、 bvasilyev は約1年前にこのサイクルの翻訳を中断し、最も興味深いものは元の言語に残っていました。 したがって、サイクルの4番目の記事を翻訳し 、仮想接続の実装を サイクルの3番目の記事からjavaに 書き換える ことにしました（少し後で説明します）。 私以外の誰かがこの記事を使用できるように、ここに投稿します。 残念ながら、私はプロの翻訳に従事したことはありませんでした。私は常に英語のドキュメントを勉強しました。 しかし、この場合、完全に異なる意味で特定の単語が何度も使用されているため、あらゆる種類の定義の名前で、繰り返し-同じ文内で、翻訳し、その後私に馴染みのある言語でテキストを操作する方が便利であることがわかりました 修正および合理的な提案を歓迎します。



最初の記事

第二の記事

第三の記事



（リコール： bvasilyev翻訳済み）

---

信頼性、順序付け、UDPを介した過負荷の回避

エントリー

こんにちは、私の名前はグレンフィードラーです。シリーズ「ゲーム開発者向けネットワークプログラミング」の第4回の記事でお迎えします。



前の記事では、UDPに基づいた仮想接続の独自の概念を作成しました。



ここで、仮想UDP接続に信頼性、秩序、および輻輳回避を追加します。



これは、ゲームにおける低レベルのネットワーク作業の中で最も難しい部分であるため、この記事は非常に波乱に富むので、我慢して行きました！

TCPの問題

TCPに精通している人は、信頼性の高い合理化されたパケット転送システムと輻輳回避を備えた独自の内部接続コンセプトを既に持っていることを知っています。



問題は、「アクション」ジャンルのマルチプレイヤーゲームは、1秒あたり10〜30パケットの頻度で送信されるパケットの一定のストリームに依存していることです。 。 これには、プレイヤーの入力デバイスからのデータ、各キャラクターの位置と速度の方向、ゲーム世界のオブジェクトの物理状態が含まれます。



TCPの問題は、信頼性の高い合理化されたフローのための抽象データ配信です。 このため、パケットが失われた場合、TCPは停止し、パケットが再送信されるのを待つ必要があります。 これにより、パケットの一定のフローが中断されるため、再送信パケットを受信するまで後のパケットが順番に待機する必要があり、パケットを正しい順序に並べることができます。



必要なのは、異なるタイプの信頼性です。 すべてのデータを適切に順序付けられたストリームとして扱うのではなく、一定の速度でパケットを送信し、別のコンピューターによる受信についての通知を受け取ります。 これにより、再送信されたパケットを待たずに時間依存のデータを配信できると同時に、アプリケーションレベルでのパケット損失の処理方法を決定することができます。

TCPを使用して指定されたプロパティで信頼性の高いシステムを作成することはできないため、UDPの上に独自のシステムを作成する以外に選択肢はありません。



残念ながら、書き換える必要があるのは信頼性だけではありません。 これは、TCPが輻輳回避も提供するため、接続のプロパティに応じて、送信データの速度を動的に変更できるためです。 たとえば、TCPは28.8kモデムを使用した場合、T1回線よりも少ないデータを送信し、接続のタイプを事前に知らなくてもこれを行うことができます。

シーケンス番号

信頼性に戻りましょう！



信頼性システムの目標は単純です：接続の反対側に到達するパケットを知りたい。



まず、パッケージを識別する方法が必要です。



「パッケージ識別子」の概念を追加するとどうなりますか？ 整数にします。 これをゼロから開始し、送信するすべてのパケットでこの数を1つ増やすことができます。 送信する最初のパケットは「パケット0」で、送信される100番目のパケットは「パケット99」です。



これは実際にはかなり一般的な方法です。 TCPでも使用されています！ これらのバッチ識別子はシーケンス番号と呼ばれます。 また、TCPとまったく同じように信頼性を実装するわけではありませんが、同じ用語を使用することは理にかなっているため、今後はシリアル番号と呼びます。



UDPはパケットの順序を保証しないため、100個の受信パケットが必ずしも100個のパケットが送信されたことを意味するわけではありません。 その結果、シリアル番号をパケットのどこかに挿入する必要があるため、接続のもう一方の端にあるコンピューターはどの特定のパケットを知ることができます。



前の記事の仮想接続用の単純なパッケージヘッダーが既にあるため、ヘッダーにシーケンス番号を追加するだけです。 次のようになります。

[uint protocol id] [uint sequence] (packet data…)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

接続の反対側にあるコンピューターがパケットを受信したので、送信コンピューターによって割り当てられたシリアル番号がわかります。

アック

シーケンス番号を使用してパケットを識別できるようになったので、次のステップは、受信しているパケットを接続の反対側に知らせることです。



論理的には、これは非常に簡単です。受信した各パケットのシリアル番号をメモし、それらのシリアル番号を送信元のコンピューターに返送するだけです。



2台のマシン間で常にパケットを交換しているため、シリアル番号で行ったように、パケットヘッダーにackを追加するだけです。

 [uint protocol id] [uint sequence] [uint ack] (packet data...)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

一般的なアプローチは次のとおりです。

• パケットを送信するたびに、ローカルシーケンス番号を増やします。
• パケットを受信すると、パケットのシーケンス番号を、リモートシーケンス番号と呼ばれる最近受信したパケットのシーケンス番号と比較します。 受信したパケットの数が多い場合、リモートシリアル番号を更新し、受信したパケットのシリアル番号と同じに設定します。
• パケットヘッダーをコンパイルすると、ローカルシリアル番号がパケットのシリアル番号になり、リモートシリアル番号がackになります。

この単純なackシステムは、到着するすべてのパケットに送信パケットがあるという条件で機能します。



しかし、パッケージを送信する前に2つのパッケージが到着するようにパッケージが移動するとどうなりますか？ パッケージごとに1つのackしかないので、どうしますか？



次に、接続の片側がより速いペースでパケットを送信する場合を考えます。 クライアントが1秒あたり30パケットを送信し、サーバーが1秒あたり10パケットしか送信しない場合、サーバーから送信される各パケットに少なくとも3 ACKを入れる必要があります。



さらに複雑にしましょう！ ackを含むパッケージが失われた場合はどうなりますか？ ソースパケットを送信したコンピューターは、実際には受信されたのに対して、それが失われたと考えます！



信頼性の高いシステムをより信頼性の高いものにする必要があるようです。

信頼されたACK

ここでは、TCPプロトコルから離れます。



TCPは、次のシーケンス番号を持つパケットで送信されたackのスライディングウィンドウを保持している間、何をしますか-指定された順序で受信することを期待しています。 TCPが特定のパケットのACK確認応答を受信しない場合、TCPは停止し、このシーケンス番号を持つパケットを再度送信します。 これはまさに避けたい動作です！



したがって、信頼性の高いシステムでは、特定のシーケンス番号を持つパケットを再送信することはありません。 番号nのパケットを1回だけ送信してから、n + 1、n + 2などを送信します。 パケットnが失われた場合、再送信を停止することはありません。必要に応じて失われたデータを含む新しいパケットを作成するためにこのアプリケーションを終了し、このパケットは新しいシリアル番号で送信されます。



TCPとは異なることを行っているため、ackを送信するパケットのセットをスキップ（ホール）できるようになったため、受信した最後のパケットのシーケンス番号を送信するだけでは不十分です。



1つのパッケージに複数のackを入れる必要があります。



どのくらいのackが必要ですか？



前述のように、接続の一方が他方よりも速くパケットを送信する場合があります。 最悪の場合、一方が少なくとも毎秒10パケットを送信し、他方が30以下を送信すると仮定しましょう。この場合、各パケットに必要なackの平均数は3ですが、パケットが小さなヒープに来る場合、もっと必要かもしれません。 最悪の場合は6〜10としましょう。



それらを含むパッケージが失われたという事実のために受信されなかったそれらのackについてはどうですか？



この問題を解決するために、従来のネットワーク冗長性戦略を使用してパケット損失を無効にします！



各パケットに33個のackが含まれるようにします。最大33個、ただし常に33個まで含めることはできません。したがって、特定のackに対して、ackを持つ1つのパケットが通過できなかった場合、冗長性を加えて最大32回送信します！



しかし、33個の確認をパッケージで送信するにはどうすればよいですか？ 結局、各ackの4バイトは132バイトです！



コツは、ビットフィールドを使用して「ack」になる32個のその他のackを表すことです。

 [uint protocol id] [uint sequence] [uint ack] [uint ack bitfield] (packet data...)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

「ackビットフィールド」を定義して、各ビットが「ack」の前にある32個のシーケンス番号のackに対応するようにします。 「ack」100としましょう。「ack bit field」の最初のビットが設定されている場合、パケットにはパケット99のackも含まれます。2番目のビットが設定されると、パケット98が確認されます。 。



調整されたアルゴリズムは次のようになります。

• パケットを送信するたびに、ローカルシーケンス番号を増やします。
• パケットを受信すると、パケットのシーケンス番号とリモートシーケンス番号を比較します。 受信したパケットの数が多い場合、リモートシリアル番号を更新し、受信したパケットのシリアル番号と同じに設定します。
• パケットヘッダーをコンパイルすると、ローカルシリアル番号がパケットのシリアル番号になり、リモートシリアル番号がackになります。 ackビットフィールドは、[リモートシリアル番号-32、リモートシリアル番号]の範囲のシーケンス番号を含む33パケットのキューを調べることで計算されます。 「リモートシーケンス番号-n」に等しいパケットシーケンス番号が受信キューにある場合、ビットフィールド（[1.32]）のビットnを「1」に設定します。
• さらに、パケットを受信すると、ackビットフィールドがスキャンされ、ビットnが設定されている場合、パケットnのシーケンス番号が確認されます（まだ確認されていない場合）。

アルゴリズムのこの改善されたバージョンを使用すると、ackの損失を開始するために、1秒以上100％のパケットを失う必要があります。

パケット損失検出

接続の反対側でパケットが受信されることがわかったので、パケット損失をどのように検出するのですか？



ここでのコツは、ackが私たちに戻ってくることです。特定の時間内に確認を受け取らなかった場合、パケットは失われたと見なされます。



1秒間に30パケット以下を送信し、1秒間にパケットのackを受信しない場合、パケットが失われた可能性が非常に高いと考えられます。



そのため、ビットを使用したこのようなトリックを使用すると、到着したパケットを100％確信でき、受信されなかったパケットのセットを推測するためのかなりの信頼を得ることができます。



その結果、この信頼性の手法を使用して再送信するすべてのデータには独自のメッセージ識別子が必要になるため、何度も受信した場合は拒否できます。 これは、アプリケーションレベルで実行できます。

シリアル番号リセット処理

シリアル番号と確認の議論は、シリアル番号のリセットの問題を強調せずには完了しません！



シーケンス番号とackは32ビットの符号なし整数なので、範囲は[0.4294967295]です。 これは非常に大きな数です！ 1秒間に30パケットを送信すると、この範囲を使い果たしてシーケンス番号をリセットする必要があるまでに4年半以上かかります。



ただし、帯域幅を節約し、シーケンス番号とackを16ビット整数に減らしたい場合があります。 各パケットで4バイト節約できますが、範囲は30分で使い果たされます！



では、これをどのように処理しますか？



秘Theは、現在のシリアル番号が既に非常に大きく、到着した次のシリアル番号が非常に小さい場合、シリアル番号のカウントダウンを開始する必要があることを理解することです。 したがって、新しいシーケンス番号は、シーケンス番号の現在の値よりも数値的には小さいですが、実際にはそれ以降のパッケージです。



たとえば、シーケンス番号を1バイトでエンコードするとします（方法で推奨されません:)）、255の後にゼロ化が発生します。

 ... 252, 253, 254, 255, 0, 1, 2, 3, ...
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この場合に対処するには、255の後にシリアル番号がゼロにリセットされることを知っている新しい関数が必要です。したがって、0、1、2、3は255より遅いと見なされます。パッケージ255。



関数は次のとおりです。

 bool sequence_more_recent( unsigned int s1, unsigned int s2, unsigned int max) { return ( s1 > s2 ) && ( s1 - s2 <= max/2 ) || ( s2 > s1 ) && ( s2 - s1 > max/2 ); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この関数は、2つの数値とそれらの差を比較することにより機能します。 それらの差がシリアル番号の最大値の半分よりも小さい場合、それらは互いに近いはずです。そのため、通常、一方の番号が他方の番号よりも大きいかどうかを確認します。 ただし、それらが離れている場合、それらの差はシリアル番号の最大値の半分以上になり、逆説的に、現在のシリアル番号よりも小さいシリアル番号を後で検討します。



これにより、透過的にシーケンス番号のゼロ化が可能になるため、0,1,2は255より後と見なされます。



とてもシンプルでエレガント！



シーケンス番号の処理には必ずこれを含めてください。

過負荷防止

信頼性に関する問題を解決しましたが、依然として輻輳を防ぐという問題があります。 TCPはTCP信頼性パケットの一部として輻輳回避を提供しますが、UDPには輻輳回避の手段がありません！



フロー制御なしで単純にパケットを送信すると、接続がフラッディングし、強い遅延（2秒以上！）が発生します。これは、当社と他のコンピューター間のルーターバッファーが過負荷になるためです。 これは、ルーターが送信したすべてのパケットを配信しようと非常に一生懸命試みるために発生します。したがって、パケットをドロップする時間であると判断するまで、それらをバッファーキューに入れます。



パケットが時間遅延に非常に敏感であり、ルーターが過負荷になった場合にバッファリングする代わりに破棄する必要があることをルーターに伝えることができればいいのですが、世界中のすべてのルーターのソフトウェアを書き換えずにこれを行うことはできません！



そのため、そもそも通信チャネルがオーバーフローしないようにするためにできることだけに焦点を当てる必要があります。



これを行う方法は、独自のコア輻輳回避アルゴリズムを実装することです。 そして、私は強調します-主なもの！ 信頼性と同様に、TCPよりも適切なものを思い付く最初の試みには望みがありません。可能な限りシンプルにしましょう。

旅行トリップ測定（往復時間-RTT）

すべての輻輳防止は、接続の輻輳を回避し、通過時間（RTT）を増やすことで軽減されるため、チャネルを過負荷にするかどうかの最も重要な指標はRTT自体であることがわかります。



接続のRTTを測定する方法が必要です。



基本的なテクニックは次のとおりです。

• 送信されたパケットごとに、パケットのシリアル番号に加えて、送信時刻を含むエントリを追加します。
• ackを取得するたびに、このレコードを見て、ackが受信された時刻とパケットが送信された時刻との現地時間の差を見つけます。 これは、このパッケージのRTT時間です。
• なぜなら パケットの到着はネットワークのジッター（ジッター-デジタルデータ信号の位相ジッター-送信信号の不要な位相および/または周波数のランダム偏差）によって変化するため、新しい値を取得するたびにこの値を平滑化して実用的な値の指標を提供する必要がありますRTT現在のRTTパッケージとRTTパッケージの差をパーセンテージで計算します。 私の意見では、10％は実際には良いようです。 これは指数的に平滑化された移動平均と呼ばれ、RTTの偏差を平滑化する効果があります。
• 送信されたパケットのキューが常に大きくならないようにするため、予想される最大RTTを超えたパケットの送信をキャンセルします。 信頼性に関する前のセクションで述べたように、ackが1秒以内に受信しなかったパケットは失われる可能性が非常に高いため、最大RTTには1秒が適切な値です。

これでRTTが得られ、輻輳回避をガイドするメトリックとして使用できます。 RTTが大きくなりすぎると、データの送信頻度が低くなり、許容範囲内であれば、データの送信頻度を増やすことができます。

単純なバイナリ過負荷防止

前に述べたように、飽くことのないように、非常に単純な過負荷防止を実装します。 この過負荷防止には2つのモードがあります。 良い面と悪い面。 この単純なバイナリ過負荷防止と呼びます。



あるサイズ、たとえば256バイトのパケットを送信していると仮定しましょう。 これらのパケットを1秒間に30回送信したいが、状況が悪い場合は、送信速度を1秒間に10回に減らすことができます。



したがって、256バイトのパケットは1秒間に30回、約64 kbit / sの速度を提供し、1秒間に10回は約20 kbit / sの速度を提供します。 少なくとも20kbit / sを処理できないブロードバンドネットワーク接続は世界に存在しないため、この仮定を進めます。 一般に送信/受信帯域幅を持つデバイスに適しているTCPとは異なり、接続に参加しているデバイスの最小帯域幅を想定します。



したがって、主なアイデアは次のとおりです。 ネットワーク状態が「良い」場合、1秒あたり30パケットを送信し、ネットワーク状態が「悪い」場合、1秒あたり10パケットにドロップします。



もちろん、「良い」と「悪い」を好きなように定義できますが、RTTのみを考慮すると、良い結果が得られました。 たとえば、RTTが特定のしきい値（250ミリ秒など）を超えた場合、接続が過負荷になる可能性があることがわかります。 もちろん、これは、輻輳のない通常の条件下では、誰も250ミリ秒を超えないことを前提としています。これは、ブロードバンド要件を考慮すると妥当です。



善と悪を切り替える方法は？ 使用したいアルゴリズムは次のように機能します。

• 現在良好なモードであり、状態が悪化している場合は、すぐに不良なモードに切り替えてください。
• 低品質モードで、特定の期間「t」の間条件が良好だった場合は、高品質モードに戻ります。
• 良いモードと悪いモードをすばやく切り替えるのを避けるために、10秒で良いモードから悪いモードに切り替えた場合は、時間 't'を2倍にしてから、悪いモードが良いモードに戻ることができます。 時間「t」の最大値を最大値、たとえば60秒に制限します。
• 接続が短期間しか接続されていない状態で良好な通信モードが切断されないようにするには、接続が良好なモードである10秒ごとに、「t」時間を半分にします。 時間「t」の最小値を何らかの最小値、たとえば1秒に制限します。

このアルゴリズムを使用すると、悪い状態に迅速に対応し、パケットの送信頻度を1秒あたり10に減らして、チャネルの輻輳を回避します。 また、ネットワークの状態が良好な間は、保守モードで良好なモードに切り替えて、毎秒30の高いパケット送信レートを維持しようとします。



もちろん、はるかに複雑なアルゴリズムを実装できます。 そのため、RTTだけでなく、パケット損失の割合をメトリックとして、さらにはネットワークジッタの値（パケット確認応答の分散時間）として考慮することができます。



また、輻輳回避に貪欲になり、はるかに高い帯域幅（LANなど）でデータを送信できる場合を見つけようとしますが、非常に注意する必要があります。 貪欲が増えると、接続が過負荷になるリスクが大きくなります！

おわりに

新しい信頼性システムにより、安定したパケットストリームを送信し、受信したパケットを通知できます。 これから、必要に応じて、失われたパケットに関する結論を導き出し、受信されなかったデータを再送信できます。



さらに、ネットワークの状態に応じて1秒あたり10〜30回パケットを送信する単純な輻輳回避システムがあるため、接続が過負荷になることはありません。



この記事で言及するにはあまりにも具体的な詳細の実装が多数ありますので、サンプルのソースコードを見て、これらの実装方法を確認してください。



信頼性、合理化、および輻輳回避は、おそらく低レベルネットワークの最も複雑な側面です。