网络传输公平性测量与算法设计：视频应用案例

王子逸; 胡晓宇; 王歆; 张行功; 曹振; 郑凯; 崔勇

doi:10.7544/issn1000-1239.202330022

网络传输公平性测量与算法设计：视频应用案例

王子逸^1,,
胡晓宇¹,
王歆²,
张行功³,
曹振⁴,
郑凯⁴,
崔勇^1, ,

1.
清华大学计算机科学与技术系　北京　100084
2.
纽约州立大学石溪分校电气与计算机工程系　纽约　NY11794
3.
北京大学王选计算机研究所　北京　100080
4.
华为技术有限公司计算机网络与协议实验室　北京　100085

基金项目: 国家自然科学基金重点项目（62132009）；国家自然科学基金面上项目（61872211）

详细信息

作者简介:
王子逸: 1996年生. 博士研究生. 主要研究方向为视频流媒体和边缘计算

胡晓宇: 1991年生. 硕士. 主要研究方向为视频流媒体和边缘计算

王歆: 1968年生. 博士，副教授. 主要研究方向为移动计算和网络系统

张行功: 1973年生. 博士，副教授. CCF会员. 主要研究方向为视频流媒体和机器学习

曹振: 1982年生. 博士. 主要研究方向为无线网络和分布式系统

郑凯: 1978年生. 博士. 主要研究方向为数据中心网络和网络协议

崔勇: 1976年生. 博士，教授. CCF会员. 主要研究方向为移动云计算和网络架构

通讯作者:
崔勇（cuiyong@tsinghua.edu.cn）

中图分类号: TP393
计量
- 文章访问数: 218
- HTML全文浏览量: 20
- PDF下载量: 122
出版历程
- 收稿日期: 2023-01-07
- 修回日期: 2023-02-06
- 网络出版日期: 2023-02-26
- 刊出日期: 2023-04-17

Fairness Measurement and Algorithm Design of Network Transmission: A Case Study of Video Applications

1.
Department of Computer Science and Technology, Tsinghua University, Beijing 100084
2.
Department of Electrical and Computer Engineering, Stony Brook University, New York, NY11794
3.
WangXuan Institute of Computer Technology, Peking University, Beijing 100080
4.
Computer Network and Protocol Laboratory, Huawei Technologies Co., Ltd., Beijing 100085

Funds: This work was supported by the Key Program of the National Natural Science Foundation of China (62132009) and the General Program of the National Natural Science Foundation of China (61872211).

More Information

Author Bio:
Wang Ziyi: born in 1996. PhD candidate. His main research interests include video streaming and edge computing

Hu Xiaoyu: born in 1991. Master. His main research interests include video streaming and edge computing

Wang Xin: born in 1968. PhD, associate professor. Her main research interests include mobile computing and network systems

Zhang Xinggong: born in 1973. PhD, associate professor. Member of CCF. His main research interests include video streaming and machine learning

Cao Zhen: born in 1982. PhD. His main research interests include wireless networking and distributed systems

Zheng Kai: born in 1978. PhD. His main research interests include data center networking and network protocol

Cui Yong: born in 1976. PhD, professor. Member of CCF. His main research interests include mobile cloud computing and network architecture

摘要

摘要:
算网融合以计算为中心、网络为根基，通过网络连接异构计算节点，实现算网资源的高效分配与调度. 关于竞争流之间资源共享的公平性问题是算网融合的重要研究方向. 作为算网融合的典型场景，视频应用正变得越来越重要，但人们对于它们是否以及在多大程度上遵守公平性原则知之甚少. 在高度多样化的网络环境和缺乏自动化测量工具的情况下，公平性测量研究面临着巨大的挑战. 通过测量典型视频应用Zoom的竞争行为来研究这个问题发现，资源竞争行为是复杂多变的，Zoom在不同的场景下有着不同的资源抢占行为. 为了深入理解这些竞争行为，开发了自动化工具并进行测量以了解其用户体验（QoE）指标，包括端到端视频/音频时延、视频帧率和视频质量等. Zoom使用抢占带宽的策略来保证自身应用的用户体验. 为了追求更好的用户体验，Zoom往往会自私地发送过多的冗余数据包来应对异常的网络情况，其中一些是不必要的. 为此，设计一种能够在用户体验和公平性目标之间取得平衡的传输算法是非常重要的. 提出了算法QLibra，并通过实验证明它可以有效保障上层应用的用户体验并且对竞争流无害.
- 算网融合 /
- 公平性测量 /
- 算法设计 /
- 网络传输 /
- 视频应用
Abstract:
Computing-networking integration takes computing as the center and networking as the foundation, connects heterogeneous computing nodes through the network, and realizes the efficient allocation and scheduling of computing-networking resources. The fairness of resource sharing among competing flows is an important research direction of computing-networking integration. As typical scenarios, video applications are becoming more and more important, but little is known about whether and how much they adhere to the fairness principle. Given the highly diversified network environment and the shortage of automated measurement tools, fairness measurement study entails significant challenges. We investigate this problem by measuring the competing behaviors of typical video application (i.e., Zoom), and find that, resource competition behaviors are complex and transient, and Zoom has its own selfish behaviors in different operation scenarios. To take a deep dive into these competitive behaviors, we develop automated tools and conduct measurement to understand its QoE (quality of experience), including end-to-end video/voice delay, video frame rate, and video quality. We discover that the strategies of seizing bandwidth are used by Zoom to ensure its own QoE. In the pursuit of better QoE, Zoom tends to selfishly send excessively redundant packets to cope with abnormal network conditions, some of which are not necessary. To this end, it is important to specify a transport algorithm which is able to balance between QoE and fairness goals. We then present the design of QLibra, and demonstrate that it can effectively ensure the QoE and behave harmlessly to competing flows.
- computing-networking integration /
- fairness measurement /
- algorithm design /
- network transmission /
- video application

HTML全文

开放最短路径优先（open shortest path first, OSPF）^[1]协议和中间系统到中间系统（intermediate system to intermediate system, IS-IS）协议是互联网目前使用的2个典型的域内路由协议^[2]，这2个协议采用最短路径将报文从源地址转发到目的地址. 在OSPF和IS-IS中，每个路由器通过交互链路状态通告获得整个网络的拓扑结构，然后该路由器通过迪杰斯特拉算法计算以自身为根的最短路径树，最后该路由器根据最短路径树构造出自己的路由表. 当网络出现故障时，OSPF和IS-IS采用重新收敛机制来应对网路中的故障. 但是研究表明^[3-5]，它们的重新收敛时间大概在几秒甚至几十秒左右，在路由协议重新收敛的过程中受这些故障影响的报文将会被丢弃，严重影响了网络的性能，大大降低了用户的体验. 互联网部署的实时应用对网络的收敛时间提出了更高的要求^[6-8]. 传统的路由协议无法满足实时应用对网络收敛时间的要求^[9]. 为此，业界提出利用路由保护算法来解决此问题，研究表明路由保护算法^[10]可以大大降低由于故障造成的网络中断时间，显著减少报文丢失.

