到达包络与网络服务曲线

一个出口平均每秒能发四字节，不代表任意十二字节突发都能立刻发完；如果它还可能先停三秒，所需缓冲会更大。确定性网络演算同时记录两项承诺：输入最多来多少，服务至少推进多少。它不要求到达服从某个随机分布，而是对满足这些合同的每条轨迹给出上界。

形式陈述

先把累计量和事件口径固定下来

考虑初始为空、因果、无损的一条数据流。 $A(t)$ 、 $D(t)$ 分别是到达与离开的累计计费量，非降且满足 $A(0)=D(0)=0$ 、 $0\le D(t)\le A(t)$ 。本页先采用可无限细分的数据模型；累计函数按 $[0,t)$ 计数、取左连续版本。一个恰在 $t$ 到达的突发要在 $A(t+)$ 才被包含。实际比特的迟延也相应从右侧极限读取。[1, §§1.1.1–1.1.2]

到达曲线 $\alpha$ 承诺任意 $0\le s\le t$ 都有

A(t)-A(s)\le\alpha(t-s).

本页复用令牌桶的逐区间预算： $\alpha(0)=0$ ，正长度窗口内 $\alpha(u)=b+\rho u$ ，其中 $b\ge0$ 为突发量、 $\rho\ge0$ 为持续速率。它是每个窗口的上界，不是要求输入永远按 $b+\rho t$ 到达。严格整包桶还要求每个获准包不超过桶容量；本页将已经给出的包络作为输入合同。[1, §1.2.1]

最小服务不是空闲时也必须发送

对非负函数定义min-plus卷积

(f\otimes g)(t)=\inf_{0\le s\le t}\{f(s)+g(t-s)\}.

系统提供最小服务曲线 $\beta$ ，是指对所有 $t\ge0$ ，

D(t)\ge(A\otimes\beta)(t),

其中 $\beta$ 非降且 $\beta(0)=0$ 。卷积尝试每个分割时刻 $s$ ：此前到达的 $A(s)$ 加上随后时段的服务承诺；所有候选的下包络给出实际输出必须达到的位置。[1, Definition1.3.1]

本文重点是速率—时延曲线

\beta_{R,T}(u)=R(u-T)^+,\qquad R>0,\ T\ge0,

其中 $x^+=\max\{x,0\}$ 。先容许一段时延 $T$ ，之后以斜率 $R$ 增加下界。它不是“每个长度为u的墙钟窗口都发送至少 $\beta(u)$ ”：没有输入时， $A$ 、 $D$ 都可为零，卷积也为零。

一个已知恒速FIFO服务器可以从最后一次空队列的时刻推导这份合同；其他调度器也可能给出相同合同。服务曲线是对真实机制已经证明的输入/输出保证，不能因为设备铭牌写着速率 $R$ ，就假设它还提供任意指定的 $T$ 。

两种可检查的偏差

时刻 $t$ 的积压为 $B(t)=A(t)-D(t)$ 。虚拟迟延定义为

d(t)=\inf\{\tau\ge0:D(t+\tau)\ge A(t)\}.

积压沿竖直方向比较同刻两条累计线；虚拟迟延沿水平方向寻找输出何时追上当前累计输入。在FIFO且数据不丢失、不复制的条件下，追上同一个累计位置才表示这批较早数据已经全部离开。无FIFO时，它只说明输出数量追上，不能认证具体旧数据的完成。

直觉

上面的输入线，下面的服务承诺

突发 $b$ 让输入可以突然跳高；持续速率 $\rho$ 决定后面还会以多快的速度增长。时延 $T$ 让服务器最初可以少做工作，速率 $R$ 决定它之后追赶的能力。如果 $\rho\le R$ ，最坏积压出现在追赶开始附近；突发最后一份数据还要额外支付约 $b/R$ 的发送时间。

十二字节初始突发经两个速率时延节点，累计线最大竖差十八、初始突发末尾在六秒完成 — 串联服务的竖直积压与水平迟延

积压上界怎样从定义出来

由服务合同，

\begin{aligned} A(t)-D(t) &\le A(t)-\inf_{0\le s\le t}\{A(s)+\beta(t-s)\}\\ &=\sup_{0\le s\le t}\{A(t)-A(s)-\beta(t-s)\}\\ &\le\sup_{u\ge0}\{\alpha(u)-\beta(u)\}. \end{aligned}

注意这里减去的是服务，不是加上服务。[1, Theorem1.4.1] 对 $\alpha(u)=b+\rho u$ 和 $\beta_{R,T}$ ，当 $0<u\le T$ ，差为 $b+\rho u$ ；当 $u>T$ ，差为

