基于SDN網絡大象流負載均衡算法研究

張一凡，韓衛占

(中國電子科技集團公司 第五十四研究所，石家莊 050081)

0 引言

隨著互聯網技術的迅速發展，近年來大數據[1]、云計算[2]、5G[3]等新興技術也在飛速步入應用階段。互聯網在人們日常生活中占據的比重越來越大。網絡用戶與網絡業務的規模也在迅速擴大，這就導致了網絡的維護與管理難度的增加。為了提高網絡服務質量，負載均衡技術[4]就成為了當前的研究熱點。

負載均衡技術是指根據網絡狀況以及任務需求，將負載分攤到多個操作單元上運行，從而利用有限的資源來完成更多的任務。利用負載均衡技術主要避免了網絡資源的不合理利用等問題，從而最大化地利用網絡現有資源，是提高網絡性能最常用的策略之一[5]。

負載均衡技術總體可分為軟/硬件負載均衡、本地/全局負載均衡四大類[6]。其中應用最多的是軟件負載均衡。通過部署軟件來完成負載均衡，因此成本低廉，對于硬件設備的要求也很低。硬件負載均衡是通過部署負載均衡器，利用專用設備來完成負載均衡，因此成本要更高。但由于網絡的規模巨大，很難統一得增加專門的硬件設備，因此硬件負載均衡僅在小規模網絡中使用。本地負載均衡僅針對本地范圍內的網絡進行負載均衡，需要新增一臺服務器來完成工作。全局負載均衡針對的是大規模網絡場景，實現了地理位置無關性。但需要大量的軟硬件設備來進行支持，成本極高。

在眾多負載均衡算法中等價多路徑路由(ECMP，equal cost multi-path)算法[7]是最常用的負載均衡算法。算法通過CRC16算法來計算數據流的五元組哈希值。然后將哈希值與轉發路徑條數進行取模運算，根據余數選擇對應的轉發路徑，使同一條數據流的傳輸路徑不變。理論上來說哈希值取模后的余數分布概率均等，因此可以一定程度上達到負載均衡的效果。但ECMP算法是靜態算法，將所有路徑都認為是等價路徑，不考慮網絡實際狀態。因此無法達到最佳負載均衡效果。為了解決ECMP算法的弊端，文獻[8]提出了Hedera算法。算法通過控制器來周期進行鏈路信息獲取和大象流檢測。針對大象流選擇最先發現的能滿足大象流轉發帶寬的路徑進行轉發，老鼠流選擇基于哈希的ECMP算法進行轉發。基于貪婪思想的Hedera算法雖然考慮了大象流的需求，但計算出的轉發路徑并不一定是最優路徑。同時也沒有考慮到老鼠流跟在大象流后的排隊時延問題。但由于Hedera算法是一種動態負載均衡算法，會根據網絡狀態及時調整轉發路徑，因此負載均衡效果仍比ECMP算法優秀。

相比于靜態負載均衡算法，軟件定義網絡(SDN，software defined network)的負載均衡通過控制器來獲取全網狀態信息，能夠滿足現代網絡對高速數據傳輸[9]的需求。例如文獻[10]提出的動態負載均衡算法，通過對網絡狀態的實時監測來動態調整流量，從而適應網絡的變化。文獻[11]通過控制器來分析網絡節點的負載狀況，然后通過調整源節點的發送速率來有效緩解網絡負載狀況。文獻[12]針對大象流進行路徑規劃，以避免大象流之間產生沖突，減少網絡擁塞的出現。以上算法的重點都是針對網絡狀態來實時調整負載，比傳統網絡的負載均衡算法更加優秀。但在數據流量較多的環境下，單個控制器可能無法完成所有功能，因此文獻[13-15]通過部署多個控制器來減輕控制器負擔，完成負載均衡等功能，來提高網絡性能。

同時協議無關的可編程包處理器[16-17](P4,programming protocol-independent packet processors)的出現實現了數據平面的可編程性。使得研究人員可以完整的定義數據包處理流程，也為負載均衡的發展提供了新的選擇。文獻[18]提出了一種基于可編程數據平面的負載均衡算法HULA。通過探針實現對網絡狀態的實時感知，并根據感知信息來實時調整轉發路徑，提高了算法的可擴展性。文獻[19]提出了SilkRoad算法，通過減少匹配與和動作的數量，可以使用一臺可編程交換機來完成大量負載均衡工作，有效降低了成本。文獻[20]提出的Beamer算法可以利用后端服務器來保存數據流的狀態信息，減少了其他設備的工作量，提高了負載均衡性能。此外還可以借助P4語言來定制新的協議，文獻[21]提出新協議NDP，同時實現了大流的高吞吐量和小流的低時延傳輸。

