面向數據中心網絡流量的路由優化設計*

陳 松，謝 衛

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

0 引 言

基于軟件定義的數據中心網絡采用控制平面和數據平面分離的思想。分離出的控制平面為應用程序提供北向編程接口，并通過南向接口控制數據平面的轉發行為。集中式運行的網絡控制平面具有靈活和細粒度的控制能力，是網絡的“大腦”，在軟件定義的數據中心網絡具有舉足輕重的作用。網絡控制器可以根據當前網絡狀態和流的信息，為業務流量優化路由選擇，實現全局網絡流量分布優化，提高流量傳輸性能。

1 數據中心網絡流量特點

與傳統網絡相比，數據中心網絡業務和拓撲結構有其特殊性。比如，數據中心網絡中90%以上的流為小流，只有約10%的流為大流。小流通常需要在盡量短的時間內完成，而大流占用80%以上的網絡帶寬。再如，由于數據中心網絡特有的業務類型（如MapReduce業務），數據中心網絡中傳輸的若干個流通常具有相關性（通常稱為Coflow）。為了保證Coflow的性能，網絡需要對Coflow進行合理調度和路由。為了保證網絡對不同流的傳輸性能要求，需要重點研究面向海量流的數據中心網絡流路由優化方法。同時，為了保證數據中心網絡中特有的Coflow的傳輸性能，還要研究如何對Coflow的調度和路由進行聯合優化。

2 面向海量流的數據中心網絡路由優化方法

隨著數據中心網絡規模的不斷擴大和應用的不斷增加，數據中心網絡中傳輸的流的數目將非常巨大。因此，在大規模數據中心網絡中要實現海量流的路由優化必然面臨可擴展性的問題，即網絡控制可能無法在可接受的時間限制內完成流的路由優化計算。這是一項需要突破的關鍵技術[1]。

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

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

首先，數據中心網絡路由優化問題可以建模為如下的混合整數規劃模型：

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

表1 路由優化模型中使用的符號

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

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

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

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

3 數據中心Coflow的調度和路由聯合優化算法

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

在給定每一個Coflow中所有單個流的信息（如流的大小，源目節點）的情況下，網絡控制器需要實時決定每個流的路徑、何時啟動以及傳輸速率等，即Coflow的調度和路由問題。例如，在數據中心網絡中對Coflow平均完成時間進行優化時，需要對流量路由和調度進行聯合優化，如圖2所示。

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

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

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

圖2 數據中心網絡流量優化需要路由和調度的聯合

由此可以看出，對數據中心網絡中的Coflow平均完成時間進行優化時，需要對路由和調度進行統一優化。本例中，采用圖2（c）中的路由方案和圖2（f）中的調度策略，才能得到最優的Coflow平均完成時間。此時，兩個Coflow的完成時間分別為1 s和1.6 s，平時完成時間為1.3 s。

4 結 語

在數據中心網絡業務路由方面，本文針對數據中心網絡中存在的幾種特殊業務模式，提出面向海量流采用GPU并行計算的路由優化算法，提高了路由控制的實時性。另外，針對數據中心常見的Coflow流設計了調度和路由聯合的優化算法，進一步提高了業務傳輸的服務質量。