GPS 虚拟时钟与加权公平排队

两条流各发一个包，其中一个包十二字节、另一个一字节。如果每次只轮流发一个包，两流获得的字节服务并不相同；如果先发长包，后来到达的短包又必须等它结束。加权公平排队把这两个问题分开：先用一个能同时服务多条流的理想模型定义份额，再选择一个实际可以完整发送的包，并计算这种整包化最多会多等多久。

形式陈述

同一批输入，两个服务系统

固定有限条流，每流权重 $w_i>0$ ，出口恒定速率 $C>0$ 字节/秒。每个包完整到达后才可用，长度 $L>0$ ，所有包长至多 $M$ ；每流保留FIFO次序。初始队列为空，无丢弃、切换开销、暂停或权重改变。下文时间、长度、权重均使用精确值，真实链路额外首部若要计费，应先包含在给定长度内。

GPS（广义处理器共享）是流体参考：允许把字节无限细分，同时服务所有尚有剩余数据的流。令 $B(t)$ 是GPS内积压流集合；在集合不变的一段时间内，流 $i\in B(t)$ 的服务速率为

r_i(t)=\frac{Cw_i}{\sum_{j\in B(t)}w_j}.

空流不占份额，其余流立即分掉全部 $C$ 。这是参考模型，不是把同一条串行链路真的分成几条并行线。[1, §II]

WFQ，又称逐包GPS（PGPS），使用相同到达数据，但真实出口一次只能发送一个完整包，不抢占。出口有包时不故意空闲；上一个包完成后，从已经到达且尚未发送的包中选择虚拟完成标签最小者。并列用固定全局到达序号决定。它不等待该包在参考GPS中真正完成。[1, §III]

给每个包标一个虚拟完成位置

维护参考虚拟时钟 $V$ ，初值零。GPS活跃集合不变时，经过真实时间 $\delta$ ，

V(t+\delta)=V(t)+\frac{C\delta}{\sum_{j\in B(t)}w_j}.

集合为空时冻结 $V$ 。这相当于保留已经走过的虚拟坐标；原论文也可在每个全局忙期重新取零，只要该忙期的全部标签同换坐标，选择次序不变。

对流 $i$ 的第 $k$ 个包，到达时刻为 $a_i^k$ ，长度为 $L_i^k$ 。令 $F_i^0=0$ ，计算

S_i^k=\max\{F_i^{k-1},V(a_i^k)\},\qquad F_i^k=S_i^k+\frac{L_i^k}{w_i}.

$S$ 、 $F$ 是虚拟开始/结束位置，不是秒。前一个包还在GPS中服务时，新包接在它后面；流已经空闲时，新包从当前 $V$ 开始，不能领取空闲期间别人已经消耗的历史服务。[1, §III-A，式(10)–(11)]

同一流的标签严格递增，所以在所有待发包中取最小标签，自动不会越过本流前包。用优先队列按 $(F,\text{序号})$ 选择，是这条规则的一种实现。

哪些事件真正推动参考时钟

维护GPS尚未完成包的标签堆，以及每流参考包数。若当前 $V=v$ 、活跃权重和为 $W$ ，最小待完成标签为 $f$ ，在没有更早到达的情况下，下一个GPS完成时刻是

t_{next}=t+(f-v)W/C.

若新到达先发生，只把 $V$ 推进到到达时刻，再赋标签；若参考完成先发生，就先推进到 $f$ 、移除该包，只有该流参考包数变零才从 $W$ 减掉它的权重。一个真实时间间隔内可能发生多次参考完成，必须逐项结算，不能用旧 $W$ 一次跨过去。

本页同刻先结算GPS完成，再收包；真实发送完成的同刻，先收齐该时刻全部到达，再选下一包。参考同标签完成可逐个移除，中间推进时间为零。真实发送中的包即使已在GPS完成，也仍要发完；真实已发完的包也可能仍留在GPS参考堆中。两套状态不互相删除。

直觉

相同的虚拟距离，对应不同的真实字节

当 $V$ 增加一单位时，一条始终积压的权重二流得到两字节，权重一流得到一字节。因此长度六、权重二的包只需走三单位虚拟距离。更多流加入会让 $V$ 按墙钟走得更慢，却不会改变已经标好的两个包谁的 $F$ 更小。