為了解決大象流導致的網絡擁塞[22]和排隊時延[23]等負載不均衡問題，本文提出的BD-WLB負載均衡系統通過控制器來獲取網絡狀態信息，同時進行大象流檢測。數據平面針對大象流選擇剩余帶寬最大的路徑轉發，老鼠流選擇路徑時延最小的路徑轉發。并選擇ECMP算法以及Hedera算法在網絡吞吐量、鏈路利用率、網絡時延三方面進行了比較分析。

1 BD-WLB負載均衡系統架構

根據功能不同，可以將BD-WLB負載均衡系統劃分為三個模塊。分別為信息獲取模塊、負載均衡模塊、數據平面轉發模塊三個部分。其具體架構如圖1所示。

圖1 負載均衡系統整體架構

SDN網絡控制器擁有整個網絡的網絡資源視圖，因此信息獲取模塊通過SDN網絡控制器來獲取網絡拓撲結構以及各個交換機的流量數據。通過對流量數據的分析，可以獲得網絡鏈路的剩余帶寬和鏈路時延等信息。同時還可以根據預先設定好的閾值，來判斷該數據流是否為大象流。同時控制器還需對當前網絡狀態進行周期性檢測，根據網絡狀況及時調整轉發路徑，避免網絡擁塞的出現。負載均衡模塊的工作是根據信息獲取模塊獲得的網絡狀態信息對轉發路徑進行加權，針對大象流和老鼠流選擇不同的加權公式計算最優轉發路徑。并將轉發路徑信息保存到轉發表中，用于后續數據流的轉發。數據平面轉發模塊的工作是根據轉發表完成數據流的轉發，使用P4語言優化轉發處理流程。

2 BD-WLB負載均衡系統實現

2.1 大象流檢測

文獻[24]研究發現，網絡中的數據流量也存在著二八原則。百分之二十的大象流包含著網絡中百分之八十的流量，百分之八十的老鼠流僅占網絡流量的百分之二十。其中大象流對于網絡帶寬情況敏感，老鼠流對于網絡時延情況敏感。因此為了避免上述問題導致的網絡資源浪費，必須要將大象流和老鼠流區分開。為大象流選擇剩余帶寬最大的路徑轉發，老鼠流選擇鏈路時延最短的路徑轉發，來確保網絡資源得到充分的利用。

因此信息獲取模塊將通過檢測交換機端口信息來確定數據流是否為大象流，其中大象流閾值設置為鏈路帶寬的10%，只要數據流的平均傳輸速率達到鏈路帶寬的10%，就認為該數據流為大象流。具體偽代碼如圖2所示。

圖2 大象流檢測偽代碼

2.2 BD-WLB算法

為了盡可能減少網絡擁塞和排隊時延。本文提出的BD-WLB算法利用控制器獲取網絡實時狀態信息，同時進行大象流檢測。使用剩余帶寬最大的路徑轉發大象流，時延最小的路徑轉發老鼠流。其中大象流最優路徑的權值計算公式如下所示。

式(1)用來計算大象流當前路徑j的權值Ej:

(1)

式(2)用來計算老鼠流當前路徑j的權值Mj:

(2)

(3)

從當前路徑的帶寬與時延權值信息中選擇所有路徑中具有最大權值信息的路徑，將該路徑作為最優轉發路徑，并保存到轉發表中方便后續數據流轉發。式(4)用來計算大象流所有權值路徑中具有最大權值的路徑：

Wej=MAXEj

(4)

式(5)用來計算老鼠流的最大權值路徑：

Wmj=MAXMj

(5)

BD-WLB負載均衡系統轉發數據流的具體流程如圖3所示：

1)當第一個數據流到達交換機時，首先通過哈希算法計算數據流五元組哈希值得到流ID。同時利用SDN網絡控制器進行大象流檢測。交換機根據獲得的鏈路帶寬與時延信息來計算大象流與老鼠流的最優轉發路徑并保存。其中大象流選擇剩余帶寬最大的路徑轉發，老鼠流選擇時延最小的非擁塞路徑轉發。

