基于瓶頸感知的多級(jí)反饋隊(duì)列Coflow 調(diào)度機(jī)制

都繁杰，李靜，郭志勇，任穎文，尹曉宇，董小菱

（1.南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京 211106；2.國(guó)家電網(wǎng)有限公司信息通信分公司，北京 100761；3.國(guó)網(wǎng)安徽省電力有限公司信息通信分公司，合肥 231299）

0 概述

隨著云計(jì)算、大數(shù)據(jù)的高速發(fā)展，云計(jì)算數(shù)據(jù)中心內(nèi)部的通信量呈爆炸性增長(zhǎng)［1］，逐步代替?zhèn)鹘y(tǒng)的數(shù)據(jù)中心。海量通信數(shù)據(jù)的處理需要大量計(jì)算節(jié)點(diǎn)協(xié)同完成，數(shù)據(jù)并行計(jì)算框架（如Apache Spark［2］、Dryad［3］、MapReduce［4］、CIEL［5］等）廣泛應(yīng)用于云計(jì)算數(shù)據(jù)中心。在數(shù)據(jù)并行計(jì)算框架中，用戶上傳計(jì)算任務(wù)，云數(shù)據(jù)中心通過(guò)一系列計(jì)算和通信階段得到計(jì)算結(jié)果，在收到所有計(jì)算結(jié)果后才能展示給用戶。由于通信階段可能占任務(wù)完成時(shí)間的50%以上，因此將顯著影響應(yīng)用程序的性能。然而，傳統(tǒng)的流級(jí)優(yōu)化難以滿足應(yīng)用程序低延遲、高吞吐量的要求，因此在應(yīng)用程序優(yōu)化方面不夠有效。在這種情況下，Coflow 應(yīng)運(yùn)而生，彌補(bǔ)了應(yīng)用程序與框架之間的差距。

Coflow 被稱(chēng)為具有語(yǔ)義相關(guān)的一組通信數(shù)據(jù)流，可以捕獲并行應(yīng)用程序中的通信信息［6］。Coflow 能夠高效地對(duì)網(wǎng)絡(luò)資源使用的應(yīng)用程序級(jí)語(yǔ)義進(jìn)行建模。在建模過(guò)程中將Coflow 作為網(wǎng)絡(luò)資源分配或調(diào)度的基本元素，以實(shí)現(xiàn)優(yōu)化目標(biāo)的目的。Coflow 完成時(shí)間（Coflow Completion Time，CCT）縮短的問(wèn)題通常被稱(chēng)為Coflow 調(diào)度問(wèn)題。因此，Coflow 調(diào)度已被廣泛應(yīng)用于數(shù)據(jù)中心傳輸設(shè)計(jì)中。為降低Coflow 的平均CCT，Coflow 調(diào)度方法應(yīng)運(yùn)而生，如Varys［7］、Aalo［8］、Baraat［9］等，它們?cè)谝欢ǔ?度上縮短平均CCT。然而大多數(shù)Coflow 調(diào)度機(jī)制未考慮網(wǎng)絡(luò)瓶頸。云計(jì)算數(shù)據(jù)中心內(nèi)部存在網(wǎng)絡(luò)鏈接故障、路由不均衡問(wèn)題，容易造成鏈路擁塞，產(chǎn)生流量傳輸瓶頸。因此，忽略網(wǎng)絡(luò)中的瓶頸會(huì)導(dǎo)致Coflow 優(yōu)先級(jí)判斷錯(cuò)誤及核心鏈路上不必要的帶寬爭(zhēng)用，極大影響CCT 的性能。

本文根據(jù)實(shí)際場(chǎng)景中Coflow 的特點(diǎn)，提出基于瓶頸感知的多級(jí)反饋隊(duì)列Coflow 調(diào)度機(jī)制。將瓶頸感知機(jī)制引入到數(shù)學(xué)建模過(guò)程中，分析Coflow 調(diào)度的典型場(chǎng)景，描述調(diào)度過(guò)程的實(shí)體信息，根據(jù)鏈路狀態(tài)與Coflow 大小、寬度等信息，確定流的最大速率。同時(shí)基于鏈路狀態(tài)與Coflow 已發(fā)數(shù)據(jù)、流速、寬度等信息確定Coflow 的優(yōu)先級(jí)，縮短Coflow 的平均完成時(shí)間。

1 相關(guān)工作

為提高云數(shù)據(jù)中心應(yīng)用的性能，云數(shù)據(jù)中心需要優(yōu)化流量調(diào)度。傳統(tǒng)的優(yōu)化對(duì)象是面向單個(gè)數(shù)據(jù)流，其優(yōu)化指標(biāo)為單個(gè)數(shù)據(jù)通信流的完成時(shí)間（Flow Completion Time，F(xiàn)CT），主要的研究工作包括pHost［10］、MJS［11］等。該類(lèi)方法通常是對(duì)單一數(shù)據(jù)流進(jìn)行調(diào)度，因此無(wú)法實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)資源最優(yōu)調(diào)度的目的。Coflow 是具有相關(guān)語(yǔ)義和并發(fā)性能目標(biāo)的并發(fā)流集合，其優(yōu)化CCT 能夠真正優(yōu)化云計(jì)算數(shù)據(jù)中心的應(yīng)用通信。

