柯文龍，王勇，葉苗,3，陳俊奇

（1.桂林電子科技大學信息與通信學院，廣西 桂林 541004；2.桂林電子科技大學計算機與信息安全學院，廣西 桂林 541004；3.桂林電子科技大學認知無線電與信息處理省部共建教育部重點實驗室，廣西 桂林 541004）

1 引言

全球范圍內(nèi)數(shù)據(jù)規(guī)模的高速增長已成為信息產(chǎn)業(yè)界所面臨的巨大挑戰(zhàn)。根據(jù)國際數(shù)據(jù)公司（IDC,International Data Corporation）的數(shù)據(jù)統(tǒng)計，全球數(shù)字領(lǐng)域數(shù)據(jù)量將由2018 年的33 ZB 增加到2025 年的175 ZB[1]。這種數(shù)據(jù)爆炸式增長所帶來的挑戰(zhàn)可以使用云存儲技術(shù)來應對，云存儲系統(tǒng)采用數(shù)據(jù)中心網(wǎng)絡技術(shù)將大量存儲設(shè)備集成為統(tǒng)一整體，進而提供海量且可擴展的存儲能力[2]。目前，已有多種云存儲系統(tǒng)投入商業(yè)使用，包括Ceph[3]、OpenStack Swift、Dropbox 以及Google Drive 等。其中，Ceph 因其穩(wěn)定的架構(gòu)、開源的思想和統(tǒng)一存儲的設(shè)計模式，得到了越來越多云存儲系統(tǒng)使用者的青睞。

隨著云存儲系統(tǒng)規(guī)模的不斷擴大，網(wǎng)絡問題逐漸成為云存儲系統(tǒng)的主要問題。云存儲網(wǎng)絡中的流調(diào)度問題，作為影響用戶體驗的關(guān)鍵問題之一，正受到越來越多的關(guān)注。相比一般網(wǎng)絡環(huán)境下的流調(diào)度問題，云存儲網(wǎng)絡下的流調(diào)度更加復雜。首先，云存儲網(wǎng)絡中流量的傳輸機制更加多樣。為了提高數(shù)據(jù)存儲的安全性與可靠性，云存儲系統(tǒng)常使用多副本存儲機制。在多副本存儲機制下，用戶上傳的數(shù)據(jù)首先被存儲在主存儲節(jié)點，再由主存儲節(jié)點分發(fā)至多個從存儲節(jié)點。這使云存儲網(wǎng)絡中不僅包含一對一的單播傳輸，還包含大量一對多的多播傳輸以降低數(shù)據(jù)分發(fā)時產(chǎn)生的冗余流量。其次，云存儲網(wǎng)絡中流量的類型也更加多樣。除了用戶執(zhí)行上傳下載時所產(chǎn)生的業(yè)務流量，作為一個大規(guī)模的分布式系統(tǒng)，云存儲系統(tǒng)本身也包含豐富的背景業(yè)務流，不同類型的背景業(yè)務流對網(wǎng)絡性能的需求也不相同。如心跳數(shù)據(jù)流用于監(jiān)測系統(tǒng)各模塊是否工作正常，需要的傳輸帶寬較少，但對時延相對敏感；而遷移業(yè)務流用于各存儲節(jié)點之間的負載均衡，對時延要求不高，但需要較大的傳輸帶寬。

因此，針對更加復雜的云存儲網(wǎng)絡環(huán)境，如何制定高效的云存儲網(wǎng)絡流調(diào)度方法以提高用戶的使用體驗，已成為云存儲系統(tǒng)管理者所面臨的巨大挑戰(zhàn)。首先，不同類型的業(yè)務流對網(wǎng)絡性能的要求不同，如何在一個共享的云存儲系統(tǒng)中滿足不同業(yè)務流的服務質(zhì)量需求是流調(diào)度所面臨的一個挑戰(zhàn)。其次，網(wǎng)絡的整體利用率同樣重要，如何在提高不同業(yè)務流服務質(zhì)量的同時盡可能地實現(xiàn)網(wǎng)絡的負載均衡以提高整體利用率，是設(shè)計云存儲網(wǎng)絡流調(diào)度方法所要面對的另一挑戰(zhàn)。最后，在云存儲網(wǎng)絡存在大量多播傳輸任務的背景下，如何構(gòu)建流調(diào)度的多播樹，并最大化降低數(shù)據(jù)分發(fā)時產(chǎn)生的冗余流量，也是制定云存儲網(wǎng)絡流調(diào)度方法所要面臨的挑戰(zhàn)之一。

因此，迫切需要設(shè)計一種云存儲網(wǎng)絡環(huán)境下的多播流調(diào)度方法，以實現(xiàn)在降低冗余流量、提高系統(tǒng)負載均衡性能的同時提高不同業(yè)務流的服務質(zhì)量性能。雖然云存儲系統(tǒng)采用數(shù)據(jù)中心網(wǎng)絡技術(shù)整合存儲設(shè)備，但現(xiàn)有的數(shù)據(jù)中心網(wǎng)絡流調(diào)度方法大多針對流量模式符合長尾分布的數(shù)據(jù)中心網(wǎng)絡環(huán)境，即90%的數(shù)據(jù)流為小流；剩余10%數(shù)據(jù)流為大流，卻占據(jù)了90%的網(wǎng)絡帶寬[4]。在這種數(shù)據(jù)中心網(wǎng)絡環(huán)境背景下，部分研究者提出針對所有數(shù)據(jù)流的通用調(diào)度方法[5-7]，即不考慮不同業(yè)務流之間的差異性，對所有數(shù)據(jù)流采用通用的調(diào)度策略。也有研究者按數(shù)據(jù)流的大小將其分為“大象流”與“老鼠流”，并分別采用不同的調(diào)度機制[8-10]。這些方法雖然在設(shè)計的應對場合取得了較好的效果，但難以應對云存儲網(wǎng)絡環(huán)境中針對不同業(yè)務的多播流調(diào)度需求。

對此，本文在Ceph 云存儲網(wǎng)絡環(huán)境下，給出一種針對多業(yè)務場景的多播流調(diào)度方法，主要貢獻如下。

