Sincronia: Near-Optimal Network Design for Coflows

一 文章概述

这篇文章针对Coflow调度问题，提出了一种接近最优的Coflow调度策略，本文提出的Coflow调度方案运行在网络传输层之上，也就是说下面具体是TCP，phost都可以。不同于之前coflow调度方案考虑了每个flow的发送，本文方法不考虑对单个flow的调度，而只是使用一种贪心算法将coflow进行排序。文章认为只需要对Coflow进行正确的排序，对于任意的per-flow调度方法都能达到很好的性能（最优的时间的4倍）。

二 这篇文章主要贡献

本文主要贡献是提出了Sincronia，一个针对coflow优化的数据中心网络设计。解决了前面Coflow的一些不可行的问题：1.之前Coflow调度方法对单个flow进行rate控制，但是这需要了解网络拥塞信息，如果拥塞信息动态变化，那就不可行了；2.之前每一个coflow到达或者结束都会导致flow rate的更新，但是一个数据中心中每秒有成千上万的coflow到达。
针对原来Coflow研究不太可行，本文做了以下工作：

• 时间分片为epoch，控制了coflow调度频率
• 在每个epoch中，会取当前coflow集合的子集，使用贪心算法（核心BSSI）进行排序
• 每个host按照coflow排序结果给flow进行优先级设置，并将flow交给下面可以处理优先级的传输层
• 在epoch中间来的coflow会使用贪心方法调度，从而使得work conservation（持续工作，保持资源一直被使用）

本文有一个比较核心的工作就是证明了本文基于的一个关键理论（只要对Coflow排的序是“对”的，并且按照这个顺序发，那么就可以平均达到最优CCT的4X的CCT的结果，和单个flow的控制没有关系）

三 回答四个问题

1 该文章解决的核心问题？前人使用的方法为什么不能解决本文提出的问题，困难在哪？本文提出的方法为什么能够有效解决这些问题？

本文解决的核心问题是Coflow调度问题的优化。
前人提出的Coflow调度方法存在的一些不可行的问题，比如每个流发送率的控制，策略调整频率。
本文提出的方法是基于作者证明的一个理论：只需要coflow的顺序是“对”的，那么不管是哪一种per-flow发送控制策略，其平均的CCT都是最优CCT的4X左右。基于此，本文就主要关注了Coflow的排序问题，将流具体发送率控制问题交给下层的传输层，同时通过时间片方式减少了调度方案的更新频率。
总的来说，本文方法之所以解决了前面方法的问题，最关键的就是那个基础理论的提出，coflow排序的贪心算法也不再使用剩余带宽这个量（Varys提出的基于bottle-neck的方法需要知道剩余带宽量），简化了排序算法。

2 该核心问题的解决带来了什么冲击？正负面都有哪些影响？

得出了Coflow调度和单个流发送率控制无关的结论，将coflow与flow调度解耦，coflow只负责设置优先级，后面的flow调度可以采取各种方案。
正向影响：得出的结论大大简化coflow的调度问题，变成了只要排序正确就能达到好的性能，同时本文的coflow的调度方案更加可行了
负面影响：首先得出的基本理论是否可靠完备，假设是否合理。如果这个理论存在问题，那么整个文章的方法都不可信了。其次，本文Coflow问题的抽象模型和Varys一样，认为数据中心网络是一个庞大的交换机，coflow的控制只是在ingress和egress端口进行的，内部网络的路由等等是不是有影响呢？所以这种大交换机的抽线是否合理也存在疑问。

3 作者如何进行验证？数学推导还是实验测试？是否完备？如果你进行验证，你会采取什么办法？如果你的方法和本文不一样，思考作者为什么不采用你想的方法？采用你想的方法，会有什么困难？如果你用文中方法，你回遇到什么困难？

本文作者的成果其实主要有两个部分：
一个是理论成果：得出的Coflow调度只需要排序的理论
一个是实践成果：实现了Sincronia，一种针对Coflow的接近最优的网络设计方案（其中包括BSSI算法）
其中理论成果在技术报告中做了详细证明（这个我还没有细看，后面可以仔细学习一下）
实践成果部分通过实验测试进行了评估：
首先workload采用的是依据facebook trace数据自动生成的
其次关注的指标包括：离线算法测试的CCT，在线算法测试的slowdown metric（CCT/OCT， OCT值只有这个coflow的话他花费的时间，实际上就是每个coflow的降速比）
离线算法所做的实验包括：

