面向數(shù)據(jù)中心網(wǎng)絡(luò)流量的路由優(yōu)化設(shè)計*

陳 松，謝 衛(wèi)

（中國電子科技集團(tuán)公司第三十研究所，四川 成都 600045）

0 引 言

基于軟件定義的數(shù)據(jù)中心網(wǎng)絡(luò)采用控制平面和數(shù)據(jù)平面分離的思想。分離出的控制平面為應(yīng)用程序提供北向編程接口，并通過南向接口控制數(shù)據(jù)平面的轉(zhuǎn)發(fā)行為。集中式運(yùn)行的網(wǎng)絡(luò)控制平面具有靈活和細(xì)粒度的控制能力，是網(wǎng)絡(luò)的“大腦”，在軟件定義的數(shù)據(jù)中心網(wǎng)絡(luò)具有舉足輕重的作用。網(wǎng)絡(luò)控制器可以根據(jù)當(dāng)前網(wǎng)絡(luò)狀態(tài)和流的信息，為業(yè)務(wù)流量優(yōu)化路由選擇，實現(xiàn)全局網(wǎng)絡(luò)流量分布優(yōu)化，提高流量傳輸性能。

1 數(shù)據(jù)中心網(wǎng)絡(luò)流量特點(diǎn)

與傳統(tǒng)網(wǎng)絡(luò)相比，數(shù)據(jù)中心網(wǎng)絡(luò)業(yè)務(wù)和拓?fù)浣Y(jié)構(gòu)有其特殊性。比如，數(shù)據(jù)中心網(wǎng)絡(luò)中90%以上的流為小流，只有約10%的流為大流。小流通常需要在盡量短的時間內(nèi)完成，而大流占用80%以上的網(wǎng)絡(luò)帶寬。再如，由于數(shù)據(jù)中心網(wǎng)絡(luò)特有的業(yè)務(wù)類型（如MapReduce業(yè)務(wù)），數(shù)據(jù)中心網(wǎng)絡(luò)中傳輸?shù)娜舾蓚€流通常具有相關(guān)性（通常稱為Coflow）。為了保證Coflow的性能，網(wǎng)絡(luò)需要對Coflow進(jìn)行合理調(diào)度和路由。為了保證網(wǎng)絡(luò)對不同流的傳輸性能要求，需要重點(diǎn)研究面向海量流的數(shù)據(jù)中心網(wǎng)絡(luò)流路由優(yōu)化方法。同時，為了保證數(shù)據(jù)中心網(wǎng)絡(luò)中特有的Coflow的傳輸性能，還要研究如何對Coflow的調(diào)度和路由進(jìn)行聯(lián)合優(yōu)化。

2 面向海量流的數(shù)據(jù)中心網(wǎng)絡(luò)路由優(yōu)化方法

隨著數(shù)據(jù)中心網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大和應(yīng)用的不斷增加，數(shù)據(jù)中心網(wǎng)絡(luò)中傳輸?shù)牧鞯臄?shù)目將非常巨大。因此，在大規(guī)模數(shù)據(jù)中心網(wǎng)絡(luò)中要實現(xiàn)海量流的路由優(yōu)化必然面臨可擴(kuò)展性的問題，即網(wǎng)絡(luò)控制可能無法在可接受的時間限制內(nèi)完成流的路由優(yōu)化計算。這是一項需要突破的關(guān)鍵技術(shù)[1]。

為了解決該問題，一種是發(fā)展并行的路由優(yōu)化方法，通過利用CPU多線程并行計算能力來減少路由優(yōu)化的計算時間。目前，雖然通用CPU通常都具有多個核心，且每個核心能支持多個線程，但是由于體系架構(gòu)的限制，一個CPU能支持的線程也只有數(shù)十個到上百個，無法為并行路由計算帶來滿意的并行增益。近年來，GPU的性能和通用計算編程模型有了非常大的改進(jìn)。與CPU相比，GPU能同時支持?jǐn)?shù)以萬計的線程，并行計算能力非常可觀。因此，采用基于GPU實現(xiàn)并行路由優(yōu)化算法比較適合[2]。