1)提出Ceph 云存儲網(wǎng)絡中業(yè)務優(yōu)先級區(qū)分的多播流調(diào)度優(yōu)化模型。模型根據(jù)不同業(yè)務流對網(wǎng)絡性能的不同需求以及當前網(wǎng)絡的狀態(tài)信息，為各業(yè)務流定制最佳的傳輸路徑。通過最小化全網(wǎng)流量、最小化累積加權(quán)時延以及最小化最大鏈路帶寬利用率來提高系統(tǒng)的服務質(zhì)量性能。

2)提出基于理想解法（TOPSIS,technique for order preference by similarity to ideal solution）與最大公共子路徑的多播流調(diào)度方法（MFSTM,multicasting flow scheduling method based on TOPSIS and maximum common sub-path），將多播調(diào)度任務分解為多個單播調(diào)度的多屬性決策問題，并結(jié)合尋找最大公共子路徑的方法，設(shè)計求解多播流調(diào)度問題。

3)Mininet 搭建模擬Ceph 云存儲網(wǎng)絡環(huán)境，驗證MFSTM 的有效性與適用性。模擬平臺驗證表明，MFSTM 多播流調(diào)度方法可以在降低冗余流量、提高網(wǎng)絡負載均衡性能的同時，減少高優(yōu)先級業(yè)務流的傳輸時延。

2 相關(guān)工作

在大規(guī)模云存儲網(wǎng)絡環(huán)境中，網(wǎng)絡流調(diào)度技術(shù)對云存儲網(wǎng)絡的性能具有重要影響。它是指對于云存儲系統(tǒng)中各項服務產(chǎn)生的數(shù)據(jù)流，通過調(diào)度這些數(shù)據(jù)流在云存儲網(wǎng)絡中的傳輸路徑、傳輸優(yōu)先級等，來優(yōu)化網(wǎng)絡流量的傳輸，提高用戶的使用體驗[11]。在優(yōu)化傳輸路徑方面，ECMP（equal cost multipath）[12]為所有數(shù)據(jù)流隨機選擇一條可達目的節(jié)點的傳輸路徑，其目標是充分利用數(shù)據(jù)中心網(wǎng)絡中存在多路徑的特點，利用哈希的方式將數(shù)據(jù)流均衡地分配到各個傳輸路徑之上。Hedera[13]是一種集中控制式的流量調(diào)度方法，它將數(shù)據(jù)流按大小分類，并將大流分配到剩余帶寬較多的傳輸路徑上。在優(yōu)化傳輸優(yōu)先級方面，PDQ（preemptive distributed quick）[14]是一種以搶占方式執(zhí)行最小任務優(yōu)先的啟發(fā)式流調(diào)度方法，以數(shù)據(jù)流的剩余時間為傳輸優(yōu)先級的評判依據(jù)，剩余時間越小的數(shù)據(jù)流具有越高的傳輸優(yōu)先級。pFabric[15]將數(shù)據(jù)流的剩余量大小作為傳輸優(yōu)先級的評判依據(jù)，剩余量越小的數(shù)據(jù)流具有越高的傳輸優(yōu)先級。

上述流調(diào)度方法大多針對點對點的單播傳輸環(huán)境，然而隨著網(wǎng)絡業(yè)務越來越復雜，一對多的多播發(fā)送場景也越來越多。交互式網(wǎng)絡電視業(yè)務的視頻音頻分發(fā)[16]、云存儲系統(tǒng)的多副本復制[17]、傳感器監(jiān)視數(shù)據(jù)的分發(fā)[18]等業(yè)務都伴隨大量的多播傳輸需求?，F(xiàn)有的多播流調(diào)度技術(shù)大多結(jié)合軟件定義網(wǎng)絡（SDN,software defined network）技術(shù)，通過對網(wǎng)絡狀態(tài)信息的采集以及采用集中控制的思想提高對網(wǎng)絡的管理效率。RMMR（robust multipath multicast routing）[19]針對視頻流的分發(fā)場景，通過使用基于SDN 的多路徑多播流調(diào)度機制，獲得了比傳統(tǒng)網(wǎng)際互連協(xié)議（IP,internet protocol）多播機制更低的分組丟失率以及更好的網(wǎng)絡負載均衡能力。BCMS（multicast scheduling with bounded congestion）[20]是針對胖樹拓撲展開討論的數(shù)據(jù)中心網(wǎng)絡多播流調(diào)度方法，它根據(jù)多播業(yè)務流的網(wǎng)絡帶寬需求以及當前網(wǎng)絡各鏈路的剩余帶寬情況，為每個多播業(yè)務流計算最佳的傳輸路徑，以實現(xiàn)網(wǎng)絡擁塞控制與負載均衡。MSaSDN[21]針對基于胖樹拓撲的數(shù)據(jù)中心網(wǎng)絡，提出了基于最小化鏈路擁塞開銷的多播樹構(gòu)建方法，提高了網(wǎng)絡的負載均衡性能。MSaMC[22]針對目前SDN 網(wǎng)絡狀態(tài)測量的滯后性問題，通過結(jié)合馬爾可夫鏈，利用當前時隙的擁塞概率來預測下一時隙的擁塞概率，提高了網(wǎng)絡的吞吐量并降低了數(shù)據(jù)流的平均傳輸時延。DuSM[8]針對數(shù)據(jù)中心網(wǎng)絡的多播流調(diào)度問題，將數(shù)據(jù)流按大小分為“大象流”與“老鼠流”，針對“老鼠流”，將其多播任務轉(zhuǎn)化為多個單播任務，以降低交換機所需的流表數(shù)量；針對“大象流”，構(gòu)建多個共享樹，以實現(xiàn)其在多鏈路上的負載均衡。

