在固定宽度消息计数器中检测环绕的好方法是什么？

Question

我正在编写一个客户端应用程序来通过 UDP 与服务器程序进行通信。客户端定期发出数据请求，并需要使用最新的服务器响应。请求消息有一个由服务器回显的 16 位无符号计数器字段，因此我可以将请求与服务器响应配对。

由于它是 UDP，我必须处理服务器响应无序到达（或根本不到达）的情况。天真地，这意味着保留迄今为止看到的最高消息计数器并丢弃任何具有较低数字的传入消息。但是，一旦我们传递 65535 条消息并且计数器回滚到零，该操作就会失败。是否有一个好的方法来检测（以合理的概率）消息 5 实际上是在消息 65,000 之后出现的？

实现语言是C++。

Answer 1

处理这个问题的常用方法是进行模减法。如果 & 则序列号 b 位于序列号 a 之后。仅当 (a - b) % 65536 大于 (b - a) % 65536 时。

对于您的示例，(65000 - 5) % 65536 是 64995，(5 - 65000) % 65536 是 541，因此序列号 5 在序列号 65000 之后。

Answer 2

如果我理解正确的话，你也许可以使用一些窗口（如果你还没有的话）。

也就是说，不要接受窗口之外的消息。例如，如果您的计数器为 1000，您可以将接受的传入计数器 ID 范围限制为 1000...1031（含）。因此，超出该范围的任何内容对于您来说都难以处理（迫使您启动一些重新发送协议）。一旦你得到 1000，你的上限将变为 1032。然后，一旦你得到 1001 的下限计数器，你的上限将是 1033，依此类推。你最终得到的是一个滑动窗口。

如果这种情况可以接受，那么您只需检查您的收货计数器 ID 是否在可接受的窗口内。这将是 16 位计数器的子集，因此您可以测试...

传入计数器 ID - lowerLimitCount < windowSize

只要您处理的是无符号变量，就应该没问题。

希望这有帮助（并且有意义）。

Answer 3

您的问题很久以前就在 RFC1982 中得到了解答，其中说明您是否有未签名的序列号 i1 和i2，如果 i1 <> 则适当的测试是

i1 小于 i2。 i2，并且

    (i1 < i2 and (i2 - i1) < 2^(SERIAL_BITS - 1)) or
    (i1 > i2 and (i1 - i2) > 2^(SERIAL_BITS - 1))

（或使用其反向大于测试）

对于 32 位无符号，2^(SERIAL_BITS - 1) = 2^31 = x80000000

Answer 4

我可以让客户端保存两件事：

• 未签名的 32 位内部消息计数器
• 待处理服务器请求的列表

对于每个请求，客户端都会递增其内部计数器并将其保存在列表中。在请求消息中，它将消息计数器设置为该数字模 65536。当响应消息传入时，客户端将遍历其待处理请求列表以查找匹配数字模 65536。如果该内部数字大于迄今为止的最高数字，该消息已被接受。这将环绕问题推迟到 40 亿左右。伪代码如下。

unsigned long internalCounter = 0;
unsigned long highestSoFar = 0;

// On message send...
++internalCounter;
message.counter = internalCounter % 65536;
pendingList.push_back(internalCounter);

// On message receive...
for (i = pendingList.begin(); i != pendingList.end(); ++i)
{
    if (*i % 65536 == message.counter && *i > highestSoFar)
    {
        highestSoFar = *i;
        pendingList.remove(i);
        process(message);
        break;
    }
}

Answer 5

这主要是所说的内容的组合，所以不要选择我作为答案，但既然你知道

1. 你所要求的内容（请求和请求编号）

2. 您收到了什么

3. 距离您发出请求已有多长时间

4. 对特定请求的响应应该是什么样子

   对

您应该能够让一个相当好的系统运行。

从请求提出者/响应接受者方面：

1. 永远不要接受对您尚未提出或很久以前提出的请求的响应，以免您认为该请求已过时。应删除此类响应中的数据。仅接受预期请求的第一个响应，并在接受时将请求编号标记为非预期。 （处理程序 (*f)() 是实现此目的的好方法）

2. 无论何时收到响应，您都应该记录与该请求编号相关的当前时间，以便在您开始回收请求编号时为您提供帮助。应对已接受和未接受的响应（在 1 中删除的响应）执行此操作。

3. 不接受不属于所提出问题的合法数据的回复。如果收到这样的响应，请将其丢弃，并且如果您可以确定再次发出应该使用该请求代码的实际请求不会对另一台计算机造成不良副作用，那么您可能需要使用新请求重复该请求代码（如果有足够长的时间未受影响 - 请参阅 4）并将旧的请求代码标记为不期望的。

4. 从您在最长时间内未看到回复的请求号中选择您的请求号。如果最近最少使用的请求代码太年轻，则记录事件，但尝试继续工作。将所有未使用的请求号视为很久以前使用过。

5. 在请求发送代码之前调出您的响应侦听代码，以便它可以查看是否有任何旧响应从该程序上次运行的管道中传入。

在请求接受者/响应制定者方面：

1. 如果使用请求编号发出任何请求，则您已经在处理响应以记录事件，并且仅为新响应提供服务。

除非您非常快地发送大量请求，否则这应该可以很好地工作。这并不假设网络上有人想做坏事。在此设置上实施拒绝服务 (DOS) 是微不足道的。