c++：流和速率调节

Question

在一次采访中，我被问到了一个有趣的问题：

假设您不断地从一个源接收一些字节流(让我们假设一个客户机-服务器模型)，其速率是可变的。你想在你的终端对数据包进行排序，然后以恒定的速率将它们重新传输到其他地方。您将如何在C++中实现这样的系统？

我提供了一个基本系统，一个工作线程将包推到堆中，调度员线程弹出排序的数据包，并将它们与某个内部时钟同步发送出去，时间间隔为X。

面试官合理地认为，由于线程之间的上下文切换，这样的系统很容易错过重传的最后期限。我回答说，如果没有对特定机器中的线程调度算法的任何控制，我就无法保证恒定的重传速率。他坚持下去，这让我觉得我可能错了，这实际上是可以实现的。那我是吗？

Answer 1

对问题的描述太模糊了。“分类”是什么意思？数据包体内是否有某种序列号？如果我们从来没有收到带有序列号的数据包呢？以下是我对一些通用算法的想法，这些算法可以适应不同的具体情况。

参数

算法取决于以下参数：

1. 允许我们缓冲的最大数据包数(例如，4096)。
2. 水印值高。这是一个相对于(1)的百分比。如果目前缓冲区中的数据包比HWV多，那么即使数据包没有排序，我们也会发送它。(50%，即2048)。
3. 最大的时间，我们允许我们的数据包被缓冲。

变量

首先，我们需要一个固定长度的环形缓冲器。环形缓冲器包括：

1. 缓冲包的Array4096
2. 指向上述数组的指针的Array4096 (以避免在排序操作期间复制数据包本身)
3. 元信息的Array4096 -每个数据包的序列号(从数据包中解析)和接收数据包时的时间戳
4. 指向头部和尾部的指针。

我们还需要存储全局变量--下一个要发送的序列号。

算法

当数据包到达时，我们将数据包添加到适当的位置(插入排序的一个步骤)，因此我们的缓冲区总是按序列号排序。在此之后，如果至少有下列一项是正确的，我们可能希望从缓冲区的头发送数据包：

1. 头包的Seq数小于或等于预期的seq数。这意味着头数据包是下一个排序顺序。典型的情况。
2. 缓冲器中的分组数超过高水印值(2048)。我们发送head数据包(尽管它没有排序)，因为我们担心传入活动的突发可能会填满缓冲区的其余部分，我们将不得不丢弃更多的传入数据包。
3. 当前时间减去头包到达的时间超过TTL。

如果以上至少有一个是正确的，我们发送头包并从缓冲区中删除它。我们还将预期的序列号分配为发送数据包的seq号加上一个。如果在发送头数据包后，缓冲区不是空的，我们也(重新)用TTL值启动计时器。当计时器被触发时，我们执行相同的检查。这是为了避免将数据包无限期地保存在缓冲区中(以防没有更多的传入数据包)。