• 1.当所有coflow都在0时刻到达的情况下，Sincronia相会于其他方法（NCF SCF TCF Varys）的CCT的加速比。这个实验主要关注的是BSSI算法的优势
• 2.比较了不同Coflow规模下，Sincronia对于Varys的CCT加速比，除了每个coflow的平均CCT加速比，还比较了尾部（90th，99th）coflow的加速比，尾部加速比更大
• 3.绘制了Sincronia对于Varys的CCT加速比的CDF图，发现只有20%的Coflow是Varys比Sincronia好。但是Sincronia加速了65%的Coflow
• 4.比较了Sincronia（BSSI+greedy）对于不同coflow排序算法结合MADD（Varys中提出的per-flow rate控制方法）的加速比，从结果来看BSSI+MADD一直比SEBF+MADD好，这主要是为了说明加速的优势主要是来自BSSI算法。
• 5.比较了不同大小的coflow（OCT来分割）下，Sincronia对于Varys的CCT加速比分布，发现主要加速的部分既不是很小的也不是很大的，而是中间段，说明大的和小的coflow，两种方案做的决定基本相同，只有中间大小的BSSI的决策更好。

在线算法所做的实验包括：

• 比较了不同规模coflow下，相对于unload network（就是所有的slowdown都是1），0.9 workload情况下，sincronia的slowdown值。包括平均coflow以及tail部分coflow
• 比较了不同规模coflow下，CDF图展示了不同slowndown的coflow占比，发现60%的coflow能够保证slowdown=1
• 比较了不同规模coflow下，sincronia对于不同大小Coflow的slowdown大小，发现越大的coflow其slowdown越大
• 灵敏度分析之load大小影响，比较了load在0.7和0.9下不同slowdown的coflow占比，
• 灵敏度分析之epoch数量比较，不同epoch数量下不同slowdown的coflow占比
• 灵敏度分析之epoch机制比较，比较了立即计算（每个coflow到来就更新），指数epoch和线性epoch方法下不同slowdown的coflow占比

整个系统实验：
比较了Sincronia在TCP之上实现的性能与不使用coflow调度的TCP实现的性能
1.比较了不同load（背景流量，使用的是目的端口聚合的流量MSL为单位）下CCT加速比
2.比较了不同load下，不同加速比的coflow的比例
3.比较了不同coflow规模下，不同加速比的coflow的比例
这个实验本身是不公平的，但是可以和Varys指标做比较

4 找本文不完善的地方，是否还有可改进的空间？

首先介绍一下作者认为还存在的开放问题：

• 1.最好和最差性能存在差距，如何弥补性能差距
• 2.是否需要提出更好竞争比（competitive ratio）的Coflow调度方法。竞争比指的是在线算法性能和离线算法性能的比例，最坏情况比最优情况，所以必须是有限的
• 3.中心控制器需要的计算任务量到底有多少
• 4.本文方法没有考虑网络里面路径路由，所以将coflow调度与路由结合会不会有更好的性能
• 5.本文方法假设coflow信息都是已知的，如果coflow信息未知，接近最优算法如何设计
• 6.本文算法设计时以优化平均Coflow加权完成时间为性能指标，是否可以将其扩展到其他指标：deadline敏感的coflow，最小化尾部coflow完成时间等。

个人认为不完善可改进的地方：

• 1.假设大交换机的方式忽略数据中心网络拥塞，这个是否合理。所以我感觉如果改进可以考虑数据中心网络中coflow路由等等，这些已经有研究，后面会读一下。
• 2.文中也提到一个问题，就是有些应用不关心coflow完成时间，关注的是flow的完成时间。对于coflow调度和flow调度并存问题，本文提到使用权值来控制，但是如何加权值本文提到超出了本文范围，所以如何通过权值协调flow与coflow？
• 3.本文提出的BSSI算法在本文提出的example中最优，但是Varys中提出的example，Varys是不是比BSSI要好呢（这个我后面进一步分析一下）？所以BSSI算法是不是也是针对某一种模式的coflow呢？这个应该把Varys中提出的example也进行分析才有说服力
• 4.本文证明的结论得出per-flow调度对于结果没有很大影响，而且贪心调度算法比Varys的MADD性能更好，这些结论是否完全可信，或者假设是否现实这个都有待考证。这个因为没看具体证明，也不能下定论