研究人員對(duì)Coflow 調(diào)度進(jìn)行研究。文獻(xiàn)［7］提出啟發(fā)式調(diào)度算法，以最小化平均CCT 達(dá)到Coflow截止時(shí)間。文獻(xiàn)［8］使用Coflow-Aware 最少服務(wù)（D-CLAS）算法，根據(jù)已經(jīng)發(fā)送的數(shù)據(jù)量，將Coflow劃分為各種優(yōu)先級(jí)。與上述集中式工作不同，文獻(xiàn)［9］提出一種用于任務(wù)感知調(diào)度的分布式算法，將任務(wù)意識(shí)引入到網(wǎng)絡(luò)優(yōu)化中。CODA［12］是借助機(jī)器學(xué)習(xí)技術(shù)檢測(cè)單個(gè)流中的Coflow。MPLBF［13］是通過(guò)貪婪策略設(shè)計(jì)一種高效的在線調(diào)度方法，提高在線調(diào)度的性能。DRGC［14］調(diào)度算法分析了多資源環(huán)境中Coflow 調(diào)度問(wèn)題，并對(duì)調(diào)度序列優(yōu)先級(jí)進(jìn)行排序。IAOA 調(diào)度算法［15］根據(jù)作業(yè)的權(quán)重和瞬時(shí)網(wǎng)絡(luò)狀況動(dòng)態(tài)調(diào)度Coflow。MCS 調(diào)度算法［16］聯(lián)合利用多個(gè)Coflow 級(jí)別屬性進(jìn)一步縮短Coflow 完成時(shí)間。NC-DRF 調(diào)度算法［17］為不同租戶提供對(duì)資源的隔離訪問(wèn)并保證調(diào)度性能，證明最小化CCT 的單一Coflow 路由和調(diào)度問(wèn)題為NP-hard［7］。CoRBA 算法［18］綜合考慮路由和帶寬分配，以確定路由的最優(yōu)帶寬分配。MCRS 算法［19］基于葉脊拓?fù)浣Y(jié)構(gòu)設(shè)計(jì)多跳Coflow 路由和調(diào)度策略，以最小化CCT。OMCoflow 算法［20］同時(shí)考慮路由和流量調(diào)度，具有理論性能的在線算法。以上調(diào)度算法將網(wǎng)絡(luò)抽象為無(wú)阻塞大型交換機(jī)，而忽略了網(wǎng)絡(luò)資源受限的問(wèn)題。Fai 調(diào)度算法［21］根據(jù)流速和字節(jié)發(fā)送檢測(cè)瓶頸，提高帶寬分配的效率；DBA 調(diào)度算法［22］是通過(guò)改進(jìn)最小剩余時(shí)間優(yōu)先的啟發(fā)式方法，有效識(shí)別網(wǎng)絡(luò)內(nèi)瓶頸。在多個(gè)Coflow 的情況下，Coflow 之間和Coflow 內(nèi)部的路徑發(fā)生重疊現(xiàn)象，并且流將爭(zhēng)奪相同的鏈接資源，產(chǎn)生鏈路間瓶頸。

云數(shù)據(jù)中心存在網(wǎng)絡(luò)內(nèi)鏈路故障、路由不平衡等問(wèn)題，核心鏈路上可能發(fā)生擁塞，流量的瓶頸將轉(zhuǎn)移到網(wǎng)絡(luò)內(nèi)部。網(wǎng)絡(luò)內(nèi)瓶頸決定實(shí)際可使用多少帶寬流，直接影響CCT。針對(duì)網(wǎng)絡(luò)中的瓶頸問(wèn)題，本文從瓶頸感知的角度入手，分析云數(shù)據(jù)中心架構(gòu)下Coflow 調(diào)度典型場(chǎng)景，提出基于瓶頸感知的多級(jí)反饋隊(duì)列Coflow 調(diào)度機(jī)制，并通過(guò)模擬實(shí)驗(yàn)從Coflow的平均完成時(shí)間和吞吐量?jī)蓚€(gè)角度對(duì)調(diào)度模型進(jìn)行有效評(píng)估。

2 多級(jí)反饋隊(duì)列Coflow 調(diào)度機(jī)制

本文首先對(duì)Coflow 調(diào)度進(jìn)行分析，構(gòu)建Coflow調(diào)度體系；然后對(duì)調(diào)度機(jī)制進(jìn)行數(shù)學(xué)建模，以減小CCT；最后參考已有優(yōu)化調(diào)度的方法，設(shè)計(jì)適用于當(dāng)前場(chǎng)景的調(diào)度方法。本文結(jié)合瓶頸感知、增加鏈路利用率等需求，設(shè)計(jì)基于瓶頸感知的多級(jí)反饋隊(duì)列Coflow 調(diào)度機(jī)制Bamq。

2.1 Coflow 調(diào)度分析

傳統(tǒng)的流級(jí)優(yōu)化難以滿足應(yīng)用程序低延遲、高吞吐量的要求，因此在應(yīng)用程序優(yōu)化方面不夠有效。與傳統(tǒng)的流定義不同，Coflow 由具有獨(dú)立輸入和輸出的多個(gè)并行流組成，且具有多個(gè)屬性。假設(shè)第i個(gè)Coflow 表示為四元組Ci=＜S，Wk，Le，f＞。其 中：S表示Coflow 流的總大??；Wk表示Coflow 流的寬度，即并行流的個(gè)數(shù)；Le表示Coflow 流的長(zhǎng)度，即并行流中最大流的大小；f表示Coflow 的并行流；Ci={f1，f2，…，fq}表示第i個(gè)Coflow包含q個(gè)并行子流{f1，f2，…，fq}。Coflow 調(diào)度場(chǎng)景如圖1 所示。

圖1 Coflow 調(diào)度場(chǎng)景Fig.1 Coflow scheduling scenarios

