令牌桶计量与整形 | Codeboy's Blog

形式陈述

每个字节花一个令牌

考虑一个出口的非空分组，每个包有明确计费长度 $\ell>0$ 字节。令牌桶容量为 $B>0$ 字节，补充速率为 $r>0$ 字节/秒，状态为最近更新时刻 $t_0$ 与剩余令牌 $b\in[0,B]$ ；初态满桶。到单调时刻 $t\ge t_0$ 时，先更新

b\leftarrow\min(B,b+r(t-t_0)),\qquad t_0\leftarrow t.

严格整包准入要求 $b\ge\ell$ ；通过后扣除 $\ell$ ，不通过时不扣。这是RFC 3290附录A.4的严格令牌桶口径。计费字节必须先约定：本文是模型给定的分组长度，不混用应用载荷、IP总长度和链路线上所有开销。[1]

令牌只在有事件时按时间差一次补齐，与连续匀速补充后封顶完全等价，不需要每毫秒执行一次“加令牌”。所有同时刻事件仍按给定顺序处理；第一个包花掉的余额不能同时再被第二个包使用。

计量器和整形器面对不足时做不同的事

计量器（meter）只判断到达时是否合格。本文选择“合格则接受，不合格则丢弃”的policer，失败不扣令牌；标记不合格包也是可能的另一个动作，但不在本例中。它没有通过等待来保证这次包最终合格。

整形器（shaper）先把包放进FIFO队列，只考察队首。若头包长 $\ell\le B$ 、当前余额不足且下游已可接收，最早再试时间为

t_{eligible}=t+\frac{\ell-b}{r}.

到时重新补充、检查、扣账并交给下游。队首没有通过时，后面的短包不能越过它。本文先使用下游瞬时接收且没有额外瓶颈的模型；下游若忙碌，实际准入更晚，必须在实际准入时才扣账。只预先计算资格时间、很久后把一批旧资格包同时放行，不能保证实际放行流量满足同一个桶。

突发包络量的是哪种事件

令 $A(s,t]$ 表示在时间区间 $(s,t]$ 内通过该门的完整包计费字节总数，在每个准入事件处一次计入整包。对任意 $s\le t$ ，有

A(s,t]\le B+r(t-s).

证明只需记账：时刻 $s$ 之后能花的令牌，至多是当时的余额 $B$ 加区间中新生成的 $r(t-s)$ ；封顶丢掉的令牌只会减少可花数。每次通过必须先付完整包长，因此不可能透支。初始时刻的突发同理最多 $B$ ；若要把时刻0的包也计入统计，可从0之前无发送的时刻开始取区间。

直觉

速率决定补得多快，容量决定能攒多少

令 $r=1000$ B/s：一秒空闲可以补1000字节预算。若容量 $B=2000$ B，空闲十秒也只剩2000；之前没有使用的八秒不会变成无限信用。因此长期平均发送受到 $r$ 约束，同时允许一阵最多约 $B$ 的短时突发。

$B$ 和 $r$ 不能互相替代。把 $B$ 加大，会允许更大的初始突发，却不提高长期补充速度；把 $r$ 加大，会缩短等余额的时间，却不能让长度超过 $B$ 的包通过严格检查。

例子与边界

相同输入，等待和丢弃得到不同结果

取 $B=2000,r=1000$ ，三个包按1500、1000、500字节的顺序在0秒同时到达。

整形器事件	时刻秒	扣前令牌	本次通过	扣后令牌
初始满桶	0	2000	1500	500
头包缺500，等0.5秒	0.5	1000	1000	0
头包缺500，再等0.5秒	1	500	500	0

三个包全部保留，放行时刻为0、0.5、1。0秒通过第一包后，不能跳到后面那个500字节包，哪怕余额刚好足够；这是本页FIFO规则的实际约束。

若改用立即计量并丢弃的policer，同一个0秒先接受1500、剩500；1000不合格被丢弃且不扣余额；最后500仍合格。接受总量2000，并不违背包络。它与整形器的差异是第二个包是否等待，不是“哪个实现的减法对”。

头包比桶还大，时间不能救它

把容量改成1000，其他不变，1500字节头包永远无法取得足够令牌。即使等一小时，余额也只到1000。若只反复按 $(1500-b)/r$ 设闹钟，会无限醒来却没有进展。实现应在入队时拒绝这种包，或在允许分组的上层重新切分；不能默默绕过严格计量，更不能宣称有限等待保证。

另一种“允许余额为负、整包先走”的宽松桶有不同包络，一般需要额外包长项。它并不是本页检查 $b\ge\ell$ 的等价实现，不能共用这里的精确突发界。

队列容量和链路序列化仍需单独处理

如果输入持续2000 B/s而补充率只有1000 B/s，整形队列会不断增长。令牌桶限制出口，不会自动限制内存；背压仍要给队列设容量，并规定满时等待、拒绝或丢弃。无界排队也不意味着每个有限等待者都有统一延迟上界。

若进一步已知下游提供速率—时延服务曲线，到达突发b、持续速率ρ与服务R、T可在ρ≤R时给出积压b+ρT和FIFO迟延T+b/R。两节点(6,1)、(4,2)串联、输入12+2u的主例给总积压18和迟延6；必须分别核对真实输出计数与内部队列，不能仅凭链路铭牌或两个队列峰值相加就声明合同成立。

若物理链路速率为 $c$ B/s，一个长度 $\ell$ 的包至少占用 $\ell/c$ 秒。可以令牌门只在链路空闲时准入下一个包，此时资格等待与链路等待取共同约束；每次实际开始发送仍受桶限制。本文包络按开始时整包计数，不能不加说明就套到“最后一个比特发送完”或远端收包时刻。后者还受序列化和网络抖动影响。

推论与应用

和流调度器组合时保留哪一个保证

DRR选择下一个流，令牌桶控制聚合出口何时有预算。一个易复算的组合是先按DRR产生包序列，再让这一个序列按FIFO通过共享桶。共享桶保持这个顺序和聚合包络；它不等于为每条流各开一个独立桶，也不自动给出每条流的端到端最低速率。

例如待发顺序为500、500、500、500、1500、500，桶仍为2000/1000且初态满。前四包都可在0秒通过；第五包须等到1.5秒；第六包在2秒通过。如果在每个流里都放一个容量2000的桶，两个同时满桶的流可能合计突发4000，已经是另一份聚合契约。

事件驱动实现只做必要工作

每个到达或定时唤醒事件补充一次、比较一次、扣除至多本次获准字节，单个包的常数次算术不随等待毫秒数增长。连续放行 $k$ 个包需 $O(1+k)$ 控制工作，另计队列操作和实际复制/发送的字节成本。浮点数在边界附近可能误判“刚好够”；示例检查器使用有理数，生产实现可以使用明确取整方向的整数时间与信用单位。

参考资料

[1] Yoram Bernet等，RFC 3290: An Informal Management Model for Diffserv Routers，2002，附录A.3讨论严格/宽松计量与包长，附录A.4给出严格桶的补充、成功扣除、失败保留和最早整形时刻。本文的队列例、时间包络记账证明及容量迁移题均按明示模型构造。

形式陈述 ​

每个字节花一个令牌 ​

计量器和整形器面对不足时做不同的事 ​

突发包络量的是哪种事件 ​

速率决定补得多快，容量决定能攒多少 ​

相同输入，等待和丢弃得到不同结果 ​

头包比桶还大，时间不能救它 ​

队列容量和链路序列化仍需单独处理 ​

和流调度器组合时保留哪一个保证 ​

事件驱动实现只做必要工作 ​

反向链接