对两份已经到达的数据，后续到达只会改变共同的时钟推进速度。它们在GPS中的完成次序仍由各自固定的 $F$ 决定。这正是WFQ能在到达时赋标签、不偷看未来输入的原因。附件先计算完整参考轨迹、再重放真实出口以方便比较；每个标签的计算仍只访问此前到达和参考状态。

同一组六包中参考完成和真实整包发送分开，空闲后虚拟钟保持七 — GPS参考钟与WFQ发送次序

至多晚一个最大包，为什么不是一句近似直觉

记同一个包在WFQ和GPS中的完成时刻为 $d_p$ 、 $g_p$ 。在本页合同内，

d_p\le g_p+M/C.

下面展开原论文的忙期证明。[1, Theorem1] 两系统对聚合输入都以速率 $C$ 工作且不故意空闲，所以全局忙期相同。在一个忙期内，把包按WFQ完成次序编号为 $1,\ldots,k$ 。

令这段忙期起点为 $b$ ，在 $k$ 前面找最后一个满足 $g_m>g_k$ 的包 $m$ 。若没有，前 $k$ 个包在GPS中都不晚于 $g_k$ 完成；GPS在这段时间可付出的服务只有 $C(g_k-b)$ ，故 $\sum_{j=1}^kL_j\le C(g_k-b)$ 。WFQ连续发送给出 $d_k=b+\sum_{j=1}^kL_j/C\le g_k$ 。

若存在这样的 $m$ ，令它在WFQ开始的时刻为 $s=d_m-L_m/C$ 。包 $m+1,\ldots,k$ 都有 $g_j\le g_k<g_m$ ，且在 $s$ 尚未到达：如果其中任何一个已经可用，它的标签更小，WFQ就不会选 $m$ 。因此这些包的全部长度只能在 $(s,g_k]$ 内由GPS服务，故

\sum_{j=m+1}^{k}L_j\le C(g_k-s).

WFQ在同一忙期连续发送，于是

d_k=s+\frac{L_m+\sum_{j=m+1}^{k}L_j}{C} \le g_k+L_m/C\le g_k+M/C.

多等待的来源是已经开始、不能被后来小标签包抢占的那个整包。此式只限制“WFQ比GPS晚多少”；它没有把两个完成时刻的绝对差限制在 $M/C$ 。

例子与边界

六个包逐项核对

令 $C=6$ ，三流权重为A二、B一、C一。输入序号按下表从上到下给定；单位是秒与字节。

包	到达	长度	到达时V	标签F	GPS完成	WFQ完成
A1	0	6	0	3	3/2	1
B1	0	6	0	6	8/3	7/3
A2	1	2	2	4	2	4/3
C1	2	3	4	7	17/6	17/6
A3	4	4	7	9	49/10	14/3
B2	21/5	2	38/5	48/5	5	5

开始时只有A、B积压， $W=3$ ，所以 $V$ 每秒增加二。时刻1到达A2，接在A1的标签3后，得到4。A1在参考时刻 $3/2$ 完成，但A2还在，A的权重不能删除。到时刻2，A2也完成，才把 $W$ 从3减到1；C1在同刻加入后变为2。

真实出口先发A1，占用 $[0,1]$ ；时刻1收到了标签4的A2，它比B1的6小，所以先发A2至 $4/3$ ，再发B1至 $7/3$ ，再发C1至 $17/6$ 。可见时刻 $4/3$ 真实A队列已空，GPS里的A2却要到2才完成。拿真实队列计算 $W$ ，会过早给B额外参考服务。

在 $[17/6,4]$ 两系统都空闲， $V$ 保持7。A3不能从旧A标签4继续，而要从7开始得到9。到B2在 $21/5$ 加入时，参考钟已为 $7+3/5=38/5$ ，其标签为 $48/5$ 。此后两流共享至A3在 $49/10$ 参考完成，B2独占剩下的 $1/10$ 秒。真实出口A3、B2则分别在 $14/3$ 、5完成。

一个刚错过长包的短包

另取 $C=1$ 、两流等权。A长十二字节，在0到达并立即开始发送；B长一字节，在 $1/10$ 到达。GPS在B到达后给它半速，所以B在 $21/10$ 完成；WFQ不能中断A，先到12发完A，再到13发完B。B晚了

