基于瓶頸感知的多級反饋隊列Coflow 調度機制

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

（1.南京航空航天大學 計算機科學與技術學院，南京 211106；2.國家電網有限公司信息通信分公司，北京 100761；3.國網安徽省電力有限公司信息通信分公司，合肥 231299）

0 概述

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

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

本文根據實際場景中Coflow 的特點，提出基于瓶頸感知的多級反饋隊列Coflow 調度機制。將瓶頸感知機制引入到數學建模過程中，分析Coflow 調度的典型場景，描述調度過程的實體信息，根據鏈路狀態與Coflow 大小、寬度等信息，確定流的最大速率。同時基于鏈路狀態與Coflow 已發數據、流速、寬度等信息確定Coflow 的優先級，縮短Coflow 的平均完成時間。

1 相關工作

為提高云數據中心應用的性能，云數據中心需要優化流量調度。傳統的優化對象是面向單個數據流，其優化指標為單個數據通信流的完成時間（Flow Completion Time，FCT），主要的研究工作包括pHost［10］、MJS［11］等。該類方法通常是對單一數據流進行調度，因此無法實現整個網絡資源最優調度的目的。Coflow 是具有相關語義和并發性能目標的并發流集合，其優化CCT 能夠真正優化云計算數據中心的應用通信。

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

云數據中心存在網絡內鏈路故障、路由不平衡等問題，核心鏈路上可能發生擁塞，流量的瓶頸將轉移到網絡內部。網絡內瓶頸決定實際可使用多少帶寬流，直接影響CCT。針對網絡中的瓶頸問題，本文從瓶頸感知的角度入手，分析云數據中心架構下Coflow 調度典型場景，提出基于瓶頸感知的多級反饋隊列Coflow 調度機制，并通過模擬實驗從Coflow的平均完成時間和吞吐量兩個角度對調度模型進行有效評估。

2 多級反饋隊列Coflow 調度機制

本文首先對Coflow 調度進行分析，構建Coflow調度體系；然后對調度機制進行數學建模，以減小CCT；最后參考已有優化調度的方法，設計適用于當前場景的調度方法。本文結合瓶頸感知、增加鏈路利用率等需求，設計基于瓶頸感知的多級反饋隊列Coflow 調度機制Bamq。

2.1 Coflow 調度分析

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

圖1 Coflow 調度場景Fig.1 Coflow scheduling scenarios

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

網絡瓶頸包括網絡內瓶頸與鏈路間瓶頸，忽略網絡瓶頸會導致Coflow 性能下降。為提高Coflow性能，需要增大Coflow 流的速率，提高吞吐量。然而單方面增大吞吐量會造成網絡擁塞，導致鏈路爭用，產生大量鏈路間瓶頸，造成Coflow 性能下降。因此，在增大吞吐量與避免產生瓶頸之間實現平衡成為研究熱點。

針對以上問題，本文設計基于瓶頸感知的多級反饋隊列Coflow 調度機制Bamq，通過對云數據中心進行建模，實現流速最大化。由于單方面增大吞吐量會形成鏈路爭用，造成Coflow 流排隊，產生鏈路間瓶頸，因此設計基于Lyapunov 優化的流量調度進行隊列建模，使得數據在有限時間內離開發送隊列，確保隊列穩定，避免產生網絡擁塞，從而提高Coflow 調度性能。

2.2 Coflow 調度過程建模

假設一個云計算數據中心有N個主機、M臺交換器，并具有任意的拓撲結構以形成L條鏈路，將流量傳輸過程抽象成無向圖G(V，E)，其中|V|=N+M，|E|=L。對于無向圖G，節點V對應云計算數據中心的一個節點，每條邊E代表一個全雙工鏈路。

假設Coflow 所有內部流同時到達端口，即使內部流異步到達，可將它們視為一起到達，并將最后一個流的到達時間視為Coflow 的到達時間。

2.2.1 數學模型

