Skip to content

算法Algorithm

多路复用流的独立重组

Multiplexed stream reassembly · Per-stream delivery frontier · Packet number versus stream offset

用独立包身份和每流字节偏移重组同连接的两条流,证明前缀与不重复交付,并用相同载荷复算TCP上的跨流等待。

形式陈述 ​

一个包的身份与一段内容的身份 ​

R9把一个固定流的缺口补成连续前缀。本页改变接口:同一连接中有多个分别排序的字节序列,一个包可以带多个流的片段。包到达次序不能充当任何一条流的字节次序。

固定一个已经建立、已经认证的连接实例 c,只研究客户端到服务端方向 d=c2s,以及一个应用数据包序号空间 e。没有握手、密钥更新、路径迁移、包号截断恢复、拥塞控制或崩溃恢复。进入本接口的包已经完成认证和外层格式检查;这不是用流编号代替认证。发送者不复用包号,属于同一流同一位置的内容不可改变;网络可以丢失、乱序和复制完整包。发送者可把未获确认的相同流内容重新封装进新包号的包,也可改变片段切分。

包表示为 P=(c,d,e,pn,frames),其中每个数据帧为 (sid,o,b):流号 sid、非负偏移 o 和有限字节串 b。其末端 t=o+len(b),区间为 [o,t)。包身份是 (c,d,e,pn),内容位置是 (c,sid,d,o)。两种键不能互换。一个包含两个流片段的包也只有一个包身份;同一内容可先后出现在多个包中。

为让存储合同可执行,预先给定有限流集合 S 和每流数组界 B_i;只接受 0≤o≤t≤B_i。B_i 是课堂实现容量,不是流最终长度,也不是对端收到的流控许可。本页暂令全部样例数据已获许可;双层信用接口会补上逐事件的许可检查。

接收接口与每流前沿 ​

连接状态有已处理包号集合 Seen;每个流 i 分别保存字节数组 A_i、已填位图 V_i、连续交付前沿 r_i 和追加输出 O_i。初态 Seen 为空、全部位未填、r_i=0、O_i 为空。receive(P) 返回本次每流新增交付及包接收记录:

  1. 检查固定连接、方向、包号空间、已准入流、范围及帧内结构。已认证的同包号副本若已在 Seen 中,跳过其帧处理;它不造成新字节交付。真实 ACK 调度是另外的职责,本模型不实现它
  2. 对未见包,检查全部帧的重叠位置:已存值必须相同;同一新包内较后帧也须与较前帧的暂存写入比较。若有冲突,本模型报告 ContentConflict 并使连接持久进入 FAILED,之后的接收均拒绝。不把“认证成功”理解成诚实对端不会违反协议
  3. 把各帧字节填入各自流的相应位置。对每条受影响流,只从它自己的 r_i 起越过连续已填格,将新前缀追加到 O_i;遇到该流的第一个缺口便停止
  4. 提交 Seen 中的新包号。本检查器在副本状态上检查整个包再提交,因此一包后部的错误不会留下半次提交;这是便于测试的原子事件约定,不宣称 QUIC 要求整包应用交付回滚

给每流固定原串 X_i,在诚实内容输入下要求:V_i 中每个已填位置都等于 X_i 同位置;O_i=X_i[0:r_i);r_i 恰为从0起连续覆盖的最大末端。不同流可独立推进。接口没有定义跨流总交付顺序,也没有把一次 receive 返回等同业务消息边界。

直觉

一辆车同时运几本书的散页,车牌回答“这趟车来过没有”,书号与页码回答“这张纸放到哪里”。同一缺页换车运来,应补进原书;同一页坐两辆车到达,也只属于原书一次。一本书缺第一页,不妨碍另一本已经到齐的书交给读者。

这不是“任何迟到都不再造成等待”。每本书内部仍按页交付;运输车辆、道路、装卸工和总仓库仍由多本书共享。独立前沿解决的是一个特定等待关系。

例子与边界

两条流、一个连接、四次有效到达 ​

设流0的原串为 abcd,流4为 XY,均只考察 c2s 半部。QUIC 的0与4实际是客户端发起的双向流的两个合法 ID;这里没有声称它们是单向流类型。若使用客户端发起的单向流,ID 才应取2与6等。本例固定已有两条流,不实现隐式建流与 MAX_STREAMS。

事件 帧内容 到达后的覆盖 (r_0,r_4) 本次新增交付
包10发送后丢失 s0:[0,2)=ab 两流均空 (0,0) 无
包11到达 s4:[0,2)=XY s4:[0,2) (0,2) s4:XY
包12到达 s0:[2,4)=cd s0:[2,4),s4:[0,2) (0,2) 无
包13到达 s0:[0,2)=ab s0:[0,4),s4:[0,2) (4,2) s0:abcd
包14到达 s0:[0,2)=ab 不变 (4,2) 无

包13修复包10遗失的信息,但它不是“包10再次出现”。包14又有新包身份,不能被 Seen 当成旧包丢掉;真正防止第二份 ab 交付的是流偏移和 r_0。若网络再复制包11,才由包级 Seen 直接识别。若包10后来也迟到,包号10虽小仍可处理,覆盖和输出不变;不能仅因小于目前最大包号就判为重复。

包身份与每流独立前沿