云計(jì)算數(shù)據(jù)中心存在網(wǎng)絡(luò)瓶頸問(wèn)題。圖1（a）有3 個(gè)Coflow 同時(shí)到達(dá)數(shù)據(jù)輸入端口（S1），若平均分配帶寬，則會(huì)造成帶寬爭(zhēng)用，形成瓶頸。圖1（a）的CCT為（10/3=（3+3+4）/3），圖1（b）的CCT 為（7/3=（1+2+4）/3），CCT 明顯降低，可以看出若及時(shí)發(fā)現(xiàn)瓶頸，并調(diào)整帶寬分配可降低CCT。圖1（c）存 在3 個(gè)Coflow(C1，C2，C3)，其中C1包括 3個(gè)流(C1.1，C1.2，C1.3)，C2包括2 個(gè)流（C2.1，C2.2），C3則為較大的流，其完成時(shí)間較長(zhǎng)，暫不討論。當(dāng)C1、C2同時(shí)到達(dá)數(shù)據(jù)輸入端口（S1、S2、S3），會(huì)形成鏈路間瓶頸，若平均分配帶寬，能夠有效降低CCT，圖1（c）的CCT為（5=（4+6）/2），圖1（d）的CCT（4.5=（4+5）/2）。

網(wǎng)絡(luò)瓶頸包括網(wǎng)絡(luò)內(nèi)瓶頸與鏈路間瓶頸，忽略網(wǎng)絡(luò)瓶頸會(huì)導(dǎo)致Coflow 性能下降。為提高Coflow性能，需要增大Coflow 流的速率，提高吞吐量。然而單方面增大吞吐量會(huì)造成網(wǎng)絡(luò)擁塞，導(dǎo)致鏈路爭(zhēng)用，產(chǎn)生大量鏈路間瓶頸，造成Coflow 性能下降。因此，在增大吞吐量與避免產(chǎn)生瓶頸之間實(shí)現(xiàn)平衡成為研究熱點(diǎn)。

針對(duì)以上問(wèn)題，本文設(shè)計(jì)基于瓶頸感知的多級(jí)反饋隊(duì)列Coflow 調(diào)度機(jī)制Bamq，通過(guò)對(duì)云數(shù)據(jù)中心進(jìn)行建模，實(shí)現(xiàn)流速最大化。由于單方面增大吞吐量會(huì)形成鏈路爭(zhēng)用，造成Coflow 流排隊(duì)，產(chǎn)生鏈路間瓶頸，因此設(shè)計(jì)基于Lyapunov 優(yōu)化的流量調(diào)度進(jìn)行隊(duì)列建模，使得數(shù)據(jù)在有限時(shí)間內(nèi)離開(kāi)發(fā)送隊(duì)列，確保隊(duì)列穩(wěn)定，避免產(chǎn)生網(wǎng)絡(luò)擁塞，從而提高Coflow 調(diào)度性能。

2.2 Coflow 調(diào)度過(guò)程建模

假設(shè)一個(gè)云計(jì)算數(shù)據(jù)中心有N個(gè)主機(jī)、M臺(tái)交換器，并具有任意的拓?fù)浣Y(jié)構(gòu)以形成L條鏈路，將流量傳輸過(guò)程抽象成無(wú)向圖G(V，E)，其中|V|=N+M，|E|=L。對(duì)于無(wú)向圖G，節(jié)點(diǎn)V對(duì)應(yīng)云計(jì)算數(shù)據(jù)中心的一個(gè)節(jié)點(diǎn)，每條邊E代表一個(gè)全雙工鏈路。

假設(shè)Coflow 所有內(nèi)部流同時(shí)到達(dá)端口，即使內(nèi)部流異步到達(dá)，可將它們視為一起到達(dá)，并將最后一個(gè)流的到達(dá)時(shí)間視為Coflow 的到達(dá)時(shí)間。

2.2.1 數(shù)學(xué)模型

Map/Reduce 的計(jì)算階段和CPU 的計(jì)算速度都與網(wǎng)絡(luò)的傳播速度直接相關(guān)。當(dāng)CPU 計(jì)算速度更快時(shí)，主機(jī)接收數(shù)據(jù)后被立即處理而不用排隊(duì)，因此可將網(wǎng)絡(luò)傳輸時(shí)間作為reducer 的完成時(shí)間。當(dāng)網(wǎng)絡(luò)傳輸更快時(shí)，主機(jī)接收到的數(shù)據(jù)不能被及時(shí)處理，導(dǎo)致數(shù)據(jù)排隊(duì)、緩存，因此在網(wǎng)絡(luò)完成傳輸后需要額外的計(jì)算時(shí)間。因?yàn)镃oflow 調(diào)度過(guò)程要關(guān)注網(wǎng)絡(luò)調(diào)度問(wèn)題，在數(shù)學(xué)分析中將忽略任務(wù)在每個(gè)reducer 上的計(jì)算時(shí)間，而只考慮網(wǎng)絡(luò)傳輸時(shí)間。以上問(wèn)題抽象化可簡(jiǎn)化數(shù)學(xué)建模過(guò)程，在實(shí)驗(yàn)評(píng)估中，由于實(shí)驗(yàn)使用真實(shí)的網(wǎng)絡(luò)環(huán)境，因此不需要強(qiáng)制遵從這些抽象問(wèn)題。數(shù)學(xué)模型的參數(shù)設(shè)置如表1 所示。

表1 數(shù)學(xué)模型的參數(shù)設(shè)置Table 1 Parameter settings of mathematical model

在不損失通用性的情況下，假設(shè)CoflowCi包含關(guān)于流Ci的所有信息，在時(shí)間Ti到達(dá)網(wǎng)絡(luò)時(shí)立即開(kāi)始傳輸，當(dāng)時(shí)間t＞Ti時(shí)，流Ci被分配到速率(t)的路徑上。當(dāng)(t)為零時(shí)，說(shuō)明此流正等待傳輸。在此基礎(chǔ)上，將調(diào)度問(wèn)題表示為時(shí)間t內(nèi)的優(yōu)化問(wèn)題，如式（1）所示：

