1 Introduction 说明研究的是路由决策
“在过去几年中，我们看到了基于互联网的电话，特别是长途国际电话的急剧增长[5]。基于互联网的音频通话流和Netflix等点播视频流之间的主要区别在于互动。音频通话的实时交互特性使得它们对网络引发的RTT，丢包和抖动（本文研究这三个指标）等问题更为敏感[14]。（见图1）
“应用方面对其有优化方案，但是系统层面还没有。
“另外，可以好好利用当前Internet的骨干网结构。
“真正的解决方案应该是：放弃选择默认路径的传统方案，而是动态选择骨干网中继。我们设想了一个名为VIA的框架，这个框架可以被看作是一个管理覆盖的例子。 VoIP通话可以通过服务提供商（如Skype）部署的管理覆盖（Managed Overlay）服务器进行选择性中继。这种预测性中继选择，与最佳情况对比，可以改善53％的质量受到网络性能差的影响的通话。（贡献1）
“面对时空上显着的性能动态变化以及是否存在大量的中继选择（骨干网可能会超载）。我们开发了一种实用的中继选择方法。它仅以来自历史的表现信息做出这些决定。我们使用通话记录中的性能信息来过滤除最有前途的（top-k）中继替代品之外的所有信息（粗略划出备选集合），然后我们采用在线勘探开发策略来确定最佳中继路径（在备选集合中求最优）。”（贡献2）
*2 网络表现对通话质量的影响
图1显示了三种网络性能指标（RTT，丢包率，抖动）对（归一化）用户派生PCR（poor call rate）的影响。数据显示PCR显著增加所有三个网络指标（相关系数0.97,0.95,0.91），证实了用户感知质量确实对网络性能敏感。
常用的评分标准为MOS，相关的实验已经很多了。
*WAN与无线最后一跳的问题
2.3 空间相关性分析
2.4 时间相关性分析
发现：不良网络上的通话在地理上和时间上都是分散的、动态的（根源探究）
3 管理覆盖系统的潜在优势：怎么了解最优潜力？
VIA注重的是优化网络性能和通话质量（锦上添花），而不是给端到端提供连接（从0到1）
每个通话都可以采用“默认路径”（红色箭头）或“中继路径”（绿色箭头），将流量路由通过DC中的一个或多个中继节点。中继路径可能包括单个中继以“反弹”流量或一对中继，以使流量“通过”管理覆盖网络的专用骨干网。（一般不需要更多的中继）
研究使用的网络全部位于单个AS中（因此所有的中继路径都位于专用WAN内），但遍布全球数十个数据中心和边缘集群。（相当于把全球连接起来的一个骨干网）
当建立一个呼叫时，在主叫方向被叫方发出信号后，主叫方和被叫方都会联系同一个控制器（图7）来确定他们是使用直接路径还是使用中继路径、哪些中继。
贡献1：说明最优情况下中继改进的最佳潜力：
使用“Oracle”控制逻辑来量化VIA的潜在收益。假设它事先知道每个中继选项在给定日期的平均性能，并选择最佳的中继路径（即，最低RTT，丢包率或抖动）oracle的两个简化的假设：（1）中继或网络骨干没有负载限制;（2）每个中继选项的性能测量是其实际性能的无偏样本。（外推法）在§4.7中，将放宽第一个假设。
改进效果：
设RTT≥320ms，丢包率≥ 1.2％，抖动≥12ms的网络为poor network；定义单项的PNR（Poor Network Rate）为单项达到阈值的poor network的比例
目标之一就是减少每个单独度量的PNR。 但是，由于网络指标之间可能存在相关性，改进一个指标可能会增加另一个指标的PNR度量。因此，也集中精力减少三个度量标准的PNR（只要有一个指标达到阈值就算做poor network）
oracle可以帮助减少RTT，丢包率和抖动中位数的30％ – 60％（图8a）。在用户感知质量的情况下，在尾部的减少具有特别重要的意义，而oracle的重新选择尤其能改善尾部通话（高于对中位数通话的改善），接近40％-65％。
图8b描述了对三个单项PNR的改善，和总体PNR的改善（也能改善30%）
为什么需要动态选择中继：控制逻辑是应该动态选择还是静态选择取决于中继决策需要更新的频率。图9显示了中间持续时间的分布情况，30％的AS对的最优中继选择持续不到2天，只有20％的AS对具有相同的最佳中继选项超过20天。
图6：大部分单项poor network的持续性低
它们表明中继的选择应该动态而不是静态地进行。
4 VIA中继决策（贡献2）
中继决策：
控制器根据历史呼叫（由客户端提供）和策略约束（如基于中继预算或当前负载的性能测量）的性能测量结果动态做出决定（第4节）。
为了避免控制器过载，每个客户端都可以缓存中继决策并定期刷新（参见第7节）（就是动态路由表嘛）
提出Strawman（稻草人）方法
设C表示想要优化的一组调用，让R表示可用中继选项的集合。
使用c∈C和r∈R分别表示特定的呼叫和中继选项。令Q(c, r)表示使用r时c的网络度量的期望值（越小越好）。（然而并没有仔细建模）
假定呼叫的中继决定是独立的，因为呼叫的执行不受其他呼叫的中继决定的影响。（因为没有负载限制嘛……）
N个端点和M个中继策略导出O(N^2*M)个选择，最小化问题求解
如果根据以往历史数据计算平均表现，O(N^2*M)的历史数据空间太大了、每个的波动都很大，需要收集大量历史数据才能收敛（数据稀疏）
所以要折衷一下，先粗略划出备选集合top-k（每指定时间刷新一次，默认24小时），然后在备选集合中求最优（prediction-guided exploration approach）（贡献2）
N*N*M表格中，对于缺数据的点，可以通过临近点进行推测（网络诊断算法：图11，没讲清楚？？？）
现在给定起点和终点，在O(M)的决策空间中（M本身也是中继数目平方的级别，也很大）求解
首先粗略划出备选集合top-k
k不是固定的。具体而言，我们将top-k定义为中继选项的最小集合，使得任何不在top-k中的中继选项的95％置信下限高于在 top-k中任何中继选项的95％置信上限。（算法2）
function getTopK
h <- infinity，topK <- ø
while true
r取R集合中的upper分位数对应的选项（快速求k分位数）
若 lower分位数 > h
结束
否则
h <- upper分位数
r从R中删除，加入topK
然后在备选集合中求最优：算法1
采用强化学习的多臂老虎机模型，每个中继选项都是一个bandit，每次选择一个中继选项时，从它的历史数据里随机选择一个作为收益，根据收益调整自己的决策参数，进行下一次决策
收益的具体值：UCB1（算法3）将来自每个bandit（即中继选项）的rewards（即，性能）归一化到0和1之间。这通过将rewards除以top-k集合的上限95％置信区间的平均值来实现
为了更新网络参数，我们将采用一种称为e-greedy的策略。应用这个策略意味着在大多数情况下，我们的agent会选择带来最大预期好处的动作，但是偶尔的、以e的概率，它将随机选择。
2、中继的预算：
具体来说，中继呼叫的比例必须小于某一限制B（例如30％）
使用历史通话信息（中继优势）来跟踪百分比。只有当预期收益高于Bth对应的百分比收益时，才决定使用中继路径。
暂时不考虑其他预算模型：比如对每个中继/每条链路的带宽进行限制
5 评估
VIA在三个指标和整体方面都取得实质性进展。
在粒度加细的时候（考虑每一对节点、每天的最优的时候），收益受影响
实际数据驱动的评估表明，VIA的通话质量提高了60％，与oracle所指出的最佳潜力非常接近。