目前基于直播的应用程序类型较多，包括商务直播、在线会议、云游戏等，这些应用程序已成为人们日常生活的重要组成部分。与此同时，这些应用程序对互联网的服务质量(quality of service，QoS)提出了更严格的要求。例如，相比单向通信的直播中用户可以容忍几秒的延迟，交互式语音或视频服务中传输延时只有小于300 ms，用户才能获得良好体验^[1]；云游戏中用户能接受的流量传输往返时间(round-trip time，RTT)必须低于100 ms^[2]。此外，其他QoS指标如数据速率、抖动等也有严格要求。如果应用程序不能满足高QoS要求，就会极大地降低用户体验，进而影响服务提供商的利润。

由于互联网的资源由所有用户共享，因此现有互联网只能提供尽力而为的服务，无法满足高质量的流量传输要求。虽然一些服务提供商选择建设或租用私有骨干网以提高QoS^[3-4]，但是私有骨干网的建设和运营成本高，且难以覆盖世界各地的所有用户。为解决成本问题，许多服务提供商利用Overlay技术建立了低成本、高性能的虚拟网络。一些早期研究主要利用对等网络(peer-to-peer，P2P)技术和Overlay技术实现高效的流量传输^[5-6]，通过多跳中间节点绕过底层拥塞链路，进而提升传输质量^[7-8]。文[9-10]提出了针对P2P场景的优化方案，但无法满足直播流媒体传输的低延时要求。文[11]指出，通过公共互联网和专用Overlay网络联合优化可提升网络电话的通话质量。

随着云计算和内容分发网络(content delivery network，CDN)技术快速发展，以较小预算成本为大量用户提供更好的QoS成为可能^[12-14]。CDN主要通过部署和调度更接近用户的边缘服务器改善用户体验^{[12, 15-16]}。Dai等^[17]研究了基于服务器的多源和多渠道直播网络延时优化。He等^[18]通过贪心方法和凸优化方法解决了流量传输的成本优化问题，降低了CDN的传输成本和传输延时。这些方案基于传统的CDN结构——树结构实现，其优势在于可通过分层缓存提高实时用户体验质量(quality of experience，QoE)^[19]，但不能满足本文场景中直播流媒体传输的低延时要求。Li等^[14]为大规模低延时直播提出了一种扁平状的CDN结构，可以有效降低实时音视频的传输延时，但该方案的路径权重由启发式算法计算，这可能导致高频率的路由振荡。

在上述方案中，服务提供商仍然需要支付租赁服务器和订阅带宽的费用，这自然就引入了成本问题，即满足高QoS要求的同时如何实现成本最小化。然而，现有较多研究忽视了该问题。例如，文[20-21]关注了云传输成本与性能，权衡了不同云节点之间传输的总流量成本与性能，但忽视了由峰值带宽计价规则产生的与时间序列相关的成本问题。

本文目标是从流量工程(traffic engineering，TE)角度提供经济高效的直播流媒体服务。考虑的场景是由转发节点和虚拟链路组成的Overlay网络，业务流沿着转发节点间的传输路径传输，该传输路径可能包含多条虚拟链路，比直接使用互联网路由能获得更好的性能^[22]。同时，Overlay网络中每个转发节点使用的带宽会产生传输成本。本文通过计算确定业务流在转发节点间的传输路径，从而使1个长时间周期的总成本最小化。该成本问题比一般的TE问题更复杂，除了难以预测的流量波动和端到端传输的低延时要求，还需要细化传输流量的成本。传输流量的成本通常由1个与转发节点峰值数据速率相关的函数决定，在该成本函数中，根据当前情况直接选择最便宜的路径可能不会使总成本最小。因此，低成本的直播流媒体TE问题是1个涉及时间序列决策的复杂问题。

本文研究了低成本大规模流量工程问题。首先，将直播流媒体中成本敏感的TE问题形式化为时间序列优化问题，并将该问题解耦为一系列基于时间序列的整数规划。其次，提出了通过可微函数解决不可微问题的方法，通过Gumbel-Softmax函数^[23]近似路径选择过程，同时使用可微函数逼近成本函数和传输延时函数，并使用Lagrange乘子法对问题进行变换。最后，开发了在线路由算法LiveTE，采用LiveTE输出决策路径集，并基于梯度下降算法进行优化。