Map/Reduce 的計算階段和CPU 的計算速度都與網絡的傳播速度直接相關。當CPU 計算速度更快時，主機接收數據后被立即處理而不用排隊，因此可將網絡傳輸時間作為reducer 的完成時間。當網絡傳輸更快時，主機接收到的數據不能被及時處理，導致數據排隊、緩存，因此在網絡完成傳輸后需要額外的計算時間。因為Coflow 調度過程要關注網絡調度問題，在數學分析中將忽略任務在每個reducer 上的計算時間，而只考慮網絡傳輸時間。以上問題抽象化可簡化數學建模過程，在實驗評估中，由于實驗使用真實的網絡環境，因此不需要強制遵從這些抽象問題。數學模型的參數設置如表1 所示。

表1 數學模型的參數設置Table 1 Parameter settings of mathematical model

在不損失通用性的情況下，假設CoflowCi包含關于流Ci的所有信息，在時間Ti到達網絡時立即開始傳輸，當時間t＞Ti時，流Ci被分配到速率(t)的路徑上。當(t)為零時，說明此流正等待傳輸。在此基礎上，將調度問題表示為時間t內的優化問題，如式（1）所示：

其中，式（1）應該滿足的約束條件如下：

對式（1）進行變換得：

式（2）表示鏈路狀態，在任何時刻聚合流帶寬不能超過鏈路容量，即網絡內瓶頸。為簡化模型，式（3）在單位時間內將Coflow 分配的帶寬看作Coflow 分配的流速和。一方面，為最小化CCT，該問題可看作是一個線性規劃問題，1(Sk(t)+df(t))可以看作流f的流速(t)的權重，然后加權和求最小，為了使加權和最小，即需要增大流速(t)；另一方面，增大流速會造成鏈路爭用，產生鏈路間瓶頸，導致擁塞，反而會增加總體CCT。因此，Coflow 調度過程需要在增大吞吐量與減少瓶頸之間實現平衡。

此外，最小化CCT 是NP-hard 問題。在實際生產中，網絡中多個Coflow 可能同時競爭鏈路資源，導致Coflow 調度更加復雜。凸優化廣泛應用于機器學習等領域。凸優化是通過尋找這些非凸優化問題中“凸”的結構，從而解決眾多非凸優化的問題。最小化CCT 的NP-hard 問題是通過將原問題轉換為凸問題，提高求解速率。

2.2.2 Lagrange 優化

Lagrange 對偶［23］思想是在目標函數中考慮問題的約束條件，原問題的Lagrange 函數如式（7）所示。原函數的Lagrange 對偶函數如式（8）所示。

對偶函數是一族關于(λ，v)仿射函數的逐點下確界。此外，對偶函數是原問題最優解p*的下界，即對于任意λ≥0和v成立，如式（9）所示：

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

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

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

通過梯度下降法求解(r，λ，v)，令和(λ*，v*)分別為原問題和對偶問題的某對最優解，對偶間隙為零。因為L(，λ*，v*)是在處取得最小值，所以函數在處的梯度為零，即：

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

因此，在上述凸優化過程中滿足KKT 最優性條件。本文調度機制通過Lagrange 優化將原問題轉換為凸優化問題進行求解，加快求解速度，求解每條鏈路的最優解，使得CCT 最小。Lagrange 優化是通過增加Coflow 流的流速來減小CCT，客觀上會造成鏈路爭用，形成網絡擁塞。

2.2.3 Lyapunov 優化

Lagrange 優化［24］在增大流速過程中會占用鏈路帶寬，造成Coflow 流在等待隊列中積壓，導致網絡擁塞。本文設計全新的瓶頸因子，確保隊列的穩定性，以優化多級反饋隊列的Coflow 調度。隊列穩定性指網絡總是在追求一個理想的狀態，以確保所有到達的數據在有限時間內離開緩沖區，實現高性能與公平性之間的平衡。在現實場景中，網絡大多數處于不平衡狀態，但隊列穩定性可以使其具有理想的均衡特性。

發送隊列模型如式（16）～式（19）所示：

其中：為流最大流速；為嚴格的凸函數；為優先級系數，即瓶頸因子。虛擬隊列中Coflow 流的優先級與β相關，即Coflow 流發送的數據越大，其數據本身也就越大，并且其寬度越小時，優先級越高。是Coflow 流的流速，流速狀態直接表示鏈路的擁塞情況，因此，流速對虛擬隊列中Coflow 流的優先級的影響極為關鍵。虛擬隊列如式（20）所示：

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