GPU雖然能支持海量的并行線程，但是其獨(dú)特的體系架構(gòu)決定了它處理復(fù)雜邏輯的能力較弱，且在host device編程模型下，算法的數(shù)據(jù)在每次迭代中都要從主內(nèi)存拷貝到設(shè)備內(nèi)存，會消耗額外的時間。因此，一個高效的運(yùn)行于GPU環(huán)境上的并行算法應(yīng)該具有以下兩個特征。第一，算法的并行度要非常高，并每個并行線程的計算邏輯要簡單；第二，算法的迭代次數(shù)要少。因此，擬使用拉格朗日松弛方法來分解路由優(yōu)化問題，并使用并行化的Bellman-Ford最短算法為每個業(yè)務(wù)計算路由。

首先，數(shù)據(jù)中心網(wǎng)絡(luò)路由優(yōu)化問題可以建模為如下的混合整數(shù)規(guī)劃模型：

上述模型中使用到的符號定義如表1所示。

表1 路由優(yōu)化模型中使用的符號

模型中，式（1）為流量守恒約束，該約束限制流的路由，式（2）為鏈路容量約束。通過使用拉格朗日松弛方法，可以把式（3）松弛到優(yōu)化目標(biāo)，進(jìn)而得到模型：

容易得知，上述模型等價于在鏈路權(quán)重(wij+λij)下求解每個流的最短路徑。由于松弛掉式（4）后，模型中的流之間沒有了相互關(guān)系，所以他們的最短路由可以并行計算。但是，如果使用串行算法為每個流計算最短路由，會涉及復(fù)雜的邏輯判斷而影響算法的并行效率。為了解決這個問題，可以通過使用并行化的Bellman-Ford算法來為每個流計算路由，以提高算法的并行度和降低單個并行線程的邏輯復(fù)雜度。在GPU上實現(xiàn)并行路由計算的設(shè)計方案，如圖1所示?？梢钥吹剑珺ellman-ford最短路算法中針對每條邊的松弛操作都在獨(dú)立的線程上并行完成，且不同業(yè)務(wù)的最短路計算也是并行完成，所以該方案的并行程度非常高，每個并行進(jìn)程處理的邏輯非常簡單，有利于GPU并行計算環(huán)境[3]。

圖1 基于GPU的并行路由算法設(shè)計方案

上述方法還會涉及如何選擇拉格朗日乘子的步長、如何減少迭代的次數(shù)等提高算法效率的關(guān)鍵問題。

3 數(shù)據(jù)中心Coflow的調(diào)度和路由聯(lián)合優(yōu)化算法

相較于傳統(tǒng)Internet中的流量，數(shù)據(jù)中心網(wǎng)絡(luò)中的流量有一個明顯的特征：執(zhí)行前一個任務(wù)的前一個階段的主機(jī)，會把中間數(shù)據(jù)發(fā)送給執(zhí)行后一個階段任務(wù)的主機(jī)作為后一個階段任務(wù)的輸入數(shù)據(jù)。這些數(shù)據(jù)往往來自于多個不同的主機(jī)，即由多個流共同完成中間數(shù)據(jù)的傳輸。在這樣的一組流中，只要有一個流的傳輸沒有完成，下一階段的計算就無法開始。比如，在MapReduce中，一個Reduce只有在接收完所有Map產(chǎn)生的數(shù)據(jù)后才會開始進(jìn)行計算。于是，有人提出了Coflow的概念，來定義這樣一組有語意相關(guān)性的流[4]。為了優(yōu)化網(wǎng)絡(luò)中應(yīng)用的性能，需要優(yōu)化這樣的Coflow完成時間，而不是與傳統(tǒng)網(wǎng)絡(luò)一樣，對單個流的完成時間進(jìn)行優(yōu)化。

在給定每一個Coflow中所有單個流的信息（如流的大小，源目節(jié)點(diǎn)）的情況下，網(wǎng)絡(luò)控制器需要實時決定每個流的路徑、何時啟動以及傳輸速率等，即Coflow的調(diào)度和路由問題。例如，在數(shù)據(jù)中心網(wǎng)絡(luò)中對Coflow平均完成時間進(jìn)行優(yōu)化時，需要對流量路由和調(diào)度進(jìn)行聯(lián)合優(yōu)化，如圖2所示。