在已有的路由保护算法中，最经典的方法是IP快速重路由（IP fast rerouting, IPFRR）^[11]，该算法可以选择事先计算好的备份下一跳绕过故障，从而降低由于故障造成的报文丢失率. 与最短路径路由相比，IPFRR有明显的优点：可以立即重新转发数据包，而不是等待路由重新收敛（通常为几秒甚至几十秒），从而避免在路由重新收敛阶段出现路由环路和数据包丢失问题^[12].

路由保护算法最核心的技术是如何为每个结点计算到达目的结点的无环路备份下一跳. 下游规则（downstream criterion, DC）^[13]是一种经典的无环路计算规则，该规则选择距目的地址更近的邻居结点作为备份下一跳. 以目的结点构造有向无环图（directed acyclic graph, DAG），也可以计算出无环路备份下一跳. 基于最大邻接顺序的最大可选择性路由算法（maximum alternative routing algorithm, MARA）^[14]的核心思想就是将网络拓扑转换为DAG. 但是文献[13-14]算法和网络拓扑结构密切相关，在某些拓扑结构中故障保护率较低. 在DAG图中，每条链路仅有1个方向，这个要求大大降低了结点可以计算出无环路备份下一跳的可能性. JNHOR-SP（shortest path compatible Joker-capable next hop optimality routing）^[15]利用路由结点排序和Joker链路来提高DAG图的故障保护率，网络中的Joker链路具有2个方向，但是由于计算Joker链路算法的缺陷，JNHOR-SP平均仅能提供95%左右的故障保护率. 基于报文入端口的无环路路由（loop free inport-dependent, LFID）^[16]通过扩展DAG，将部分链路修改为双向链路，从而同时解决网络故障和网络拥塞问题，但是LFID的故障保护率为88.9% ~ 98.2%. Not-Via^[17]和段路由^[18]（segment routing, SR）可以保护网络所有可能的单故障，但是二者需要借助辅助机制的协助，在实际中部署比较困难.

已有的路由保护算法存在4个方面的问题：1）无法应对网络中所有可能的单故障情形；2）需要额外辅助机制的协助；3）不支持增量部署；4）需要存储多个备份下一跳. 我们拟设计一个路由算法，该算法满足4个要求：1）每个路由器存储2个下一跳，其中一个为最优下一跳，另外一个为备份下一跳；2）可以应对网络中所有可能出现的单故障情形；3）不需要额外辅助机制的协助；4）支持增量部署. 基于此本文提出了一个满足这4个要求的基于转发图的域内路由保护算法（an intra-domain routing protection algorithm based on forwarding graph, RPBFG）. 受JNHOR-SP和LFID这2个算法的启发，本文通过构造转发图来解决DAG图故障保护率较低的问题. 在转发图中，每条链路可能存在2个方向，这将明显提高故障保护率. 与JNHOR-SP和LFID不同的是，RPBFG可以提供100%故障保护率. 我们将在后面的章节中详细介绍什么是转发图，如何构造转发图，如何利用转发图计算无环路备份下一跳.

本文的主要贡献包括4个方面：

1）提出了以最大化故障保护率为目标，转发图包含反向最短路径树为约束条件的路由保护算法模型RPBFG.

2）针对提出的路由保护算法模型，首先提出了利用RPBFG解决快速构造转发图的算法，然后利用转发图为每个结点计算唯一一个备份下一跳.

3） RPBFG是对当前链路状态路由协议的扩展，不会改变路由协议报文的交互过程. RPBFG需要的数据都可以从链路状态路由协议中获得，唯一的变化是路由计算部分，因此RPBFG支持增量部署.

4）在11个真实网络拓扑中进行了实验，实验结果表明RPBFG不仅可以支持100%的单故障保护，而且具有较小的路径拉伸度.

根据这4点贡献的描述可知RPBFG可以应对网络中所有可能的单故障情形，不需要额外辅助机制的协助，支持增量部署，每个结点存储唯一一个到达目的地址的备份下一跳. 因此RPBFG可以解决文中描述的已有路由保护算法存在的4个问题.

1. 相关工作

已有研究^[19]证实，互联网中每天都会出现大量的网络故障. 为了应对互联网中频繁出现的故障，业界提出了路由保护算法^[20]，从而尽量降低由于故障造成的损失. 根据报文在转发过程中是否需要辅助机制的协助，可以将路由保护算法分为2类：第1类不需要借助辅助转发机制；第2类需要借助辅助转发机制.

第1类路由保护算法主要包括等价多路径路由（equal cost multipath routing, ECMP）、无环路备选条件（loop-free alternates, LFA）、U-turn、MARA-MA、基于扩展最短路径的最大可选择性路由算法（maximum alternative routing algorithm-shortest path extension, MARA-SPE）等；第2类路由保护算法主要包括Not-Via、SR、多配置路由（multiple routing configuration, MRC）、报文携带故障（failure carrying packet, FCP）等. 第1类算法和目前使用的路由协议是兼容的，因此支持增量部署. 然而第2类路由保护算法需要对目前使用的路由协议进行修改，实现难度较大. 本文重点研究第1类路由保护算法，下面将分别介绍这类路由算法.

OSPF协议增加了对ECMP的支持，但是ECMP仅仅支持代价相同的最短路径，因此对提高路由可用性的贡献比较有限^[21]. 为了应对ECMP在解决路由可用性方面存在的问题，国际互联网工程任务组（Internet Engineering Task Force, IETF）提出了快速重路由的基本框架. LFA就是基于此框架提出的无环路路由. LFA包括3种应对故障的保护条件：链路保护条件（link protection condition, LPC）、结点保护条件（node protection condition, NPC）和DC. 文献[22-23]分别介绍了如何通过调整链路权值和修改网络拓扑结构提高LFA的故障保护率. U-turn^[24]将选择备份下一跳扩展到计算结点邻居的邻居，即如果计算结点的邻居没有满足无环路规则的下一跳，但是计算结点的邻居的邻居有满足无环路规则的下一跳，则该邻居可以作为计算结点的备份下一跳，因此U-turn可以进一步提高故障保护率. MARA-MA^[14]以最大化最小连通性为目标构造DAG，MARA-SPE^[14]和MARA-MA的目标是一致的，但是MARA-SPE的约束条件为DAG必须包含最短路径树.

