Abstract & 1 Introduction
视频网站类型多样，需求各异。有“mega-events”类型的：用户数量巨大，都看同一个内容，例如世界杯；也有long-tail类型的：非流行的内容很多，以至于它们的总和可以与最流行的内容匹敌，例如twitch游戏直播
本文设计的VDN是专用于视频的CDN
CCS Concepts
优化视频传输的方法：
1、Traffic-engineer：全局统筹拥塞问题。延迟比较大
2、overlay：视频之间自己优化、互相竞争。都只考虑自己的优化，不考虑全局
3、CDN
参考[32]：centralized controller could improve end-user experience[32]，本文设计的控制层是centralized + distributed的混合
本文着重满足的用户需求：1) fast join times, high bitrates, lost delivery cost; 2) 对网络异常的快速反应与处理。
2 Motivation （提了杂七杂八的一堆点，没什么意义）
*关于HTTP-based的live流，对一个video先定bitrate，再编码，再切片；client进行多次GET、自取需要的bitrate
CDN的负载从web-oriented转到live流时，用DNS来映射请求是很自然的。因为大多数live内容是内嵌于网页的，本身就会用DNS
一般IP网络的DNS要找的source，而CDN的DNS找到的可能是附近的边缘节点（出于负载和延迟的因素），边缘节点再找到source
但是，使用DNS将请求映射到适当的上游集群的问题：
1）CDN不能将更新“推送”到集群，而是等待集群在超时时间（DNS TTL）之后从DNS“拉”（不能主动报告故障、内容更新）
2）为了减少DNS上的负载，CDN将不同的流组合在一起，减少粒度[29,40]
3）此外，CDN使用启发式算法更新DNS映射[2，29，35，40]，影响性能
DNS的TTL：一个域名解析记录在DNS服务器中的存留时间
因为域名一般不会更改，TTL长的话，一般就不用花时间重新临时查找域名，但若这期间域名更改／发生拥塞，则会发生错误／拥塞，还是需要重新查找（类似于NDN里的断路）
DNS设置TTL的意义：对缓存的DNS发出请求后，如果在TTL（1～30s）内还没有回应，则要求更新（由“断路”处节点运行分布式控制算法（§4）），而不需要central controller发送更新（*这降低了central controller的efficacy，从而降低了边缘用户体验质量和对故障的反应速度）
如果TTL太长（“断路”处节点处理太慢，最后应该就成了超时user重发请求），CDN群集可能远在更新到达之前就发现本地网络故障；如果TTL太短（由“断路”处节点迅速另找出路发送所有请求），更逼近基于“push”的系统（更能相对即时、主动报告故障），但是代价是大量增加DNS查询的数量
关于DNS如何工作：基于启发式（这个词不用关心）的映射算法
1、监控系统收集性能和负载信息，每分钟更新DNS系统[35]（收集与更新原始数据）
2、通常，CDN根据地理位置等原始数据，将最终用户映射到边缘集群[2,29,35,40]
但是，具体的算法不太为人关注。实际上，算法提供的映射方案不够好：多个用户集中在同一集群了（然而本文也没有具体解决这一问题）
处理mega-events相对简单，只需对所有用户构建一棵树；处理long-tail内容最困难，因为需要协调许多视频。目前规模达到10,000个频道[40]和2000个边缘集群[17]，超出了当今最大的CDN规模。这种规模具有挑战性，因为找到最佳的放置的算法是NP-hard的
协调（Coordination）：参见Figure 3～5，证明集中式的全局优化是优于局部优化的
为什么使用集中式和分布式的混合：它们各有优势
分布式的优势：新用户刚一加入，可能马上就会发出新的视频请求。相对集中式系统，分布式系统能大大降低连接时间（快速响应）
集中式的优势：分布式系统缺乏协调，集中式能保证high bitrates和low cost
VDN网络里有四层拓扑，期间有严格的上下层次之分（参见Figure 2），请求不会循环传递；另外，VDN把每个集群视为原子单元（参见Figure 6，不考虑集群内的流量）
3 VDN system overview
VDN使用专门的物理实体部分，来基于网络状态计算路径、处理请求
中央控制循环（Central control loop，能看到所有集群、请求和拓扑）：使
- 5中描述的算法计算optimal distribution trees（一种针对流内容的专门算法），来设计视频的转发路径、并填充转发表FIB
分布控制循环（Distributed control loop，只能看到本集群和少量的分布状态）：必要时（为了快速应对局部变化，例如链路故障）快速对群集的转发表进行修改
4 Hybrid control
设置一个FIB表的前身：RIB表（路由信息表），见Figure 7
1、集中式系统计算出RIB表，并附上计算时用到的必要参数、版本号（时间戳）作为“证据”（Evidence）
计算RIB具体采用的是距离矢量路由算法
IP网络的距离矢量路由算法：每个路由器维护一个距离矢量表，然后通过相邻路由器之间的距离矢量通告进行距离矢量表的更新。每个距离矢量表项包括两部分：到达目的结点的最佳输出线路，和到达目的结点所需时间或距离。每隔一段时间，路由器会向所有邻居结点发送它到每个目的结点的距离表，同时它也接收每个邻居结点发来的距离表。这样以此类推，经过一段时间后便可将网络中各路由器所获得的距离矢量信息在各路由器上统一起来，这样各路由器只需要查看这个距离矢量表就可以为不同来源分组找到一条最佳的路由。
CDN中，距离矢量考察的不是节点，而是内容（参数为视频名v和比特率b）之间的距离。我们考察的是实时视频，cache的意义不大，每个节点只用广播自己正在接收的视频
若集群a包含（subscribe）了视频（v1，b1），集群b包含了视频（v2，b2），两个视频之间的距离就是a到b的跳数（如果有两个集群包含了同一个内容，跳数最后能被更新成更近的那个），两个视频之间的容量就是该链路上最窄链路的可用容量
2、分布式系统控制跟踪上游邻居的收视率和路径信息，快速响应局部变化。分布式系统根据节点的当前情况，对RIB进行调整计算出FIB。具体来说，如果满足以下一个或多个条件，则集群会考虑RIB条目过期：
- 证据引用的一个链接的变化超过了设定的某个百分比（例如20％）
- 由超时检测到的断路
- 收到一个没有FIB条目的请求
则使用Figure 8的分布式控制算法（Algorithm 1），将请求转发到具有足够备用路径（基于c值）的视频的“最近”（根据d值）的父节点（表示四层拓扑里的上层节点）；如果父节点也不包含该内容，则迭代下去；如果没有可选节点，算法结束，等待超时重发。It breaks ties randomly to avoid groups of clusters potentially overloading a high capacity cluster after failure. （？？？）该节点用新找到的局部路径作为新的RIB和FIB路径
这个路径也会计入RIB表，但类型标记为D而不是C
*3、关于DNS：DNS根据用户的地理位置和AS进行统计，以便将它们映射到中央控制器计算的正确边缘集群。如果这个特定的AS以前没有分配给边缘集群，则使用简单的启发式来提供合理的起始分配（例如，已经订阅该视频的边缘集群，通常由本地区使用的边缘集群） / AS等）
Discussion部分说明了分布式算法不会干扰中央控制已经实施的决策。对n层结构，走另一条路最多影响上层的n-1条边。另外，集中式系统最后也会发现网络的局部变化，并更新RIB和新的路径，分布式系统不再认为RIB过时时，则不再采用分布式控制算法
5 Centralized optimization
按照Figure 10构建有向图（其实应该是无向图），这可以看成一个01整数规划：所有决策变量均要求为0－1的整数规划
给每个用户（AS）到每个edge连一条虚拟边LAS
参数介绍：
1) 内容用（v，b）描述，每个内容包含bitrate，以及一个优先级权重priority
2) 每条链路l有容量Capacity(l)：带宽；成本Cost(l)：每取消一比特的代价；另设计一个ws（全局给service的权重，在目标函数里与service部分相乘），wc（全局给cost的权重，在目标函数里与cost部分相乘）用于全局的平衡与调控
3) 若AS a请求内容o，则对所有a相连的链路l，记request(l, o) = 1；其他情况下request(l, o) = 0。Request表示视频对象o是否应该通过链路l分布
以上都是常量，只有serves是变量（待求解内容）
Figure 9: Integer program at the controller. 给出了这个01整数规划问题的目标函数和限制条件。inLinks表示上层节点
限制条件（3）意思是，上层没发来内容，则下层不能发内容；上层发来内容，下层也可以不发内容
求全剧最优解可能很耗时，可以使用贪心算法来近似求解；另外，类似于迭代加深，Integer程序先给出一个近似解，然后逐渐逼近最优解。本文考虑了如何在求解效率／近似解质量之间折中，在合适的时候停止继续优化
7 Evaluation
- 用真实的trace评估了high bitrate/low cost折衷性、可扩展性；2) 测试了混合控制的反应速度
本文的亮点：
1、阐述了集中式和分布式系统各自的长处，并将它们结合了起来
2、提出了RIB表，阐述了集中式和分布式系统对RIB表的维护、各自采用的路由策略
3、用线性规划／最大流定量计算，进行了全局性的网络优化