8

我正在开发一种算法来重新排序传输中的数据包。每个数据包在 [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 件或更多的物品。

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

4

3 回答 3

1

有趣的问题！

我的解决方案是根据到达时间对数据包进行排序，并根据数据包编号在本地循环排序一个元素窗口（比如 10）。您可以通过多种方式对此进行细化。如果两个连续的数据包编号之间的差异（根据到达时间排列）大于某个阈值，您可能会在它们之间设置一个障碍（即您不能跨障碍排序）。此外，如果数据包之间的时间差（根据到达时间排列）大于某个阈值，您可能需要设置一个障碍（这可能会解决问题 2）。

于 2012-02-01T18:48:57.720 回答
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 的混合

于 2012-02-01T19:03:50.723 回答
0

使用优先队列。

每次收到每个数据包后：

  • 把它放在队列中。
  • 重复删除队列的顶部元素，只要它是您正在等待的元素。

对于第二个问题：

  • 一般来说，不，没有办法解决它。
  • 如果数据包到达有一定的周期性（例如：期望每20ms有一个数据包），那么您可以轻松检测到这一点，清理队列，在收到5个数据包后，您将知道如何再次处理......
于 2012-02-01T18:08:49.737 回答