Learning in situ: a randomized experiment in video streaming¶

Francis Yan 老师的代表性巨著, 虽然跟直接 crowd-src 关系不大, 但里面的实验设计和分析方法对 crowd-src 有启发意义. 同时, 笔者也很想主动学习一下这篇神作!

alt text

平台建设: Puffer 流媒体平台

背景: 学术界提出了许多基于机器学习或控制理论的 ABR 算法 (如 Pensieve, MPC 等), 并在仿真器或模拟器中表现优异
问题: 由于互联网环境的复杂性 (长尾效应, 噪声, 多变的路径), 在仿真环境中训练出来的算法往往难以在真实网络中复现其性能, 甚至难以超越简单的基于缓冲区的算法 (BBA)
平台: 为此, 作者构建了一个向公众开放的电视直播流媒体平台 Puffer. 该平台在 Stanford 运行, 通过随机对照试验 (Randomized Controlled Trial, RCT) 的方式, 在真实用户和真实网络环境中评估不同的 ABR 算法

核心贡献: Fugu 算法

提出了一种名为 Fugu 的新算法, 旨在通过"原位学习" (Learning in situ) 来解决泛化难题

细节先不管, 下文展开

核心观点: Learning in situ

in situ 在现场 / 原位

要想在狂野的互联网上获得鲁棒的性能, 必须在真实的部署环境中进行学习 (Learning in situ), 并结合合适的模型结构 (经典控制 + 监督学习预测), 而不是单纯依赖离线仿真或复杂的强化学习策略

Introduction 核心内容

(1) 研究背景与现存问题

ABR 的重要性: 视频流占据了互联网流量的绝大部分, 自适应码率 (ABR) 算法通过平衡视频质量 (压缩率) 和卡顿风险来优化用户体验 (QoE).
机器学习 (ML) 的局限性:
- 尽管 ML 能够处理多种信号并发现模式, 但其性能高度依赖于训练环境.
- 由于互联网的复杂性和长尾效应, 在仿真或模拟环境中训练的算法往往难以泛化到真实网络, 导致实际部署效果不佳 (例如 CS2P, Pensieve 等算法在真实网络中的表现往往不如仿真中理想).

long-tailed effects

长尾效应 (Long-tailed effects) 是指互联网性能指标 (如吞吐量, 延迟, 丢包率等) 的统计分布呈现"长尾"特征.

核心特点:

大多数情况正常: 绝大多数用户/会话的网络条件都在一个"正常"范围内 (分布的主体部分)
少数极端情况: 但存在一小部分用户会遇到极端差的网络条件 (分布的"尾部"), 这些极端情况虽然少见, 但影响巨大
尾部拖后腿: 这些极端情况会严重拖累算法的整体表现, 导致平均性能下降

在视频流场景中的表现:

90% 的用户可能网络很好 (吞吐量稳定在 5-10 Mbps)
但 5% 的用户可能遇到突发拥塞, 吞吐量暴跌到 100 Kbps
还有 5% 的用户可能遇到间歇性断线, 路由切换等复杂情况

为什么仿真难以捕捉:

仿真器通常基于"平均"网络轨迹 (traces), 这些轨迹往往只覆盖了分布的主体部分, 而忽略了尾部的极端情况.
长尾部分的极端情况 (rare events) 在有限的训练数据中很难被充分采样
当算法部署到真实环境时, 这些未见过的极端情况会导致性能大幅下降

(2) 实验平台: Puffer

研究方法: 为了探究如何构建在真实互联网上鲁棒的 ABR 算法, 作者建立了 Puffer —— 一个面向公众开放的视频直播网站.
规模与机制:
- Puffer 作为一个持续进行的随机对照试验 (RCT), 已向 63,508 名用户传输了 38.6 年的视频数据.
- 系统随机将用户会话分配给不同的 ABR 算法进行盲测.

(3) 关键发现: 模拟与现实的差距

复杂算法未必更好:
- 在真实环境中, 基于控制理论或强化学习 (RL) 的复杂算法 (如 MPC, Pensieve) 并没有击败简单的基于缓冲区的控制算法 (BBA).
原因分析:
- 这些复杂算法是基于吞吐量轨迹 (Traces) 开发和评估的, 而这些轨迹在回放时无法捕捉到互联网真实的长尾效应和动态变化.
- 即使使用 Puffer 的真实数据重新训练, 如果仅仅是基于轨迹回放, 效果依然没有改善.
统计不确定性: 真实网络的高变异性导致统计误差很大. 即使有 20% 的性能提升, 在统计上也可能无法与噪声区分开来 (95% 置信度下不可检测).

