8

送信でパケットを並べ替えるアルゴリズムを開発しています。各パケットには、[0, 256) のシーケンス番号が関連付けられています。最初のパケットのシーケンス番号はこれらの値のいずれかを取ることができ、その後、次のパケットは次の値を取り、次のパケットはその後の値を取ります (255 の後にロールオーバーします)。

正しい順序でのパケットのシーケンス番号は次のようになります。ここで、「n」は最初のパケットのシーケンス番号です。

n, n+1, n+2, ..., 254, 255, 0, 1, 2, ..., 254, 255, 0, 1, 2, ..., 254, 255, 0, 1, ...

各パケットには、宛先に到着した時点でタイムスタンプが付けられ、すべてほぼ順番に到着します。(正確な数値はわかりませんが、到着タイムスタンプでソートされたパケットのリストを考えると、シーケンス番号で示されるリスト内の位置からパケットが 5 スポット以上離れることはないと言って間違いありません。)

電気通信の普及とコンピュータ サイエンスの発展にとっての歴史的重要性を考えると、私がこのような問題に対処した最初の人物ではなかったと思います。私の質問、それから：

  1. 周期的に変化するキーが与えられた場合、上記のようなほぼ順序付けられたシーケンスを並べ替えるよく知られたアルゴリズムはありますか?

  2. 欠けているアイテムの大きなチャンクを許容するこのアルゴリズムのバリエーションはありますか? これらのチャンクは任意の長さにできると仮定しましょう。256 個以上の不足アイテムのチャンクが特に心配です。

最初のアルゴリズムのアイデアはいくつかありますが、2 番目のアルゴリズムにはありません。しかし、自分のアルゴリズムが正しいことを検証するために工数を費やす前に、ベル研究所 (または他の場所) の誰かが 30 年前にこれを改善していないことを確認したかったのです。

4

3 に答える 3

1

このソリューションが実際にどこでも使用されているかどうかはわかりませんが、ここで試してみます (パケットの欠落がなく、最大「シャッフル」が 5 つの位置で、最大シーケンス番号が 255 であると仮定します)。

n = 0;
max_heap h = empty;
while( true ) do
  while( h.top().index != 0 ) do
    p = next_packet;
    i = n - p.seq;
    if( i > 0 ) i = i - 255;
    h.add( i, p );
  done

  p = h.pop();
  n = n + 1;
  p.increase_indexes( 1 );
  // Do something with it
done

基本的に、プライオリティ キューには、最後に処理されたパケットと処理待ちのパケットの間にあるパケットの数が格納されます。パケットは入ってくるとすぐに処理されるため、キューは非常に小さいままです。ヒープの並べ替えが必要ないため、キーの増加も非常に簡単です。

これを欠落したパケットにどのように適応させることができるかわかりません。ほとんどの場合、タイムアウトまたは最大オフセットを使用してから、パケットが「次の」と宣言され、それに応じてヒープが更新されます。

ただし、256 を超えるパケットが欠落している場合、この問題が発生する可能性はまったくないと思います。サブシーケンスを取る

127,130,128,129

これにはいくつかの原因が考えられます

1) パケット 128 と 129 が故障しており、再注文する必要があります

2) パケット 128 と 129 が失われ、次に 253 パケットが失われたため、順序は正しい

3) 1と2の混合物

于 2012-02-01T19:03:50.723 に答える
1

面白い問題！

私の解決策は、到着時間に従ってパケットをソートし、要素のウィンドウ (たとえば 10) をパケット番号に従って循環的にソートすることです。これはさまざまな方法で改良できます。2 つの連続するパケット番号 (到着時間に従って配置) の差が特定のしきい値よりも大きい場合、それらの間にバリアを配置できます (つまり、バリアを越えてソートすることはできません)。また、パケット間の時間差 (到着時間に従って配置) があるしきい値よりも大きい場合は、バリアを配置することをお勧めします (これでおそらく問題 2 が処理されるはずです)。

于 2012-02-01T18:48:57.720 に答える
0

プライオリティ キューを使用します。

各パケットを受信するたびに:

  • キューに入れます。
  • それがあなたが待っているものである限り、キューの一番上の要素を繰り返し削除します。

2 番目の質問:

  • 一般的に、いいえ、それを解決する方法はありません。
  • パケットの到着にある程度の周期性がある場合 (例: 20 ミリ秒ごとにパケットが予想される場合)、これを簡単に検出してキューをクリーンアップし、5 つのパケットを受信した後、再度処理する方法を知ることができます...
于 2012-02-01T18:08:49.737 に答える