2)后續數據流到達時，首先計算出數據流的流ID值，解析數據流的IPv4地址。然后使用流ID和目的IP地址對轉發表進行關鍵字段匹配。匹配成功后根據轉發信息轉發該數據流。若數據流ID匹配但目的IP地址不匹配，則說明發生了哈希沖突，此時將流ID與目的IP地址相異或作為新的流ID，然后利用BD-WLB算法計算最優轉發路徑，并保存到轉發表中。

3)由于大象流的持續時間一般很長。為了避免大象流長時間使用同一路徑轉發，導致區域路徑擁塞。同時最優路徑隨著網絡狀態的變化也在不斷變化。因此針對轉發表項設置了存在時間，從而過一段時間就重新計算大象流最優路徑。同時存在時間也應大于老鼠流傳輸時間，從而避免老鼠流多次計算轉發路徑，占用計算資源。當數據流在轉發表中無匹配項時，重復步驟(1)，重新計算數據流的最優轉發路徑并保存，從而完成數據流轉發。

圖3 數據流轉發流程圖

2.3 P4實現數據流轉發

利用P4語言來實現數據平面數據流的整個處理過程，實現數據流的定制轉發，使數據包處理過程更加靈活。一個完整的P4程序主要包含首部(Headers)、解析器(Parsers)、表(Tables)、動作(Actions)、控制程序(Control Programs)五個部分。其中路徑選擇動作表的工作是首先讀取數據流的流ID和數據包的目的IP地址，進行最長前綴匹配，若能成功匹配，則根據匹配項轉發數據包。若不能匹配，則判斷是否出現哈希沖突。若出現則執行流ID與目的IP地址的異或運算。然后進行BD-WLB路徑選擇等操作。而執行路徑選擇動作時，根據當前的流ID值和相應的路徑權值計算公式來進行路徑選擇。其中BD-WLB路徑選擇的偽代碼如圖4所示。

圖4 BD-WLB路徑選擇偽代碼

判斷轉發鏈路優劣的標準是根據式(1)～(5)來計算出的當前路徑的狀態參數信息，針對大象流選擇具有最大鏈路帶寬權值參數的路徑作為最優轉發路徑。針對老鼠流選擇具有最大時延參數的路徑。并將選擇的最優路徑信息保存到轉發表中，用于后續數據流的轉發。其路徑計算過程偽代碼如圖5所示。

圖5 BD-WLB鏈路計算偽代碼

流控制程序是將前面四個組件所定義的包頭、解析流程、表、動作整合起來。用來定義數據流的處理和轉發邏輯。流控制程序的偽代碼如圖6所示。

圖6 BD-WLB流控制程序偽代碼

3 性能評估

3.1 模擬環境搭建和參數設置

實驗采用ONOS控制器和Mininet軟件搭建實驗仿真平臺。網絡拓撲結構如圖7所示，使用k=4的Fat-tree拓撲，包括16臺主機、8個接入層交換機、8個匯聚層交換機、4個核心層交換機。鏈路帶寬設置為100 Mbit/s，鏈路延時設置為1 μs，并使用iperf工具產生模擬流量。

圖7 網絡拓撲結構

選擇網絡吞吐量、鏈路利用率、網絡時延三個指標作為負載均衡性能指標。

其中網絡的吞吐量是指在單位時間內通過網絡傳輸并且能夠成功接收到的數據總量。網絡的吞吐量越高，說明性能越優。

鏈路利用率指的是數據傳輸中使用的鏈路數量與所有鏈路數量的比值。鏈路利用率可以反映出網絡中傳輸鏈路的使用情況，若鏈路利用率越高，則說明網絡流量分布均衡，網絡資源利用越充分。反之則說明網絡資源沒有被充分利用。

網絡時延指的是從源節點到目的節點的傳輸時間，傳輸時間越小則證明傳輸性能越好，網絡服務質量越高。反之則說明網絡可能出現了擁塞情況。

3.2 對比算法和流量模型

選擇ECMP與Hedera兩個經典負載均衡算法與本文提出的BD-WLB算法進行對比實驗，來驗證BD-WLB算法的可行性與有效性。