(4) 解决方案: Fugu 算法

核心设计: 作者提出了 Fugu 算法, 它结合了经典控制策略 (MPC) 和一个通过原位学习 (learning in situ) 训练的 ML 预测器.
原位学习: 指直接利用部署环境 (Puffer) 中记录的真实数据进行监督学习训练, 而非依赖仿真器.
Fugu 的预测器具有三个关键特征:
- 1) 显式根据切片大小预测传输时间 (而非仅预测吞吐量)
- 2) 输出传输时间的概率分布 (而非点估计)
- 3) 利用底层的拥塞控制统计信息 (如 TCP stats) 作为输入.

(5) 实验结果与贡献

性能提升: 在 2019 年的大规模实验中, Fugu 在卡顿率, 视频质量及其稳定性上均优于现有技术.
用户参与度: 被分配到 Fugu 的用户, 其平均观看时长比其他算法的用户长 5-9%, 具有实际的应用价值.
开放研究: 作者将 Puffer 作为一个开放研究平台, 并公开发布数据集, 邀请社区在真实流量上测试新算法.

Background and related work 核心内容

对笔者而言, 这一部分重点是补充以下几个背景:

Video Streaming 的基本原理和 QoE 指标
ABR 算法是干啥的
MPC 策略是什么

还有一些相关工作, 比如基于 RL 的 Pensieve 算法, 以及 CS2P, Oboe 等基于 MPC 的改进工作

(1) 自适应视频流的基本问题

编码机制: 为了应对客户端网络性能的不可预测性, 服务器将视频编码为多个不同质量 (比特率/分辨率) 的版本, 并将其切分为独立的"切片" (Chunks, 通常 2-6 秒).
ABR 的作用:
- 自适应码率 (ABR) 算法决定客户端在每个切片边界下载哪个版本的视频
- 目的是: 在播放缓冲区耗尽前下载切片以避免卡顿 (Rebuffering)
优化目标: ABR 的目标是优化体验质量 (QoE), 即: 在最小化启动时间和卡顿的同时, 最大化视频质量并减少质量的波动.

(2) ABR 算法的分类

研究界提出了多种 ABR 方案, 主要分为三类:

基于速率 (Rate-based): 侧重于将视频比特率与网络吞吐量相匹配.
基于缓冲区 (Buffer-based): 侧重于控制播放缓冲区的时长.
控制理论/模型预测控制 (MPC. Model Prediction Control):
- 利用吞吐量预测和预测模型, 在滚动的时间窗口内规划切片序列, 以最大化预期的 QoE.

(3) MPC 及其相关工作

MPC 原理: 包含"吞吐量预测器"和"控制策略"两个模块, 通过预测未来缓冲区和 QoE 的变化来做出决策.
改进版本: CS2P 和 Oboe 等工作主要是在 MPC 框架下改进了吞吐量预测器 (例如使用隐马尔可夫模型或聚类), 利用历史数据来提升预测准确性.

alt text

(4) Fugu 算法的定位与独特性

Fugu 属于 MPC 类算法, 但其预测模块 (传输时间预测器, TTP) 具有以下显著特征:

显式考虑切片大小: Fugu 不直接预测吞吐量, 而是根据切片大小预测传输时间, 因为吞吐量会随文件大小非线性变化.
概率性预测: 输出传输时间的概率分布 (而非单一数值), 实现了随机模型预测控制 (Stochastic MPC).
利用底层信号: 使用神经网络处理多种输入信号, 包括底层的 TCP 拥塞控制统计数据 (如 RTT, CWND 等).

(5) 与 Pensieve (RL) 的对比

决策方式不同:
- Pensieve 也是基于神经网络, 但它直接输出决策 (选哪个切片)
- 而 Fugu 的神经网络仅用于预测环境状态 (传输时间), 决策仍由 MPC 控制
训练方式不同:
- Fugu 的预测器可以通过监督学习 (Supervised Learning) 在历史数据上训练
- 而 Pensieve 作为强化学习 (RL) 算法, 需要一个能反馈决策后果的训练环境 (通常是模拟器). 而模拟器的系统复杂性太高, 现实很难部署