上述多播流調(diào)度方法大多針對所有數(shù)據(jù)流給出通用的調(diào)度策略，或是僅按數(shù)據(jù)流的大小進行分類并給出2 種調(diào)度機制。然而在云存儲網(wǎng)絡環(huán)境下，出于成本的考慮，一個云存儲系統(tǒng)往往由多業(yè)務所共享。不同業(yè)務產(chǎn)生的數(shù)據(jù)流對網(wǎng)絡性能的要求不盡相同。如在以視頻業(yè)務為主的網(wǎng)絡環(huán)境下，網(wǎng)絡帶寬是需要考慮的重點因素[23]。在以游戲業(yè)務為主的網(wǎng)絡環(huán)境下，時延是用戶考量的重點[24]。而在以分布式計算任務為主的網(wǎng)絡環(huán)境下，不僅需要考慮一對多發(fā)送帶來的多播傳輸問題[25]，還需要考慮多對一發(fā)送所帶來的TCP-incast 問題[26]。因此，在云存儲網(wǎng)絡這種較為復雜的環(huán)境下采用單一的調(diào)度策略往往難以取得理想的效果。

因此，網(wǎng)絡流調(diào)度方法需要根據(jù)不同業(yè)務場景下各業(yè)務流對網(wǎng)絡性能的不同需求給出定制化的解決方案。本文針對現(xiàn)有網(wǎng)絡流調(diào)度方法難以處理云存儲網(wǎng)絡中多業(yè)務流的不同多播調(diào)度需求問題，以Ceph 云存儲系統(tǒng)為代表，結(jié)合SDN 中的集中控制思想，給出一種支持業(yè)務優(yōu)先級區(qū)分的云存儲網(wǎng)絡多播流調(diào)度方法。

3 云存儲網(wǎng)絡多播流調(diào)度問題的建模

本節(jié)首先簡單介紹基于SDN 與胖樹拓撲的Ceph 云存儲系統(tǒng)基本工作機制并分析其流量構(gòu)成，然后對云存儲網(wǎng)絡環(huán)境下的多播流調(diào)度問題進行分析與建模。建模目標是在降低系統(tǒng)冗余流量、提高系統(tǒng)負載均衡性能的同時，減少高優(yōu)先級業(yè)務流的傳輸時延，從而提高系統(tǒng)的服務質(zhì)量性能。

3.1 基于SDN 與胖樹拓撲的Ceph 云存儲系統(tǒng)

對數(shù)據(jù)流的傳輸路徑進行合理調(diào)度需要基于當前的網(wǎng)絡狀態(tài)信息。SDN 作為一種新的網(wǎng)絡模式，采用集中控制的思想，將控制平面與數(shù)據(jù)平面相分離，提高了網(wǎng)絡狀態(tài)測量以及網(wǎng)絡管理的靈活性。本文采用前期工作中基于SDN 的網(wǎng)絡狀態(tài)測量方法[27]實時更新并維護系統(tǒng)網(wǎng)絡中各鏈路的狀態(tài)信息，為流調(diào)度工作提供數(shù)據(jù)支撐。胖樹拓撲是當前數(shù)據(jù)中心網(wǎng)絡中最常見的多根樹拓撲之一，它為網(wǎng)絡內(nèi)部各源目的節(jié)點之間構(gòu)建多條并行路徑，提高了網(wǎng)絡內(nèi)部東西向流量的吞吐量并降低了單點故障與網(wǎng)絡熱點的出現(xiàn)概率。圖1 展示了基于SDN 與4 叉胖樹的Ceph 云存儲系統(tǒng)，其中pod 表示一組直接互聯(lián)的匯聚及邊緣交換機。

圖1 基于SDN 與4 叉胖樹的Ceph 云存儲系統(tǒng)

本文主要探討處于多副本工作模式下的Ceph集群，即用戶上傳一份數(shù)據(jù)至某個Ceph 節(jié)點后，該Ceph 節(jié)點會將數(shù)據(jù)復制并以多播傳輸?shù)姆绞椒职l(fā)至其他Ceph 節(jié)點進行多副本存儲，以提高數(shù)據(jù)的安全性與可靠性。除了用戶執(zhí)行上傳/下載操作產(chǎn)生的業(yè)務數(shù)據(jù)流之外，作為一個大規(guī)模的分布式系統(tǒng)，Ceph 集群也包含了心跳數(shù)據(jù)流和遷移數(shù)據(jù)流在內(nèi)的背景業(yè)務流。雖然Ceph 的數(shù)據(jù)遷移一般發(fā)生于系統(tǒng)空閑時，但由于數(shù)據(jù)遷移的時間常長達數(shù)小時，因此會出現(xiàn)遷移數(shù)據(jù)流與業(yè)務數(shù)據(jù)流同時存在的場景。在這種場景下，Ceph 云存儲網(wǎng)絡中主要包含如下3 種類型的流量。

1)心跳數(shù)據(jù)流，用于監(jiān)測Ceph 各節(jié)點是否正常工作。其擁有最高的傳輸優(yōu)先級，對時延高度敏感，需要的傳輸帶寬較少。

2)用戶業(yè)務數(shù)據(jù)流，由用戶執(zhí)行的上傳/下載任務產(chǎn)生。其完成時間直接影響用戶的使用體驗，具有較高的傳輸優(yōu)先級，對時延較為敏感，需要的傳輸帶寬較多。

3)系統(tǒng)遷移數(shù)據(jù)流數(shù)據(jù)流，由Ceph 系統(tǒng)的負載均衡機制產(chǎn)生。其時延不會影響系統(tǒng)的正常運行以及用戶的使用體驗，傳輸優(yōu)先級最低，但需要的網(wǎng)絡帶寬較多。

3.2 業(yè)務優(yōu)先級區(qū)分的多播流調(diào)度問題建模

云存儲網(wǎng)絡可以表示為G=(V,E)，其中，V表示網(wǎng)絡中的頂點，對應物理環(huán)境中的SDN 交換機；E表示頂點之間的邊。e=(εe,δe)表示從頂點εe到頂點δe的鏈路。第一個目標函數(shù)f1為找到使全網(wǎng)流量最小化的多播傳輸路徑。

