Sincronia: Near-Optimal Network Design for Coflows

一 文章概述

這篇文章針對(duì)Coflow調(diào)度問題名眉，提出了一種接近最優(yōu)的Coflow調(diào)度策略敌完，本文提出的Coflow調(diào)度方案運(yùn)行在網(wǎng)絡(luò)傳輸層之上乌庶，也就是說下面具體是TCP杭朱，phost都可以蔼囊。不同于之前coflow調(diào)度方案考慮了每個(gè)flow的發(fā)送瘫拣，本文方法不考慮對(duì)單個(gè)flow的調(diào)度陕赃，而只是使用一種貪心算法將coflow進(jìn)行排序省艳。文章認(rèn)為只需要對(duì)Coflow進(jìn)行正確的排序亲茅，對(duì)于任意的per-flow調(diào)度方法都能達(dá)到很好的性能（最優(yōu)的時(shí)間的4倍）回铛。

二 這篇文章主要貢獻(xiàn)

本文主要貢獻(xiàn)是提出了Sincronia狗准，一個(gè)針對(duì)coflow優(yōu)化的數(shù)據(jù)中心網(wǎng)絡(luò)設(shè)計(jì)。解決了前面Coflow的一些不可行的問題：1.之前Coflow調(diào)度方法對(duì)單個(gè)flow進(jìn)行rate控制茵肃，但是這需要了解網(wǎng)絡(luò)擁塞信息腔长，如果擁塞信息動(dòng)態(tài)變化，那就不可行了免姿；2.之前每一個(gè)coflow到達(dá)或者結(jié)束都會(huì)導(dǎo)致flow rate的更新饼酿，但是一個(gè)數(shù)據(jù)中心中每秒有成千上萬的coflow到達(dá)。
針對(duì)原來Coflow研究不太可行胚膊，本文做了以下工作：

• 時(shí)間分片為epoch故俐，控制了coflow調(diào)度頻率
• 在每個(gè)epoch中，會(huì)取當(dāng)前coflow集合的子集紊婉，使用貪心算法（核心BSSI）進(jìn)行排序
• 每個(gè)host按照coflow排序結(jié)果給flow進(jìn)行優(yōu)先級(jí)設(shè)置药版，并將flow交給下面可以處理優(yōu)先級(jí)的傳輸層
• 在epoch中間來的coflow會(huì)使用貪心方法調(diào)度，從而使得work conservation（持續(xù)工作喻犁，保持資源一直被使用）

本文有一個(gè)比較核心的工作就是證明了本文基于的一個(gè)關(guān)鍵理論（只要對(duì)Coflow排的序是“對(duì)”的槽片，并且按照這個(gè)順序發(fā)，那么就可以平均達(dá)到最優(yōu)CCT的4X的CCT的結(jié)果肢础，和單個(gè)flow的控制沒有關(guān)系）

三 回答四個(gè)問題

1 該文章解決的核心問題还栓？前人使用的方法為什么不能解決本文提出的問題，困難在哪传轰？本文提出的方法為什么能夠有效解決這些問題剩盒？

本文解決的核心問題是Coflow調(diào)度問題的優(yōu)化。
前人提出的Coflow調(diào)度方法存在的一些不可行的問題慨蛙，比如每個(gè)流發(fā)送率的控制辽聊，策略調(diào)整頻率。
本文提出的方法是基于作者證明的一個(gè)理論：只需要coflow的順序是“對(duì)”的期贫，那么不管是哪一種per-flow發(fā)送控制策略跟匆，其平均的CCT都是最優(yōu)CCT的4X左右⊥常基于此玛臂，本文就主要關(guān)注了Coflow的排序問題，將流具體發(fā)送率控制問題交給下層的傳輸層封孙，同時(shí)通過時(shí)間片方式減少了調(diào)度方案的更新頻率迹冤。
總的來說，本文方法之所以解決了前面方法的問題敛瓷，最關(guān)鍵的就是那個(gè)基礎(chǔ)理論的提出叁巨，coflow排序的貪心算法也不再使用剩余帶寬這個(gè)量（Varys提出的基于bottle-neck的方法需要知道剩余帶寬量），簡(jiǎn)化了排序算法呐籽。

2 該核心問題的解決帶來了什么沖擊锋勺？正負(fù)面都有哪些影響蚀瘸？

