按周期序列号对项目进行排序

Question

我正在开发一种算法来重新排序传输中的数据包.每个数据包在[0,256]中都有一个相关的序列号.第一个数据包的序列号可以取这些值中的任何一个,之后下一个数据包采用下一个值,下一个数据包采用该值之后的值,依此类推(在255之后滚动).

数据包的序列号按正确顺序显示如下,其中"n"是第一个数据包的序列号:

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

每个数据包在到达目的地时都会得到一个时间戳,它们都大致按顺序到达.(我没有确切的数字,但是根据到达时间戳排序的数据包列表,可以肯定地说,数据包永远不会超过其序列号所指示的列表中的位置五个点.)

鉴于电信的普及及其对计算机科学发展的历史重要性,我觉得我不可能成为第一个处理这类问题的人.那么我的问题是:

1. 在给定循环变化的密钥的情况下,是否存在一种众所周知的算法来重新排序近似有序的序列,例如上述序列？

2. 这个算法的变体是否能够容忍大块缺失的物品？让我们假设这些块可以是任何长度.我特别担心256个或更多遗失物品的大块.

我对第一个算法有一些想法,但对第二个没有.然而,在我投入工时来验证我的算法是否正确之前,我想确保贝尔实验室(或其他任何地方)的某个人在三十年前还没有完成这项工作.

Answer 1

我不知道这个解决方案是否实际在任何地方使用，但这是我会尝试的（假设没有丢失数据包，最多“洗牌”五个位置，最大序列号为 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的混合物