按循环序列号排序项目

Question

我正在开发一种在传输中重新排序数据包的算法。每个分组在[0,256]中有一个相关联的序列号。第一个数据包的序列号可以接受这些值中的任何一个，在此之后，下一个分组将获得下一个值，而下一个分组将获得该值之后的值，依此类推(在255之后滚动)。

按正确顺序排列的数据包序列号如下，其中"n“是第一个数据包的序列号：

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

每个数据包到达目的地时都有一个时间戳，并且它们几乎都是按照顺序到达的。(我没有确切的数字，但给出了一个按到达时间戳排序的数据包列表，可以肯定地说，一个数据包将永远不会超过五个点，而这个位置是由它的序列号表示的。)

我觉得我不可能是第一个处理这类问题的人，因为电讯的普及，以及它对电脑科学发展的历史重要性。我的问题是：

1. Is有一个众所周知的算法来重新排序一个近似有序的序列，如上面所描述的，给出了一个循环变化的key?
2. Is，这个算法有一个变化，可以容忍大量丢失的项？，假设这些块可以是任意长度的。我特别担心256个或更多的丢失物品。

对于第一个算法，我有一些想法，但对于第二个算法，我没有一些想法。然而，在我投入工时来验证我的算法是否正确之前，我想确保贝尔实验室(或其他任何地方)的人在30年前还没有做得更好。

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

基本上，在优先级队列中，我们存储上次处理的数据包与仍在等待处理的数据包之间有多少个数据包。队列将保持非常小，因为数据包一进来就会尽快处理。另外，增加键将非常简单，因为不需要重新排序堆。

我不知道你怎么才能适应丢失的数据包。最有可能的方法是使用一些超时或最大偏移量，然后将包声明为"next“，然后相应地更新堆。

我不认为这个问题是不可能的，但是，如果你错过超过256个包。取子序列

127,130,128,129

这可能有几个原因

( 1)包128和129出现故障，应重新订购

2)丢包128和129，丢失253包，订单正确。

3) 1和2的混合物

Answer 2

有趣的问题！

我的解决方案是根据到达时间对数据包进行排序，并根据分组号对元素窗口(例如10)进行局部排序。您可以在许多方面改进这一点。如果两个连续的分组号码之间的差异(根据到达的时间排列)大于一定的阈值，那么您可以在它们之间设置一个屏障(也就是说，您不能跨越障碍进行排序)。另外，如果数据包之间的时间差(根据到达时间排列)大于某个阈值，您可能希望设置一个障碍(这可能会解决问题2)。

Answer 3

使用优先级队列。

每次收到每一包后：

queue.

• repeatedly中的
• 将其放入队列的顶部元素，只要它是您正在等待的.

关于第二个问题：

一般情况下，

• 是没有办法解决的。如果数据包到达有一定的周期性(例如:每隔20‘s等待一个数据包)，那么您可以很容易地检测到这一点，清理队列，在收到5个数据包之后，您将知道如何再次处理.