其中，b?表示多播流?所需要的傳輸帶寬；be表示鏈路e的最大帶寬容量；式(2)所示約束條件保證了每個鏈路e上所分配的數(shù)據(jù)流的帶寬之和不大于鏈路的帶寬容量；x?e為一個二進制的決策參數(shù)，x?e=0 表示多播流?未經(jīng)過鏈路e，x?e=1 表示多播流?經(jīng)過了鏈路e。本文所用的符號及其對應的含義如表1 所示。

表1 符號及其對應的含義

除了最小化全網(wǎng)流量以降低云存儲網(wǎng)絡的整體負載外，為了進一步提高用戶的使用體驗，需要最小化累積加權(quán)時延，對應目標函數(shù)f2為

其中，w?表示多播流?對時延的敏感系數(shù)，它由業(yè)務流的特性決定，對時延越敏感的數(shù)據(jù)流對應的w?值越大；k表示一源到多端的多播傳輸路徑；p表示k中源到某一個端節(jié)點的單播傳輸路徑；d?p表示數(shù)據(jù)流經(jīng)路徑p的傳輸時延；約束條件(5)保證了每個多播路徑k上所分配的數(shù)據(jù)流的帶寬之和不大于多播路徑的瓶頸帶寬；約束條件(6)確保了每條多播流?必須選擇且只能選擇一個多播傳輸路徑；約束條件(7)保證了被選擇的多播路徑需要滿足數(shù)據(jù)流的最大傳輸時延限制；x?k為一個二進制的決策參數(shù)，x?k=0 表示多播流?未經(jīng)過多播路徑k，x?k=1表示多播流?經(jīng)過了多播路徑k。

在提高各業(yè)務流服務質(zhì)量的同時，整體系統(tǒng)的負載均衡性能同樣重要。最小化最大鏈路帶寬使用率的目標函數(shù)f3為

其中，約束條件(10)保證了每個鏈路e上所分配的數(shù)據(jù)流的帶寬之和不大于鏈路的帶寬容量，x?e為數(shù)據(jù)流進行鏈路選擇的二進制決策參數(shù)。

至此得到了在云存儲網(wǎng)絡中，針對多業(yè)務多播流調(diào)度問題的3 個目標函數(shù)，分別是最小化全網(wǎng)流量、最小化累積加權(quán)時延以及最小化最大鏈路帶寬使用率。由于這3 個目標函數(shù)不完全相互獨立，無法通過單獨處理同時得出各自的最優(yōu)解，因此整體的優(yōu)化目標函數(shù)Z為

針對上述云存儲網(wǎng)絡中不同業(yè)務流的多播調(diào)度問題，本文提出了基于理想解與最大公共子路徑的流調(diào)度方法。

4 MFSTM 多播流調(diào)度方法

Z的3 個子目標函數(shù)難以同時取得最小值，即難以同時找到滿足3 個子目標的最優(yōu)解。由于在Ceph 云存儲網(wǎng)絡中，提高多副本數(shù)據(jù)多播分發(fā)的效率可以有效降低用戶業(yè)務數(shù)據(jù)流的規(guī)模，進而降低系統(tǒng)負載并提高用戶使用體驗。因此，MFSTM 將最小化全網(wǎng)流量作為主要優(yōu)化目標。在找到一組滿足最小化全網(wǎng)流量的解集后，MFSTM 再根據(jù)剩余的優(yōu)化目標選擇其中的最佳傳輸路徑。具體的求解流程使用基于理想解的多屬性決策方法以及最大公共子路徑方法來實現(xiàn)。

針對一個多播流的發(fā)送請求flow?=(τ,T,b?,d?)，其中，τ表示數(shù)據(jù)流的源節(jié)點，T={t1,t2,…,ts}為該多播流的目的節(jié)點集合，b?、d?分別為數(shù)據(jù)流?傳輸所需的帶寬和最大傳輸時延閾值。MFSTM 首先使用基于SDN 的網(wǎng)絡狀態(tài)測量技術(shù)找出同時滿足數(shù)據(jù)流傳輸時延以及帶寬需求的鏈路集合；然后針對源節(jié)點與目的節(jié)點集合中的每個節(jié)點分別構(gòu)建點對點傳輸路徑，基于理想解法找出每個點對點傳輸?shù)那唉莻€最優(yōu)傳輸路徑；最后通過尋找各個點對點路徑之間的最大公共子路徑來確定多播樹，多播樹的分發(fā)節(jié)點為最大公共子路徑中的最后一個節(jié)點。

4.1 網(wǎng)絡狀態(tài)參數(shù)的選取及其向量化表示

合適網(wǎng)絡狀態(tài)參數(shù)的選取對于理想解這種多屬性決策方法的效果起決定性作用。本文針對云存儲網(wǎng)絡環(huán)境下的多播流調(diào)度場景，選擇傳輸路徑的剩余最大瓶頸帶寬、傳輸路徑的平均端到端時延以及核心交換機上的流表數(shù)量作為決策參數(shù)。這些決策參數(shù)表示為

其中，P表示數(shù)據(jù)流端到端傳輸路徑的集合，每條路徑p由多個鏈路e連接構(gòu)成。這些路徑的集合可以由Dijkstra[28]算法得出，如式(20)所示。

其中，BP表示每條傳輸路徑的剩余最大瓶頸帶寬的集合，由于每個路徑p由多個鏈路e連接構(gòu)成，路徑p的剩余最大瓶頸帶寬即為構(gòu)成它的各個鏈路e中的最小剩余帶寬值。這里的鏈路剩余帶寬可以通過基于SDN 的網(wǎng)絡狀態(tài)測量方法[27]得出，如式(21)所示。

其中，DP表示數(shù)據(jù)流分別經(jīng)過每條傳輸路徑的端到端時延集合。這里的端到端時延可以通過基于SDN 的網(wǎng)絡狀態(tài)測量方法[27]得出。

其中，OP表示每條路徑所經(jīng)過的核心交換機中已存在的流表數(shù)量的集合。流表數(shù)量越多則流表查找時延越高，同時選擇通過流表數(shù)量較多的核心交換機也會增加數(shù)據(jù)流沖突的概率。這里的交換機流表數(shù)量可以通過SDN 中的OpenFlow 協(xié)議獲得。

