C++：私はインタビューで頼まれたストリーミングや料金規制

Question

興味深い質問：

あなたは常に可変レートで（のは、クライアントサーバーモデルを想定してみましょう）ソースからいくつかのバイトストリームを受信して​​いると仮定します。あなたは、あなたの終わりにオンザフライでパケットをソートし、それらを一定のレートで他の場所に再送したいと思っています。どのようにC++でそのようなシステムを実装しますか？

私はインタビュアーが合理的だと主張ワーカースレッドヒープとソートされたパケットをポップディスパッチャスレッドにパケットを押してXの一定の間隔でいくつかの内部クロックに同期して、それらを離れて送信

と基本的なシステムを提供このようなシステムでは、スレッド間のコンテキスト切り替えによる再送信の期限が間に合わなくなりがちです。私は、特定のマシンのスレッドスケジューリングアルゴリズムを制御することなく、一定の再送速度を保証できないと答えました。彼は私が間違っているかもしれないと思うように主張し続け、これは実際に達成可能です。私もです？

Answer 1

この問題の説明はあまりにも曖昧です。 「並べ替え」は何を意味していますか？パケットには何らかの種類のシーケンス番号がありますか？何らかのシーケンス番号のパケットを受け取らない場合はどうなりますか？ここでは、異なる特定の状況に適応できるいくつかの一般的なアルゴリズムに関する私の考えです。

パラメータ

アルゴリズムは、次のパラメータに依存する：

1. 最大我々はバッファを許可されたパケットの数（例えば4096）。
2. 高い透かし値。これは、（1）に対するパーセントです。現在、HWVよりも多くのパケットをバッファに格納している場合は、ソートされていない順序であってもパケットを送信します。 （50％、または2048）。
3. TTL - パケットをバッファできる最大時間。

変数

まず第一に、我々は、固定長のリングバッファを必要としています。 リングバッファで構成さ：メタの緩衝パケット上記アレイへのポインタの

配列[4096]（並べ替え操作中に自身のコピーパケットを避けるために）

配列[4096]の

1. 配列[4096]各パケットの情報：パケットのシーケンス番号（パケットから解析された）とパケットが受信されたときのタイムスタンプ
2. ヘッドとテールへのポインタ。

送信するグローバル変数 - 次のシーケンス番号も保存する必要があります。

アルゴリズム

パケットが到着すると、私たちは私たちのバッファは常にシーケンス番号でソートされ、適切な位置（挿入ソートの1つのステップ）にバッファに私達のパケットを追加します。その後、次のうち少なくとも1つが当てはまる場合、バッファの先頭からパケットを送信することができます。

1. ヘッドパケットのSeq番号が予想されるseq番号より小さいか等しい。これは、先頭のパケットがソートされた順序で次にあることを意味します。典型的な状況。
2. バッファ内のパケット数が最高透かし値（2048）を超えています。着信アクティビティのバーストがバッファの残りを埋める恐れがあるので、私たちは（それがソートされた順序ではないにもかかわらず）ヘッドパケットを送信し、さらに着信パケットを捨てなければなりません。
3. ヘッドパケットの現在時刻からTTLを差し引いた時間。

上記のうち少なくとも1つが当てはまる場合は、ヘッドパケットを送信してバッファから削除します。また、期待されるシーケンス番号を、送信されたパケットのseq番号+ 1に割り当てる。ヘッドパケットを送信した後、バッファが空でない場合は、TTL値でタイマーを開始します。タイマーが起動すると、上記と同じチェックが実行されます。これは、バッファにパケットを無期限に保存しないようにするためです（受信パケットがない場合）。