其中，式（1）應(yīng)該滿足的約束條件如下：

對(duì)式（1）進(jìn)行變換得：

式（2）表示鏈路狀態(tài)，在任何時(shí)刻聚合流帶寬不能超過(guò)鏈路容量，即網(wǎng)絡(luò)內(nèi)瓶頸。為簡(jiǎn)化模型，式（3）在單位時(shí)間內(nèi)將Coflow 分配的帶寬看作Coflow 分配的流速和。一方面，為最小化CCT，該問(wèn)題可看作是一個(gè)線性規(guī)劃問(wèn)題，1(Sk(t)+df(t))可以看作流f的流速(t)的權(quán)重，然后加權(quán)和求最小，為了使加權(quán)和最小，即需要增大流速(t)；另一方面，增大流速會(huì)造成鏈路爭(zhēng)用，產(chǎn)生鏈路間瓶頸，導(dǎo)致?lián)砣?，反而?huì)增加總體CCT。因此，Coflow 調(diào)度過(guò)程需要在增大吞吐量與減少瓶頸之間實(shí)現(xiàn)平衡。

此外，最小化CCT 是NP-hard 問(wèn)題。在實(shí)際生產(chǎn)中，網(wǎng)絡(luò)中多個(gè)Coflow 可能同時(shí)競(jìng)爭(zhēng)鏈路資源，導(dǎo)致Coflow 調(diào)度更加復(fù)雜。凸優(yōu)化廣泛應(yīng)用于機(jī)器學(xué)習(xí)等領(lǐng)域。凸優(yōu)化是通過(guò)尋找這些非凸優(yōu)化問(wèn)題中“凸”的結(jié)構(gòu)，從而解決眾多非凸優(yōu)化的問(wèn)題。最小化CCT 的NP-hard 問(wèn)題是通過(guò)將原問(wèn)題轉(zhuǎn)換為凸問(wèn)題，提高求解速率。

2.2.2 Lagrange 優(yōu)化

Lagrange 對(duì)偶［23］思想是在目標(biāo)函數(shù)中考慮問(wèn)題的約束條件，原問(wèn)題的Lagrange 函數(shù)如式（7）所示。原函數(shù)的Lagrange 對(duì)偶函數(shù)如式（8）所示。

對(duì)偶函數(shù)是一族關(guān)于(λ，v)仿射函數(shù)的逐點(diǎn)下確界。此外，對(duì)偶函數(shù)是原問(wèn)題最優(yōu)解p*的下界，即對(duì)于任意λ≥0和v成立，如式（9）所示：

設(shè)(r～，λ，v)為原問(wèn)題的一個(gè)可行解，如式（10）所示：

雖然式（11）成立，但是當(dāng)g(λ，v)=-∞時(shí)，對(duì)偶函數(shù)的意義不大。只有當(dāng)λ≥0 且(λ，v)∈domg 時(shí)，即g(λ，v)≠-∞時(shí)，對(duì)偶函數(shù)才能給出p*的一個(gè)非平凡下界，滿足λ≥0 及(λ，v)∈domg 的(λ，v)是對(duì)偶可行的。

因此，不等式的對(duì)偶問(wèn)題是在滿足約束λ≥0 的條件下極大化對(duì)偶函數(shù)g(λ，v)，如式（12）所示：

通過(guò)梯度下降法求解(r，λ，v)，令和(λ*，v*)分別為原問(wèn)題和對(duì)偶問(wèn)題的某對(duì)最優(yōu)解，對(duì)偶間隙為零。因?yàn)長(zhǎng)(，λ*，v*)是在處取得最小值，所以函數(shù)在處的梯度為零，即：

顯然，必存在(λ*，v*)使得下式成立：

因此，在上述凸優(yōu)化過(guò)程中滿足KKT 最優(yōu)性條件。本文調(diào)度機(jī)制通過(guò)Lagrange 優(yōu)化將原問(wèn)題轉(zhuǎn)換為凸優(yōu)化問(wèn)題進(jìn)行求解，加快求解速度，求解每條鏈路的最優(yōu)解，使得CCT 最小。Lagrange 優(yōu)化是通過(guò)增加Coflow 流的流速來(lái)減小CCT，客觀上會(huì)造成鏈路爭(zhēng)用，形成網(wǎng)絡(luò)擁塞。

2.2.3 Lyapunov 優(yōu)化

Lagrange 優(yōu)化［24］在增大流速過(guò)程中會(huì)占用鏈路帶寬，造成Coflow 流在等待隊(duì)列中積壓，導(dǎo)致網(wǎng)絡(luò)擁塞。本文設(shè)計(jì)全新的瓶頸因子，確保隊(duì)列的穩(wěn)定性，以優(yōu)化多級(jí)反饋隊(duì)列的Coflow 調(diào)度。隊(duì)列穩(wěn)定性指網(wǎng)絡(luò)總是在追求一個(gè)理想的狀態(tài)，以確保所有到達(dá)的數(shù)據(jù)在有限時(shí)間內(nèi)離開(kāi)緩沖區(qū)，實(shí)現(xiàn)高性能與公平性之間的平衡。在現(xiàn)實(shí)場(chǎng)景中，網(wǎng)絡(luò)大多數(shù)處于不平衡狀態(tài)，但隊(duì)列穩(wěn)定性可以使其具有理想的均衡特性。

發(fā)送隊(duì)列模型如式（16）～式（19）所示：