b+\rho T+(\rho-R)(u-T).

因此在 $\rho\le R$ 时，

B(t)\le b+\rho T.

$T=0$ 时从 $u\downarrow0$ 取上确界也得到 $b$ ；不必把 $\alpha(0)$ 错设成 $b$ 。若 $\rho>R$ ，第二段随 $u$ 无界增长，给定合同无法提供统一有限积压证书。

FIFO迟延为何是另一条公式

令 $H=T+b/R$ ，仍假设 $\rho\le R$ 。要证明 $D(t+H)\ge A(t)$ ，检查卷积在时刻 $t+H$ 的每个候选。

若 $s\le t$ ，到达包络给

A(t)-A(s)\le b+\rho(t-s)\le b+R(t-s)=\beta(t+H-s).

若 $s>t$ ，则 $A(s)\ge A(t)$ ，再加非负 $\beta$ 仍不少于 $A(t)$ 。所以全部候选都至少为 $A(t)$ ，其下确界也一样。于是

d(t)\le T+b/R.

对突发到达点取右侧极限，可把它读为FIFO数据的迟延上界。[1, Theorem1.4.2的本页特例] 积压除以输入速率不是这个证明： $b+\rho T$ 和 $T+b/R$ 量纲不同，使用的速率也不同。

例子与边界

两节点的端到端证书

输入包络取 $b=12,\rho=2$ 。第一节点承诺 $(R_1,T_1)=(6,1)$ ，第二节点承诺 $(R_2,T_2)=(4,2)$ ；第一输出完整成为第二输入，中途没有额外流加入或数据删除。

串联系统的服务曲线为 $\beta_1\otimes\beta_2$ 。对两个速率—时延曲线，它恰为

\beta_{R_1,T_1}\otimes\beta_{R_2,T_2} =\beta_{\min(R_1,R_2),T_1+T_2}.

所以本例端到端为 $(4,3)$ ，得到

B_{end}\le12+2\cdot3=18,\qquad H_{end}\le3+12/4=6.

这里 $B_{end}=A-D_2$ 是已进入整条链而尚未从末端离开的总量，可分布在不同节点。它不能直接指定成某一个内部队列所需的最小容量。

一条达到上界的真实流体轨迹

初始突发十二字节，随后每秒继续到达二字节，写为 $A(0)=0$ 、 $A(t)=12+2t$ （ $t>0$ ）。选择各节点恰好输出其卷积下包络。第一节点输出为

D_1(t)= \begin{cases} 0,&0\le t\le1,\\ 6(t-1),&1<t\le4,\\ 2t+10,&t\ge4. \end{cases}

第二节点输出为

D_2(t)= \begin{cases} 0,&0\le t\le3,\\ 4(t-3),&3<t\le9,\\ 2t+6,&t\ge9. \end{cases}

时刻3，累计到达18、最终输出0，总积压确为18。时刻6，第二输出达到12，初始突发最后一个字节完成，迟延恰为6。初始事件在 $A(0+)$ 中读取，而 $A(0)=0$ ；把零时刻的虚拟迟延直接代为初始突发迟延会漏掉整个突发。

第一节点在时刻1的最大积压是14，第二节点在时刻4的积压为 $D_1(4)-D_2(4)=18-4=14$ 。它们分别达到峰值的时刻不同，不能把两个峰值28当作这条实际轨迹同时占用的内存。

逐节点相加为什么更松

第一节点的迟延证书是 $1+12/6=3$ 。进入第二节点时，到达包络不能未经证明仍用突发12；第一节点可能把等待的数据更集中地放出。

一般地，对 $t>s$ ，因果性 $D(t)\le A(t)$ 与服务合同给

D(t)-D(s) \le\sup_{0\le v\le s}\{A(t)-A(v)-\beta(s-v)\} \le\sup_{w\ge0}\{\alpha(t-s+w)-\beta(w)\}.

在本页仿射到达、速率—时延服务且 $\rho\le R$ 时，右边为 $b+\rho T+\rho(t-s)$ 。因此中间输出可用突发 $12+2\cdot1=14$ 、速率2的包络。[1, Theorem1.4.3]

第二节点单独给出 $2+14/4=11/2$ ；两份逐节点上界相加是 $17/2$ ，大于直接串联得到的6。两种都是安全界，但前一种在每个节点重新为突发留预算，丢掉了串联结构。所谓“突发只支付一次”，说的是更精确地组合服务合同，不是第二节点没有排队。

数量追上，不一定是那份旧数据出去