圖2中，有2個Coflow，分別為Coflow a和Coflow b。其中，Coflow a有兩個流，分別是fa1和fa2，兩個流的大小分別為40 Mb和100 Mb。同樣，Coflow b也有兩個流，分別是fb1和fb2，大小分別為60 Mb和100 Mb。四個流都需要從網(wǎng)絡(luò)中的S節(jié)點(diǎn)發(fā)送到D節(jié)點(diǎn)。每個流都有兩條路可以選擇，分別是S→Mu→D和S→Md→D。同時，例子中的所有鏈路帶寬都是100 Mb/s。通過枚舉可以知道，這個例子里，最小的Coflow平均完成時間是1.3 s。

圖2（a）給出了利用等價多路徑協(xié)議（Equal Cost Multi-Path，ECMP）進(jìn)行路由所得到的一種情況。如果在該路由策略下，采用公平共享鏈路帶寬的調(diào)度策略（即單純的TCP競爭所得到的結(jié)果），那么對于兩個Coflow來說，路徑S→Md→D會是它們的瓶頸。因為在這條路徑上承載了兩個流，所以每個流可以分到50 Mb/s的帶寬，從而兩個流都會在2 s時完成。所以，兩個Coflow的完成時間都是2 s，Coflow平均完成時間也是2 s。如果按照如圖2（d）所示的調(diào)度方案，兩個Coflow的完成時間分別為1 s和2 s，則Coflow平均完成時間為1.5 s?？梢钥闯?，對于網(wǎng)絡(luò)流量優(yōu)化，即減小網(wǎng)絡(luò)中Coflow的平均完成時間，調(diào)度可以起到很大作用。但是，在圖2（a）所示的路由下，僅靠調(diào)整調(diào)度策略能得到的最小Coflow平均完成時間也是1.5 s，離1.3 s的最好性能還有一定距離。這是因為在圖2（a）的路由條件下，兩條路徑上所承載的流量嚴(yán)重不平衡，S→Md→D上的流量是S→Mu→D上流量的2倍。因此，僅靠調(diào)度并不能得到最優(yōu)的Coflow平均完成時間。

圖2（b）給出了一種負(fù)載均衡的路由方式：Coflow a的兩個流都經(jīng)過路徑S→Mu→D，而Coflow b的兩個流都經(jīng)過路徑S→Md→D。在這一路由策略下，使用圖2（e）所示的調(diào)度策略，兩個Coflow的完成時間分別為1.4 s和1.6 s。此時，Coflow平均完成時間為1.5 s，依舊不是最優(yōu)。原因是同一個Coflow的所有流都被路由到同一條路徑上，使得調(diào)度策略很難對平均完成時間的優(yōu)化起到作用。事實上，該例子中，如果采用圖2（b）所示的路由方案，無論采用何種調(diào)度策略，只要充分利用網(wǎng)絡(luò)帶寬，Coflow平均完成時間都不會改變。因此，獨(dú)立考慮路由和調(diào)度并不能得到一個好的解[5]。

圖2 數(shù)據(jù)中心網(wǎng)絡(luò)流量優(yōu)化需要路由和調(diào)度的聯(lián)合

由此可以看出，對數(shù)據(jù)中心網(wǎng)絡(luò)中的Coflow平均完成時間進(jìn)行優(yōu)化時，需要對路由和調(diào)度進(jìn)行統(tǒng)一優(yōu)化。本例中，采用圖2（c）中的路由方案和圖2（f）中的調(diào)度策略，才能得到最優(yōu)的Coflow平均完成時間。此時，兩個Coflow的完成時間分別為1 s和1.6 s，平時完成時間為1.3 s。

4 結(jié) 語

在數(shù)據(jù)中心網(wǎng)絡(luò)業(yè)務(wù)路由方面，本文針對數(shù)據(jù)中心網(wǎng)絡(luò)中存在的幾種特殊業(yè)務(wù)模式，提出面向海量流采用GPU并行計算的路由優(yōu)化算法，提高了路由控制的實時性。另外，針對數(shù)據(jù)中心常見的Coflow流設(shè)計了調(diào)度和路由聯(lián)合的優(yōu)化算法，進(jìn)一步提高了業(yè)務(wù)傳輸?shù)姆?wù)質(zhì)量。