其中：為流最大流速；為嚴(yán)格的凸函數(shù)；為優(yōu)先級(jí)系數(shù)，即瓶頸因子。虛擬隊(duì)列中Coflow 流的優(yōu)先級(jí)與β相關(guān)，即Coflow 流發(fā)送的數(shù)據(jù)越大，其數(shù)據(jù)本身也就越大，并且其寬度越小時(shí)，優(yōu)先級(jí)越高。是Coflow 流的流速，流速狀態(tài)直接表示鏈路的擁塞情況，因此，流速對(duì)虛擬隊(duì)列中Coflow 流的優(yōu)先級(jí)的影響極為關(guān)鍵。虛擬隊(duì)列如式（20）所示：

其中：Ql(t)為虛擬隊(duì)列的長(zhǎng)度，其與分配Coflow 流的流速及鏈路帶寬Bl直接相關(guān)。

到達(dá)云計(jì)算平臺(tái)的獨(dú)立任務(wù)具有隨機(jī)性，離散時(shí)間排隊(duì)過(guò)程Ql(t)達(dá)到隊(duì)列穩(wěn)定狀態(tài)，如式（21）所示：

Lyapunov 函數(shù)如式（22）所示：

則單位時(shí)間內(nèi)Lyapunov 漂移可以表示為：

本文通過(guò)Lyapunov 漂移Δ(Q(t))求解隊(duì)列穩(wěn)定性。虛擬隊(duì)列的DPP 如式（24）所示：

其中：V為懲罰因子，通過(guò)最小化式（24），得到網(wǎng)絡(luò)穩(wěn)定性。然后直接求解隨機(jī)和非線性Lyapunov 漂移式（24）。本文通過(guò)在式（25）中推導(dǎo)出式（24）的上界，然后以極小化式（24）的上界為目標(biāo)，得到極小化式（24）。基于Lyapunov 優(yōu)化的啟發(fā)式搜索算法中，?V≥0和?Q(t)，使得式（24）轉(zhuǎn)化為：

其中：α為最差情況值的上界。α值是有限的，由于集合χ被假定為連續(xù)的，因此對(duì)于每個(gè)時(shí)間間隙有在式（20）兩邊同時(shí)平方，可以得到如下不等式：

對(duì)不等式（26）求和，得到：

Coflow 調(diào)度假定所有到達(dá)者都被立即放置在路徑的所有鏈接上，是近似于實(shí)際網(wǎng)絡(luò)動(dòng)態(tài)排隊(duì)的方法。

2.3 調(diào)度機(jī)制設(shè)計(jì)

基于瓶頸感知的Coflow 調(diào)度機(jī)制Bamq 分為調(diào)節(jié)機(jī)制優(yōu)化和調(diào)度模型2 個(gè)部分。

2.3.1 調(diào)度機(jī)制優(yōu)化

整個(gè)調(diào)度機(jī)制分為信息收集、數(shù)據(jù)預(yù)處理、性能優(yōu)化3 個(gè)步驟。

1）信息收集。Coflow 是具有語(yǔ)義相關(guān)的一組通信數(shù)據(jù)流，若一組Coflow 流沒(méi)有發(fā)送，便無(wú)法提前獲取每個(gè)流發(fā)送的字節(jié)數(shù)、Coflow 關(guān)系和Coflow 寬度信息，采用文獻(xiàn)［8］和文獻(xiàn)［12］提出的兩種方法來(lái)收集信息。信息收集一方面采集Coflow 相關(guān)信息，另一方面監(jiān)控整體網(wǎng)絡(luò)狀態(tài)。當(dāng)Coflow 較多時(shí)，會(huì)產(chǎn)生鏈路競(jìng)爭(zhēng)，導(dǎo)致網(wǎng)絡(luò)擁塞，信息收集模塊采集Coflow 調(diào)度過(guò)程中的網(wǎng)絡(luò)信息，將信息傳給調(diào)度器進(jìn)行網(wǎng)絡(luò)優(yōu)化。

2）數(shù)據(jù)預(yù)處理。在初始化階段，Coflow 調(diào)度采用簡(jiǎn)單的調(diào)度機(jī)制，即平均分配每個(gè)流的帶寬，等待隊(duì)列采用FIFO 的策略。

3）性能優(yōu)化。傳統(tǒng)的Coflow 調(diào)度采用平均分配帶寬的策略，造成大量的剩余空間，影響Coflow的調(diào)度性能。針對(duì)上述問(wèn)題，Lagrange 優(yōu)化增大部分Coflow 的流速，從而降低CCT。因增大吞吐量會(huì)導(dǎo)致Coflow 流產(chǎn)生鏈路爭(zhēng)用，造成網(wǎng)絡(luò)擁塞。因此，Bamq 通過(guò)Lyapunov 優(yōu)化，確定調(diào)度隊(duì)列中不同Coflow 流的優(yōu)先級(jí)，達(dá)到增大吞吐量與減少擁塞平衡的目的。

2.3.2 調(diào)度模型

根據(jù)Coflow 調(diào)度機(jī)制，基于瓶頸感知的多級(jí)反饋隊(duì)列Coflow 調(diào)度模型如圖2 所示。

圖2 本文調(diào)度模型結(jié)構(gòu)Fig.2 Structure of the proposed scheduling model

Coflow 調(diào)度模型包括主節(jié)點(diǎn)、工作節(jié)點(diǎn)、守護(hù)進(jìn)程和監(jiān)視器。主節(jié)點(diǎn)是系統(tǒng)的大腦，起著控制器的作用；工作節(jié)點(diǎn)具有優(yōu)化信息的作用；守護(hù)進(jìn)程則作為全局調(diào)度器，協(xié)同處理主節(jié)點(diǎn)，從工作節(jié)點(diǎn)收集Coflow 信息，執(zhí)行Coflow 優(yōu)先級(jí)調(diào)度；監(jiān)控模塊則收集Coflow 信息，監(jiān)控鏈路狀態(tài)以判斷擁塞情況。

