近年来大规模视频直播经历了飞速的发展。诸如抖音、快手等直播平台在全球范围内获得了前所未有的关注。为了尽可能满足用户的观看体验，直播内容提供商租用云服务厂商提供内容分发服务，因而云服务厂商在内容分发过程中起到了至关重要的作用。相较于传统的云服务任务（比如计算任务），大量的直播间和分散的用户请求使得分发过程中会产生大量的带宽成本，特别是大量的回源成本，高额的带宽成本将会严重影响内容提供商的进入门槛。华为云算法创新lab联合清华大学，针对大规模直播视频的云服务业务，提出一种通过汇聚各区域分散用户，减少边缘节点个数并减低回源带宽的方法。该方法上线华为云一年内，在保障服务质量的同时节省15%+的回源带宽成本。

传统LocalDNS调度的问题

对现网数据采用分桶统计，按照流行度（观众数量）将16000+直播间进行间隔分桶，并对桶内直播间瓶颈使用的节点数作为该流行度对应的边缘节点使用数量。统计结果如下图所示：

对于不同直播间（图1），当直播间观众较少时，仍占有大量边缘节点（ 直播间观众为100人时，仍占据50+边缘节点），此时回源带宽利用率极低。

对于同一直播间（图2），各个边缘节点负载分布差异巨大，有35个节点只服务了25-的观众。

故在观众地理分布广、直播源头数量多的情况下，LocalDNS就近原则会导致边缘节点利用率低下。

本论文方法

为了解决上述问题，本文提出了AggCast: 一种基于冷热流的边缘节点带宽资源优化方法。 其决策逻辑主要分为直播间分类阶段和调度阶段，如下图所示：

直播间分类

如图1所示，当观众人数少时，随着直播间人数增加（<100人），边缘节点数量迅速增加，而当直播间流行度够大（>2000人），边缘节点数趋于稳定。故需要找出流行度较低的冷流直播间，并对其进行优化，降低回源成本。

• 流行度预测：隐马尔可夫模型

因为直播场景中，绝大多数用户倾向于在不同直播间切换，隐马尔可夫模型作为一种基于状态转移的概率预测模型，可以通过捕捉隐状态的变化进行预测。

下面我们具体给出隐马尔可夫模型的模型定义。我们用$X_t$$X_t$来表示 $t$$t$ 时刻某一直播间的用户数量，用$S_t\in \mathcal{S}=\{S_0,S_1,...,S_{n-1}\}$$S_t \in \mathcal{S}=\{S_0, S_1, ..., S_{n-1}\}$ 来表示隐变量的状态。则由隐马尔可夫模型的定义，$S_t$$S_t$ 为随机变量，因此我们可以定义其概率分布为${\pi }_t=(P(S_t=S_0),...,P(S_t=S_{n-1}))$$\pi_t=(P(S_t=S_0), ..., P(S_t=S_{n-1}))$。隐马尔可夫模型假设状态迁移遵循马尔可夫过程（Markov process），即当前状态的分布只和上一步状态有关。从数学形式上，我们可以写为：

其中$P=\{p_{i,j}\}$$P=\{p_{i,j}\}$为转移概率矩阵，$p_{i,j}=P(S_t=s_i|S_{t-1}=s_j)$$p_{i,j}=P(S_t=s_i|S_{t-1}=s_j)$表示状态由上一时刻$s_j$$s_j$切换至下一时刻$s_i$$s_i$的概率。在转移概率矩阵的基础上，我们可以通过下式计算下一时刻各个状态的概率：

最后，在已知隐状态$S_t$$S_t$的基础上，下一时刻用户数量$X_t$$X_t$的概率分布（也被称为发射概率）为：

即概率分布满足高斯分布（我们在尝试了不同的概率分布后，高斯分布的效果最好）。与其他常用回归模型的效果比较如下（其中衡量指标采用归一化绝对值误差）：

• 冷热流阈值计算

按百分比设定阈值门限 $threshol{d}_{\text{冷}\text{流}\text{门}\text{限}}$$threshold_{冷流门限}$。 通过对观众数量对直播间排序，将观众数量排名末位的 $threshol{d}_{\text{冷}\text{流}\text{门}\text{限}}\ast \text{直}\text{播}\text{间}\text{总}\text{数}$$threshold_{冷流门限}*直播间总数$ 个直播间，定义为冷流直播间，其余为热流直播间。

服务质量保证的用户调度

在调度中，需要保证的服务质量主要包括延迟（首屏时长）和卡顿（百秒卡顿时长、百秒卡顿频率）。本文通过实验验证：地理位置的远近和网络链路的远近并不等价，地理就近接入节点并非时延最优节点。卡顿主要受限于边缘节点的接入带宽，当边缘节点不发生过载时，卡顿与是否跨区域接入无关。因此只要保证汇聚过程不过载，AggCast 的汇聚逻辑将不会影响到用户质量。