1 问题 1.1 系统架构

目前，一些经典的直播流媒体优化方案已经投入使用并获得了较好效果。Livenet^[14]由阿里巴巴团队提出，网络结构见图 1，由1个作为集中式控制器的流式大脑、多个提供各种服务的服务器节点和客户端主机构成。该结构中，流式大脑以网络拓扑和网络状态信息为依据，通过确定的路由算法计算网路中媒体流传输路径；服务器节点具有多种功能，包括收集网络状态信息、编解码音视频和充当转发节点进行数据转发等；客户端主机负责收发媒体流。通过该集中式的扁平化的CDN结构，Livenet可以获得较低的媒体流传输延时。

VIA^[11]是微软公司于2016年提出的1个基于Overlay技术的网络通话优化方案。该方案将一些云服务提供商部署在世界各地的数据中心节点作为转发节点，利用业务流收集网络状态信息，并通过集中式控制的方式进行路由决策，从而提升网络电话的通话质量。VIA的网络结构见图 2，由控制器、中继节点和客户端主机构成。控制器根据业务流在不同路径上的传输质量，确定当前状态下的最优传输路径，并通知客户端主机；客户端主机则根据控制器下发的最优传输路径发送媒体流。这种设计可以绕过公共互联网的拥塞链路，提升网络通话的QoS。

以上2个优化方案的网络结构虽然不同，但考虑到各自特点和各部分作用，本文将二者抽象精简后提出了1个通用的集中式控制网络结构，便于描述问题并用于部署LiveTE，结构如图 3所示。其中，所有节点都通过白色云雾代表的公共互联网连接，蓝色虚线表示控制器与节点间进行控制信息与网络状态信息的交互，绿色实线表示某条流量沿路径转发。LiveTE的网络结构由1个集中式的控制器及多个转发节点、服务节点和各节点间的虚拟链路组成。其中，控制器负责管理网络拓扑，根据网络状态信息通过LiveTE计算节点之间的传输路径，并将路由表下发至每个节点；转发节点负责收集网络状态信息和转发流量，并与控制器交互；服务节点除具有转发节点的功能外，还负责与用户通信、编解码视频流及缓冲数据。

本文通过1个简单的例子说明数据包在Live TE网络结构中的转发过程。在图 3中，首先，服务节点1接收用户A向用户B发送的数据包后，根据控制器预先下发的路由表将整个传输路径写入数据包包头。其次，数据包根据写入的传输路径通过若干个转发节点转发。需要说明的是，数据包也可能直接从服务节点1发送至服务节点2，中间不经过任何转发节点，这取决于控制器根据前1个时隙的网络状态信息而做出的决定。最后，服务节点2接收数据包后，根据数据包的目的互联网协议(internet protocol，IP)将其发送给用户B。

在Live TE网络结构中，如有必要，部署于服务节点的数据包的控制逻辑(如控制拥塞、编解码音视频等)也可以部署于转发节点，Livenet方案^[14]的转发节点具有类似的设计，这与本文的研究没有冲突。此处区分服务节点和转发节点的主要原因是方便读者理解，让转发节点可以使用所有的中央处理器(central processing unit，CPU)资源进行数据转发。由于本文后续不涉及服务节点上有关数据包控制逻辑的研究，因此本文中服务节点的功能与转发节点一致，为了避免歧义和方便理解，以下将不区分服务节点与转发节点，统一称为节点。

1.2 问题形式化

首先，将网络表示为由节点集合$V$和节点间的有向虚拟链路集合$E$组成的有向图$G=\langle V，E\rangle$。$C_v$表示节点$v$的最大吞吐率; $t$表示时隙序号，$t \in T，T=\{1，2，\cdots，n\}$表示计费周期（如$1 \mathrm{~d}$) 中所有时隙序号的集合。其次，对于任意虚拟链路$e \in E，l_e^t$表示$e$在时隙$t$的平均传输延时，$U_v^t$表示$v$在时隙$t$的峰值流量，同时，根据传输延时和峰值流量的实测结果，引人了1个由节点负载产生的额外传输延时函数$h_v$。再次，对于给定的源、目标节点对$(s，d)，p_{s d}^t$表示从备选路径集合$P_{s d}^t$中选择的路由路径，$p_{s d}^t \in P_{s d}^t，N_{s d}^t$和$M_{s d}^t$分别表示$p_{s d}^t$的节点和链路的集合。最后将$v$的流量传输成本表示为关于$U_v^t$的函数$g_v\left(U_v^t\right)$，并假设$(s，d)$在时隙$t$的流量需求$f_{s d}^t$可以被准确预测^[24]。本文使用一个0-1变量$I_{\text {cond }}$表示是否满足条件cond。若满足条件cond，则$I_{\text {cond }}=1$; 否则，$I_{\text {cond }}=0$。问题表示如下：