13-21/10=109/10<12=M/C.

如果B改在0与A同时到达，本页规则会先收齐两个包，B的标签1小于A的12，B便先走。这不是只改一个算术数值：它跨过了“发送是否已经开始”的非抢占边界。

反方向也能差很多。 $n$ 条等权流各在0交一个长度 $M$ 的包，GPS让它们全在 $nM/C$ 完成；WFQ第一个包在 $M/C$ 完成，领先 $(n-1)M/C$ 。所以一侧的界不能改成绝对值界。

推论与应用

从份额得到单流包迟延证书

令 $R_i=Cw_i/\sum_{j\text{全部流}}w_j$ 。只要流 $i$ 在GPS中积压，它得到的速率至少 $R_i$ ，因为活跃权重和不超过全部权重和。与一台独占、恒速 $R_i$ 的FIFO服务器比较，其第 $k$ 包完成时刻递推为

G_i^k=\max\{a_i^k,G_i^{k-1}\}+L_i^k/R_i.

GPS至少这么快，结合刚才的单向界，得 $d_i^k\le G_i^k+M/C$ 。这是保证速率合同，不是每个时刻都只给 $R_i$ ；别人空闲时可以多给。

若本流到达满足严格令牌桶的逐区间包络 $b+\rho u$ ，并且 $\rho\le R_i$ ，将递推展开为

G_i^k=\max_{j\le k}\left(a_i^j+\frac{\sum_{h=j}^kL_i^h}{R_i}\right).

包含两端到达包的区间可从左端稍前开始，取极限得到 $\sum_{h=j}^kL_i^h\le b+\rho(a_i^k-a_i^j)$ 。每个候选减去 $a_i^k$ 后至多 $b/R_i$ ，故

d_i^k-a_i^k\le b/R_i+M/C.

主例A的到达符合 $b=6,\rho=2$ ；全部权重和4，保留率为3，因此得到三秒证书。它不要求另外两流也遵守这个桶，但所有流都必须守住给定最大包长与固定权重合同。

成本与可迁移范围

对 $P$ 个包、 $f$ 条登记流，附件读入并校验权重，按到达/序号排序；每包在GPS堆与真实堆各入队出队一次。预先维护参考包数和活跃权重和，完整重放需 $O(1+f+P\log(P+1))$ 次基本比较与算术，保留所有包、完成表与事件证据需 $O(1+f+P)$ 空间。不是每次更新都扫描全部流，也不对已走过的每个时间刻度循环。流身份散列表按通常期望常数访问计，精确有理算术的位成本、身份字节处理与载荷复制另计。

DRR用量子与余量证明对齐轮边界的份额；本页多维护一个流体参考系统，换取逐包完成的GPS比较。把 $V$ 换成真实出队标签、改变权重或让出口暂停，都是新调度规则或新服务模型，不能直接继承本页证明。服务曲线进一步讨论输入包络与多节点服务合同；将完整包完成量接到它之前，必须说明分组化和逐跳等待。

参考资料

[1] Abhay K. Parekh、Robert G. Gallager，A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case，IEEE/ACM Transactions on Networking 1(3)，1993，pp.344–357；§II的GPS份额，§III、Lemma1及Theorem1，pp.346–347；§III-A式(10)–(11)，p.348。本文用任意速率C并在空闲期保留全局虚拟坐标，六包轨迹与边界迁移自行构造。

[2] Jean-Yves Le Boudec、Patrick Thiran，Network Calculus: A Theory of Deterministic Queuing Systems for the Internet，作者在线2022版，§2.1.2，Proposition2.1.1，pp.68–69；§2.1.3，Definition2.1.1、Theorems2.1.1与2.1.4，pp.70–71，区分GPS比较、保证速率递推与包迟延。

形式陈述 ​

同一批输入，两个服务系统 ​

给每个包标一个虚拟完成位置 ​

哪些事件真正推动参考时钟 ​

相同的虚拟距离，对应不同的真实字节 ​

至多晚一个最大包，为什么不是一句近似直觉 ​

六个包逐项核对 ​

一个刚错过长包的短包 ​

从份额得到单流包迟延证书 ​

成本与可迁移范围 ​

反向链接