文献[25]提出了基于Not-Via地址的快速重路由机制. 在该算法中，网络中的每条链路都有2个地址，一个是正常的IP地址，另一个Not-Via地址. 该机制使用Not-Via地址显示的说明网络中出现故障的结点或者链路，从而使报文避开该故障. 基于隧道的路由保护算法^[26]为所有源目的对计算中转隧道结点，然而并不是所有的结点对之间都存在中转结点. 基于SR^[14]的路由保护算法将网络的路径分成一个个的小段，然后为这些段和网络结点分配Segment Routing的ID，通过对这些 Segment Routing ID进行有序的排列，就可以生成一条完整的转发路径.

MRC^[27]通过改变网络中链路的代价计算出多个配置图，这些不同配置图可以应对网络中出现的不同故障，从而达到提高路由可用性的目的，但是MRC部署开销较大. FCP^[28]的核心思路为：首先将报文遇到的故障存放在其头部，然后根据该头部信息更新网络拓扑结构，最后利用新的网路拓扑结构计算新的最短路径. FCP可以应对网络中的单故障问题，但是该方法需要改变路由协议，部署难度较大.

表1列出了RPBFG和已有路由保护算法的链路状态路由协议，在支持逐跳转发和支持100%的单故障保护等方面进行比较.

表 1 路由保护算法的比较

Table 1. Comparison of Routing Protection Algorithms

算法	是否是链路状态路由协议	是否支持逐跳转发	是否支持100% 的单故障保护
OSPF^[1]	√	√	×
LFA^[11]	√	√	×
MARA-MA^[14]	√	√	×
MARA-SPE^[14]	√	√	×
JNHOR-SP^[15]	√	√	×
LFID^[16]	√	√	×
SR^[18]	×	×	√
U-turn^[24]	√	√	×
Not-Via^[25]	×	×	√
MRC^[27]	×	×	√
FCP^[28]	×	×	√
RPBFG （本文）	√	√	√

下载: 导出CSV

| 显示表格

1）链路状态路由协议. 每个路由器根据网络拓扑结构做出最终的路由决策.

2）支持逐跳转发. 每个路由器基于目标地址查找数据报的下一跳，转发过程不需要借助额外机制的协助.

3）支持100%的单故障保护. 当网络出现单故障时，只要网络依然保持链路，数据报就可以被正确转发到目的地址.

2. 基于转发图的网络模型和问题描述

本节首先定义了反向最短路径树、转发图、故障保护率和路径拉伸度，然后对基于转发图的路由保护算法进行了形式化的描述. 为了便于读者阅读，将文中使用的部分符号总结在表2中.

表 2 本文定义的符号

Table 2. Symbols Defined in Our paper

符号	含义
G=(V, E)	网络拓扑图
V	网络中结点（路由器）的集合
E	网络中边（链路）的集合
r(d)	目的地址为d的反向最短路径树
G(d)	目的地址为d的转发图
P（v, G(d)）	转发图G（d）的故障保护率
bestn(v, d)	结点v到结点d的最优下一跳
backn(v, d)	结点v到结点d的备份下一跳

下载: 导出CSV

| 显示表格

2.1 网络模型

本文使用无向图G=（V, E）来表示一个网络，其中V是无向图中的结点集合，代表网络中的路由器，E是无向图中的边集合，代表网络中的链路. 对于网络中的任意一个结点 $v \in V$ ，bestn（v, d）表示结点v到结点d的最优下一跳，backn（v, d）表示结点v到结点d的备份下一跳. 下面给出反向最短路径树、转发图、故障保护率和路径拉伸度的定义.

定义1. 反向最短路径树. 对于目的结点d，其余结点到目的结点d都具有最短路径的树. r（d）表示目的地址为d的反向最短路径树.

定义2. 转发图. 按照一定的规则遍历无环路的有向图. G（d）表示目的地址为d的转发图.

定义3. 在转发图G（d）中，对于任意的结点 $v \in V,v \ne d$ ，如果v到d的最优下一跳出现故障，v依然可以到达目的地址d，我们称在G（d）中结点v可以被保护，否则结点v未被保护.

定义4. 转发图G（d）的故障保护率可以表示为 $P(v,G(d)) = \dfrac{{\displaystyle\sum\limits_{v \in V} {f(v,d)} }}{{|V| - 1}}$ ，其中当结点v被保护时f（v, d）=1，否则f（v, d）=0.

定义5. 路径拉伸度. 当网络出现故障时，利用路由保护算法计算出的所有源目的对之间的代价总和与利用最短路径计算出的所有源目的对之间的代价总和的比值.

我们通过一个简单的例子解释上面的定义1~5. 图1表示网络拓扑结构，链路上的数字表示该链路对应的代价. 图2表示以结点d为根的反向最短路径树，实线表示在反向最短路径树中的边，从图2中可以计算出每个结点到目的结点d的最优下一跳. 例如，f到d的最优下一跳可以表示为bestn（f, d）=c, k到d的最优下一跳是bestn（k, d）=j. 图3是以d为目的地址的转发图，从图3中可以计算出每个结点到目的结点d的备份下一跳. 在图3中实线箭头表示结点的最优下一跳，空心箭头表示结点的备份下一跳. 例如，f到d的备份下一跳可以表示为backn（f, d）=e, k到d的备份下一跳可以表示为backn（k, d）=h. 转发图是如何构造出来的，为什么利用转发图可以计算出结点的备份下一跳将在后面的章节中详细介绍.

图 1 网络拓扑结构

Figure 1. Network topology structure

下载: 全尺寸图片幻灯片

图 2 反向最短路径树

Figure 2. Reverse shortest path tree

下载: 全尺寸图片幻灯片

图 3 转发图

Figure 3. Forwarding graph

下载: 全尺寸图片幻灯片

2.2 问题描述

为了解决已有路由保护算法存在的4个问题，我们形式化地描述了本文需要解决的科学问题. 在已知网络拓扑结构G=（V, E）的前提条件下，对于目的结点 $d \in V$ ，如何构造一组转发图G（d）包含反向最短路径树r（d），从而使得故障保护率最高. 该问题可以形式化表示为

$\mathrm{Maximize} \frac{{\displaystyle \sum _{d\in V}{\displaystyle \sum _{v\in V,v\ne d}P(v,G(d))}}}{\left|V\right|}，$

(1)

$\mathrm{s}.\mathrm{t}.\quad G(d) \supseteq r(d)，$

(2)

其中式（1）为目标函数，即最大化故障保护率；式（2）表示反向最短路径树属于转发图.

3. 转发算法

在构造转发图的过程中，需要解决2个关键问题：1）如何设计遍历算法，即转发算法；2）如何给转发图中链路设置方向，从而使得该转发图包含反向最短路径树.

3.1 转发算法规则

对于问题1我们采用互联网部署的路由转发算法，这样设计的算法和互联网是兼容的，便于实际部署. 我们对转发算法进行简单地描述：在网络中，当路由器收到一个报文后，就会根据报文中目的地址的信息从路由表中查找对应的下一跳，然后将该报文直接发送给对应的下一跳. 具体的转发规则为：