到達云計算平臺的獨立任務具有隨機性，離散時間排隊過程Ql(t)達到隊列穩定狀態，如式（21）所示：

Lyapunov 函數如式（22）所示：

則單位時間內Lyapunov 漂移可以表示為：

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

其中：V為懲罰因子，通過最小化式（24），得到網絡穩定性。然后直接求解隨機和非線性Lyapunov 漂移式（24）。本文通過在式（25）中推導出式（24）的上界，然后以極小化式（24）的上界為目標，得到極小化式（24）。基于Lyapunov 優化的啟發式搜索算法中，?V≥0和?Q(t)，使得式（24）轉化為：

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

對不等式（26）求和，得到：

Coflow 調度假定所有到達者都被立即放置在路徑的所有鏈接上，是近似于實際網絡動態排隊的方法。

2.3 調度機制設計

基于瓶頸感知的Coflow 調度機制Bamq 分為調節機制優化和調度模型2 個部分。

2.3.1 調度機制優化

整個調度機制分為信息收集、數據預處理、性能優化3 個步驟。

1）信息收集。Coflow 是具有語義相關的一組通信數據流，若一組Coflow 流沒有發送，便無法提前獲取每個流發送的字節數、Coflow 關系和Coflow 寬度信息，采用文獻［8］和文獻［12］提出的兩種方法來收集信息。信息收集一方面采集Coflow 相關信息，另一方面監控整體網絡狀態。當Coflow 較多時，會產生鏈路競爭，導致網絡擁塞，信息收集模塊采集Coflow 調度過程中的網絡信息，將信息傳給調度器進行網絡優化。

2）數據預處理。在初始化階段，Coflow 調度采用簡單的調度機制，即平均分配每個流的帶寬，等待隊列采用FIFO 的策略。

3）性能優化。傳統的Coflow 調度采用平均分配帶寬的策略，造成大量的剩余空間，影響Coflow的調度性能。針對上述問題，Lagrange 優化增大部分Coflow 的流速，從而降低CCT。因增大吞吐量會導致Coflow 流產生鏈路爭用，造成網絡擁塞。因此，Bamq 通過Lyapunov 優化，確定調度隊列中不同Coflow 流的優先級，達到增大吞吐量與減少擁塞平衡的目的。

2.3.2 調度模型

根據Coflow 調度機制，基于瓶頸感知的多級反饋隊列Coflow 調度模型如圖2 所示。

圖2 本文調度模型結構Fig.2 Structure of the proposed scheduling model

Coflow 調度模型包括主節點、工作節點、守護進程和監視器。主節點是系統的大腦，起著控制器的作用；工作節點具有優化信息的作用；守護進程則作為全局調度器，協同處理主節點，從工作節點收集Coflow 信息，執行Coflow 優先級調度；監控模塊則收集Coflow 信息，監控鏈路狀態以判斷擁塞情況。

當發送一組Coflow 后，監視器收集Coflow 信息，包括每個流的發送字節數、Coflow 關系和Coflow 寬度信息，為調度提供初始信息。守護進程根據監控信息，初始化調度過程，采用簡單的調度策略處理數據，即平均分配每個流的帶寬，等待隊列采用FIFO 的策略等。同時，監控節點實時監控鏈路狀況，檢測到擁塞時，立即通知主節點的調度器進行優化。

隨著Coflow 流的增加，簡單的調度機制已不能滿足CCT 需求，通過Lagrange 優化，增大部分流流速，從而縮短CCT。然而增大吞吐量會產生鏈路競爭，部分流會進入等待隊列，影響CCT 性能。Lyapunov 優化根據等待隊列中的Coflow 流的瓶頸因子，為其分配不同的優先級，并進行優先調度，達到增大吞吐量與減少擁塞的穩定狀態，最終降低CCT。

算法2Bamq 算法

3 模擬實驗

本文基于小規模流級別的模擬器和開源網絡模擬器，使用Facebook 的真實數據集對Bamq 調度機制進行驗證，通過對比現有先驗知識已知和先驗知識未知場景下的調度機制來驗證Bamq 調度機制的有效性。