同一载荷为何在HTTP/2对照中一起等待 ​

TCP的一个方向只有一条字节交付序列。设 HTTP/2 连接已建立,流1、3的合法 HEADERS 已处理。将本例逻辑流0、4分别映射到 HTTP/2 流1、3:HTTP/2 的流0保留给连接控制,不能直接沿用 QUIC 流0作为 DATA 流。

依次编码三个无填充 DATA 帧:(s1,ab)、(s3,XY)、(s1,cd)。每帧有9字节头及2字节数据,所以在此后 TCP 子序列中分别占 [0,11)、[11,22)、[22,33)。让前段丢失,第二段先到,第三段再到,最后补回第一段。TCP 连续前沿依次为0、0、33;HTTP/2解析器在前两步得不到后方帧字节,因此此时连 s3 的 XY 也不能解析交付。第三步才依次解析三个帧,最终两条逻辑流仍为 abcd 与 XY。

这个对照只使用 HTTP/2 DATA 帧结构,前置状态明确假定已成立;它不是一个完整 HTTP/2 会话或任意帧解析器。相同载荷的等待差别来自传输层是否各流分别重组,而非数字版本自身有某种魔力。HTTP/3 把普通请求映射到 QUIC 流,但字段解压可能还等待 QPACK 更新;传输可交付不等于整个请求已可处理。

仍会一起变慢的情况 ​

一个包同时携带 s0 的 ab 和 s4 的 X,丢掉该包就让两条流同时缺字节。只要后来 s4 的 Y 独立到达,它仍要等自己的 X;收到替补 X 后,s4 可交付 XY,而 s0 若仍缺 ab 便继续停在0。这与“s0的缺口直接卡住s4”不同。

多流仍共享连接拥塞控制、发送调度、CPU及连接级信用。慢消费者占住连接许可,其他流可能也无权发新数据。跨流业务依赖和 QPACK 依赖又可增加等待。因此本接口不承诺完全没有队头阻塞,也不承诺带宽、公平性或时延隔离。

推论与应用

三项安全性质如何逐步保持 ​

初态各流输出都是空前缀。丢包不改变状态。对新包,一个帧只能写入键中指定的流和偏移,且同位置检查相同值,所以不会污染另一条流。推进循环只越过本流连续格,输出仍是自身 X_i 的前缀。r_i 只增不减,已交付位置严格小于新输出的起点,故同偏移重传没有第二份交付。包内多帧只是上述填格操作的有限组合;完整验证后统一提交保持同一性质。重复包无新动作,也保持不变量。

前缀安全不保证结束。对一条没有被取消的有限流,若其每个尚缺位置最终都到达且接收处理持续进行,最终可以交付全串;这是额外的交付条件。本模型没有丢包检测与重传调度,不能把有限轨迹检查当作完整可靠性或无限公平活性证明。

成本与身份边界 ​

设已准入流数 K,数组容量总和 B=ΣB_i,累计处理载荷字节数 D,累计帧数 F,曾处理的不同包数 P。数组/位图与留存输出共 O(B+K+P) 空间,初始化与填格、推进共 O(B+D+F+P) 次基础操作,假定字典/集合查找为期望常数且偏移为固定字长。Seen 全集合随包数增长;这是有限实验的可审计选择,不是可无限运行的内存界。检查器为了原子失败复制状态,并逐次扫描不变量和生成快照,另外产生每包 O(B+K+P) 的复制/扫描成本;为输出已见包号而排序还需 O(P log(P+1))。不能把核心填格界直接贴到整份 Python 程序上。

生产实现可按流保存尚未交付的区间,把已消费字节释放,并用有界包号接收历史。若每流有 G_i 个离散 gap,区间树要另计 O(ΣG_i) 元数据,插入与合并另计查找成本;只写“载荷还有几字节”会漏掉大量小碎片的开销。拒绝过老包必须与恢复策略一致,不能直接套一个有限重放窗再声称任意迟到包都能补洞。

连接实例、CID、stream ID、packet number、业务 request ID 各有职责。一个连接可有多个用于选路/分派的 CID;它们不是已认证身份,也不能用 CID 改变来重置本页内容键。包号辨认一次传输,stream ID 与方向辨认一条内容序列,请求 ID 辨认上层操作。重建连接、重开流或换包号都不能提供业务结果证据。认证与重放仍由记录保护接口等独立机制负责;本页没有更改旧安全会话合同。

手算和完整有限测试见多流终点任务。下一页单独处理流控与结束:最高末端、连续前沿、最终长度与当前缓存字节数,四者不能混用。

参考资料
  • RFC 9000,§§2.1–2.2:流身份、偏移与重复内容;§§5.1–5.2:CID与连接;§12.3:包号空间;§13.3:在新包内重发信息。正文的有限数组、原子检查、abcd/XY与证明为独立教学构造,不是QUIC实现。
  • RFC 9113,§§1–2、4.1、5:HTTP/2在TCP上的多路复用、9字节帧头及传输层队头等待。本文仅编码已有流的无填充DATA帧。
  • RFC 9114,§2、§§4.1、4.2.1:HTTP/3请求映射与字段压缩依赖。本页未实现HTTP/3或QPACK。
关系图谱5 个相邻概念 · 1 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组