1）如果最优下一跳路由器发生了故障，就从备份路由表中查找备份下一跳，将报文发送给备份下一跳；

2）如果收到的报文来自最优下一跳，也将报文发送给备份下一跳；

3）其他情况均将报文发送给最优下一跳.

下面通过一个例子来解释转发算法. 在图3中，假设报文的源地址是c，目的地址是d，当结点a出现故障时，结点c将报文转发给备份下一跳f，结点f发现该报文来自于自己的最优下一跳c，因此结点f将报文发送给其备份下一跳e，接着结点e将报文转发给最优下一跳b，最后b将报文转发给目的地址d.

3.2 基于遗传算法构造转发图的算法

下面重点描述如何解决问题2. 给定目的地址d，构造G（d）就是为网络拓扑中的链路设定特定的方向. 其中G（d）包含r（d）的条件比较容易实现，只需要在反向最短路径树r（d）的基础上构造转发图即可. 如何保证构造的图是转发图成为本文研究的重点和难点. 构造转发图就是为网络中的链路指定方向，对于网络中的链路 $(u,v) \in E$ ，每条链路有4种状态：第1种状态是该链路不在转发图中；第2种状态是该链路的方向为 $u \to v$ ；第3种状态是该链路的方向为 $v \to u$ ；第4种状态是 $u \to v$ 和 $v \to u$ 都在转发图中，用 $v - u$ 来表示. 如果 $(u,v) \in r（d）$ ，假设链路的方向为 $u \to v$ ，则该链路的状态只有 $u \to v$ 和 $v - u$ 这2种可能性；反之假设链路的方向为 $v \to u$ ，则该链路的状态只有 $v \to u$ 和 $v - u$ 这2种可能性. 通过上述分析可知当链路 $(u,v) \in r（d）$ 时，该链路的状态有2种可能性；当 $(u,v) \notin r（d）$ ，则该链路的状态有4种可能性；对于一个包含|V|个结点、|E|条边的网络拓扑来讲，有|V|−1条链路在反向最短路径树上，|E|+|V|+1条链路不在反向最短路径树上，因此链路状态的数量为 ${2^{|V| - 1}} \times {4^{|E| - |V| + 1}} = {2^{2 \times |E| - |V| + 1}}$ ，如果把所有的链路状态的组合都枚举出来，然后从中选择符合条件的转发图，在实际网络中部署是一种不现实的解决方案.

为了解决该问题，本文提出利用遗传算法来构造转发图，该算法包含2个步骤：1）计算以结点d为根的反向最短路径树r（d）；2）在r（d）的基础上，利用遗传算法构造转发图.

算法1（RPBFG算法）描述了利用遗传算法构造转发图的过程. 算法的输入为网络拓扑结构G=（V, E），输出为每个结点的备份路由表. 下面以目的地址d为例进行描述.RPBFG主要通过3个步骤实现：首先对网络中的链路进行编码，在链路编码的基础上生成初始转发图；然后利用选择、交叉和变异操作计算出最优个体，根据选择的最优个体构造出最优转发图；最后根据最优转发图计算出所有结点的备份下一跳.

算法1. RPBFG算法.

输入：G=（V, E）；

输出：backn（v, d）， $v \in V,v \ne d$ .

① for each $v \in V,v \ne d$

② 　backup（v, d） $\leftarrow \varnothing$ ；

③ end for

④ compute r（d）；

⑤ population $\leftarrow$ InitPopulation（G, d）；

/* 利用r（d）生成初始种群*/

⑥ for each $i \in \{ 1,2,…,m\}$ /*算法迭代次数*/

⑦　remains $\leftarrow$ RouWheelSel（population）；

⑧　children $\leftarrow \varnothing$ ；

⑨　for each parentA $\in$ remains

⑩　　parentB $\in$ random_select_remains；

⑪　　child $\leftarrow$ Cross（parentA, parentB）；

⑫　　child $\leftarrow$ Mutate（child）；

⑬　　children $\leftarrow$ children $\cup$ {child}；

⑭　　population $\leftarrow$ children $\cup$ remains；

⑮　end for

⑯ end for

⑰ FG $\leftarrow$ ComputeFG（Best（population））；

⑱ for each $v \in V,v \ne d$

⑲　backup（v, d） $\leftarrow$ ComputeBackup（FG）；

⑳ end for

㉑ return backup（v, d）， $v \in V,v \ne d.$

在介绍RPBFG之前，我们描述链路编码的算法和适应度函数. 首先描述链路编码的算法. 对于网络中的链路 $(u,v) \in E$ ，用2位二进制编码来表示链路的状态：因此每条链路有4种状态：00表示该链路不在转发图中，01表示该链路的方向为 $u \to v$ ，10表示该链路的方向为 $v \to u$ ,11表示该链路的方向为 $v - u$ . 例如网络中有5条链路，分别是（a, b）,（b, c）,（c, d）,（a, d）,（b, d），如果对应的链路编码为（1001101101），则表示链路（a, b）的方向为 $a \to b$ ，链路（b, c）的方向为 $c \to b$ ，链路（c, d）的方向为 $c \to d$ ，链路（a, d）的方向为 $a \to d$ ，链路（b, d）的方向为 $d \to b$ . 然后描述适应度函数. 为了保证RPBFG在满足最大化故障保护率的同时，尽可能降低重路由路径的路径拉伸度，本文的适应度函数=故障保护率+0.001×路径拉伸度. 下面详细介绍算法RPBFG的执行过程，如算法1所示. 将备份下一跳集合初始化为空（行①~③）；对于网络中的结点 $d \in V$ ，利用迪杰斯特拉算法计算反向最短路径树r（d）（行④）. 行⑤表示生成初始化种群，本文利用r（d）生成初始种群，所有种群的规模数为N，所有初始种群的编码相同. 遗传算法的迭代过程中迭代次数为m（行⑥），在每次迭代中，利用轮盘赌算法^[29]进行选择操作，该算法根据个体的适应度和累计概率计算个体被选择的概率，轮盘赌选择中个体的适应度越好越有可能被保留，如果要保留n个个体，则在现有的2n个个体中进行n次有放回抽样，每次抽样中每个个体被抽中的概率为 $p_i ={{{f_i}}}\big/{{\displaystyle\sum\limits_{j = 1}^N {{f_j}} }}$ ，其中p_i表示该个体被保留的概率，f_i表示该个体的适应度， $\displaystyle\sum\limits_{j = 1}^N {{f_j}}$ 表示所有个体适应度之和（行⑦ ）. 行⑪和行⑫分别表示交叉和变异操作. 本文使用的交叉方法为多点交叉. 具体方法为：首先将要执行交叉的2个个体分别表示为A和B，然后随机选择若干个位置（每个位置被选择的概率是提前设置好的），将这些位置记为{i₁,i₂,…,i_n}，而后将A和B中的{i₁,i₂,…,i_n}位置上的基因相互交换. 算法1中使用2个位置的基因表示1条边的方向，所以在交叉互换的过程中将基因两两视为一个整体，以确保边的方向信息作为整体被交换.