Puffer - an ongoing live study of ABR 核心内容

该部分详细介绍了 Puffer 平台的系统架构, 实验设计, 算法部署, 统计方法:

(1) Puffer 实验平台概览

平台性质: Puffer 是一个免费向公众开放的电视直播网站, 实则是一个持续进行的随机对照试验 (RCT).
实验机制: 用户的会话被随机分配给不同的 ABR 或拥塞控制算法, 且用户对分配结果不知情 (盲测).
目标: 通过流式传输六个免费的无线电视频道, 收集足够的真实用户和网络路径数据, 以得出关于 ABR 算法性能的稳健结论.

alt text

PS: Nano banana 直接生成的图, 太强了. 笔者看了一下, 应该没什么问题.

(2) 后端处理: 编解码与 SSIM 计算

视频源处理: 系统接收 ATSC 信号并解码, 处理丢包以保持同步, 并将视频去隔行处理为 1080p60 或 720p60 的"标准"源.
切片与编码: 视频切片长度为 2.002 秒. 系统使用 libx264 (veryfast 模式) 将每个切片编码为 10 个不同的 H.264 版本, 质量范围从 CRF 26 (约 200 kbps) 到 CRF 20 (约 5,500 kbps).
质量度量: 系统计算每个编码切片相对于源视频的 SSIM (结构相似性) 指标. 该指标被用于 BBA, MPC, RobustMPC 和 Fugu 的目标函数中.
比特率与质量的关系: 实验发现最大化比特率并不一定能带来图像质量的同等提升, 且不同切片的比特率与质量关系各异.

(3) ABR 算法的部署架构

服务器端逻辑: 为了便于测试任意算法, Puffer 采用了"哑"客户端 (仅使用 HTML5 <video> 标签), 将 ABR 逻辑放置在服务器端.
通信机制: 浏览器通过 WebSocket 与服务器守护进程连接, 服务器端负责 TCP 拥塞控制 (主要使用 BBR) 和 ABR 决策.
算法实现:
- 经典算法 (BBA, MPC, RobustMPC, Fugu): 在后端 C++ 守护进程中实现, 均使用 SSIM 作为优化目标.
- Pensieve:
  - 直接使用原作者发布的 Python/TensorFlow 代码, 通过子进程运行.
  - 作者对 Pensieve 进行了针对性调整 (如调整训练时长, 熵参数), 但无法修改其优化目标为 SSIM (Pensieve 仍优化平均比特率).

(4) 实验规模与数据统计

数据规模: 在 2019 年 1 月至 2020 年 2 月期间, Puffer 向 63,508 名用户传输了 38.6 年的视频数据.
遥测数据: 记录了每个视频切片的大小, SSIM, 传输时间, 客户端缓冲区状态以及 TCP 统计信息.
长尾效应与统计噪声:
- 数据表现出明显的长尾特征, 实际卡顿非常罕见 (仅 4% 的流出现卡顿).
- 这种偏斜分布导致统计不确定性很大. 即使有 2.5 年的数据, 卡顿率的 95% 置信区间宽度仍达到均值的 \(\pm13\%\) 到 \(\pm21\%\).
- 这意味着, 在短期实验或数据量不足的情况下, 很难在统计上区分出算法之间真实的性能差异 (例如 20% 的卡顿率提升可能无法被检测到).

Fugu - design and implementation 核心内容

这一部分 ML 方面的术语太多了, 笔者并非关心, 因此简要用 ai 过一遍

Fugu 是一个旨在通过"原位学习" (in situ) 在真实部署环境中进行训练的码率选择控制算法.

它结合了经典的模型预测控制 (MPC) 和一个使用监督学习训练的非线性预测器:

(1) 系统架构与设计概览

alt text

混合架构:
- Fugu 由 一个经典的 MPC 控制器 和 一个基于深度神经网络的"传输时间预测器" (Transmission Time Predictor, TTP) 组成.
部署位置: Fugu 运行在服务器端, 这使得模型更新和跨客户端的性能数据聚合变得容易.
工作流程: 客户端向服务器发送遥测数据 (如缓冲区水平), 服务器端的控制器根据 TTP 的预测来做出码率选择决策.

(2) 优化目标函数