得出了Coflow調(diào)度和單個(gè)流發(fā)送率控制無關(guān)的結(jié)論，將coflow與flow調(diào)度解耦庶橱，coflow只負(fù)責(zé)設(shè)置優(yōu)先級(jí)贮勃，后面的flow調(diào)度可以采取各種方案。
正向影響：得出的結(jié)論大大簡(jiǎn)化coflow的調(diào)度問題苏章，變成了只要排序正確就能達(dá)到好的性能寂嘉，同時(shí)本文的coflow的調(diào)度方案更加可行了
負(fù)面影響：首先得出的基本理論是否可靠完備，假設(shè)是否合理枫绅。如果這個(gè)理論存在問題泉孩，那么整個(gè)文章的方法都不可信了。其次并淋，本文Coflow問題的抽象模型和Varys一樣寓搬，認(rèn)為數(shù)據(jù)中心網(wǎng)絡(luò)是一個(gè)龐大的交換機(jī)，coflow的控制只是在ingress和egress端口進(jìn)行的县耽，內(nèi)部網(wǎng)絡(luò)的路由等等是不是有影響呢句喷？所以這種大交換機(jī)的抽線是否合理也存在疑問。

3 作者如何進(jìn)行驗(yàn)證兔毙？數(shù)學(xué)推導(dǎo)還是實(shí)驗(yàn)測(cè)試唾琼？是否完備？如果你進(jìn)行驗(yàn)證澎剥，你會(huì)采取什么辦法锡溯？如果你的方法和本文不一樣，思考作者為什么不采用你想的方法肴裙？采用你想的方法趾唱，會(huì)有什么困難涌乳？如果你用文中方法蜻懦，你回遇到什么困難？

本文作者的成果其實(shí)主要有兩個(gè)部分：
一個(gè)是理論成果：得出的Coflow調(diào)度只需要排序的理論
一個(gè)是實(shí)踐成果：實(shí)現(xiàn)了Sincronia夕晓，一種針對(duì)Coflow的接近最優(yōu)的網(wǎng)絡(luò)設(shè)計(jì)方案（其中包括BSSI算法）
其中理論成果在技術(shù)報(bào)告中做了詳細(xì)證明（這個(gè)我還沒有細(xì)看宛乃，后面可以仔細(xì)學(xué)習(xí)一下）
實(shí)踐成果部分通過實(shí)驗(yàn)測(cè)試進(jìn)行了評(píng)估：
首先workload采用的是依據(jù)facebook trace數(shù)據(jù)自動(dòng)生成的
其次關(guān)注的指標(biāo)包括：離線算法測(cè)試的CCT，在線算法測(cè)試的slowdown metric（CCT/OCT蒸辆， OCT值只有這個(gè)coflow的話他花費(fèi)的時(shí)間征炼，實(shí)際上就是每個(gè)coflow的降速比）
離線算法所做的實(shí)驗(yàn)包括：

• 1.當(dāng)所有coflow都在0時(shí)刻到達(dá)的情況下，Sincronia相會(huì)于其他方法（NCF SCF TCF Varys）的CCT的加速比躬贡。這個(gè)實(shí)驗(yàn)主要關(guān)注的是BSSI算法的優(yōu)勢(shì)
• 2.比較了不同Coflow規(guī)模下谆奥，Sincronia對(duì)于Varys的CCT加速比，除了每個(gè)coflow的平均CCT加速比拂玻，還比較了尾部（90th酸些，99th）coflow的加速比宰译，尾部加速比更大
• 3.繪制了Sincronia對(duì)于Varys的CCT加速比的CDF圖，發(fā)現(xiàn)只有20%的Coflow是Varys比Sincronia好魄懂。但是Sincronia加速了65%的Coflow
• 4.比較了Sincronia（BSSI+greedy）對(duì)于不同coflow排序算法結(jié)合MADD（Varys中提出的per-flow rate控制方法）的加速比沿侈，從結(jié)果來看BSSI+MADD一直比SEBF+MADD好，這主要是為了說明加速的優(yōu)勢(shì)主要是來自BSSI算法市栗。
• 5.比較了不同大小的coflow（OCT來分割）下缀拭，Sincronia對(duì)于Varys的CCT加速比分布，發(fā)現(xiàn)主要加速的部分既不是很小的也不是很大的填帽，而是中間段蛛淋，說明大的和小的coflow，兩種方案做的決定基本相同篡腌，只有中間大小的BSSI的決策更好铣鹏。

在線算法所做的實(shí)驗(yàn)包括：

