Skip to content

这项任务沿排队观察到拥塞反馈路线,交三份互相衔接的事件证书:谁被AQM选中、真实队列怎样变化、发送者收到反馈后何时还有资格发新包。不能只报一个最终平均值。

标准库核验器只向stdout打印JSON。普通与优化模式都实际执行检查:

sh
python foundation-queue-feedback-check.py > result.json
python -O foundation-queue-feedback-check.py > optimized.json

程序是整数/有理数的教学状态机,没有访问网络或修改任何真实队列。RED的U由输入带提供;概率证明另算准确质量,不靠随机样本频率。CoDel取整规则、ECN受限输入与逐事件轨迹均在正式页声明。

一、先给七个包一份完整账本 ​

使用RED的C5、w1/2、低阈值2、高阈值4、pmax1/2。包1..7在0按序到达,没有出队。第4、第5、第6包用U=9/10、3/10、9/10;其他包分别在低或高阈值,不靠随机结果决定。

从空队列复算每次“先读q、更新avg、算pa、选中、检查容量、处理包”。正确avg依次为0、1/2、5/4、17/8、49/16、113/32、273/64。第5包pb17/64,此前k1,故pa17/47;3/10较小,触发提前丢弃。

输出应留队列1、2、3、4、6,丢5和7。两次丢包的完整原因不同:5到达时还有一格,因概率选中早丢;7到达时既到高阈值又硬满,执行结果记TAIL_DROP,选择器仍记selected=true。只看实际丢包分类不能恢复全部AQM选择历史。

请另交冻结pb=1/4时的四条条件概率1/4、1/3、1/2、1,以及下次标记位置的四份概率质量各1/4。均值5/2,不是独立固定1/4每包试验的几何均值4。

迁移:把早丢换成CE,后面要重算 ​

重置整个RED状态,再令所有包具有ECT能力,被AQM选中且有空间时标CE保留。第5包这次进队,队列1..5;第6包观察q5,avg变129/32,不是原drop轨迹的113/32。它已高阈值且物理满,仍被尾丢;第7包avg289/64,也尾丢。

这份结果说明标记不会释放缓存。不能将drop轨迹里的“丢5”机械替换成“标5”,同时保留后续平均、概率和所有发送结果。

二、以旧计划时刻比较,再推进CoDel时钟 ​

CoDel取C10000B、M1000B、TARGET5、INTERVAL100,一tick=1ms。A..J各1000B在0入队;额外一包应因硬满被丢,控制count仍0。

在5、104、105、405、406提供服务机会,分别记录每次helper取候选后的剩余字节、first_above、是否宜丢。5取A时设above105,104取B尚未到期;105取C时丢C,再取D并交付,进入count1、next205、lastcount1。

405时逐项填表,不能先把now写进下一计划再比较:

比较用旧drop_next 丢当前候选 增加后的count 下一候选/剩余字节 后续动作
205 E 2 F / 4000 推进205+71=276
276 F 3 G / 3000 推进276+58=334
334 G 4 H / 2000 推进334+50=384
384 H 5 I / 1000 保护余量,退出;next仍384

最终返回I,406再返回J。完整动作序列为交付A/B/D/I/J,AQM丢C/E/F/G/H;每个原包出现一次,字节账和原FIFO次序应一致。B等待104超过TARGET,说明5不是逐包截止期。

迁移:近期复用、长期重置和等号 ​

保留406后的同一状态,各走独立分支。在500重新入十包,505设above605,605重入时delta5−1=4,而且605−384<1600,故count4、next655。到2500才重入的另一分支,2605−384≥1600,故count1、next2705。

把第二个分支的首次丢弃时刻改成1984,恰有1984−384=16INTERVAL,应该归1;改成1983才满足严格小于,复用4。新队列须相应提前INTERVAL+TARGET到达,使时间顺序合法。另将某个候选的等待改为恰TARGET,应进入持续观察;剩余字节恰M则必须触发保护。两种等号的方向不同。

三、首份ACK丢失后,ECE要继续回显 ​

进入经典ECN的已协商、数据按序无丢失模型。初始八个1000B包占[0,8000),cwnd8000,接收信用充足。包1被CE,ACK1000/ECE1故意丢失;包2没CE,ACK2000仍应ECE1。

发送者收到ACK2000后,cwnd8000→4000,guard8000,u2000,在途6000,不能发新包。ACK3000和4000后也没有一个1000B包的额度;到ACK5000,在途3000,才可发包9,区间[8000,9000),第一次携CWR。发送以后pending_cwr清除,不许给每个新包都复制同一份CWR。

旧窗口后面的ECE-ACK,包括ACK8000,都不再次减窗。记录guard前沿和每次n−u,才能区分“回显仍在”与“又接受一份新的拥塞响应”。

迁移:同一个包的CWR和CE谁最后生效 ​

让包9携CWR后又被标CE。接收者先清旧echo,再按CE置1,ACK9000/ECE1跨过旧guard8000,发送者4000→2000、guard9000,再等待首次新包携CWR。

包10没有CE,携CWR后应收到ACK10000/ECE0。此后重放旧ACK8000/ECE1,u仍10000,减窗次数仍2。把处理次序反成“先CE后CWR”的错误接收器,会在包9处回ECE0;这一错误会隐藏新的拥塞。

本模块在每次接受减窗时要求cwnd至少4M,低窗口触发输入返回移交完整TCP规则。不要为了继续任意多轮测试,偷偷在一MSS处允许无限发送而省掉RFC的计时器分支。

四、交付三类不同结论 ​

完整记录应包含:

  1. RED七次q/avg/pa/k与实际入队结果,改ECN后的重新计算,以及恒定pb下的准确概率质量
  2. CoDel每次候选、旧截止、count、剩余字节、退出与短长两种重入,外加边界等号证据
  3. ECN丢ACK、重复ECE、首次新包CWR、同包新CE及迟到旧ACK的全轨迹,附每次新增发送许可
  4. 容量、FIFO单次移除、echo锁存和guard边界的不变量;控制成本与完整审核日志成本分开

它们证明的是明示状态合同。若还要报告端到端吞吐、所有包延迟或流间公平,就必须另给到达、服务、RTT、调度及合作发送者模型,并分析完整闭环。把三个局部算法各跑一次,并不会自动获得这份全网络结论。