• 区域层级CFLP问题

因为直播间数量远远大于边缘区域数量，预测开销极大，且实验表明，对于单个直播间，每个区域的观众随时间变化剧烈。而将区域内所有冷流直播间看作一个整体时，单个区域内的所有冷流直播间的观众总数随时间变化稳定。故在边缘区域层而非直播间层面建立优化问题。

将某个区域内的所有冷流直播间用户定义为这个区域内的被汇聚用户，AggCast对相同区域内的被汇聚用户采用相同的汇聚逻辑。

设边缘节点的数量为$E$$E$，边缘区域的数量为$M$$M$，区域$m\in M$$m\in M$中被汇聚的用户数量为 $R_m$$R_m$，边缘节点$e$$e$的最大接入带宽为 $C_e$$C_e$，将区域$m$$m$的用户接入到边缘节点$e$$e$的首屏时长记为 $d_{m,e}$$d_{m,e}$。在任意时刻，AggCast的决策变量包括两个：首先，AggCast需要决定哪些节点作为用户汇聚使用的边缘节点，为此我们使用一个0/1变量 $y_e$$y_e$ 来表示是否使用边缘节点$e$$e$（若$y_e=1$$y_e=1$则使用，否则不使用）；其次，在得到了目标边缘节点之后，AggCast还需要决定每个节点应该服务区域$m$$m$中的观众数量。为此，我们使用 $x_{m,e}$$x_{m,e}$ 来表示区域 $m$$m$ 中，被节点 $e$$e$ 服务的观众占比。综上，该服务质量保证的调度问题可以被定义为：

从数学形式上，该问题表示的优化问题和资源受限下工厂选址问题（Capacitated Facility Location Problem，CFLP）等价（我们问题中的边缘节点即对应原问题中的工厂）。资源受限下工厂选址问题在运筹学领域被广泛研究，虽然该问题是NP-难问题，但很多算法均被证明可以取得非常好的效果，最常见的算法有模拟退火和拉格朗日松弛。综合考虑实现难度和算法效果，我们最终选择模拟退火求解。

• 实时求解

结合隐马尔可夫模型以及各边缘区域比例计算得用户数量 $R_m$$R_m$ ；通过边缘服务器监控带宽上限 $C_e$$C_e$ ； 通过区域 $m$$m$中使用边缘节点 $e$$e$ 的 用户数据的均值近似 $d_{m,e}$$d_{m,e}$ ，因此构建出一个时延查找表，表中每个元素表示对应区域和边缘节点的链接延迟。 使用探索-利用（Exploration and Exploitation，E2）算法来更新时延查找表。即如果区域 $m$$m$ 和边缘节点 $e$$e$ 之间有用户接入，则拿用户延迟更新 $d_{m,e}$$d_{m,e}$ ，否则用其他已测得的 $d_{m,e}$$d_{m,e}$ 的均值近似。此方法虽开始时会略有误差，但随求解过程会逐渐探索到全部真实情况，且效率较高。

• 冷热流边界

对AggCast而言，考虑到预测模型的误差以及直播间流行度变化的剧烈程度，某一些直播间可能会在冷热流之间来回切换，且频繁切换会使得AggCast的汇聚逻辑失效。故 AggCast 在冷流转换为热流之前，会根据流行度预测结果和冷热流划分的阈值，估算切换为热流的带宽收益大小，以决定是否切换。

• 减少问题规模

若全量求解，则求解时间超过三分钟，不满足实时性的要求。故通过KNN对边缘节点的距离进行聚类，对每类并行解决优化问题，能有效的将单步决策的时间降低到2s-。

实验结果

实验室测试

采用华为云2020年6月真实数据，覆盖18w+直播间，2000w+观众IP，观众来自300+地区，使用超过200+边缘节点。华为云作为国内最大的云服务厂商之一，为包括快手、抖音在内的直播平台提供服务，因此针对其数据集的测量结果具有代表性和普适性。

本实验对比就近接入（按IP地理位置就近接入）、Rildish（尽量将用户调度到服务质量最优的边缘节点）、最小成本最大流MCMF（将调度问题转化为最大流），其回源成本与服务质量对比如图所示。

AggCast在回源成本的降低和服务质量的保障上，整体表现最优。

线上测试

AggCast在华为云上进行了超过8个月的A/B测试，参与实验的直播间5w+个。如下图所示，在整个测试阶段，AggCast在80%的时间里都能获得15%+的回源带宽收益。