如式(19)～式(22)所示，MFSTM 在程序初始化時即采用Dijkstra 算法計算出任意2 個存儲節(jié)點之間的傳輸路徑，并存儲于專門的數(shù)據(jù)表中，再使用基于SDN 的網(wǎng)絡狀態(tài)測量方法實時更新這些路徑的剩余帶寬、平均傳輸時延等信息。因此，在后續(xù)的最優(yōu)路徑計算過程中，可以直接遍歷數(shù)據(jù)表以獲得當前的鏈路狀態(tài)信息，降低重復路徑發(fā)現(xiàn)所帶來的計算開銷。

4.2 基于理想解的最優(yōu)單播路徑計算

MFSTM 在處理一個包含s個目的節(jié)點的一對多的多播流請求時，首先將此多播流任務分解為s個點對點的單播任務，并分別使用基于理想解的路徑計算方法找到每個單播任務的前η個最優(yōu)路徑。

理想解法是一種有效的多屬性決策方案，該方案從歸一化的原始數(shù)據(jù)矩陣中構(gòu)造出決策問題的正理想解和負理想解。通過計算各方案與正、負理想解的距離作為評價方案的準則。MFSTM 中基于理想解的單播路徑計算方法如下。

步驟1基于SDN的網(wǎng)絡狀態(tài)測量與候選路徑選取

針對云存儲網(wǎng)絡G=(V,E)，其中，V為網(wǎng)絡中的節(jié)點，對應物理環(huán)境中的 SDN 交換機；E={e1,e2,…,eq}表示節(jié)點之間的邊。MFSTM 首先利用SDN 對網(wǎng)絡鏈路狀態(tài)進行周期性的測量，實時維護一張包含所有鏈路E及其對應鏈路信息的數(shù)據(jù)表M=(E,D,B,O)，其中，D={de1,de2,…,deq}和B={be1,be2,…,beq}分別對應鏈路集合E中各子鏈路的平均傳輸時延集合與剩余帶寬集合，O={o1,o2,…,on}為各核心交換機中當前流表數(shù)量的集合。針對一個單播流傳輸任務flowφ=(τφ,tφ,bφ,dφ)，其中，τφ和tφ分別表示單播流φ的源節(jié)點與目的節(jié)點，bφ和dφ分別表示單播流φ對鏈路帶寬和傳輸時延的要求。MFSTM 首先根據(jù)數(shù)據(jù)流對傳輸路徑的性能需求來對現(xiàn)有的網(wǎng)絡進行過濾，再使用基于Dijkstra 的路徑發(fā)現(xiàn)算法找到所有的候選路徑集P*，如式(23)所示。

并滿足P＊?P，對于?e∈P＊，有be≥bφ且dp≤dφ。

步驟2決策矩陣的構(gòu)造及其歸一化處理

基于上述選取的決策參數(shù)，給出決策矩陣M。

其中，矩陣的每一行表示一種決策參數(shù)，每一列表示一個候選的端到端傳輸路徑。

為了消除不同決策參數(shù)間不同量綱帶來的影響，采用極差標準化方法對決策矩陣進行歸一化處理。處理方式如式(25)和式(26)所示。

其中，式(25)用于處理成本型決策參數(shù)，如鏈路的傳輸時延以及交換機中的流表數(shù)量，這類決策參數(shù)的特點是越小的值對應越好的效果；式(26)用于處理效益型決策參數(shù)，如鏈路的剩余帶寬容量，這類參數(shù)的特點是越大的值對應越好的效果。

最終，得到經(jīng)過標準化處理的決策矩陣M＊。

步驟3加權(quán)決策矩陣的構(gòu)建及其正負理想解的確定

不同業(yè)務的數(shù)據(jù)流對不同網(wǎng)絡參數(shù)的敏感程度不同。如在云存儲網(wǎng)絡中，心跳數(shù)據(jù)流對傳輸時延的敏感性較高，但對帶寬的敏感性較低；而遷移數(shù)據(jù)流對時延的敏感性較低，但出于網(wǎng)絡負載均衡的考慮，會傾向選擇剩余帶寬較大的傳輸路徑。為3.1 節(jié)介紹的3 種業(yè)務數(shù)據(jù)流分別構(gòu)建權(quán)重系數(shù)向量W為

其中，wb、wd、wo分別表示業(yè)務流對鏈路剩余帶寬、鏈路平均端到端時延以及鏈路中核心交換機上的流表數(shù)量的權(quán)重系數(shù)。各權(quán)重系數(shù)一般通過實驗的方式獲取[29]，本文設(shè)定的權(quán)重系數(shù)將在實驗部分進行介紹。

根據(jù)權(quán)重系數(shù)向量得出不同業(yè)務流所對應的加權(quán)決策矩陣。以時延敏感流為例，其加權(quán)決策矩陣Z的元素Zij為

其中，i∈{1,2,3}，j∈{1,2,…,n}。

根據(jù)加權(quán)決策矩陣得出其正負理想解

其中，P+表示加權(quán)決策矩陣的正理想解，由所有候選路徑中每種決策參數(shù)的最大值構(gòu)成；P?表示加權(quán)決策矩陣的負理想解，由所有候選路徑中每種決策參數(shù)的最小值構(gòu)成。

步驟4計算每個候選傳輸路徑到正、負理想解的距離

其中，Zij為候選傳輸路徑[Z1j,Z2j,Z3j]T中的一個元素，分別為各候選路徑到其到正負理想解的歐氏距離。

步驟5計算每個候選路徑與最優(yōu)候選路徑的相對貼近度為

其中，相對貼近度越大表示該傳輸路徑越適合當前的單播流任務。

4.3 通過最大公共子路徑構(gòu)建多播樹

多播傳輸路徑的數(shù)據(jù)分發(fā)節(jié)點應盡量靠近接收節(jié)點，以最小化系統(tǒng)的冗余流量。針對一個具有s個目的節(jié)點的多播流發(fā)送請求，MFSTM 根據(jù)前述基于理想解的單播流路徑計算方法，為每個單播流計算出η個符合其對網(wǎng)絡性能需求的最優(yōu)單播路徑，得到{η1}+{η2}+…+{ηs}共η s個單播路徑。每個路徑p由一組有序的鏈路e連接構(gòu)成，其中e=(εe,δe)表示從相鄰節(jié)點εe到δe的鏈路。