$ \min \sum\limits_{v \in V} \max\limits_{t \in T} g_v\left(U_v^t\right) ; $

(1)

$ \text { s. t. } \sum\limits_{s, d} f_{s d}^t I_{v \in N_{s d}^t} \leqslant \lambda C_v, \forall v \in V, \forall t \in T \text {; } $

(2)

$ \begin{gathered} \sum\limits_{e \in M_{s d}^t} l_e^t+\sum\limits_{v \in N_{s d}^t} h_v\left(U_v^t\right) \leqslant \gamma \hat{L}_{t, s d}^{\min } \\ \forall s, d \in V, \quad \forall t \in T ; \end{gathered} $

(3)

$ \sum\limits_{s, d} I_{p_{s d}^t \neq p_{s d}^{t-1}} \leqslant \xi|V|(|V|-1), \forall t \in T . $

(4)

其中：λ为最大链路使用率，ξ为限制路由变化率，γ为限制最大传输延时的倍率，$\hat{L}_{t, sd }^{\min }$为(s, d)在时隙t的最短传输延时。

式(1)表示最小化1个计费周期的网络总体传输成本。式(2)限制了每个节点的峰值流量，在满足节点使用率需求前提下，为保证节点能承受一定的突发流量，设置λ=0.8。式(3)约束了(s, d)在时隙t的传输延时L_{t, sd}，根据当前时隙的网络状态信息计算得到$\hat{L}_{t, sd }^{\min }$，表示如下：

$ \hat{L}_{t, s d}^{\min ^2}=\min\limits_{p_{s d}^t \in P_{s d}^t } \sum\limits_{e \in M_{s d}^t}l_e^t . $

(5)

式(4)限制了每次路由决策中路由路径变化的数量，可以提升路由稳定性，并降低路径更新的成本，实验中设置ξ= 0.1。

此外，本文算法中的约束条件还可以用于链路丢包和抖动等。例如，丢包可以通过取对数后相加，用类似延时的形式表示为约束条件。但这不是本文目前考虑的主要内容，未来工作可以考虑设置更多优化指标应对不同场景的数据传输需求。

1.3 复杂度分析

首先，本文调研了部分大型云服务提供商披露的节点带宽租赁价格，并实测了一些真实节点的带宽；其次，给出了g_v(U_v^t)和h_v的精确定义；最后，分析了所提问题的复杂性。

1) 成本函数。

由阿里云、腾讯云和华为云等知名云服务提供商披露的云服务器计费标准发现，云服务提供商通常根据1个时间周期内节点的峰值带宽收费，因此成本函数可以用1个分段函数表示。此外，由于不同地理位置节点的计费规则不同，因此成本函数也略有不同。g_v(U_v^t)表示如下：

$ g_v\left(U_v^t\right)= \begin{cases}a U_v^t, & U_v^t<x ; \\ a x+b\left(U_v^t-x\right), & x \leqslant U_v^t<y ; \\ a x+b y+\left(U_v^t-y\right), & y \leqslant U_v^t .\end{cases} $

(6)

其中：x、y为云服务提供商设置的峰值带宽定价阶梯，a、b、c分别为不同峰值带宽范围下每单位带宽的租金。实验中，用每个服务器节点的实际租用价格和定价阶梯分别替换a、b、c和x、y。

2) 节点负载对传输延时的影响。