本文采用的变异方法为：用变异率p表示基因变异的概率，当1个染色体发生变异时，它的每个基因都按照概率p发生变异，当某个位置的基因发生变异时，如果基因未变异概率为1，则基因概率变异为0，反之，如果基因未变异概率为0，则基因概率变异为1. 为了保证变异后的染色体所表示的转发图不产生路由环路，在每次变异后都会检查其是否产生了环路，如果这次变异导致了环路，那就将该基因还原. 需要注意的是，染色体中表示最短路径树中有向边的基因不会发生变异，因为这些基因表示的是最优下一跳. 当迭代部分执行完毕以后，根据最优个体Best（population）中链路的方向利用ComputeFG（Best（population））计算出转发图（行⑰）；然后利用该转发图为网络中的其他结点计算到达目的地址d的备份下一跳，为结点 $v \in V,v \ne d$ 计算备份下一跳的算法如下：遍历结点v的不是最优下一跳的邻居结点v，如果该边的编码为10或者11，则结点u可以将结点v作为备份下一跳（行⑱~⑳）. 当算法1执行完毕以后，返回所有结点到达目的结点d的备份下一跳集合（行㉑）.

下面分析算法的时间复杂度. 算法1的行①~③的时间复杂度为 $O(|V|)$ ，行④的时间复杂度为 $O(|V|\lg |V| + |E|)$ ，行⑤的时间复杂度为 $O(N)$ ，行⑥~⑯的时间复杂度为 $O(N \times m)$ ，行⑰的时间复杂度为 $O(|E|)$ ，行⑱~⑳的时间复杂度为 $O(|V|)$ ，RPBFG的总时间复杂度为 $O(|V|)$ + $O(|V|\lg |V| + |E|)$ + $O(N)$ + $O(N \times m)$ + $O(|E|)$ + $O(|V|)$ ，即 $O(|V|\lg |V| + 2|E|{\text{ + }}N \times m)$ .

4. 实验及结果分析

本节将RPBFG与NPC，U-turn，MARA-MA，MARA-SPE进行比较，采用Python实现这5种算法. 实验采用了11种真实的网络拓扑结构^[30]，如表3所示，使用真实拓扑结构使得实验结果更加真实准确. 实验采用的度量指标包括故障保护率和路径拉伸度. 故障保护率反映了算法应对网络中发生故障的能力，该值越大说明算法应对故障的能力越强. 路径拉伸度表示当网络出现故障以后，重路由路径的代价和最短路径的代价的比值，该值越小说明利用路由保护算法计算出的路径代价和利用最短路径计算出的路径代价接近，给网络带来的额外开销越低.

表 3 真实网络拓扑

Table 3. Real Network Topology

网络拓扑	结点的数量	边的数量
Abilene	11	14
Ans	17	24
Arpanet19719	18	22
Arpanet19723	24	27
Arpanet19728	29	32
AttMpls	25	56
Belnet2004	18	34
Cernet	14	16
Agis	16	21
NJLATA	11	23
USLD	28	45

下载: 导出CSV

| 显示表格

4.1 故障保护率

本节比较算法RPBFG，NPC，U-turn，MARA-MA，MARA-SPE的故障保护率. 图4描述了5种算法在11个真实网络拓扑图中的故障保护率. 在所有实验的网络拓扑结构中RPBFG的故障保护率均为1.0，NPC，U-turn，MARA-MA，MARA-SPE的故障保护率均低于1.0. 例如，在Abilene中，NPC，U-turn，MARA-MA，MARA-SPE对应的故障保护率分别是0.48 ，0.75， 0.85 ，0.88，在Arpanet 19728中， NPC，U-turn，MARA-MA，MARA-SPE对应的故障保护率分别是0.07，0.23 ，0.81 ，0.84. 这是因为NPC，U-turn，MARA-MA，MARA-SPE使用一定的规则计算备份下一跳，因为这些规则和网络拓扑结构密切相关，在某些网络拓扑结构中无法为所有的源目的结点对计算符合这些规则的备份下一跳. 而RPBFG与网络拓扑无关，只要网络中存在的路径可以到达目的地址，RPBFG就可以计算出相应的重路由路径.

图 4 不同算法在真实拓扑中的故障保护率

Figure 4. Failure protection ratio of different algorithms in real topologies

下载: 全尺寸图片幻灯片

4.2 路径拉伸度

在计算路径拉伸度的过程中，为了体现公平性，只考虑2个算法都能保护的路径. 具体计算算法为：算法A可以保护所有源目的结点对的集合 $\alpha$ ，算法B可以保护所有源目的结点对集合 $\beta$ ，这2个集合的交集 $C = \alpha \cap \beta$ 就是需要计算的源目的结点对集合. 表4列出了RPBFG和NPC的路径拉伸度的平均值和方差. 表5列出了RPBFG和U-turn的路径拉伸度的平均值和方差. 表6列出了RPBFG和MARA-MA的路径拉伸度的平均值和方差. 表7列出了RPBFG和MARA-SPE的路径拉伸度的平均值和方差. 从表4~7可以看出，RPBFG的路径拉伸度的平均值和方差几乎明显低于其余4种算法. 在平均路径拉伸度方面，RPBFG比NPC，U-turn，MARA-MA，MARA-SPE分别降低了0.11%，0.72%，37.79%，36.26%.

表 4 NPC和PBFG路径拉伸度比较结果

Table 4. Comparison Result of Path Stretch for NPC and RPBFG

网络拓扑	NPC		RPBFG（本文）
网络拓扑	平均值	方差	平均值	方差
Abilene	1.0042	0.0334	1.0027	0.0208
Ans	1.0019	0.0205	1.0015	0.0191
Arpanet19719	1.0008	0.0125	1.0006	0.0110
Arpanet19723	1.0002	0.0044	1.0001	0.0041
Arpanet19728	1.0000	0.0009	1.0000	0.0010
AttMpls	1.0029	0.0269	1.0004	0.0121
Belnet2004	1.0000	0.0000	1.0000	0.0000
Cernet	1.0000	0.0000	1.0000	0.0000
Agis	1.0012	0.0165	1.0020	0.0269
NJLATA	1.0068	0.0427	1.0002	0.0026
USLD	1.0034	0.0270	1.0018	0.0201

下载: 导出CSV

| 显示表格

表 5 U-turn和RPBFG路径拉伸度比较结果

Table 5. Comparison Result of Path Stretch for U-turn and RPBFG

