亏额轮转分组调度 | Codeboy's Blog

形式陈述

轮流获得字节预算

设每条流 $i$ 维护一个FIFO队列，元素为不可抢占的包，计费长度为正整数且不超过 $M_i$ 。流的字节量子为 $Q_i>0$ ，亏额计数 $D_i$ 初始为0。名字里的“亏额”表示上轮没有用完的预算，不表示允许先发送再欠账；真正扣账仍须余额足够。

另维护只含非空流的活跃队列，每条活跃流只出现一次。一次访问取出活跃队首 $i$ ，执行：

加本轮预算： $D_i\leftarrow D_i+Q_i$
只要本流非空且头包长度 $\ell\le D_i$ ，发出头包并令 $D_i\leftarrow D_i-\ell$
若本流仍非空，把 $i$ 放回活跃队尾，保留余额；若已空，令 $D_i=0$ ，本次不再加入活跃队列

新包到达原先为空且不在当前服务中的流时，把该流以余额0加入活跃队尾。教学轨迹将一次完整访问视为顺序事件；服务过程中发生的真实并发入队需要明确定序和同步，不是另一次偷偷增加量子。[1, §III、图4]

访问结束后的余量界

一次访问结束，如果队列非空，下一头包没能发送，故

0\le D_i<\ell_{head}\le M_i.

如果已经空，清零后也有 $0\le D_i<M_i$ 。这是访问结束边界的不变量；访问刚加量子、还没开始扣包时，余额可能大于 $M_i$ ，不能在这个中间点误报不变量破坏。

对一段持续积压且没有清零的 $k$ 次完整访问，设累计服务字节为 $S_i(k)$ ，初始余量为 $D_i(0)$ 。每轮只“加量子、减发送字节”，望远镜相加得到

S_i(k)=kQ_i+D_i(0)-D_i(k).

从共同新激活、余量0开始，两流各完成 $k$ 次访问且始终积压，则

\left|\frac{S_i(k)}{Q_i}-\frac{S_j(k)}{Q_j}\right| <\max\!\left(\frac{M_i}{Q_i},\frac{M_j}{Q_j}\right).

理由是两项都等于 $k$ 减去一个分别落在 $[0,M_i/Q_i)$ 、 $[0,M_j/Q_j)$ 的数。若量子相等为 $Q$ ，公共最大包长为 $M$ ，便得 $|S_i-S_j|<M$ 。这是对齐完整轮边界的结论；任意实时时刻可能某流刚被服务、另一流还没轮到，不能直接套用它。[1, §IV引理1–2；本页取共同零余量的特例]

直觉

大包欠缺的机会不能每轮清零

如果每轮只允许每流发一个包，500字节包的流与1500字节包的流获得相同包数，却不是相同字节服务。若改成每轮1000字节且不能结转，1500字节头包又会永远卡住。

DRR让这条流第一轮保留1000，第二轮加到2000，就可发1500并留下500。下一轮再加1000，又足够发1500。它用余量补偿“这一轮还不够装下一个整包”的差距，不需要把包切成每字节交替发送。

A的小包每轮花完1000，B的大包先积攒再发送，第三轮累计服务都到3000 — 字节量子与余量结转

例子与边界

两条持续积压流的前三轮

A连续提供500字节包，B连续提供1500字节包，两者 $Q=1000$ 。活跃次序A、B，初始余量都为0。

完整轮	A本轮发送/余量	B加量子后	B本轮发送/余量	累计A、B字节
1	500+500 / 0	1000	0 / 1000	1000、0
2	500+500 / 0	2000	1500 / 500	2000、1500
3	500+500 / 0	1500	1500 / 0	3000、3000

第一轮B没有发包，不是饥饿证明；下一轮的量子会加在已有1000上。共同轮边界的最大差在第一轮为1000，小于 $M=1500$ 。第二轮A刚服务完而B尚未服务时，累计为2000与0，差2000；这正好展示为何不能把轮末的“小于1500”写成任意时刻的保证。

若A只有一个500字节包，首次访问加1000、发送500后空了，剩下500必须清零。它以后重新活跃，仍从0加本次量子；不能靠长时间空闲攒出一个巨大突发。带时间补充且有容量上限的令牌桶解决的是另一种预算任务。

加权份额按量子，不按到达包数