本文通过测量云服务提供商部署的真实节点，确定了节点负载对流量传输延时的影响。具体的测量过程如下：对于节点v_A和v_B, 首先让v_A不间断地向v_B发送固定带宽的流量，并命令v_B将流量转发给v_A，以此获得流量在v_A和v_B间传输的RTT，同时通过其他节点发送背景流量，增加v_B的负载，从而可以获得不同v_B负载下v_A和v_B之间传输流量的RTT。根据上述的测量方法，获得了真实节点之间流量传输RTT随节点负载变化的规律，部分结果如图 4所示。可以看出，当节点负载低于100%时，上海—广州、北京—广州和新加坡—广州3条路径的流量传输RTT分别为27、36和49 ms；随着节点负载增加，当节点负载超过100%时，3条路径的流量传输RTT会突然增加30 ms。

因此，根据图 4中的规律，h_v表示如下：

$ h_v\left(U_v^t\right)=\delta_v \cdot I_{U_v^t>C_v} . $

(7)

其中δ_v为v超负载时的额外拥塞延时，本文中δ_v=30 ms。

3) 复杂度分析。

使用传统的基于模型的优化方法较难解决本文所提问题，主要面临以下3个挑战。

1) 所提问题中的函数g_v和h_v均是非线性的，因此该问题难以使用线性规划或整数规划建模和求解。

2) 本文目标是使性能与成本均达到最优。由于链路延时、流量请求等网络状态在每个时隙都可能发生变化，因此需要根据前1个时隙的网络状态为后1个时隙输出最佳路径选择。然而，如果简单根据当前时隙的网络状态和流量请求确定最佳路径，以最小化当前网络的节点租赁成本，反而可能导致整个计费周期的租赁成本更高。

面向直播流业务的成本敏感的TE问题示例如图 5所示。在1个计费周期内(实际中云服务提供商通常以1 d或1月为1个计费周期)，节点v_A的峰值带宽使用成本为60元/(Mb·s^-1)，节点v_B的峰值带宽使用成本为90元/(Mb·s^-1)。假设在1个计费周期内，网络分别在时隙t₁和t₂传输了2条流量。时隙t₁内数据速率为10 Mb/s的流量从v_S2通过v_B发送到v_D，这在v_B产生了900元的成本。在稍后的时隙t₂，数据速率为10 Mb/s的流量即将从v_S1传送至v_D。需要注意的是，本文为使问题更易理解，假设时隙t₁内传输的流量在时隙t₂之前已经结束传输且当前网络中没有其他的流量。如果选择路径v_S1—v_A—v_D，则这1个计费周期内v_A和v_B的峰值带宽传输速率均为10 Mb/s，总成本为1 500元。而如果选择路径v_S1—v_B—v_D，则这1个计费周期内v_A和v_B的峰值带宽传输速率分别为0和10 Mb/s，总成本为900元。

这并不是1个特例，因为在具有大量动态用户流量的大型网络中经常可以观察到类似的情况。

3) 即使掌握了全部网络状态信息，仍然难以解决决策变量众多的问题。候选路径的数量随着网络规模增大呈超线性增加，并很快达到难以枚举的量级。此外，联合所有时隙的决策变量空间会使问题变得更难以求解。

2 方法 2.1 方法概述

由1.2节可知，本文将所提问题形式化后整理为1个时间序列联合优化问题，即在一系列时隙内最小化整体网络传输成本。因此，求解过程是将时间序列联合优化问题解耦即在每个时隙求解问题，以获得近似最优解。在1.3节图 5中，若要在时隙t₂做出决策，则应考虑时隙t₁已经被使用或购买的节点带宽，并基于此进行下1个时隙的规划，在这样的情况下，由于时隙t₁内v_B已经被占用，因此实际上在时隙t₂内从v_B传输的成本应当为0，由此得到该例的最优解。因此，本文需要使每个时隙的当前流量需求和网络状态下的额外成本最小化。该优化表示如下：

$ \begin{aligned} & \min\limits_{P_{s d}^t} \sum\limits_{v \in V} \max \left(0, g_v\left(U_v^t\right)-\max _{t^{\prime}<t}\left(g_v\left(U_v^{t^{\prime}}\right)\right)\right), \\ & \;\;\;\;\;\;\text { s. t. } \sum\limits_{s, d} f_{s d}^t I_{v \in N_{s d}^t} \leqslant \lambda C_v, \forall v \in V, \\ & \sum\limits_{e \in M_{s d}^t} l_e^t+\sum\limits_{v \in N_{s d}^t} h_v\left(U_v^t\right) \leqslant \gamma \hat{L}_t^{\min }, \quad \forall s, d \in V, \\ & \;\;\;\;\;\;\sum\limits_{s, d} I_{p_{s d}^t \neq p_{s d}^{t-1}} \leqslant \xi|V|(|V|-1) . \\ & \end{aligned} $