网络拓扑	U-turn		RPBFG（本文）
网络拓扑	平均值	方差	平均值	方差
Abilene	1.0206	0.1077	1.0116	0.0677
Ans	1.0198	0.0971	1.0119	0.0736
Arpanet19719	1.0153	0.0768	1.0123	0.0689
Arpanet19723	1.0097	0.0558	1.0096	0.0562
Arpanet19728	1.0032	0.0309	1.0039	0.0408
AttMpls	1.0216	0.1573	1.0016	0.0258
Belnet2004	1.0079	0.0977	1.0000	0.0000
Cernet	1.0143	0.0877	1.0143	0.0877
Agis	1.0139	0.0871	1.0114	0.0727
NJLATA	1.0226	0.1237	1.0001	0.0022
USLD	1.0155	0.0806	1.0069	0.0469

下载: 导出CSV

| 显示表格

表 6 MARA-MA和RPBFG路径拉伸度比较结果

Table 6. Comparison Result of Path Stretch for MARA-MA and RPBFG

网络拓扑	MARA-MA		RPBFG（本文）
网络拓扑	平均值	方差	平均值	方差
Abilene	1.5751	1.3749	1.0124	0.0737
Ans	1.6528	1.1185	1.0083	0.0599
Arpanet19719	1.2989	0.5774	1.0189	0.0970
Arpanet19723	1.3634	0.7351	1.0188	0.0939
Arpanet19728	1.3767	0.8556	1.0311	0.1455
AttMpls	2.2332	1.1413	1.0018	0.0275
Belnet2004	1.2587	0.2752	1.0000	0.0000
Cernet	1.6748	1.3387	1.0136	0.0925
Agis	1.4022	0.6273	1.0080	0.0616
NJLATA	1.7628	0.8202	1.0003	0.0045
USLD	2.2750	1.9101	1.0058	0.0415

下载: 导出CSV

| 显示表格

表 7 MARA-SPE和RPBFG路径拉伸度比较结果

Table 7. Comparison Result of Path Stretch for MARA-SPE and RPBFG

网络拓扑	MARA-SPE		RPBFG（本文）
网络拓扑	平均值	方差	平均值	方差
Abilene	1.5687	1.0068	1.0247	0.1066
Ans	1.5604	1.0055	1.0098	0.0648
Arpanet19719	1.1971	0.4711	1.0124	0.0767
Arpanet19723	1.2304	0.4412	1.0209	0.0984
Arpanet19728	1.2754	0.7457	1.0280	0.1383
AttMpls	2.1765	1.0243	1.0024	0.0310
Belnet2004	1.3648	0.4243	1.0000	0.0000
Cernet	1.7156	1.4256	1.0134	0.0905
Agis	1.4858	0.7040	1.0110	0.0744
NJLATA	1.7442	0.8013	1.0003	0.0045
USLD	2.1411	1.6796	1.0056	0.0403

下载: 导出CSV

| 显示表格

5. 结　　论

为了应对网络中频繁出现的故障，本文提出了一种基于转发图的域内路由保护算法（RPBFG），该算法通过构造最优转发图应对网络故障. 与已有路由保护算法不同，RPBFG仅为每个结点存储1个备份下一跳，这样可以大大降低存储开销. 我们首先描述了需要解决的关键科学问题；然后理论分析直接求解的复杂度；接着采用遗传算法来解决提出的问题，从而降低求解的复杂度；最后在11个真实拓扑中对RPBFG的性能进行了测试. 仿真测试表明该算法可以应对网络中所有可能的单故障情形，并且具有较小的路径拉伸度. RPBFG是一种域内路由保护算法，在未来的工作中将研究如何将RPBFG的核心思想应用到域间路由保护算法中，从而进一步提高网络的可用性.

作者贡献声明：耿海军提出了算法思路和实验方案，并撰写论文；孟卓负责执行实验方案；姚珊珊参与实验方案指导和对部分实验结果分析；杨静参与论文校对和实验方案指导；池浩田提出了指导意见并修改论文；尹霞提出方法的指导意见和审核论文.

图 1 公平性测量系统

Figure 1. Fairness measurement system

下载: 全尺寸图片幻灯片

图 2 Zoom、Bilibili和iPerf在不同带宽限制下竞争时的吞吐量占比和Zoom的吞吐量构成

Figure 2. Throughput ratio of Zoom, Bilibili and iPerf when competing under different restricted bandwidth, and throughput composition of Zoom

下载: 全尺寸图片幻灯片

图 3 在1 Mbps限制带宽下竞争时Zoom的吞吐量、卡顿持续时间和探测包数

Figure 3. Zoom’s throughput, stall duration and probing packet count under the 1 Mbps restricted bandwidth

下载: 全尺寸图片幻灯片

图 4 Zoom、Bilibili和iPerf在不同丢包率限制下竞争时的吞吐量占比和Zoom的吞吐量构成

Figure 4. Throughput ratio of Zoom, Bilibili and iPerf when competing under different restricted packet loss rate, and throughput composition of Zoom

下载: 全尺寸图片幻灯片

图 5 Zoom、Bilibili和iPerf在不同缓存大小限制下竞争时的吞吐量占比和Zoom吞吐量构成

Figure 5. Throughput ratio of Zoom, Bilibili and iPerf when competing under different restricted buffer size, and throughput composition of Zoom

下载: 全尺寸图片幻灯片

图 6 Zoom、Bilibili和iPerf在不同启动顺序下竞争时的吞吐量占比和Zoom的吞吐量构成. （A：Zoom，B：Bilibili，C：iPerf. ABC表示先启动Zoom，然后是Bilibili，最后是iPerf. 其他表达式的含义可以类推）

Figure 6. Throughput ratio of Zoom, Bilibili and iPerf when competing with different start order, and throughput composition of Zoom (A: Zoom, B: Bilibili, C: iPerf. ABC means that we start Zoom first, then Bilibili, and finally iPerf. The meaning of other expressions can be deduced by analogy)

下载: 全尺寸图片幻灯片

图 7 在不同带宽限制下竞争时Zoom和Bilibili的QoE表现

Figure 7. QoE performances of Zoom and Bilibili when competing under different restricted bandwidth

下载: 全尺寸图片幻灯片

图 8 在不同丢包率限制下竞争时Zoom和Bilibili的QoE表现

Figure 8. QoE performances of Zoom and Bilibili when competing under different packet loss rate

下载: 全尺寸图片幻灯片

图 9 在不同缓存大小限制下竞争时Zoom和Bilibili的QoE表现

Figure 9. QoE performances of Zoom and Bilibili when competing under different buffer size

下载: 全尺寸图片幻灯片

图 10 在不同启动顺序下竞争时Zoom和Bilibili的QoE表现（A：Zoom，B：Bilibili，C：iPerf. ABC表示先启动Zoom，然后是Bilibili，最后是iPerf. 其他表达式的含义可以类推）