3.1 實驗設置

3.1.1 調度模型實驗環境

CoflowSim 是基于Java 語言的開源調度器，已經實現了多種Coflow 調度機制，如Varys、Aalo，被廣泛應用于Coflow 領域。本文在單機模擬下進行實驗，CoflowSim 模擬器部署環境具體為：Intel?CoreTMi7-9700 CPU 3.00 GHz、64 GB 內存，操作系統為Linux version 4.15.0-142-generic，JDK 為java 1.8.0_231。實驗使用maven 工具將CoflowSim 導入到IDEA，通過CoflowSim 內部數據中心的抽象模型，驗證Coflow 調度機制。

本文采用Facebook 改進的數據集。原始的Facebook 數據集包含3 000 臺150 機架的MapReduce集群，其合成后數據包含526 個Coflow 信息。每個數據包含以下信息：Coflow ID，mapper數量，reduce 數量，總Shuffle字節數，最大Shuffle字節數，持續時間，Coflow已發送字節數，Coflow 寬度等。由于Facebook 記錄的Coflow 僅包含發送主機、接收主機和傳送的字節數，沒有包含流級別信息，且不包含任務信息。因此，本文實驗隨機劃分為多個Coflow 任務，使其構成依賴關系。Facebook 數據集如圖3 所示。

圖3 Facebook 數據集相關信息Fig.3 Related information of Facebook dataset

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

表2 Facebook 數據集的Coflow 類型Table 2 Coflow types of Facebook data set %

NS-3（Network Simulator）是一個用于Internet 系統的離散事件網絡模擬器，用于面向對象編程C++開發的開源項目。NS-3 模擬器抽象出幾個核心概念，即節點是連接到網絡的最基本實體，包括用于應用程序、協議和網絡設備的容器類。網絡系統是分配MAC 地址，以及配置節點的協議棧。基于這些特點，NS-3 模擬器簡化了api的繁瑣工作，用于構建各種類型的仿真場景。NS-3模擬器部署環境為：Ubuntu16.04.7 LTS、nsallinone-3.32、gcc5.4.0。實驗通過編寫C++代碼模擬鏈路情況，驗證調度機制的有效性。

3.1.2 實驗對比

Bamq 調度機制是一種改進的多級隊列調度機制，通過與以下3 種經典機制對比，以驗證Bamq 調度的有效性。

1）Baraat 機制：用于數據中心的分布式任務感知調度系統，將任務感知調度問題轉化成流優先級問題。通過一種簡單的啟發式方法設置流的優先級，結合優先級和顯式速率協議的優點，解決繁重任務的實時識別并相應地改變多路復用的級別等問題。

2）Varys 機制：是一種已知信息下最短作業優先的多級隊列反饋機制，基于網絡瓶頸處的完成時間調度Coflow，然后使用最小化分配期望持續時間算法將速率分配給各個流，進而降低平均CCT。

3）Aalo 機制：提出Coflow-Aware Least-Attained Service 的Inter-Coflow 調度器，是最少獲得優先服務的多級隊列反饋機制，為每個Coflow 分配優先級且該優先級隨著Coflow 己經發送總字節數的增加而減小，以此降低平均CCT。

Coflow 調度過程的性能指標如下：

1）CCT：是Coflow 調度機制中最主要的指標，分別計算平均CCT 和95%CCT。為消除極值影響，95%CCT 是將每種機制前2.5%和后2.5%結果去掉，重新計算結果。通過對CCT 進行歸一化處理，得到Coflow 完成時間。

2）吞吐量：是數據中心應用關注的基本指標。在數據中心中，除了數據量小的Coflow 外，還有數據量大的后臺Coflow（>1GB）用于數據更新。如此大的Coflows 占傳輸總字節的99.1%，因此吞吐量也能評價調度性能。

3.2 實驗結果與分析

本文選擇CCT 與吞吐量2 個指標作為判斷標準。CCT 指標作為判斷Coflow 調度性能的直接指標被廣泛使用。為有效對比鏈路的利用率，本文對不同調度機制的吞吐量進行對比。

3.2.1 CCT 指標