考虑 $A(t)=t$ ，服务器永久留住最早的一单位数据，从时刻1起立即转发所有后来数据，因此 $D(t)=(t-1)^+$ 。这套非FIFO机制提供 $\beta_{1,1}$ ，虚拟迟延是一秒，积压一直是一单位；那份被保留的最早数据却永远没有离开。将虚拟迟延读成每份数据迟延时，FIFO条件不能省。

另一个边界是逐包存储转发。只有一个四字节包、两条速率四字节/秒的链路。第二跳必须收齐才可开始，包在时刻2完成；若错误把两跳都视为可逐字节透传的零时延流体服务，串联公式只给一秒。问题在于第一跳完整包输出不满足所假设的 $\beta_{4,0}$ ：在时刻 $1/2$ 它尚未交付任何完整包，而该下界已要求两字节。必须给分组输出另证服务曲线，或直接使用逐包完成递推。[1, §§1.7、2.1.3]

推论与应用

串联公式的两个必要步骤

设 $D_1\ge A\otimes\beta_1$ ， $D_2\ge D_1\otimes\beta_2$ 。卷积对输入单调，且展开两重下确界就是枚举三个非负时间段，所以可重新分组：

D_2\ge(A\otimes\beta_1)\otimes\beta_2 =A\otimes(\beta_1\otimes\beta_2).

这给串联合同。[1, Theorem1.4.6] 再看两条速率—时延曲线：总时长 $u\le T_1+T_2$ 时，可把两段都放在各自零服务部分，最小和为零；超过总时延后，至少有 $u-T_1-T_2$ 时间落在正斜率部分，成本至少为 $\min(R_1,R_2)$ 乘它。让全部多余时间落在较低速率那一段，恰好达到该下界，公式因此取等。

多个节点重复应用便得到最小速率和时延总和。这个合同对调换节点次序不变；实际内部队列轨迹、分组边界或与其他流的交互不因此相同。若中途又聚合新流，就需要重新计算输入，不在本条单流串联证明内。

有限证据能查到什么

单元核验器分开提供两类检查。一类对本文分段线性函数，在折点和给定有理时刻准确计算卷积；两段线性函数的和在相邻折点间线性，最小值出现在端点，故无需浮点采样。主例还逐项检查两个内部队列和总积压。

另一类接收从0到N的累计数组，验证非降、因果、全部整数窗口的到达承诺，以及每个整数时刻的离散服务卷积；失败返回具体窗口或时刻。直接枚举分割点需 $O(1+N^2)$ 次算术，输出与工作存储 $O(1+N)$ 。它只认证所给离散时间域，不把整数检查当作两采样点之间的连续证明，也不保证未知未来。如果末尾尚未看到某累计量完成，迟延查询返回 INCOMPLETE，不猜测完成时间。

由解析公式给一个仿射包络和一条速率—时延曲线计算界只需常数次算术。将 $\rho$ 改为5、瓶颈仍为4时，接口返回无统一有限证书；取持续五字节/秒输入和恰按最低承诺服务的服务器，积压确会不断增加。这里否定的是该合同对所有合法输入的保证，并非声称每条稀疏输入都会堵塞。

WFQ在固定模型中提供逐包保证速率和完成迟延比较；本页提供已经证明服务合同之后的组合工具。二者接起来时，必须保留真实输出计数、FIFO、最大包长与分组化项，才能把上界用于缓冲预算或期限检查。

参考资料

[1] Jean-Yves Le Boudec、Patrick Thiran，Network Calculus: A Theory of Deterministic Queuing Systems for the Internet，Springer LNCS2050，作者在线版2022-08-23；§1.1 pp.3–6（累计量及突发时右极限），§1.2.1 pp.7–10（到达曲线），Definition1.3.1 p.19（服务曲线）；Theorems1.4.1–1.4.3 pp.22–24、Theorem1.4.6与“Pay Bursts Only Once” pp.28–29；§1.7 pp.40–53、§2.1.3 pp.70–71（分组边界）。本文仿射/速率—时延特例的证明、连续轨迹与有限数组证据均按显式合同展开。

形式陈述 ​

先把累计量和事件口径固定下来 ​

最小服务不是空闲时也必须发送 ​

两种可检查的偏差 ​

上面的输入线，下面的服务承诺 ​

积压上界怎样从定义出来 ​

FIFO迟延为何是另一条公式 ​

两节点的端到端证书 ​

一条达到上界的真实流体轨迹 ​

逐节点相加为什么更松 ​

数量追上，不一定是那份旧数据出去 ​

串联公式的两个必要步骤 ​

有限证据能查到什么 ​

反向链接