Figure 10. QoE performances of Zoom and Bilibili when competing with different start order (A: Zoom, B: Bilibili, C: iPerf. ABC means that we start Zoom first, then Bilibili, and finally iPerf. The meaning of other expressions can be deduced by analogy)

下载: 全尺寸图片幻灯片

图 11 状态转移机

Figure 11. State transition machine

下载: 全尺寸图片幻灯片

图 12 QLibra和Zoom在1000 kbps带宽限制和10%丢包率限制下竞争时的吞吐量

Figure 12. The throughputs when QLibra and Zoom competing under 1000 kbps restricted bandwidth and 10% restricted packet loss rate

下载: 全尺寸图片幻灯片

图 13 QLibra和Bilibili在1000 kbps带宽限制和10%丢包率限制下竞争时的吞吐量

Figure 13. The throughput when QLibra and Bilibili competing under 1000 kbps restricted bandwidth and 10% restricted packet loss rate

下载: 全尺寸图片幻灯片

图 14 QLibra和原生Reno在1000 kbps带宽限制和10%丢包率限制下竞争时的吞吐量

Figure 14. The throughput when QLibra and original Reno competing under 1000 kbps restricted bandwidth and 10% restricted packet loss rate

下载: 全尺寸图片幻灯片

图 15 QLibra，Zoom和原生Reno在1000 kbps带宽限制和10%丢包率限制下竞争时的吞吐量

Figure 15. The throughput when QLibra, Zoom and original Reno competing under 1000 kbps restricted bandwidth and 10% restricted packet loss rate

下载: 全尺寸图片幻灯片

参考文献(55)