(8)

式(8)会尽可能减少下1个时隙的额外成本，同时为避免节点过载，要在限制路由路径变更数量上限的情况下保证流量的传输延时。基于上述解耦后的连续最优问题，可以在每个时隙进行优化。

然而，由可能的路由路径带来的巨大解空间导致解耦后的优化问题仍然难以解决。为此，首先，根据网络拓扑和网络状态信息选择1组候选路径；其次，用可微函数近似QoS度量(包括数据传输延时和节点负载)，将带约束的优化问题转化为可微损失函数，通过使用梯度下降算法最小化损失函数，从而解决每个时隙的成本优化问题；最后，用设计的LiveTE在每个时隙生成最佳路由路径。

2.2 用可微函数近似

本节设计了h_v的可微近似。提出了1个可微损失函数，该函数在QoS约束下可以使额外成本最小化。需要注意的是，后续的公式中可能会省略符号t以简化问题描述。

1) 将路径选择建模为可微变量。先将路径选择建模为长度为$\left|P_{s d}^t\right|$的one-hot向量$\boldsymbol{w}_{s d}=$ $\left(w_{p_{s d, 1}^t}^t, w_{p_{s d, 2}^t}^t, \cdots, w_{p_{s d, n}^t}^t\right), w_{p_{s d}^t, i}^t$表示$(s, d)$的第$i$条路径在时隙$t$内被选中, $i=1, 2, \cdots, n$, 设置所选路径位置为1, 其余为0, 但直接采用onehot向量$\boldsymbol{w}_{s d}$建模路径选择的结果不可微, 为使结果可微, 需采用Gumbel_Softmax函数重参数化$\boldsymbol{w}_{s d}$; 再使用可调优浮点向量$\boldsymbol{\theta}_{s d}$和Gumbel Softmax ^[23]函数建模源、目标节点对$(s, d)$的路径选择:

$ \boldsymbol{w}_{s d}=\text { Gumbel_Softmax }\left(\boldsymbol{\theta}_{s d}\right) \text {. } $

(9)

将$p_{s d}^t$所经过的节点条件变量$I_{v \in N_{s d}^t}$、链路条件变量$I_{e \in M_{s d}^t}$和路径改变变量$I_{p_{s d}^t \neq p_{s d}^{t-1}}$表示如下:

$ \begin{gathered} I_{v \in N_{s d}^t}=\sum\limits_{p \in P_{s d}^t} w_{p_{s d}^t}^t I_{v \in N_{s d}^t}, \\ I_{e \in M_{s d}^t}=\sum\limits_{p \in P_{s d}^t} w_{p_{s d}^t}^t I_{e \in M_{s d}^t}, \\ I_{p_{s d}^t \neq p_{s d}^{t-1}}=w_{p_{s d}^t}^t-w_{p_{s d}^t}^{t-1} . \end{gathered} $

(10)

2) 建模h_v。不可微的h_v近似表示为

$ h_v \approx 0.5 \tanh \left(\left(\frac{U_v^t}{C_v}-1\right) \cdot \alpha\right)+0.5 . $

(11)

其中α为函数的锐化幅度，本文中α=10。同时，由于g_v几乎处处可微，因此获得的可微的附加成本O为

$ O=\sum\limits_{v \in V} \max \left(0, g_v\left(U_v^t\right)-\max\limits_{t^{\prime}<t}\left(g_v\left(U_v^{t^{\prime}}\right)\right)\right) \text {. } $

(12)

可微约束的惩罚如下：

$ \begin{gathered} \varDelta_1=\sum\limits_{v \in V} \max \left(0, U_v^t-\lambda C_v\right), \\ \varDelta_2=\sum\limits_{s, d \in V} \max \left(0, L_{t, s d}-\gamma \hat{L}_{t, s d}^{\min\limits_d}\right), \\ \varDelta_3=\max \left(0, \sum\limits_{s, d} I_{p_{s d}^t \neq p_{s d}^{t-1}}-\xi|V|(|V|-1)\right) . \end{gathered} $