當(dāng)發(fā)送一組Coflow 后，監(jiān)視器收集Coflow 信息，包括每個(gè)流的發(fā)送字節(jié)數(shù)、Coflow 關(guān)系和Coflow 寬度信息，為調(diào)度提供初始信息。守護(hù)進(jìn)程根據(jù)監(jiān)控信息，初始化調(diào)度過(guò)程，采用簡(jiǎn)單的調(diào)度策略處理數(shù)據(jù)，即平均分配每個(gè)流的帶寬，等待隊(duì)列采用FIFO 的策略等。同時(shí)，監(jiān)控節(jié)點(diǎn)實(shí)時(shí)監(jiān)控鏈路狀況，檢測(cè)到擁塞時(shí)，立即通知主節(jié)點(diǎn)的調(diào)度器進(jìn)行優(yōu)化。

隨著Coflow 流的增加，簡(jiǎn)單的調(diào)度機(jī)制已不能滿足CCT 需求，通過(guò)Lagrange 優(yōu)化，增大部分流流速，從而縮短CCT。然而增大吞吐量會(huì)產(chǎn)生鏈路競(jìng)爭(zhēng)，部分流會(huì)進(jìn)入等待隊(duì)列，影響CCT 性能。Lyapunov 優(yōu)化根據(jù)等待隊(duì)列中的Coflow 流的瓶頸因子，為其分配不同的優(yōu)先級(jí)，并進(jìn)行優(yōu)先調(diào)度，達(dá)到增大吞吐量與減少擁塞的穩(wěn)定狀態(tài)，最終降低CCT。

算法2Bamq 算法

3 模擬實(shí)驗(yàn)

本文基于小規(guī)模流級(jí)別的模擬器和開(kāi)源網(wǎng)絡(luò)模擬器，使用Facebook 的真實(shí)數(shù)據(jù)集對(duì)Bamq 調(diào)度機(jī)制進(jìn)行驗(yàn)證，通過(guò)對(duì)比現(xiàn)有先驗(yàn)知識(shí)已知和先驗(yàn)知識(shí)未知場(chǎng)景下的調(diào)度機(jī)制來(lái)驗(yàn)證Bamq 調(diào)度機(jī)制的有效性。

3.1 實(shí)驗(yàn)設(shè)置

3.1.1 調(diào)度模型實(shí)驗(yàn)環(huán)境

CoflowSim 是基于Java 語(yǔ)言的開(kāi)源調(diào)度器，已經(jīng)實(shí)現(xiàn)了多種Coflow 調(diào)度機(jī)制，如Varys、Aalo，被廣泛應(yīng)用于Coflow 領(lǐng)域。本文在單機(jī)模擬下進(jìn)行實(shí)驗(yàn)，CoflowSim 模擬器部署環(huán)境具體為：Intel?CoreTMi7-9700 CPU 3.00 GHz、64 GB 內(nèi)存，操作系統(tǒng)為L(zhǎng)inux version 4.15.0-142-generic，JDK 為java 1.8.0_231。實(shí)驗(yàn)使用maven 工具將CoflowSim 導(dǎo)入到IDEA，通過(guò)CoflowSim 內(nèi)部數(shù)據(jù)中心的抽象模型，驗(yàn)證Coflow 調(diào)度機(jī)制。

本文采用Facebook 改進(jìn)的數(shù)據(jù)集。原始的Facebook 數(shù)據(jù)集包含3 000 臺(tái)150 機(jī)架的MapReduce集群，其合成后數(shù)據(jù)包含526 個(gè)Coflow 信息。每個(gè)數(shù)據(jù)包含以下信息：Coflow ID，mapper數(shù)量，reduce 數(shù)量，總Shuffle字節(jié)數(shù)，最大Shuffle字節(jié)數(shù)，持續(xù)時(shí)間，Coflow已發(fā)送字節(jié)數(shù)，Coflow 寬度等。由于Facebook 記錄的Coflow 僅包含發(fā)送主機(jī)、接收主機(jī)和傳送的字節(jié)數(shù)，沒(méi)有包含流級(jí)別信息，且不包含任務(wù)信息。因此，本文實(shí)驗(yàn)隨機(jī)劃分為多個(gè)Coflow 任務(wù)，使其構(gòu)成依賴關(guān)系。Facebook 數(shù)據(jù)集如圖3 所示。

圖3 Facebook 數(shù)據(jù)集相關(guān)信息Fig.3 Related information of Facebook dataset

Facebook 數(shù)據(jù)類(lèi)型如表2 所示。根據(jù)長(zhǎng)度（Long 和Short）和寬度（Narrow 和Wide）分為4 類(lèi)，SN 表示短窄流（Short-Narrow）；LN 表示長(zhǎng)窄流（Long-Narrow）；SW 表示短寬流（Short-Wide）；LW表示長(zhǎng)寬流（Long-Wide）。若Coflow 流的最長(zhǎng)流小于5 MB，則為短流（Short）；若Coflow 流的寬度小于50，則為窄流（Narrow）。此外，基于Facebook 記錄的Coflow 信息不包含流速、吞吐量等信息，因此需要使用開(kāi)源網(wǎng)絡(luò)模擬器，模擬鏈路狀況。

表2 Facebook 數(shù)據(jù)集的Coflow 類(lèi)型Table 2 Coflow types of Facebook data set %