定義1若路徑p滿足如下條件，則稱p為一組單播流路徑{η1}+{η2}+…+{ηs}中的最大公共子路徑。

條件1p同時分別為路徑集合{η1}、{η2}、{ηs}中某單播路徑的子路徑。

條件2沒有其他符合條件1 的路徑p'包含比p更多的鏈路e。

若ex為從發(fā)送節(jié)點出發(fā)的最大公共子路徑p中的最后一個有序鏈路，則MFSTM 選擇ex=(εex,δex)中的節(jié)點δex作為多播樹中的數(shù)據(jù)分發(fā)節(jié)點，并分別根據(jù)原單播路徑建立從δex出發(fā)至各接收節(jié)點的多播分發(fā)路徑，從而完成多播樹的構(gòu)建。若存在多個滿足最小化全網(wǎng)流量這一條件的多播樹，則從中選擇具有最大累計相對貼近度Ctotal的多播樹，具體計算如式(35)所示。

其中，s表示多播流的接收節(jié)點數(shù)量，φ表示發(fā)送節(jié)點至某一個接收節(jié)點的單播任務流，j表示每個單播流φ可以選擇的候選路徑，表示單播流φ根據(jù)式(34)在各候選路徑j中可以得到的最大相對貼近度。

最后，通過一個調(diào)度實例來進一步說明MFSTM 構(gòu)建多播路徑的基本流程。假設(shè)有一個多播任務流{1,(2,3),b,d}，表示其發(fā)送節(jié)點為交換機1，接收節(jié)點為交換機2 與交換機3，所需帶寬和時延約束分別為b和d。MFSTM 首先將此多播任務分解為2 個單播任務，分別為{1,2,b,d}與{1,3,b,d}；其次，利用基于理想解的最優(yōu)單播路徑計算方法分別為2 個單播任務計算滿足約束條件的最優(yōu)單播路徑集，這里取每個路徑集中包含的路徑數(shù)量η=2。如圖2(a)所示，為單播任務{(diào)1,2,b,d}計算得出的最優(yōu)路徑集為{[1,4,7,5,2],[1,4,8,5,2]}。如圖2(b)所示，為單播任務{(diào)1,3,b,d}計算得出的最優(yōu)路徑集為{[1,4,8,6,3],[1,4,9,6,3]}。最后，找到2 個解集從發(fā)送節(jié)點出發(fā)的最大公共子路徑為[1,4,8]。通過將交換機8 作為多播樹的分發(fā)節(jié)點，并按原單播路徑建立從交換機8 至各接收節(jié)點的多播分發(fā)路徑，得到如圖2(c)中所示的多播路徑[1,4,8,(5,6),(2,3)]。

圖2 MFSTM 的調(diào)度實例

5 實驗設(shè)置與性能評估

本節(jié)對MFSTM 多播流調(diào)度方法進行實驗設(shè)置與性能評估。實驗使用Mininet[30]網(wǎng)絡模擬器構(gòu)建實驗網(wǎng)絡拓撲，并在開源的SDN 控制器RYU[31]上部署 MFSTM 流調(diào)度方法的邏輯，最后使用TCPreplay[32]重放真實的Ceph 云存儲系統(tǒng)業(yè)務數(shù)據(jù)流[33]以測試流調(diào)度方法的性能。整體實驗平臺搭建于一臺曙光A840r-G 服務器上，服務器擁有64 核×2.1 GHz 處理器，64 GB 內(nèi)存以及600 GB 硬盤。其中，每個處理器核被用于單獨處理一個TCPreplay進程，使其能夠以恒定速率發(fā)送一個長數(shù)據(jù)流。

在實驗拓撲選擇方面，由于Ceph 云存儲系統(tǒng)中用戶業(yè)務數(shù)據(jù)的多個副本常被存儲于不同的pod中以提高數(shù)據(jù)的安全性。因此，圖1 所示拓撲可以抽象為圖3。實驗中利用Mininet 2.3.0 構(gòu)建圖3 中的網(wǎng)絡拓撲作為實驗系統(tǒng)拓撲，并設(shè)定鏈路帶寬為50 Mbit/s。

圖3 實驗系統(tǒng)拓撲

在數(shù)據(jù)流選擇方面，如前文所述，本文主要探討多副本工作模式下，Ceph 集群執(zhí)行數(shù)據(jù)遷移任務出現(xiàn)用戶業(yè)務數(shù)據(jù)時的網(wǎng)絡流調(diào)度問題。此時，系統(tǒng)中的數(shù)據(jù)流包括心跳數(shù)據(jù)流、用戶業(yè)務數(shù)據(jù)流以及系統(tǒng)遷移數(shù)據(jù)流。實驗采用本文前期工作中采集的Ceph 云存儲集群真實數(shù)據(jù)流[33]，數(shù)據(jù)流的統(tǒng)計特征如表2 所示。

表2 Ceph 云存儲系統(tǒng)中不同業(yè)務流的統(tǒng)計特征

表2 中的不同業(yè)務流在采集時被分別保存為不同的pcap 文件。在本文的實驗過程中，通過使用TCPreplay 重放這些pcap 數(shù)據(jù)流，以模擬真實的Ceph 云存儲系統(tǒng)運行環(huán)境，每輪模擬實驗的測試時長設(shè)定為180 s。對于用戶業(yè)務數(shù)據(jù)流以及系統(tǒng)遷移數(shù)據(jù)流，流量的重放速度與其自身的流速率相同，分別為12.93 Mbit/s 以及4.36 Mbit/s。對于心跳數(shù)據(jù)流，為了降低模擬實驗環(huán)境中的分組丟失率，將對它的重放速率設(shè)定為1 Mbit/s。同時，受限于模擬實驗的測試時長，只重放系統(tǒng)遷移數(shù)據(jù)流的前40 000 個數(shù)據(jù)分組，以使其流的持續(xù)時間降低至78 s，從而可以在測試時長內(nèi)完成流的全部發(fā)送。