本文對Facebook 數據集中526 個Coflow 進行隨機分配任務，其任務到達時間遵循參數為θ的Poisson 分布，并將4 種不同類型的Coflow 流作為工作負載。圖4表示Baraat、Varys、Aalo 與Bamq 的Coflow 完成時間對比。從圖4（a）可以看出，Bamq 的CCT 平均比Baraat、Varys、Aalo 分別提高9.2%、13.5%、39.1%。這是因為Bamq 考慮網絡內瓶頸，從而比Varys 具有更精確的Coflow 優先級和帶寬分配，Bamq 提高了鏈路利用率。從圖4（b）可以看出，95%CCT 中Bamq 的CCT 平均比Baraat、Varys、Aalo 降低9.6%、14.6%、39.7%。Bamq 和Baraat 提高了鏈路利用率。

圖4 不同調度機制的CCT 對比Fig 4 CCT comparison among different scheduling mechanisms

圖5 表示4 種調度機制Coflow 完成時間的累積分布函數（Cumulative Distribution Function，CDF）。從圖5 可以看出，在這兩種負載下，Bamq 幾乎在所有百分比上都優于Varys、Baraat 和Aalo。在負載較小時，Bamq 的CCT 與Baraat 相似，主要與收斂速度相關。這個結果與圖4 的結果一致。

圖5 不同調度機制的Coflow 累積分布函數對比Fig 5 Cumulative distribution function of Coflow comparison among different scheduling mechanisms

3.2.2 吞吐量

Baraat、Varys、Aalo、Bamq 這4 種調度機制在不同工作負載下的吞吐量對比如圖6 所示。吞吐量是通過整個網絡傳輸的所有數據量除以所有Coflow的最大完成時間。在較低負荷下，4 種算法具有相似的吞吐量，在更大的負載下，Bamq 的吞吐量明顯高于Varys，略低于Baraat，相對于Baraat，Bamq 有一個收斂過程吞吐量損失很小。因此，Bamq 在優化CCT的同時保持了良好的鏈接利用率。

圖6 不同調度機制的吞吐量對比Fig 6 Throughput comparison among different scheduling mechanisms

為驗證Bamq 調度機制的收斂性，本文隨機選取3 個流，3 個流的收斂速度如圖7 所示。除了給初始流包讓路外，在短時間內3 個流大多收斂到最優速率，收斂前的平均速率也不小于最優速率，因為流量是從較大值開始收斂的。

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

3.2.3 結果分析

Bamq 調度機制是一種改進的多級隊列調度機制。初始化Coflow 優先級，然后在該隊列下，最大化Coflow 流的流速，以此降低CCT。通過設置多級隊列來分配其他Coflow 流，以此減低擁塞。

Bamq 根據Coflow 的已發大小、寬度、流速設計了全新的瓶頸因子，根據瓶頸因子大小決定Coflow 的優先級。流速是識別鏈路擁塞情況的關鍵信息，根據流速大小可以快速判斷網絡狀況。為評估CCT 與Coflow寬度等屬性的相關性，本文通過選擇Person 相關系數（PCC）作為評估指標。PCC 定義如下：

PCC 可以很好衡量兩個變量的線性關系，值越大，表明兩個變量的線性相關性越強。Person 相關性系數在計算2 個總體之間的相關性時要求兩個總體必須符合正態分布，對Person 相關性系數取對數，使其符合正態分布。Coflow 屬性相關度如表3 所示。

表3 Coflow 屬性相關度Table 3 Correlation degree of Coflow attributes

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

4 結束語

針對在云數據中心Coflow 調度過程中存在網絡瓶頸的問題，本文提出基于瓶頸感知的多級反饋隊列Coflow 調度機制Bamq。利用Lagrange 對偶優化Coflow 流速，以充分利用鏈路帶寬，從而減少CCT，為減少網絡擁塞，利用Lyapunov 優化多級反饋隊列模型，以確保隊列穩定性。在Facebook 的真實數據集和開源網絡模擬器NS-3 上的實驗結果表明，Bamq 調度機制在降低平均CCT 的前提下，能夠增大吞吐量，并且提高鏈路利用率。下一步將利用光電路交換機制優化流量調度，并結合邊緣技術提高核心互聯網絡的帶寬利用率。