• 比較了不同規(guī)模coflow下，相對(duì)于unload network（就是所有的slowdown都是1）哀蘑，0.9 workload情況下诚卸，sincronia的slowdown值。包括平均coflow以及tail部分coflow
• 比較了不同規(guī)模coflow下绘迁，CDF圖展示了不同slowndown的coflow占比合溺，發(fā)現(xiàn)60%的coflow能夠保證slowdown=1
• 比較了不同規(guī)模coflow下，sincronia對(duì)于不同大小Coflow的slowdown大小缀台，發(fā)現(xiàn)越大的coflow其slowdown越大
• 靈敏度分析之load大小影響棠赛，比較了load在0.7和0.9下不同slowdown的coflow占比，
• 靈敏度分析之epoch數(shù)量比較膛腐，不同epoch數(shù)量下不同slowdown的coflow占比
• 靈敏度分析之epoch機(jī)制比較睛约，比較了立即計(jì)算（每個(gè)coflow到來就更新），指數(shù)epoch和線性epoch方法下不同slowdown的coflow占比

整個(gè)系統(tǒng)實(shí)驗(yàn)：
比較了Sincronia在TCP之上實(shí)現(xiàn)的性能與不使用coflow調(diào)度的TCP實(shí)現(xiàn)的性能
1.比較了不同load（背景流量哲身，使用的是目的端口聚合的流量MSL為單位）下CCT加速比
2.比較了不同load下辩涝，不同加速比的coflow的比例
3.比較了不同coflow規(guī)模下，不同加速比的coflow的比例
這個(gè)實(shí)驗(yàn)本身是不公平的勘天，但是可以和Varys指標(biāo)做比較

4 找本文不完善的地方怔揩，是否還有可改進(jìn)的空間？

首先介紹一下作者認(rèn)為還存在的開放問題：

• 1.最好和最差性能存在差距脯丝，如何彌補(bǔ)性能差距
• 2.是否需要提出更好競(jìng)爭(zhēng)比（competitive ratio）的Coflow調(diào)度方法商膊。競(jìng)爭(zhēng)比指的是在線算法性能和離線算法性能的比例，最壞情況比最優(yōu)情況宠进，所以必須是有限的
• 3.中心控制器需要的計(jì)算任務(wù)量到底有多少
• 4.本文方法沒有考慮網(wǎng)絡(luò)里面路徑路由晕拆，所以將coflow調(diào)度與路由結(jié)合會(huì)不會(huì)有更好的性能
• 5.本文方法假設(shè)coflow信息都是已知的，如果coflow信息未知材蹬，接近最優(yōu)算法如何設(shè)計(jì)
• 6.本文算法設(shè)計(jì)時(shí)以優(yōu)化平均Coflow加權(quán)完成時(shí)間為性能指標(biāo)实幕，是否可以將其擴(kuò)展到其他指標(biāo)：deadline敏感的coflow阱高，最小化尾部coflow完成時(shí)間等。

個(gè)人認(rèn)為不完善可改進(jìn)的地方：

• 1.假設(shè)大交換機(jī)的方式忽略數(shù)據(jù)中心網(wǎng)絡(luò)擁塞茬缩，這個(gè)是否合理赤惊。所以我感覺如果改進(jìn)可以考慮數(shù)據(jù)中心網(wǎng)絡(luò)中coflow路由等等，這些已經(jīng)有研究凰锡，后面會(huì)讀一下未舟。
• 2.文中也提到一個(gè)問題，就是有些應(yīng)用不關(guān)心coflow完成時(shí)間掂为，關(guān)注的是flow的完成時(shí)間裕膀。對(duì)于coflow調(diào)度和flow調(diào)度并存問題，本文提到使用權(quán)值來控制勇哗，但是如何加權(quán)值本文提到超出了本文范圍昼扛，所以如何通過權(quán)值協(xié)調(diào)flow與coflow？
• 3.本文提出的BSSI算法在本文提出的example中最優(yōu)欲诺，但是Varys中提出的example抄谐，Varys是不是比BSSI要好呢（這個(gè)我后面進(jìn)一步分析一下）？所以BSSI算法是不是也是針對(duì)某一種模式的coflow呢扰法？這個(gè)應(yīng)該把Varys中提出的example也進(jìn)行分析才有說服力
• 4.本文證明的結(jié)論得出per-flow調(diào)度對(duì)于結(jié)果沒有很大影響蛹含，而且貪心調(diào)度算法比Varys的MADD性能更好，這些結(jié)論是否完全可信塞颁，或者假設(shè)是否現(xiàn)實(shí)這個(gè)都有待考證浦箱。這個(gè)因?yàn)闆]看具體證明，也不能下定論