摘要

  • 普通分组轮转平均分配的是访问机会，不是字节。Shreedhar 与 Varghese 的 DRR 为每个队列增加量子和亏欠计数器：只要余额容纳队首整包就继续发送，未用完的额度由仍然积压的队列带入下一轮。
  • 这种设计以接近常数级的逐包工作换取有界的长期吞吐偏差。它所实现的是配置队列及权重之间的服务公平；基本 DRR 本身既不限定单包等待时间，也不负责分类、整形、主动队列管理、拥塞控制或端到端质量。

公平的错觉藏在计量单位里

轮转算法最诱人的地方，是其动作具有肉眼可见的对称性：指针走到每个非空队列，允许它服务一次，然后前进。若每项工作大小完全相同，这种对称也能转化为资源份额。但 IP 分组不是同尺寸的筹码。两个队列各取一个包，可能分别占用链路 12,000 比特和 4,000 比特；连续重复时，轮次平等反而稳定地制造字节不平等。

这不是实现细节，而是资源定义错误。链路出售和消耗的是传输时间与比特容量，不是包的个数。用访问次数作为公平证据，好比给两辆卡车同样一次过桥机会，却忽略载重和占桥时间。只要包长分布不同，简单 packet round robin 的仪表盘即使显示每个队列的发送包数接近，也不能推出它们获得了相近带宽。

另一种极端是精确模拟理想化的逐比特公平排队。理论模型可以把每个流想象成同时、连续地得到服务，再据此决定整包的先后次序；代价则是更复杂的排序和每包计算。在高速转发路径上，算法是否公平与能否用廉价硬件按线速执行是同一个设计问题的两面。DRR 的关键不是追求每一瞬间都像流体模型，而是把误差限制住，同时保持操作简单。

亏欠不是欠债，而是被保留下来的服务资格

DRR 为每个活动队列保存一个 deficit counter。调度器访问队列时，把该队列配置的 quantum 加到计数器上。若队首包长度不超过余额，便发送整个包并扣除相应字节；只要下一个整包仍能由余额支付，就继续发送。若余额不足以容纳队首包，调度器不拆包，也不把差额抹去，而是转向下一个活动队列。

真正改变结果的是“结转”。仍然积压的队列把未使用余额带到下一次访问，于是一个包即使大于单轮新增量子，也能在若干轮后累积到足够额度。队列一旦排空，旧余额被清零；否则后来才到达的流量会继承一笔并非为它等待而积累的服务资格。活动列表、量子、队首包长度和计数器，共同决定每一次可执行的动作。

把它叫作亏欠容易引出错误直觉。计数器不是客户债务、拥塞价格、服务等级违约，也不是网络对用户的补偿承诺。它只是局部调度器中的会计状态：记录某队列已获得但尚未能以不可分割整包形式使用的额度。这个状态跨越轮次，恰好弥合了“按连续字节分配”与“只能发送整包”之间的裂缝。

例如两个长期积压队列拥有相同量子，其中一个包普遍较小，另一个包普遍较大。小包队列可能一次访问发出多个包，大包队列有时一个也发不出，但余额不会消失。观察单次访问会显得参差；观察足够长的字节服务，两者围绕目标份额收敛，剩余偏差受到包大小约束。DRR 接受短期颗粒度，以换取可解释的长期结果。

量子是一条政策，而不只是一个参数

若所有队列使用同一量子，目标是近似相同字节份额；若量子按比例不同，长期服务权重也随之改变。所谓“加权”并不需要另换一套哲学：相对量子就是容量政策的数值表达。把某队列的量子设为另一队列的两倍，意味着在共同持续积压的条件下，它应得到约两倍字节服务，而不是两倍包数。

量子也会影响调度颗粒度。过小的量子会让大包需要多轮积累，并提高队列访问次数；较大的量子能一次释放更多字节，却可能造成更明显的突发服务。论文讨论的效率边界与最大包长相关，工程部署不能只保存一个“DRR 已启用”的布尔值。若没有每队列量子、最大包尺度和配置版本，就无法复核当时宣称的公平含义。

Shreedhar 与 Varghese 在 1994 年技术报告及随后 SIGCOMM 论文中强调的是近乎理想的吞吐公平、低复杂度和适于硬件实现。他们所解决的难题很具体：怎样不依赖昂贵的每包排序，也能让可变长度分组的服务差距保持有界。这里的 O(1) 应理解为调度操作的低且可控成本，不是说系统中的队列数、分类规则或所有性能维度都突然成为常数。