NS-3（Network Simulator）是一個(gè)用于Internet 系統(tǒng)的離散事件網(wǎng)絡(luò)模擬器，用于面向?qū)ο缶幊藽++開(kāi)發(fā)的開(kāi)源項(xiàng)目。NS-3 模擬器抽象出幾個(gè)核心概念，即節(jié)點(diǎn)是連接到網(wǎng)絡(luò)的最基本實(shí)體，包括用于應(yīng)用程序、協(xié)議和網(wǎng)絡(luò)設(shè)備的容器類(lèi)。網(wǎng)絡(luò)系統(tǒng)是分配MAC 地址，以及配置節(jié)點(diǎn)的協(xié)議棧?；谶@些特點(diǎn)，NS-3 模擬器簡(jiǎn)化了api的繁瑣工作，用于構(gòu)建各種類(lèi)型的仿真場(chǎng)景。NS-3模擬器部署環(huán)境為：Ubuntu16.04.7 LTS、nsallinone-3.32、gcc5.4.0。實(shí)驗(yàn)通過(guò)編寫(xiě)C++代碼模擬鏈路情況，驗(yàn)證調(diào)度機(jī)制的有效性。

3.1.2 實(shí)驗(yàn)對(duì)比

Bamq 調(diào)度機(jī)制是一種改進(jìn)的多級(jí)隊(duì)列調(diào)度機(jī)制，通過(guò)與以下3 種經(jīng)典機(jī)制對(duì)比，以驗(yàn)證Bamq 調(diào)度的有效性。

1）Baraat 機(jī)制：用于數(shù)據(jù)中心的分布式任務(wù)感知調(diào)度系統(tǒng)，將任務(wù)感知調(diào)度問(wèn)題轉(zhuǎn)化成流優(yōu)先級(jí)問(wèn)題。通過(guò)一種簡(jiǎn)單的啟發(fā)式方法設(shè)置流的優(yōu)先級(jí)，結(jié)合優(yōu)先級(jí)和顯式速率協(xié)議的優(yōu)點(diǎn)，解決繁重任務(wù)的實(shí)時(shí)識(shí)別并相應(yīng)地改變多路復(fù)用的級(jí)別等問(wèn)題。

2）Varys 機(jī)制：是一種已知信息下最短作業(yè)優(yōu)先的多級(jí)隊(duì)列反饋機(jī)制，基于網(wǎng)絡(luò)瓶頸處的完成時(shí)間調(diào)度Coflow，然后使用最小化分配期望持續(xù)時(shí)間算法將速率分配給各個(gè)流，進(jìn)而降低平均CCT。

3）Aalo 機(jī)制：提出Coflow-Aware Least-Attained Service 的Inter-Coflow 調(diào)度器，是最少獲得優(yōu)先服務(wù)的多級(jí)隊(duì)列反饋機(jī)制，為每個(gè)Coflow 分配優(yōu)先級(jí)且該優(yōu)先級(jí)隨著Coflow 己經(jīng)發(fā)送總字節(jié)數(shù)的增加而減小，以此降低平均CCT。

Coflow 調(diào)度過(guò)程的性能指標(biāo)如下：

1）CCT：是Coflow 調(diào)度機(jī)制中最主要的指標(biāo)，分別計(jì)算平均CCT 和95%CCT。為消除極值影響，95%CCT 是將每種機(jī)制前2.5%和后2.5%結(jié)果去掉，重新計(jì)算結(jié)果。通過(guò)對(duì)CCT 進(jìn)行歸一化處理，得到Coflow 完成時(shí)間。

2）吞吐量：是數(shù)據(jù)中心應(yīng)用關(guān)注的基本指標(biāo)。在數(shù)據(jù)中心中，除了數(shù)據(jù)量小的Coflow 外，還有數(shù)據(jù)量大的后臺(tái)Coflow（>1GB）用于數(shù)據(jù)更新。如此大的Coflows 占傳輸總字節(jié)的99.1%，因此吞吐量也能評(píng)價(jià)調(diào)度性能。

3.2 實(shí)驗(yàn)結(jié)果與分析

本文選擇CCT 與吞吐量2 個(gè)指標(biāo)作為判斷標(biāo)準(zhǔn)。CCT 指標(biāo)作為判斷Coflow 調(diào)度性能的直接指標(biāo)被廣泛使用。為有效對(duì)比鏈路的利用率，本文對(duì)不同調(diào)度機(jī)制的吞吐量進(jìn)行對(duì)比。

3.2.1 CCT 指標(biāo)

本文對(duì)Facebook 數(shù)據(jù)集中526 個(gè)Coflow 進(jìn)行隨機(jī)分配任務(wù)，其任務(wù)到達(dá)時(shí)間遵循參數(shù)為θ的Poisson 分布，并將4 種不同類(lèi)型的Coflow 流作為工作負(fù)載。圖4表示Baraat、Varys、Aalo 與Bamq 的Coflow 完成時(shí)間對(duì)比。從圖4（a）可以看出，Bamq 的CCT 平均比Baraat、Varys、Aalo 分別提高9.2%、13.5%、39.1%。這是因?yàn)锽amq 考慮網(wǎng)絡(luò)內(nèi)瓶頸，從而比Varys 具有更精確的Coflow 優(yōu)先級(jí)和帶寬分配，Bamq 提高了鏈路利用率。從圖4（b）可以看出，95%CCT 中Bamq 的CCT 平均比Baraat、Varys、Aalo 降低9.6%、14.6%、39.7%。Bamq 和Baraat 提高了鏈路利用率。

圖4 不同調(diào)度機(jī)制的CCT 對(duì)比Fig 4 CCT comparison among different scheduling mechanisms