實驗中通過iperf工具產生模擬數據流量。且大象流帶寬范圍為10 Mbit/s到100 Mbit/s之間，老鼠流帶寬小于10 Mbit/s。并且采用兩種不同的數據流模型進行測試。第一種流量模型為Staggered(pEdge,pPod)模型。該流量模型中主機會以概率pEdge向同一交換機下的主機發送流量，以概率pPod向同一個Pod內的主機發送流量，以概率1-(pEdge+pPod)向其余Pod內主機發送流量。同時該模型中大象流和老鼠流的比例按照實際網絡中二比八的比例設置。實驗中具體選擇了stag(0,0.1)、stag(0.1,0.1)、stag(0.1,0.2)、stag(0.2,0.2)、stag(0.2,0.3)、stag(0.3,0.3)、stag(0.4,0.3)、stag(0.6,0.2)、stag(0.8,0.1)九種流量模型。

第二種模型為load_x模型，其中x代表大象流比例。通過調整大象流概率來改變網絡負載。實驗中具體選擇了load_0.1到load_0.9共九種模型來驗證算法性能。

3.3 實驗結果與分析

如圖8所示，在stag模型下的9種情況中，隨著流量模型參數的變化，大部分流量從Pod間流量轉為Pod內流量。此時三種算法的吞吐量都有提升。在前五種流量模型時，流量多數為Pod間流量，此時BD-WLB算法吞吐量要高于ECMP和Hedera算法，原因是BD-WLB算法綜合考慮網絡狀態，分別為大象流和老鼠流選擇滿足其需求的最優路徑。而Hedera算法的貪婪思想導致算法雖然考慮了大象流的帶寬需求，但選擇的路徑很可能不是最優路徑。ECMP算法由于產生的大流碰撞，導致吞吐量最低。在stag(0.3，0.3)、stag(0.4，0.3)、stag(0.6，0.2)、stag(0.8，0.1)四種情況時，流量多數為同一Pod內的流量。此時大流碰撞的情況減少，因此ECMP算法的吞吐量增加。Hedera算法將大流轉發路徑進行了優化，因此吞吐量比ECMP高。此時BD-WLB算法的吞吐量雖然比ECMP和Hedera高，但三種算法的差距在縮小。因此BD-WLB算法對于Pod間流量的處理性能更優。

圖8 stag模型網絡吞吐量

如圖9所示，在load_x模型下隨著流量負載的增加，三種算法的吞吐量都在增加。低負載狀態時，三種算法的吞吐量差別不大。但在高負載狀態時，BD-WLB算法的吞吐量最大，相比于Hedera算法提升了16.1%的吞吐量，相比于ECMP算法提升了38.4%的吞吐量。這是由于ECMP算法易產生大流碰撞，導致網絡擁塞，吞吐量下降。Hedera算法依靠貪婪思想對大流進行路徑優化，對小流采用ECMP算法進行轉發，降低了大流碰撞發生的概率，因此在高負載狀態時Hedera算法比ECMP算法的吞吐量高。BD-WLB算法吞吐量最高是因為算法綜合考慮網絡狀態，結合鏈路的帶寬、時延參數對轉發路徑進行優化，在高負載狀態下，能夠為大象流和老鼠流找到最優轉發路徑，減少擁塞而實現更高的吞吐量。

圖9 load_x模型網絡吞吐量

如圖10所示，在stag模型中的九種情況下，隨著Pod間流量的減少，三種算法的鏈路利用率都在不斷下降。這是因為Pod間流量占大多數時，三種算法對數據流的轉發都涉及到了上層的路徑。并且BD-WLB算法通過實時監測鏈路的可用帶寬和時延，并進行大象流檢測，可以根據大象流和老鼠流的流量特征與需求來選擇最合適的路徑，因此鏈路資源利用更加充分，鏈路利用率最高。Hedera算法的鏈路利用率比ECMP算法高，這是因為Hedera算法也會在檢測到大流后，為大流選擇第一條滿足要求的路徑，同樣提高了鏈路利用率。而ECMP算法不考慮網絡狀態，數據流選定路徑后，后續轉發路徑不變。無法利用網絡中的冗余鏈路，因此鏈路利用率最低。

圖10 stag模型鏈路利用率