為了進一步測試流調(diào)度方法在不同網(wǎng)絡負載下的性能，實驗設(shè)置了3 種流量負載場景。

1)低負載場景：60 條心跳數(shù)據(jù)流，10 條用戶業(yè)務數(shù)據(jù)流，10 條系統(tǒng)遷移數(shù)據(jù)流。

2)中負載場景：60 條心跳數(shù)據(jù)流，20 條用戶業(yè)務數(shù)據(jù)流，20 條系統(tǒng)遷移數(shù)據(jù)流。

3)高負載場景：60 條心跳數(shù)據(jù)流，30 條用戶業(yè)務數(shù)據(jù)流，30 條系統(tǒng)遷移數(shù)據(jù)流。

因為心跳數(shù)據(jù)流是以恒定周期在不同Ceph 節(jié)點之間進行傳輸?shù)?，所以其流?shù)目在測試時長確定時保持不變。在每輪測試過程中，隨機選擇一個Ceph 節(jié)點作為數(shù)據(jù)的發(fā)送節(jié)點，并在180 s 內(nèi)周期性地為每條數(shù)據(jù)流開啟一個TCPreplay 進程以執(zhí)行數(shù)據(jù)流的發(fā)送。對于心跳數(shù)據(jù)流和系統(tǒng)遷移數(shù)據(jù)流，因其點對點的業(yè)務特性，TCPreplay 為其隨機選擇一個剩余Ceph 節(jié)點作為數(shù)據(jù)的接收節(jié)點，執(zhí)行單播發(fā)送；對于用戶業(yè)務流，按常見三副本存儲模式下主副本需要向其他2 個從副本進行數(shù)據(jù)備份的業(yè)務場景，TCPreplay 為其隨機選擇2 個剩余Ceph 節(jié)點作為數(shù)據(jù)的接收節(jié)點，執(zhí)行多播發(fā)送。具體的流量調(diào)度以及鏈路選擇采用MFSTM多播流調(diào)度算法，其中單播流被認為是只有一個接收節(jié)點的特殊多播流進行處理。MFSTM 對心跳數(shù)據(jù)流、用戶業(yè)務數(shù)據(jù)流、系統(tǒng)遷移數(shù)據(jù)流設(shè)定的權(quán)重系數(shù)向量分別為[0,0.5,0.5]、[0.5,0.4,0.1]、[1,0,0]。

實驗將本文給出的MFSTM 與ECMP[11]以及BCMS[19]進行對比。其中，ECMP 是數(shù)據(jù)中心網(wǎng)絡中最常見的流調(diào)度方法之一，它采用哈希的方式為數(shù)據(jù)流在多條可達的路徑中隨機選擇一條作為傳輸路徑，以實現(xiàn)負載均衡。當ECMP 處理多播流時，需要將一個多播流分解成多個點對點的單播流分別進行處理。BCMS 是一種有效的針對胖樹網(wǎng)絡拓撲的多播流調(diào)度方法，它根據(jù)多播數(shù)據(jù)流的帶寬需求以及當前的網(wǎng)絡狀態(tài)為多播流選擇合適的傳輸路徑，以實現(xiàn)網(wǎng)絡擁塞控制以及負載均衡。實驗的對比項包括總體帶寬利用率、不同鏈路間的帶寬利用率標準差、核心交換機上的流表數(shù)量以及不同業(yè)務流的平均傳輸時延，每組實驗測試5 次，實驗結(jié)果取平均值。

5.1 鏈路帶寬利用率標準差

圖4 給出了在不同負載場景下，實驗系統(tǒng)各鏈路之間帶寬利用率的標準差。標準差越小表明各鏈路之間的帶寬利用率越均衡，系統(tǒng)網(wǎng)絡的負載均衡性能越好。如圖4 所示，3 種方法下的帶寬利用率標準差在0～42 s 都呈現(xiàn)快速上升的狀態(tài)，并在42 s后保持相對穩(wěn)定。這是由于占用帶寬最多的用戶業(yè)務數(shù)據(jù)流擁有39.31 s 的流持續(xù)時間。在約42 s 處，第一條用戶業(yè)務數(shù)據(jù)流完成傳輸，此后系統(tǒng)網(wǎng)絡中的用戶業(yè)務數(shù)據(jù)流數(shù)目保持恒定，從而使系統(tǒng)的整體負載達到相對穩(wěn)定的狀態(tài)。

圖4 鏈路帶寬利用率標準差

實驗結(jié)果表明，在低、中、高3 種負載場景下，使用MFSTM 時帶寬利用率標準差的平均值分別比使用ECMP 時降低了30.8%、29.8%以及22.9%，取得了與BCMS 相近的負載均衡效果。這是由于ECMP 在進行路徑選擇時為所有數(shù)據(jù)流隨機選擇路徑，若將多條大流分配到同一路徑則會造成網(wǎng)絡負載的不均衡。而MFSTM 與BCMS 在進行路徑選擇時會考慮網(wǎng)絡當前的狀態(tài)，為數(shù)據(jù)流選擇剩余帶寬較多的路徑進行傳輸。

5.2 總體帶寬利用率

系統(tǒng)的總體帶寬利用率如式(36)所示。

其中，e表示實驗系統(tǒng)拓撲中相鄰交換機之間的網(wǎng)絡鏈路，be表示鏈路e的最大傳輸帶寬，euse表示當前時刻鏈路e的帶寬利用率。圖5 給出了在不同負載場景下實驗系統(tǒng)的總體帶寬利用率。當實驗系統(tǒng)處于低、中負載場景下，使用MFSTM 時系統(tǒng)總體帶寬利用率的上升速度相比使用ECMP 時更慢，且在所有測量時刻下的總體帶寬利用率平均值比使用ECMP 時的總體帶寬利用率分別下降了17.8%和12.7%，取得了與BCMS 相近的效果。這是由于MFSTM 與BCMS 為用戶業(yè)務數(shù)據(jù)流建立了有效的多播傳輸路徑，節(jié)約了網(wǎng)絡傳輸帶寬。