计数器之后是公平，计数器之前是谁

DRR 只看调度器收到的队列。若十个租户被分类进一个共享队列，而另一个租户独占一个队列，即使两个队列的量子相同，算法公平分配的也是这两个队列，而不是十一位租户。若分类器把大象流与交互流混在一起，队首阻塞和队内等待也不会被亏欠计数器自动拆开。

因此，“我们使用 DRR”不是完整的公平陈述。至少还要说明：什么字段把包映射到队列；队列对应用户、流、优先级、隧道还是服务类；未知流量落在哪里；量子如何确定；队列何时进入或退出活动列表；状态在重配置、故障切换和硬件迁移时如何处理。算法没有替运营者回答公平对象是谁。

这一边界也关系到证据。只看端口总吞吐，无法验证每个队列是否得到应有份额；只看包数，又会重演 round robin 的单位错误。可审计记录应把分类器版本、队列成员、量子、字节出队量、包长分布、计数器结转和活动周期关联起来。否则，公平可能只是一张由聚合指标制造的漂亮图。

吞吐公平不等于等待时间有上限

基本 DRR 可以在长期字节服务上逼近目标权重，却不自动为某个包给出严格时延保证。一个队列可能等待其他活动队列轮转；它还可能在队内排在大量包之后。量子、活动队列数量、包长上限和到达过程都会改变等待。原论文明确区分吞吐公平与时延界，并讨论了为支持时延约束而需要的扩展；不能把扩展的性质倒填给基础算法。

它也不决定包何时进入队列，不限制发送者的到达速率，不发现端到端拥塞，更不选择何时丢包或标记 ECN。整形器管到达节奏，AQM 管排队信号与丢弃策略，拥塞控制改变发送端行为，分类器确定调度对象。RFC 7567 在讨论队列管理时也把 scheduling 与 AQM 分开：二者会共同影响结果，却不是同一机制。

这条界线对采购、SLA 和故障复盘尤其重要。若合同要求 99 分位时延，证明 DRR 的字节份额接近配置值并不能完成验证；若投诉源于分类错误，调整计数器不会修复身份映射；若所有队列总到达量持续超过链路容量，公平地分享拥塞也不等于消除拥塞。机制名称必须与它能支持的主张一一对应。

George Varghese 的快路径方法

Varghese 后来的职业轨迹让 DRR 更容易被放进一条连续的研究线索中。UCLA 的官方资料将他列为计算机科学杰出教授与 Jonathan B. Postel Chair，研究覆盖 network algorithmics、验证、网络安全和未来互联网。他在 MIT 获得博士学位，加入 UCLA 前曾任教于 Washington University in St. Louis 与 UC San Diego，并在 Microsoft Research 工作。

这些履历本身不是算法正确性的证据，却解释了 DRR 的设计气质：从转发路径中找出昂贵操作，改变状态表示，让理论目标在真实速率下可实现。ACM SIGCOMM 于 2014 年授予 Varghese SIGCOMM Award；Internet Hall of Fame 于 2021 年将他列为入选者，并特别提到他与 M. Shreedhar 发明 DRR，以及该算法在 Cisco GSR 等设备中的历史采用。

历史荣誉不应取代原始论文。最强的技术主张仍须回到作者的模型、假设和误差边界；产品采用信息则说明思想确实越过论文进入了路由器。把两类证据分开，既能避免用奖项证明定理，也能避免把一个有影响力的工程机制写成脱离部署的抽象技巧。

证据应当跟随配置变化

运维记录若只截取某个时刻的吞吐比例，会漏掉 DRR 最重要的状态：余额如何跨轮次累积。一次配置变更后，应该同时观察每队列量子、活动状态、队首包尺度、结转余额以及实际出队字节。小包数增加不必然意味着该队列侵占容量；大包队列短暂没有发送，也不必然意味着饥饿。需要在足以覆盖多个服务轮次的时间窗内解释因果。

最值得保留的不是一句“公平正常”，而是可重建当时公平人口与权重的材料。谁修改了分类规则，哪些标识映射到哪个队列，量子为何调整，空队列何时清零，设备升级是否保持状态语义——这些信息一旦丢失，事后仅凭接口总量无法恢复。DRR 的贡献恰恰提醒我们：看似微小的会计状态，会决定长期资源事实。

来源