如圖11所示，隨著流量負載的增加，BD-WLB算法的鏈路利用率最高，其次是Hedera算法，ECMP算法的鏈路利用率最低。這是由于ECMP在確定路徑之后，后續的數據流轉發路徑一般不變，因此無法利用網絡中的冗余鏈路。并且隨著負載的增加，ECMP不隨網絡狀態更改路徑，更易導致大流碰撞，因此ECMP算法的鏈路利用率低于另外兩種算法，并且在高負載狀態時鏈路利用率出現下降。Hedera算法通過周期性的網絡檢測，針對大象流進行轉發路徑優化，針對老鼠流采用ECMP算法進行轉發，從而可以利用網絡中的冗余鏈路。因此Hedera算法的鏈路利用率要高于ECMP算法。相比另兩種算法，BD-WLB算法根據鏈路帶寬和時延考慮了針對大小流的最優轉發路徑，盡可能利用網絡中的冗余路徑。因此在高負載狀態時BD-WLB算法的鏈路利用率要高于ECMP算法41.9%，高于Hedera算法7.3%。

圖11 load_x模型鏈路利用率

如圖12所示，在stag模型中，隨著不同Pod間傳輸的流量比重降低，三種算法的傳輸時延均呈現下降趨勢。在stag(0，0.1)、stag(0.1，0.1)、stag(0.1，0.2)、stag(0.2，0.2)、stag(0.2，0.3)五種情況時，Pod間傳輸的流量多，此時BD-WLB算法的傳輸時延最低，這是由于BD-WLB算法綜合考慮了帶寬和時延條件，為大象流和老鼠流選擇了最優的轉發路徑。避免了大流碰撞導致的時延增加問題和老鼠流在大象流后的排隊時延問題。在stag(0.3，0.3)、stag(0.4，0.3)、stag(0.6，0.2)、stag(0.8，0.1)四種情況時，流量主要在同一Pod內轉發，大部分流量無需算法進行調度，可以直接轉發，因此三種算法的傳輸時延均在下降，并且時延相差不大。

圖12 stag模型傳輸時延

如圖13所示為不同流量負載下ECMP、Hedera和BD-WLB算法的傳輸時延。在高負載狀態時，BD-WLB算法的傳輸時延最低。此時BD-WLB算法相比于ECMP算法降低了41.8%的傳輸時延，相比于Hedera算法降低了25%的傳輸時延。說明BD-WLB算法可以在高負載狀態時達到很好地負載均衡效果，避免了鏈路擁塞和排隊時延的出現。而Hedera算法雖然在一定程度上優化了大流的轉發路徑，但并未考慮對時延敏感的小流。沒有解決小流跟在大流后的排隊時延問題。因此Hedera算法的傳輸時延要高于BD-WLB算法。ECMP算法對網絡狀態和流量大小均不關心，因此隨著負載的增加，鏈路擁塞與排隊時延等問題不斷出現，因此在高負載狀態下ECMP算法的傳輸時延最高。

當網絡處于低負載狀態時，BD-WLB算法的傳輸時延要略高于ECMP算法和Hedera算法，這是因為BD-WLB算法需要進行網絡鏈路信息的搜集、大象流檢測、最優鏈路計算等過程，需要一定的時間。因此在低負載狀態時BD-WLB算法的傳輸時延較高。由于低負載狀態時小流占比例大，此時Hedera算法和ECMP算法都很少發生大流碰撞而提高時延。因此兩種算法的傳輸時延十分接近且小于BD-WLB算法。

圖13 load_x模型網絡時延

4 結束語

網絡中不同特征的流量對于鏈路的需求不同，其中大象流對鏈路帶寬條件敏感，老鼠流對鏈路時延條件敏感。因此本文設計的負載均衡算法的中心思想是根據大象流和老鼠流各自的敏感條件來選擇最優的路徑進行傳輸，從而減少網絡擁塞的出現和排隊時延過長等問題。通過控制器來進行全網狀態信息的獲取以及大象流檢測，然后再根據網絡狀態信息計算大象流和老鼠流的最優轉發路徑，通過P4語言對數據平面轉發流程進行優化，最終完成負載均衡。實驗結果表明，相比于ECMP和Hedera算法，BD-WLB算法有效提升了網絡吞吐量、鏈路利用率、網絡時延方面的性能，證明了算法的可行性和有效性。

但BD-WLB算法目前對于鏈路的評判標準還只是依靠網絡帶寬和鏈路時延兩個參數。因此下一步的優化工作是為判斷標準引入例如轉發跳數等更多參數，進一步分析不同特征流量的需求，更真實的模擬網絡狀態，從而使算法更加適應真實網絡。