(13)

因此，最终的可微损失函数为

$ \begin{gathered} L(\boldsymbol{\theta})=\ln (1+O)+\alpha \ln \left(1+\Delta_1\right)+ \\ \beta \ln \left(1+\Delta_2\right)+\eta \ln \left(1+\Delta_3\right) . \end{gathered} $

(14)

其中α、β、η是缩放约束惩罚的超参数，α>0，β>0，η>0。当获得式(12)—(14)时，可采用Lagrange乘子法求解式(8)。

2.3 在线算法设计

在线算法设计包括收集网络状态信息和设计Live TE的流程。

1) 收集网络状态信息。为使控制器获得网络状态信息，每个节点每小时向控制器报告自身与其他节点间流量传输的RTT，此处RTT由UDP ping实用程序测量^[14]。在此基础上，每个节点每分钟会向控制器发送过去1 min内节点的最高负载和流量请求信息。

2) 设计LiveTE的流程。算法的输入包括网络拓扑、虚拟链路传输延时和节点间流量，输出是节点间决策路径表。LiveTE的流程如图 6所示。其中，ϕ为空集，$\hat{P}_{s d}^t$为通过筛选获得的路径集合，K为梯度更新次数。

图 6中，第3—14行表示根据网络拓扑和网络状态信息筛选备选路径集。在第8行选择长度不超过3跳的路径。一方面，路径中每增加1个额外的中间跳，相应的使用成本将以指数方式增加，具有3个以上中间节点的路径在成本上是难以接受的。另一方面，中间跳数为3跳以内的决策路径足以覆盖几乎所有性能最佳的路径^[11]。在第9—12行，算法会过滤掉传输延时超过150 ms的路径，这也符合行业和标准机构文献推荐的实时音视频单向端到端延时要求^[1]。同时，为了尽可能减少传输延时，算法在第9—12行还会过滤掉传输延时超过最小传输延时1.4倍的路径。第15—19行表示使用梯度下降算法进行迭代训练。当路径满足式(10)的约束时，停止迭代并获得最终传输路径。

对于决策频率，考虑到网络性能的动态性^[11]和过滤备选路径集的开销，控制器每小时更新1组备选路径。在此基础上，为了处理比链路性能变化更频繁的流量请求，控制器基于当前备选路径集以min为单位计算节点间的传输路径。此外，当任何节点检测到流量突发或链路故障时，将第一时间通知控制器并上传网络状态信息，控制器立即重新计算备选路径集和最佳路径表并将其下发至节点。

3 实验 3.1 实验设置

通过数值仿真评估LiveTE方案在2种不同规模拓扑上的性能。其中，小拓扑模拟了中国某个著名大型云服务提供商的Overlay网络，该网络由全球14个地点的真实服务器和各服务器节点对之间的91条虚拟链路组成。将通过实际测量获得的1个计费周期(1 d)的网络状态信息作为小拓扑实验的输入数据。大拓扑具有84个节点和3 486条虚拟链路，其中虚拟链路的数据传输延时是根据小拓扑的实测数据，基于不同节点的地理位置再加上部分随机数生成的。在每个拓扑中，根据某著名云服务提供商提供的数据，将节点的带宽上限设置为500 Mb/s，并根据服务器所在不同区域的实际峰值带宽计费价格计算租赁成本。

实验通过Bi-model^[25]模型为小拓扑生成了低、中和高负载3套流量矩阵，同时也为大拓扑生成了1套流量矩阵，每套流量矩阵有1 440组流量。上述流量矩阵作为网络1 d的流量请求，且实验每分钟变更1组流量。为了尽可能保证实验的真实性，根据网络空间的实际情况调整了不同时段和时区的流量分布以及流量突发的概率。例如，在北京时间8 ∶ 00—11 ∶ 00及18 ∶ 00—20 ∶ 00，为北京时区的节点设置更多的流量请求和流量突发等。

在2个拓扑中将LiveTE方案与以下现有方案进行了比较：1) Livenet方案^[14]，通过对节点负载和链路延时进行加权，从而计算各节点间流量传输的路径；2) Shortest Paths方案，根据虚拟链路延时计算各节点间流量传输的最短路径；3) Direct Paths方案，流量通过节点间直连的虚拟链路直接传输。