QoE 度量: Fugu 旨在最大化未来 \(H\) 个切片的预期 QoE 总和. QoE 被定义为视频质量, 质量变化和卡顿时间的线性组合.
使用 SSIM: 与许多使用比特率作为质量代理的算法不同, Fugu 直接优化 SSIM (结构相似性), 这是一种与人类感知更相关的指标.
公式: \(QoE(K_{i}^{s},K_{i-1})=Q(K_{i}^{s})-\lambda|Q(K_{i}^{s})-Q(K_{i-1})| - \mu \max \{T(K_{i}^{s})-B_{i},0\}\), 其中 \(\lambda\) 和 \(\mu\) 是权重参数.

(3) 核心创新: 传输时间预测器 (TTP)

预测目标: TTP 不预测"吞吐量", 而是显式地预测特定大小切片的传输时间. 这是因为在真实网络中, 观测到的吞吐量会随切片大小非线性变化.
输入特征: TTP 神经网络接收极其丰富的输入, 特别是底层的 TCP 统计信息 (如 CWND, RTT, 飞行中的数据包数), 以及过去切片的大小和传输时间, 提议切片的大小.
概率输出: TTP 输出的是传输时间的概率分布 (离散化为 21 个区间), 而不是单一的点估计值. 这使得控制器能够处理不确定性 (即随机 MPC).
网络结构: TTP 是一个全连接神经网络, 包含两个各 64 个神经元的隐藏层.

(4) 训练策略: 原位监督学习

数据来源: 直接从 Puffer 平台收集的真实用户流数据中采样, 使用监督学习进行训练.
训练方式: 最小化输出概率分布与实际传输时间之间的交叉熵损失.
每日重训: 为了应对数据分布偏移, TTP 每天使用过去 14 天的数据重新训练 (近期数据权重更高).

(5) 控制器逻辑

随机最优控制: MPC 控制器利用 TTP 提供的概率分布, 通过值迭代 (Value Iteration) 和动态规划 (Dynamic Programming) 来规划未来 \(H\) 步 (约 10 秒) 的最佳切片序列, 以最大化预期 QoE.

(6) 消融实验 (Ablation Study) 发现

TCP 信息至关重要: RTT, CWND 和 inflight packets 等底层 TCP 统计信息显著提高了预测准确性.
切片大小感知: 显式考虑切片大小的预测器比通用的吞吐量预测器更准确.
概率预测的价值: 输出概率分布 (而非点估计) 对于决策至关重要. 在实际部署中, 去除概率输出会导致卡顿率恶化 5 倍.
神经网络的必要性: 相比线性回归模型, 使用 DNN 带来了显著的性能提升.
每日重训的影响:
- 令人惊讶的是, 每日重训并未显示出比使用数月前训练的模型有显著优势
- 这暗示 Puffer 的用户/网络环境相对稳定, 或者一旦数据量足够, "陈旧"的模型依然鲁棒.

Conclusion 核心内容

仿真与现实的鸿沟:
- 现有的机器学习网络系统, 常基于模拟器或受限环境宣称达到“近乎最优”的性能.
- 但由于真实互联网存在高变异性和长尾分布, 模拟器中的优异表现并不一定能转化为现实环境中的好成绩.
构建鲁棒算法的关键(原位学习):
- 作者认为, 要在狂野的互联网上构建鲁棒的 ABR 算法, 最佳策略是“作弊”: aka. 在真实的部署环境中利用真实数据进行原位训练(train in situ).
- 这需要结合足够复杂（如神经网络）的预测器进行监督学习, 同时保留足够简单直观的经典控制器结构.
大规模实验验证:
- 基于过去一年向 63,508 名用户传输的 38.6 年视频数据, 随机盲测结果显示 Fugu 算法在客观指标（SSIM、卡顿时间、变异性）上均稳健地优于其他简单或复杂的方案, 并显著延长了用户的观看时长.
Puffer 开放研究平台:
- 作者将 Puffer 确立为“开放研究”平台, 每周更新并公开发布脱敏后的完整数据档案和实验结果.
- 同时也开源了 Puffer、Fugu 及其分析工具.
未来展望与邀请:
- 项目组计划尽可能长久地运营 Puffer.
- 邀请研究社区利用该平台的真实流量来训练和验证新的 ABR、网络预测及拥塞控制算法，共同探索如何设计适用于真实互联网的鲁棒学习系统.