然而，在如圖5(c)所示的高負載場景下，雖然使用MFSTM 下的系統(tǒng)總體帶寬利用率在上升階段低于ECMP，但在42 s 后的負載相對穩(wěn)定階段，使用MFSTM 擁有比使用ECMP 更高的總體帶寬利用率。這是由于在高負載場景下，MFSTM 根據(jù)鏈路的剩余帶寬對數(shù)據(jù)流進行了合理的分配，避免了多條大流選擇相同傳輸路徑而產(chǎn)生的鏈路擁塞，提高了系統(tǒng)在高負載場景下的網(wǎng)絡吞吐量。MFSTM 與BCMS 擁有相近的總體帶寬利用率，因為在實驗設(shè)計的云存儲流量模式下，即多播流的接收節(jié)點有2 個且分布在不同的pod 中，MFSTM 與BCMS 同時選擇了各核心交換機作為多播路徑中的數(shù)據(jù)分發(fā)節(jié)點，實現(xiàn)了最大化降低系統(tǒng)冗余流量。

5.3 核心交換機上的流表數(shù)量

圖6 給出了在完成全部數(shù)據(jù)流的發(fā)送后，實驗系統(tǒng)拓撲圖中4 臺核心交換機上流表數(shù)量的標準差。由于實驗過程中的數(shù)據(jù)流都是在不同pod 之間進行傳輸，因此其傳輸路徑必須通過且只通過一臺核心交換機。每當一條數(shù)據(jù)流被分配到一條傳輸路徑上時，SDN 控制器會向這條路徑上的所有交換機下發(fā)2 條流表，分別對應數(shù)據(jù)流的往返傳輸路徑。因此，各核心交換機上的流表數(shù)量越均衡，表明數(shù)據(jù)流在不同傳輸路徑上的調(diào)度越均衡。同時，這也避免了多條流表集中于某一臺核心交換機，降低了交換機所需的最大流表空間，節(jié)約了寶貴的流表資源。

圖5 鏈路帶寬利用率標準差

如圖6 所示，MFSTM 在所有負載場景下都擁有最小的核心交換機流表數(shù)量標準差。這是由于MFSTM 在對高優(yōu)先級流進行路徑選擇時，會優(yōu)先選擇具有更小流表數(shù)量的核心交換機所在的路徑，可以降低數(shù)據(jù)流在傳輸過程中的流表查找時延。

圖6 核心交換機之間流表數(shù)量的標準差

圖7 平均傳輸時延

5.4 平均傳輸時延

圖7 給出了具有不同傳輸優(yōu)先級的業(yè)務流在不同負載場景下的平均傳輸時延。對于單播業(yè)務流，實驗中記錄的是其端到端傳輸時延；對于具有多個接收節(jié)點的多播業(yè)務流，實驗中記錄的是發(fā)送節(jié)點與最后一個收到數(shù)據(jù)的接收節(jié)點之間的端到端傳輸時延。在如圖7(a)所示的低負載場景下，不同方法之間各業(yè)務流的平均傳輸時延沒有較為明顯的差異。這是由于在低負載場景下，交換機可以有效處理數(shù)據(jù)流的轉(zhuǎn)發(fā)，即使多條數(shù)據(jù)流被分配到同一傳輸路徑，傳輸時延也不會有明顯的增加。在中負載以及高負載場景下，MFSTM 與BCMS 因較好的網(wǎng)絡負載均衡性能，避免了ECMP 下因鏈路擁塞而導致的傳輸時延大幅上升。

更重要的是，對于傳輸優(yōu)先級較高的心跳數(shù)據(jù)流與用戶業(yè)務數(shù)據(jù)流，MFSTM 具有更小的傳輸時延。如圖7(b)和圖7(c)所示，與BCMS 相比，在中、高負載場景下使用MFSTM，可以使具有最高傳輸優(yōu)先級的心跳數(shù)據(jù)流的傳輸時延分別下降37.9%和9.0%。對于具有次高傳輸優(yōu)先級的用戶業(yè)務數(shù)據(jù)流，在中、高負載場景下使用MFSTM 可以比使用BCMS 分別降低14.9%和7.5%的平均傳輸時延。實驗結(jié)果表明，本文給出的MFSTM 可以降低高優(yōu)先級流的平均傳輸時延，從而為系統(tǒng)提供更好的服務質(zhì)量性能。

6 結(jié)束語

針對Ceph 云存儲網(wǎng)絡環(huán)境中不同業(yè)務流對網(wǎng)絡性能的差異化需求，本文給出了一種基于理想解與最大公共子路徑的多播流調(diào)度方法，以實現(xiàn)支持業(yè)務優(yōu)先級區(qū)分的多播流調(diào)度。首先將多播業(yè)務流分解為多個單播任務，給出一種基于理想解法的最優(yōu)單播路徑選擇方法，為各單播任務尋找符合其對網(wǎng)絡性能需求的最優(yōu)單播路徑集；再通過各路徑集間的最大公共子路徑確定多播樹的數(shù)據(jù)分發(fā)節(jié)點以構(gòu)建多播傳輸路徑。實驗結(jié)果表明，MFSTM可以在降低冗余流量、提高網(wǎng)絡負載均衡性能的同時，降低高優(yōu)先級流的傳輸時延，提高了系統(tǒng)的服務質(zhì)量性能。下一步計劃在更大規(guī)模的云存儲網(wǎng)絡環(huán)境中測試并優(yōu)化MFSTM 的性能。在基于SDN 的大規(guī)模云存儲網(wǎng)絡環(huán)境中，SDN 控制器需要定期向更多的交換機發(fā)送探測分組并處理回復以實時維護全網(wǎng)的狀態(tài)信息。單個SDN 控制器的集中控制和管理將成為瓶頸，需要使用多個SDN控制器進行協(xié)同管理，將涉及SDN 多控制器的控制域劃分、協(xié)同通信以及數(shù)據(jù)一致性。這些都是需要后續(xù)進行的更有意義的研究工作。