3.2 实验结果

本节比较了各方案在不同实验拓扑中的服务器租赁成本。大拓扑实验中各方案的服务器租凭成本如图 7所示。可以看出，LiveTE方案的服务器租赁成本显著低于Livenet和Shortest Paths方案，为Livenet方案的52%；略高于Direct Paths方案，这是由于Direct Paths方案的流量不通过任何中间节点转发，使得其服务器租赁成本是网络流量传输的最低成本。Direct Paths方案也有缺陷，因为节点间通过公共互联网路由直连，流量传输延时有时并不理想，而通过几跳中间节点进行转发可能会获得更好的传输性能^[22]。本文后续的实验结果也证明了结论，而保证流量传输延时是LiveTE方案的优化目标之一。图 8为小拓扑实验中各方案在不同负载下的服务器租赁成本。可以看出，无论在哪种负载条件下，LiveTE方案的服务器租赁成本都低于Livenet和Shortest Paths方案，仅略高于Direct Paths方案。

图 9为大拓扑实验中各方案的流量传输延时。可以看出，LiveTE方案流量传输的最高延时和平均延时(图中白线)都优于Livenet和Direct Paths方案，其中LiveTE方案流量传输的平均延时是Livenet方案的94%，略小于Shortest Paths方案。

Shortest Paths方案虽然可以最小化传输延时，但未考虑网络中节点的实际承载能力，这会导致实际传输过程中一些节点出现超负载情况。此外，这也会提高传输成本，而尽可能降低传输成本是LiveTE方案的主要优化目标之一。在实际传输中，超高的节点负载是不可接受的，这会带来超高的丢包率，降低流量传输质量^[26]。

图 10为小拓扑实验中各方案在不同流量负载下的流量传输延时。可以看出，在低负载下，LiveTE方案的平均延时和最高延时(图中最高点)均优于Direct Paths方案，而在中负载和高负载下，Live TE方案仅最高延时优于Livenet和Direct Paths方案。

在网络传输中，频繁切换路由路径会导致路由振荡，同时带来额外开销，造成严重的网络问题。这是因为路由振荡会导致路由链路信息在全网范围内呈周期性不断更新，这些链路信息不断地被广播或撤销，占用了大量网络资源，同时也会增加网络中路由器CPU的工作负担，导致出现路由计算错误和频繁网络丢包等情况^[27-28]。因此，本文在实验中分别统计了不同方案在2种规模拓扑下每个时隙的决策路径变更数量。决策路径是指每次计算路由路径后所确定的源、目标节点对之间传输流量的虚拟链路。

图 11为小拓扑实验中各方案在不同负载下每个时隙决策路径变更数量的实验结果。可以看出，LiveTE方案的决策路径变更数量大多低于Livenet方案。图 12显示了大拓扑实验中各方案每个时隙决策路径变更数量，其中LiveTE方案的决策路径变更数量接近Shortest Paths方案，远低于Livenet方案。本文实验限制了LiveTE方案的决策路径变更数量不超过路径总数的10%；小拓扑实验中共有182条路径，LiveTE方案的决策路径变更数量通常不超过18条；大拓扑实验中共有6 972条路径，LiveTE方案的决策路径变更数量通常不会超过600条。同时，LiveTE方案的决策路径变更数量会因网络状态的动态变化而出现峰值，不会因流量请求的变化而频繁波动；而Livenet方案的决策路径变更数量不仅会因网络状态的动态变化而出现峰值，也会因流量请求的变化而频繁波动。

4 结论

本文研究了低成本大规模直播流量工程问题并提出了LiveTE算法。首先，将实时音视频传输的成本敏感的流量工程问题形式化为时间序列优化问题，并将该问题解耦为一系列基于时间序列的整数规划。其次，通过可微函数逼近不可微函数，使用Gumbel-Softmax函数逼近路径选择。最后，使用Lagrange乘子法对问题进行变换，并基于梯度下降算法求解优化问题。实验使用来自大型云服务提供商的直播流媒体网络的真实拓扑和路径传输延时数据进行数值模拟，并进一步使用大拓扑和流量矩阵进行验证。实验结果验证了LiveTE算法的有效性。