udpセッションを再構築するためにはどのような構造が必要ですか？

Question

私は実装在庫exachangeエンジンです。 私はUDPを介してティッカーデータを受信し、各UDPパケットはシーケンス番号を持っています。 取引所は、パケットを一つずつ送信しますが、UDPは、彼らが一例として、slighty「混合」の順序で受信することができる（となります）ためgaranteeていないので、私は正しい順序でパケットを受信すると仮定すると

1 2 3 5 4 6 7 10 9 8 11 12 13 14 15 

をすべてが簡単になります。パケットを追加して後でデキューするには、Queueを使用します。しかし、パケットが完全に注文されていないので、私はいくつかの問題があります：

• パケットの格納にはどのような構造が必要ですか？私はパケットを待ち行列とデキューする能力が必要であり、配列内の任意の位置にパケットを追加する能力も必要です。

• パケットが失われた場合は、「回復」手順を立ち上げる必要があります。ですから、 "nextPacketSequenceNumber！= currentPacketSequenceNumber + 1"と言うときはいつも、5msとおそらくパケットが到着するのを待たなければなりません。例

  1 2 3 5 ... after 5 ms .... 4 - OK 
  1 2 3 5 ... after 10 ms .... 4 - recover 
  1 2 3 5 6 7 - recover 
  

Answer 1

のためにあなたは、キー（優先順位）としてシーケンス番号と、並べ替え問題を解決するためにpriority queueを使用することができます。最も単純な優先度キューは、順序付けられた辞書です。回復する問題は、優先キューとアラームクロックの組み合わせを使用して解決できます。

Answer 2

これは最も効率的な方法ではないかもしれませんが、私はこれまで、不適切な問題を処理するためにOrderedDictionary（おそらくSortedDictionaryですが）を使用しました。シーケンス番号をキーとして使用し、パケットデータを値として使用します。

残念ながら、私はあなたの第2の質問に（多くの努力なしで）話すことができません。私が提案する唯一のことは、リコール受信者が発信者に送信して、元のメッセージが破棄されたためにパケットを再送信するように指示できるように、プロトコルを拡張することです。私はこのような論理を持っています（もっと洗練されています）。それは会社の財産ですが、私はそれを共有することはできません。うまくいけば、これであなたを得るのに十分です。

Answer 3

順序が重要である場合、問題はより複雑になります。たとえば、優先順位キューを使用できますが、シーケンス内の次のキューがない限り、キューから何も処理したくないなどです。したがって、シーケンスに基づいてブロックする優先度キューを実装することもできます。

この場合、欠落しているパケットが見つかるとすぐに別のスレッドで回復プロセスを開始する必要があります。待機しているポイントはありません。パケットが正常に到着した場合は、回復結果を無視できます。

これは、UDPパケットを並べ替えるためのオーディオストリームでのジッタバッファリングに似ています。 http://en.wikipedia.org/wiki/Jitter#Jitter_buffers

Answer 4

シーケンス番号はシーケンシャルな整数なので、配列は非常によく保存されます。しかし、それらも無限に進むので、リングバッファのような循環的な方法でインデックスの再利用が必要です。

これを見るもう1つの方法は、ランダムアクセス（FIFOだけでなく）のリングバッファです。