圖5 表示4 種調(diào)度機(jī)制Coflow 完成時(shí)間的累積分布函數(shù)（Cumulative Distribution Function，CDF）。從圖5 可以看出，在這兩種負(fù)載下，Bamq 幾乎在所有百分比上都優(yōu)于Varys、Baraat 和Aalo。在負(fù)載較小時(shí)，Bamq 的CCT 與Baraat 相似，主要與收斂速度相關(guān)。這個(gè)結(jié)果與圖4 的結(jié)果一致。

圖5 不同調(diào)度機(jī)制的Coflow 累積分布函數(shù)對(duì)比Fig 5 Cumulative distribution function of Coflow comparison among different scheduling mechanisms

3.2.2 吞吐量

Baraat、Varys、Aalo、Bamq 這4 種調(diào)度機(jī)制在不同工作負(fù)載下的吞吐量對(duì)比如圖6 所示。吞吐量是通過(guò)整個(gè)網(wǎng)絡(luò)傳輸?shù)乃袛?shù)據(jù)量除以所有Coflow的最大完成時(shí)間。在較低負(fù)荷下，4 種算法具有相似的吞吐量，在更大的負(fù)載下，Bamq 的吞吐量明顯高于Varys，略低于Baraat，相對(duì)于Baraat，Bamq 有一個(gè)收斂過(guò)程吞吐量損失很小。因此，Bamq 在優(yōu)化CCT的同時(shí)保持了良好的鏈接利用率。

圖6 不同調(diào)度機(jī)制的吞吐量對(duì)比Fig 6 Throughput comparison among different scheduling mechanisms

為驗(yàn)證Bamq 調(diào)度機(jī)制的收斂性，本文隨機(jī)選取3 個(gè)流，3 個(gè)流的收斂速度如圖7 所示。除了給初始流包讓路外，在短時(shí)間內(nèi)3 個(gè)流大多收斂到最優(yōu)速率，收斂前的平均速率也不小于最優(yōu)速率，因?yàn)榱髁渴菑妮^大值開(kāi)始收斂的。

圖7 流的收斂速度Fig.7 Convergence rate of flow

3.2.3 結(jié)果分析

Bamq 調(diào)度機(jī)制是一種改進(jìn)的多級(jí)隊(duì)列調(diào)度機(jī)制。初始化Coflow 優(yōu)先級(jí)，然后在該隊(duì)列下，最大化Coflow 流的流速，以此降低CCT。通過(guò)設(shè)置多級(jí)隊(duì)列來(lái)分配其他Coflow 流，以此減低擁塞。

Bamq 根據(jù)Coflow 的已發(fā)大小、寬度、流速設(shè)計(jì)了全新的瓶頸因子，根據(jù)瓶頸因子大小決定Coflow 的優(yōu)先級(jí)。流速是識(shí)別鏈路擁塞情況的關(guān)鍵信息，根據(jù)流速大小可以快速判斷網(wǎng)絡(luò)狀況。為評(píng)估CCT 與Coflow寬度等屬性的相關(guān)性，本文通過(guò)選擇Person 相關(guān)系數(shù)（PCC）作為評(píng)估指標(biāo)。PCC 定義如下：

PCC 可以很好衡量?jī)蓚€(gè)變量的線性關(guān)系，值越大，表明兩個(gè)變量的線性相關(guān)性越強(qiáng)。Person 相關(guān)性系數(shù)在計(jì)算2 個(gè)總體之間的相關(guān)性時(shí)要求兩個(gè)總體必須符合正態(tài)分布，對(duì)Person 相關(guān)性系數(shù)取對(duì)數(shù)，使其符合正態(tài)分布。Coflow 屬性相關(guān)度如表3 所示。

表3 Coflow 屬性相關(guān)度Table 3 Correlation degree of Coflow attributes

從表3 可以看出，CCT 與Coflow 大小強(qiáng)相關(guān)，由于CCT 反映Coflow 的完成時(shí)間，必然與Coflow 大小線性相關(guān)。CCT 與Coflow 寬度強(qiáng)相關(guān)，因此，Bamq 的瓶頸因子可以很好地反映CCT 性能。Coflow 大小與寬度強(qiáng)相關(guān)。在Hadoop 分布式框架中，Map 任務(wù)的數(shù)量與輸入數(shù)據(jù)的大小相關(guān)，即輸入數(shù)據(jù)越大，map任務(wù)越多，其相應(yīng)的reduce 任務(wù)越多，Coflow 寬度越大。

4 結(jié)束語(yǔ)

針對(duì)在云數(shù)據(jù)中心Coflow 調(diào)度過(guò)程中存在網(wǎng)絡(luò)瓶頸的問(wèn)題，本文提出基于瓶頸感知的多級(jí)反饋隊(duì)列Coflow 調(diào)度機(jī)制Bamq。利用Lagrange 對(duì)偶優(yōu)化Coflow 流速，以充分利用鏈路帶寬，從而減少CCT，為減少網(wǎng)絡(luò)擁塞，利用Lyapunov 優(yōu)化多級(jí)反饋隊(duì)列模型，以確保隊(duì)列穩(wěn)定性。在Facebook 的真實(shí)數(shù)據(jù)集和開(kāi)源網(wǎng)絡(luò)模擬器NS-3 上的實(shí)驗(yàn)結(jié)果表明，Bamq 調(diào)度機(jī)制在降低平均CCT 的前提下，能夠增大吞吐量，并且提高鏈路利用率。下一步將利用光電路交換機(jī)制優(yōu)化流量調(diào)度，并結(jié)合邊緣技術(shù)提高核心互聯(lián)網(wǎng)絡(luò)的帶寬利用率。