沿公平服务学习路线,先从每流FIFO构造WFQ,再用已经证明的输入与服务合同计算网络演算界。本终点有两组分别初始化的输入:第一组是真实不可抢占分组,第二组是可细分的流体链。最后用同一个整包反例判断两种接口何时不能直接相接。
下载标准库有理数核验器。运行 python foundation-fair-service-check.py,完整JSON写到标准输出;python -O同样执行全部显式检查。数组验证只覆盖给定整数时刻,随机自查只覆盖给定有限实例,不宣称认证任意实际路由器。
任务一:参考时钟与真实发送分别交付
固定出口速率六字节/秒、权重A二/B一/C一,最大包长六字节。依输入序号给六包:
| 包 | 流 | 到达秒 | 长度字节 |
|---|---|---|---|
| A1 | A | 0 | 6 |
| B1 | B | 0 | 6 |
| A2 | A | 1 | 2 |
| C1 | C | 2 | 3 |
| A3 | A | 4 | 4 |
| B2 | B | 21/5 | 2 |
提交每次到达所见V、每包标签、所有GPS完成事件,以及真实发送区间。标签依输入顺序为3、6、4、7、9、48/5;GPS完成分别为3/2、8/3、2、17/6、49/10、5。
真实顺序为A1、A2、B1、C1,空闲,再A3、B2。完整区间是0到1、1到4/3、4/3到7/3、7/3到17/6、4到14/3、14/3到5。每次选择只能看已经到达的包;同刻到达收齐后再选,实际在途包不被抢占。
至少解释两个容易混淆的状态:
- 在4/3,A的真实队列已经空了,但GPS中的A2尚未完成;A的参考权重仍要保留到2
- 在17/6到4,GPS空闲,V冻结在7;A3用max(旧A标签4,V7)作为起点,标签是9
在第一件事上使用真实队列,在第二件事上把新包放回历史标签,都会改变调度。核验器的 virtual_events 与 physical_runs 是两份不同的账,不应按同一个“完成”事件删掉两边记录。
任务二:把完成差变成有条件的期限证书
对所有六包核对 wfq_finish ≤ gps_finish + 1,因为M/C=6/6=1。这个界只控制晚发,不能改成绝对值:若n条等权流各交一个等长包,WFQ最先发完的包可以比GPS早(n−1)个包发送时间。
再单独看A。全部登记权重和4,它在GPS中持续积压时至少得到速率3。A的三个到达包6@0、2@1、4@4符合容量6、补充率2的严格桶。独占速率3的完成递推给G=(2,8/3,16/3),GPS不得晚于它;WFQ还容许一个最大包时间,得到每个A包从到达起至多 6/3+6/6=3 秒。
改变输入:速率一、两流等权,A长十二在0到达,B长一在1/10到达。B的GPS完成为21/10,WFQ完成为13,单向差109/10小于最大包时间十二。如果把B改在0同时到达,先收齐再选择会让B先发;请实际重跑并说明跨过了哪个不可抢占边界,而不只复写不等式。
任务三:两条最小服务合同如何组合
另起一条初始为空的流体输入:时刻0突发十二字节,此后每秒二字节。累计函数A(0)=0,而t>0时A(t)=12+2t,初始突发从右极限读取。两个节点的速率—时延参数分别为(6,1)、(4,2),第一输出全部进入第二输入,无额外聚合。
交付端到端曲线参数R=4、T=3,证明总积压≤18、FIFO迟延≤6。使用节点恰好输出卷积下包络的实例,重算下表:
| 时刻 | 累计输入A | 中间输出D1 | 最终输出D2 | 第一队列 | 第二队列 | 总积压 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 14 | 0 | 0 | 14 | 0 | 14 |
| 2 | 16 | 6 | 0 | 10 | 6 | 16 |
| 3 | 18 | 12 | 0 | 6 | 12 | 18 |
| 4 | 20 | 18 | 4 | 2 | 14 | 16 |
| 6 | 24 | 22 | 12 | 2 | 10 | 12 |
| 9 | 30 | 28 | 24 | 2 | 4 | 6 |
| 10 | 32 | 30 | 26 | 2 | 4 | 6 |
总积压在3达到18;初始十二字节的最后一份在6离开,FIFO迟延达到6。第一队列峰值14在1出现,第二峰值14在4出现;这两个内部峰值不能当作同刻28。
第一节点单独的迟延上界为3。中间输出的安全包络是突发14、速率2,第二节点据此得到11/2;直接相加是17/2,比串联的6更松。请从 D1≥A⊗β1、D2≥D1⊗β2 展开双重下确界,解释为何串联可把突发只支付一次;不能把中间输入仍写成未经证明的原突发12。
任务四:交一个失败时刻和一个未知出口
取上表对应函数在整数0到10的累计数组作为独立离散输入,提供同一整数网格上的到达与服务曲线。检查器穷尽所有整数窗口,结果为 PASS_FINITE_INTEGER_DOMAIN。这句话只覆盖所给离散时间域,没有检查任意两个实数时刻。
把最终输出在时刻4从4改为3,其他整数项保持不变,输出仍非降且不超过输入,但服务合同失败。应返回时刻4、所需至少4、实际3;把卷积的全部五个分割候选计算出来,能看见最小值的具体见证。
如果只提供到时刻4的数据,并查询时刻3累计到达的十八字节何时完成,答案必须是 INCOMPLETE。不能因为当前队列有界,就假造一个附件中未观察到的完成时刻。解析的全时域服务保证仍能提供理论上界,两种证据回答的问题不同。
三个改变模型的迁移
第一,把允许整条链总共保存的未交付预算降为17。上表时刻3的18已经给出违反预算的具体轨迹;若17仅是某一内部队列的预算,不能用总量18直接断言那个队列溢出。内部峰值需按其所有权单独核。
第二,把持续输入速率改为5而瓶颈仍为4。bounds应返回 NO_FINITE_UNIFORM_BOUND。选择持续5和最低承诺服务,超过启动期后积压线性增加;输入稀疏时仍可能没有长队。改变节点次序则仍有同一流体端到端曲线,但内部队列曲线要重新计算。
第三,改成一个四字节包经过两条速率四的链路,第二跳必须收齐整包才开始。第一跳在1完成,第二跳在2完成。零时延流体串联只会给一秒,因此不能把两跳完整包交付接口都标成β4,0;它在第一跳时刻1/2已经被实际零整包交付量否定。请指出需要补上的分组服务假设,而不是把2秒结果当作串联定理失效。
验收口径
调度重放核心用两个堆与每流参考包数,P包、f流的基本操作为O(1+f+P log(P+1)),轨迹空间O(1+f+P)。慢速剩余字节oracle用于自查,不包含在这条核心界里。有理数位运算、身份和载荷字节成本另计。
连续主例按分段折点取真实最小值,仿射参数界只用常数次算术;有限数组检查则穷尽O(1+N²)个窗口/分割点。最后提交应同时保留六包执行、18/6的全时域证明、实际有限证据和三个边界迁移,不能让一个“PASS”替代输入合同。