把 $Q_A=1000,Q_B=2000$ ，包长仍为500和1500，保持两流持续积压。前3轮A服务1000、1000、1000；B服务1500、1500、3000，余量500、1000、0。累计服务为3000与6000，刚好达到1:2；其他轮末允许有包长尺度的误差。

一个暂时没有包的流无法使用自己的份额，DRR会跳过它。因此这个比例针对同时积压的流，不是按墙上时钟为每个登记过的流预留永久带宽，也不是应用流量需求不足时仍能凭空发送。

小量子会让无发送访问变多

若某流头包1500而 $Q=1$ ，从0开始要第1500次访问才够发送。算法仍能结转并最终处理这个有限包，但前1499次都只做加法和轮转。把量子视为任意输入时，就不能无条件声称每包只有常数调度工作。

当每条流 $Q_i\ge M_i$ 时，一次非空访问至少发一个包。假设活跃队列和各流队列的头尾操作是常数成本，且流身份已解析，则每次包出队及可能切换到下一流只需常数控制工作；把一次发出多包的完整访问合起来看，发 $k$ 包需 $O(1+k)$ 。从空结构开始， $a$ 次入队、 $b$ 次出队的总控制成本为 $O(1+a+b)$ ，初始化流数组成本另计。[1, 定理4]

若流ID用散列表查找，匹配通常只能按合适散列假设声称期望常数，而非忽略碰撞后宣称最坏常数。配套核验器还在每次访问后扫描活跃集合及全部流队列来检查不变量，并复制全流累计服务数组生成日志快照，另付 $O(1+\text{流数})$ 调试成本；这不是核心队列操作的成本。上述界也不包含每包载荷复制或链路实际发送时间。 $Q_i<M_i$ 时的无发送访问数必须另计，不能藏进一个与 $M_i/Q_i$ 无关的常数。

推论与应用

证明长时间份额，不能代替延迟契约

对固定量子和有界包长，完整轮数量 $k$ 增大时，余量误差相对 $kQ_i$ 会减小。这解释了持续积压流的长期字节份额为何接近量子比例。有限延迟仍需要活跃流数量、各流量子、包长和链路速率等边界；DRR并不是理想的逐比特轮转，增大某流量子也会增加别人等待其一整次服务的时间。

GPS参考钟驱动的WFQ提供另一种可验目标：同时推进理想流体与真实整包两套状态，以虚拟完成标签选包，证明每包比GPS至多晚一个最大包发送时间。其六包轨迹中，真实A在4/3已空，GPS的A2到2才完成，不能用真实活跃集合替代参考集合。这与本页对齐轮边界的余量保证分别成立。

一次访问不截断头包，也不越过本流的长头包服务后面的短包。这保证每流FIFO，却意味着“控制工作常数”和“小包立即得到服务”是两件不同的事。

和恢复队列、聚合出口组合

QUIC恢复可以把仍需发送的信息交给一个明确的流调度器，但QUIC并不强制采用DRR。主例前三轮选出的包次序开始于A500、A500、A500、A500、B1500、A500。再经过初态满的2000 B/1000 B/s共享令牌桶，这六包在0、0、0、0、1.5、2秒依次获准。

这个组合先固定包次序，再由一个门决定实际时间，便于分别复算份额账本和聚合包络。若边整形边改变活跃流、跳过不合格队列或补入新到达包，就要重新规定事件次序；不能直接拿这份预先选出的六包轨迹当作该实现的证明。

参考资料

[1] M. Shreedhar、George Varghese，Efficient Fair Queuing Using Deficit Round-Robin，IEEE/ACM Transactions on Networking 4(3)，1996，pp.375–385；§III及图4在pp.378–379定义活跃队列与余量，§IV引理1–2给出余量/服务记账，定理4在p.380说明量子至少最大包长时的成本条件。本文数值、共同零余量轮末特例及整形组合为教学推导。

形式陈述 ​

轮流获得字节预算 ​

访问结束后的余量界 ​

大包欠缺的机会不能每轮清零 ​

两条持续积压流的前三轮 ​

加权份额按量子，不按到达包数 ​

小量子会让无发送访问变多 ​

证明长时间份额，不能代替延迟契约 ​

和恢复队列、聚合出口组合 ​

反向链接