[1]	Zhang H. Service disciplines for guaranteed performance service in packet-switching networks[J]. Proceedings of the IEEE, 1995, 83(10): 1374−1396 doi: 10.1109/5.469298
[2]	Shenker S. Fundamental design issues for the future Internet[J]. IEEE Journal on Selected Areas in Communications, 1995, 13(7): 1176−1188 doi: 10.1109/49.414637
[3]	Ware R, Mukerjee M K, Seshan S, et al. Beyond Jain’s fairness index: Setting the bar for the deployment of congestion control algorithms[C] //Proc of the 18th ACM Workshop on Hot Topics in Networks (HotNets). New York: ACM,2019: 17−24
[4]	Index C V N. Forecast and methodology 2017-2022[R]. San Jose, CA, USA: Cisco, 2019
[5]	Kunze I, Rüth J, Hohlfeld O. Congestion control in the wild-investigating content provider fairness[J]. IEEE Transactions on Network and Service Management, 2019, 17(2): 1224−1238
[6]	Langley A, Riddoch A, Wilk A, et al. The QUIC transport protocol: Design and Internet-scale deployment[C]//Proc of the Conf of the ACM Special Interest Group on Data Communication (SIGCOMM). New York: ACM, 2017: 183−196
[7]	Floyd S. RFC 5166: Metrics for the evaluation of congestion control mechanisms[Z]. 2008
[8]	Floyd S, Handley M, Padhye J, et al. RFC 5348: TCP friendly rate control (TFRC): Protocol specification[Z]. 2008
[9]	Handley M. Keynote[C] //Proc of the ACM Special Interest Group on Data Communication (SIGCOMM). New York: ACM, 2019: 1-1
[10]	Sundaresan S, Allman M, Dhamdhere A, et al. TCP congestion signatures[C] //Proc of the 2017 Int Measurement Conf (IMC). New York: ACM, 2017: 64−77
[11]	Sundaresan S, Deng X, Feng Y, et al. Challenges in inferring Internet congestion using throughput measurements[C] //Proc of the 2017 Int Measurement Conf (IMC). New York: ACM, 2017: 43−56
[12]	Mohan N, Corneo L, Zavodovski A, et al. Pruning edge research with latency shears[C] //Proc of the 19th ACM Workshop on Hot Topics in Networks (HotNets). New York: ACM, 2020: 182−189
[13]	Zoom. Zoom video communications[EB/OL].(2011-04-21)[2023-01-01]. https://zoom.us
[14]	Bilibili. Bilibili live streaming[EB/OL]. (2009-06-26)[2023-01-01]. https://www.bilibili.com
[15]	iPerf. Tool for active measurements of the maximum achievable bandwidth on IP networks[EB/OL].(2014-01-01)[2023-01-01]. https://iperf.fr
[16]	Wireshark. Network protocol analyzer[EB/OL]. (2006-05-01)[2023-01-01]. https://www.wireshark.org
[17]	Netflix. Video Multi-Method Assessment Fusion (VMAF)[EB/OL]. (2016-06-01)[2023-01-01]. https://github.com/Netflix/vmaf
[18]	Denso Wave. QR code[EB/OL]. (1997-10-01)[2023-01-01]. https://www.qrcode.com
[19]	Goldwave. Digital Audio Editing Software[EB/OL].(1993-04-01)[2023-01-01]. https://www.goldwave.com
[20]	Liu Q, Jia Z, Jin K, et al. Error resilience for Interactive Real-Time Multimedia Applications[P]. U.S. patent 9, 813, 193, 2017
[21]	Ha S, Rhee I, Xu L. Cubic: A new TCP-friendly high-speed TCP variant[J]. ACM SIGOPS Operating Systems Review, 2008, 42(5): 64−74 doi: 10.1145/1400097.1400105
[22]	Hock M, Bless R, Zitterbart M. Experimental evaluation of BBR congestion control[C] //Proc of the 2017 IEEE 25th Int Conf on Network Protocols (ICNP). Piscataway, NJ: IEEE, 2017: 1−10
[23]	Ware R, Mukerjee M K, Seshan S, et al. Modeling BBR’s interactions with loss-based congestion control[C] //Proc of the Int Measurement Conf (IMC). New York: ACM, 2019: 137−143
[24]	Cardwell N, Cheng Y, Gunn C S, et al. BBR: Congestion-based congestion control: Measuring bottleneck bandwidth and round-trip propagation time[J]. Queue, 2016, 14(5): 20−53 doi: 10.1145/3012426.3022184
[25]	Dong M, Meng T, Zarchy D, et al. PCC vivace: Online-learning congestion control[C] //Proc of the 15th USENIX Symp on Networked Systems Design and Implementation (NSDI). Berkeley, CA: USENIX Association, 2018: 343−356
[26]	Arun V, Balakrishnan H. Copa: Practical delay-based congestion control for the Internet[C] //Proc of the 15th USENIX Symp on Networked Systems Design and Implementation (NSDI). Berkeley, CA: USENIX Association, 2018: 329−342
[27]	Jiang J, Sekar V, Zhang H. Improving fairness, efficiency, and stability in HTTP-based adaptive video streaming with FESTIVE[C] //Proc of the 8th Int Conf on Emerging Networking Experiments and Technologies (CoNEXT). New York: ACM, 2012: 97−108
[28]	Akhshabi S, Anantakrishnan L, Begen A C, et al. What happens when HTTP adaptive streaming players compete for bandwidth?[C] //Proc of the 22nd Int Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV). New York: ACM, 2012: 9−14
[29]	Huang T Y, Handigol N, Heller B, et al. Confused, timid, and unstable: Picking a video streaming rate is hard[C] //Proc of the 2012 Int Measurement Conf (IMC). New York: ACM, 2012: 225−238
[30]	MacMillan K, Mangla T, Saxon J, et al. Measuring the performance and network utilization of popular video conferencing applications[C] //Proc of the 21st ACM Int Measurement Conf (IMC). New York: ACM, 2021: 229−244
[31]	Sander C, Kunze I, Wehrle K, et al. Video conferencing and flow-rate fairness: A first look at Zoom and the impact of flow-queuing AQM[C] //Proc of the Int Conf on Passive and Active Network Measurement (PAM). Berlin: Springer, 2021: 3−19
[32]	Yan J, Katrinis K, May M, et al. Media-and TCP-friendly congestion control for scalable video streams[J]. IEEE Transactions on Multimedia, 2006, 8(2): 196−206 doi: 10.1109/TMM.2005.864265
[33]	Nathan V, Sivaraman V, Addanki R, et al. End-to-end transport for video QoE fairness[C] //Proc of the ACM Special Interest Group on Data Communication (SIGCOMM). New York: ACM, 2019: 408−423
[34]	Georgopoulos P, Elkhatib Y, Broadbent M, et al. Towards network-wide QoE fairness using openflow-assisted adaptive video streaming[C] //Proc of the 2013 ACM SIGCOMM Workshop on Future Human-Centric Multimedia Networking. New York: ACM, 2013: 15−20
[35]	Chen J, Ammar M, Fayed M, et al. Client-driven network-level QoE fairness for encrypted “DASH-S”[C] //Proc of the 2016 ACM SIGCOMM workshop on QoE-Based Analysis and Management of Data Communication Networks. New York: ACM, 2016: 55−60
[36]	Mu M, Broadbent M, Farshad A, et al. A scalable user fairness model for adaptive video streaming over SDN-assisted future networks[J]. IEEE Journal on Selected Areas in Communications, 2016, 34(8): 2168−2184 doi: 10.1109/JSAC.2016.2577318
[37]	李杰,张静,李伟东,等. 一种基于共享公平和时变资源需求的公平分配策略[J]. 计算机研究与发展,2019,56(7):1534−1544 Li Jie, Zhang Jing, Li Weidong, et al. A fair distribution strategy based on shared fair and time-varying resource demand[J]. Journal of Computer Research and Development, 2019, 56(7): 1534−1544 (in Chinese)
[38]	Xu S, Sen S, Mao Z M, et al. Dissecting VOD services for cellular: Performance, root causes and best practices[C] //Proc of the 2017 Int Measurement Conf (IMC). New York: ACM, 2017: 220−234
[39]	Li Z, Lin J, Akodjenou M I, et al. Watching videos from everywhere: a study of the PPTV mobile VoD system[C] //Proc of the 2012 Int Measurement Conf (IMC). New York: ACM, 2012: 185−198
[40]	Ghasemi M, Kanuparthy P, Mansy A, et al. Performance characterization of a commercial video streaming service[C]//Proc of the 2016 Int Measurement Conf (IMC). New York: ACM, 2016: 499−511
[41]	Dimopoulos G, Leontiadis I, Barlet-Ros P, et al. Measuring video QoE from encrypted traffic[C] //Proc of the 2016 Int Measurement Conf (IMC). New York: ACM, 2016: 513−526
[42]	Wang B, Zhang X, Wang G, et al. Anatomy of a personalized livestreaming system[C] //Proc of the 2016 Int Measurement Conf (IMC). New York: ACM, 2016: 485−498
[43]	Siekkinen M, Masala E, Kämäräinen T. A first look at quality of mobile live streaming experience: The case of Periscope[C] //Proc of the 2016 Int Measurement Conf (IMC). New York: ACM, 2016: 477−483
[44]	Chen Q A, Luo H, Rosen S, et al. QoE doctor: Diagnosing mobile APP QoE with automated UI control and cross-layer analysis[C] //Proc of the 2014 Int Measurement Conf (IMC). New York: ACM, 2014: 151−164
[45]	Dimopoulos G, Leontiadis I, Barlet-Ros P, et al. Identifying the root cause of video streaming issues on mobile devices[C] //Proc of the 11th ACM Conf on Emerging Networking Experiments and Technologies (CoNEXT). New York: ACM, 2015: 1−13
[46]	Shafiq M Z, Erman J, Ji L, et al. Understanding the impact of network dynamics on mobile video user engagement[J]. ACM SIGMETRICS Performance Evaluation Review, 2014, 42(1): 367−379 doi: 10.1145/2637364.2591975
[47]	Hohlfeld O, Pujol E, Ciucu F, et al. A QoE perspective on sizing network buffers[C] //Proc of the 2014 Int Measurement Conf (IMC). New York: ACM, 2014: 333−346
[48]	Yu C, Xu Y, Liu B, et al. “Can you see me now?” a measurement study of mobile video calls[C] //Proc of IEEE Conf on Computer Communications (IEEE INFOCOM 2014). Piscataway, NJ: IEEE, 2014: 1456−1464
[49]	Xu Y, Yu C, Li J, et al. Video telephony for end-consumers: Measurement study of Google+, iChat, and Skype[C] //Proc of the 2012 Int Measurement Conf (IMC). New York: ACM, 2012: 371−384
[50]	Jansen B, Goodwin T, Gupta V, et al. Performance evaluation of webrtc-based video conferencing[J]. ACM SIGMETRICS Performance Evaluation Review, 2018, 45(3): 56−68 doi: 10.1145/3199524.3199534
[51]	Chang H, Varvello M, Hao F, et al. Can you see me now? a measurement study of Zoom, Webex, and Meet[C] //Proc of the 21st ACM Int Measurement Conf (IMC). New York: ACM, 2021: 216−228
[52]	Lloyd W F. Two Lectures on the Checks to Population[M]. Oxford: J.H. Parker, 1833.
[53]	Nagle J. RFC 896: Congestion control in IP/TCP internetworks[Z]. 1984
[54]	Philipp H. How Zoom’s web client avoids using WebRTC (datachannel update)[EB/OL]. (2019-09-08)[2023-01-01]. https://webrtchacks.com/zoom-avoids-using-webrtc
[55]	Briscoe B. Flow rate fairness: Dismantling a religion[J]. ACM SIGCOMM Computer Communication Review, 2007, 37(2): 63−74 doi: 10.1145/1232919.1232926