數據中心負載均衡方法研究綜述*

劉敬玲,黃家瑋,蔣萬春,王建新

(中南大學 計算機學院,湖南 長沙 410083)

在計算機技術和互聯網應用迅猛發展的推動下,用戶對數據訪問的需求日益增多,信息對儲存容量的要求日益提高.云計算使用戶可以按需地享受高質量服務和無處不在的網絡訪問[1],但是用戶將數據外包給云服務器,使數據脫離了物理控制,隨之帶來了數據隱私泄露的問題.

隨著云計算技術的興起,數據中心(data center)作為云計算的硬件基礎架構也在不斷普及和應用.為了構建高可用、高性能、低成本的云計算基礎存儲和計算設施[1-5],數據中心通常部署了大量商用交換機和服務器.數據中心網絡連接了大規模服務器集群,是傳遞計算和存儲數據的橋梁[6].為了提供超高帶寬,數據中心網絡的拓撲結構普遍采用CLOS 結構[7],在主機之間提供了多條可用路徑.在網絡高負載狀態下,為了降低鏈路擁塞和數據包丟失的概率[8],數據中心負載均衡機制將網絡流量分配到所有可用路徑上,充分利用了網絡中存在的冗余鏈路,提高網絡傳輸性能.

由于數據中心之間的流量相對穩定,通常采用中心控制器統計數據中心間的流量狀態信息,并下發負載均衡控制規則以均衡流量.而數據中心內部流量占數據中心網絡流量的絕大部分,且數據中心內部流量具有高動態和強突發的特性[9,10],給負載均衡工作帶來了更大的挑戰.因此,本文僅對數據中心內部的負載均衡工作進行討論.本文主要綜述了數據中心負載均衡的相關研究工作.具體來說,本文根據負載均衡方案部署的位置將它們劃分成了三大類.

· 基于中央控制器的負載均衡方案:采用集中式的思想,基于中央控制器的負載均衡方案,通過引入中央控制器,收集各個交換機上的流量信息,得到關于網絡路徑和動態流量的全局視圖,并根據中央控制器上的全局視圖對網絡擁塞作出快速反應,自動調整網絡流量的轉發路徑.

· 基于主機的負載均衡方案:基于主機的負載均衡方案將負載均衡操作轉移到分布式的主機上進行.主機依據端到端的擁塞信息,通過修改TCP/IP 協議棧或引入虛擬軟件交換機技術,以重路由、切分流量或細粒度調度的方式實施負載均衡.

· 基于交換機的負載均衡方案:多對一的通信模式使得瓶頸交換機上的負載過高,形成鏈路擁塞.基于交換機的負載均衡方案在交換機上感知網絡擁塞,并采用不同的調度粒度將網絡流量發送到不同的路徑,實現快速的流量均衡.

本文第1 節描述數據中心的背景和負載均衡研究的意義.第2 節介紹數據中心網絡結構與流量特征.第3節具體介紹相關的負載均衡方案,并對比分析各方案的基本思想、實現方法及均衡效果.最后探討未來值得關注的研究方向.

1 研究背景和意義

近年來,隨著云計算、大數據、分布式存儲等新興技術飛速發展,越來越多的企業和政府部門搭建了大型數據中心來提供金融、電商、交通等各種各樣的在線服務.作為下一代互聯網應用服務的基礎架構,數據中心吸引了工業界和學術界的關注,成為了研究的熱點領域.為了充分利用數據中心強大的計算和存儲能力,網頁訪問、即時通信、財經金融、在線游戲等延時敏感型服務和數據分析、科學計算、網頁內容索引等計算密集型服務被遷移到數據中心.隨著數據中心在線應用服務規模的不斷擴大,對數據中心網絡帶寬和性能提出了更高的挑戰.為了向用戶提供滿意的服務質量,數據中心網絡(data center networks)的傳輸性能備受關注[11-13].

數據中心網絡通過交換機連接數據中心內部的大量主機,獲取規模效應.為了提高網絡傳輸性能,在數據中心網絡架構設計方面,出現了胖樹(fat-tree)[14]、VL2[15]、DCell[16]、BCube[17]等新型的“富連接”的網絡拓撲結構.這些新型網絡拓撲結構在源和目的主機之間提供了多條可用傳輸路徑,可以利用并行多路徑傳輸來提升數據中心的網絡吞吐率和可靠性[18-20].

在數據中心網絡特有的網絡流量和應用需求背景下,針對日益增長的用戶規模,數據中心供應商不斷升級硬件設備,使用 10Gb/s,100Gb/s 級別的高帶寬和微秒級別的低延時鏈路來提升傳輸速率.學術界提出了DCTCP[1]、D3[21]、D2TCP[22]等新型傳輸控制協議和PDQ[23]、PIAS[24]等交換機調度算法,同時利用新型的多路徑網絡架構來提高并發傳輸速度和網絡整體健壯性.這些方案在一定程度上提升了網絡性能,但無法解決數據中心網絡中并行路徑傳輸的流量不均衡問題.研究數據表明:不同類型的數據中心通常只有不到25%的核心鏈路利用率,其余鏈路總是處于空閑狀態,存在著嚴重的負載不均衡問題[25].

負載均衡的首要目標是將流量均勻地分配到各條并行路徑上,提升網絡鏈路利用率,避免高負載流量引發網絡擁塞.作為數據中心負載均衡的標準方案,等價多路徑路由(equal-cost multipath routing,簡稱ECMP)[26]策略采用靜態哈希機制,依據數據包頭的源IP 地址、目的IP 地址、源端口號、目的端口號和協議這五元組信息,利用哈希函數將不同的數據流分散到等價多路徑上.ECMP 雖然實現部署簡單,但并不感知路徑的擁塞狀態和流量特征,容易造成多條數據流(特別是長流)在路徑上發生哈希沖突,導致鏈路擁塞和應用性能下降.

顯然,在數據中心多路徑網絡環境和特有的網絡應用下,如何設計高效的網絡流量負載均衡機制,就成為了一個重要的研究問題.

2 數據中心網絡結構與流量特征

為保證數據中心網絡傳輸和應用服務的性能的關鍵技術,需要結合以下數據中心的拓撲結構和流量特性開展數據中心負載均衡機制的設計和優化.

2.1 數據中心網絡結構

數據中心利用交換機和路由器等網絡設備將大量服務器連接起來,以建設高性能的計算和存儲基礎設施.隨著用戶需求迅猛發展,數據中心的服務器數目在高速增長.由于傳統基于樹狀的3 層數據中心網絡結構難以滿足大規模數據中心的要求[7,27],如圖1 所示的Fat-Tree[14]、VL2[15]、DCell[16]、BCube[17]等新型數據中心網絡結構不斷涌現,以提供超高帶寬,降低大規模部署的開銷,并適應不同應用需求.新型數據中心網絡結構具有以下特點:(1) 主機之間存在大量可用并行路徑,增加了網絡的容錯性和帶寬;(2) 拓撲結構規則、對稱,利于網絡布線、自動化配置和擴展升級;(3) 對分帶寬隨著網絡規模的擴展而增大,能為數據中心提供高速傳輸服務.

Fig.1 Typical architecture of modern data center network圖1 典型的新型數據中心網絡結構

2.2 數據中心流量特征

數據中心中運行著網頁搜索、零售和廣告等大量不同的應用系統,這些應用是數據中心的建設和研究的主要驅動因素,也是數據中心運營商的主要業務,它們會產生各種類型的數據流量.不同于傳統的廣域網,數據中心的網絡流量和應用需求具有以下特點.

· 數據中心不同應用產生的數據流具有各不相同的網絡傳輸性能需求[21,22].例如,在線搜索和實時推薦等應用的數據流往往有嚴格的延時期限需求,而虛擬機遷移和文件備份等應用的數據流則要求很高的網絡吞吐率.

· 數據中心網絡數據流的長度呈現重尾分布特性.據統計,大部分應用中數據流的數據量很小,90%的數據流屬于小于100KB 的短流,其數據傳輸在10ms 內完成.數據量大于100KB 的長流只占數據流總量的10%,但這些長流卻發送了超過80%的數據量[1].其中,0.1%的長流發送時間超過200s,其數據量占了總數據量的20%[28].長流的大量數據包容易占據交換機緩存隊列,對短流數據包形成線頭阻塞,增大短流的延時.

· 數據中心網絡流量呈現較強的突發性[29,30].在硬件設計上,目前高速網卡普遍采用了負載卸除設計來降低CPU 的系統開銷,以支持超高的鏈路帶寬,但這使得大量數據包在極短時間內發送而形成突發流量;在傳輸控制協議TCP 的擁塞控制機制下,發送方也會成簇發送擁塞窗口內的所有數據包;在應用層,數據中心通常采用劃分聚合(partition/aggregate)的并發通信模式,即向服務器群發送請求后,服務器會同步地返回數據并匯聚生成響應結果,進一步加大了并行數據流的突發強度[30,31].

3 數據中心負載均衡方法研究進展

在本節中,我們將根據部署位置將數據中心網絡流量負載均衡機制分成了3 大類,包括基于中央控制器、基于主機和基于交換機的負載均衡機制.本節將具體介紹相關的負載均衡方案,并對比分析各方案的設計思想和工作原理.

3.1 基于中央控制器的負載均衡機制的研究

采用集中式的思想,基于中央控制器的負載均衡方案利用控制器對網絡設備進行集中控制.中央控制器收集擁塞信息,并基于全局視圖為數據流分配傳輸路徑.控制器與交換機之間采用OpenFlow 等協議通信.控制器定期測量各個交換機擁塞情況,根據全局鏈路利用率和流量信息向交換機下發轉發表,以此決定數據流的轉發路徑,從而實現整體網絡的負載均衡.近年來,學術界提出了多種基于中央控制器的方案,見表1,它們的解決思路包括:①Hedera[32]、MicroTE[33]、Mahout[34]、OmniFlow[35]、Shafiee[36]等重路由方法;② Fastpass[37]、SAPS[38]、MSaSDN[39]等細粒度控制方法;③RAPIER[40]、FDALB[41]、Freeway[42]、OFLoad[43]、AuTO[44]、SOFIA[45]等區分長短流的調度方法;④ LBDC[46]等多控制器間的負載均衡方法.

Table 1 Comprehensive comparison of central controller-based load balancing mechanisms表1 基于中央控制器的負載均衡機制的綜合對比

Table 1 Comprehensive comparison of central controller-based load balancing mechanisms (Continued)表1 基于中央控制器的負載均衡機制的綜合對比(續)

3.1.1 基于重路由的中央控制器負載均衡機制

Hedera[32]方案是一個集中式的主動負載均衡算法,如圖2 所示.中央控制器從ToR 交換機上收集流信息以檢測長流,計算沖突路徑后,通告各交換機為遭遇擁塞的長流重新切換轉發路徑.為了實現最大最小公平的帶寬分配,Hedera 建立長流的帶寬需求矩陣,通過多次調整速率,以收斂至公平帶寬.Hedera 采用了全局最先匹配和模擬退火算法兩個調度算法,以增加對分帶寬.全局最先匹配算法遍歷所有可能路徑,將長流分配到第1 條能夠滿足帶寬需求的路徑上.同時,Hedera 為各目標主機而不是為各流分配核心交換機,以縮小搜索空間,再利用模擬退火算法為長流選擇路徑.Hedera 利用全局信息避免了長流間的沖突,但是對短流并不友好.

Fig.2 Schematic diagram of Hedera圖2 Hedera 原理圖

針對流量相對穩定的長流和突發性強的短流,MicroTE[33]方案使用中央控制器來跟蹤長流,并優先分配轉發路徑,剩余帶寬則按加權等價多路徑路由策略分配給難以預測的短流.MicroTE 包含3 個組件:監測組件,用于監控ToR 間的流量模式和確定流量的可預測性;路由組件,基于控制器提供的網絡信息確定路由;網絡控制器,收集服務器的流量需求,并下發轉發表給交換機.

Mahout[34]方案首先在主機端依據套接字緩存占用情況探測長流,當套接字緩存占用超過閾值時,判定該主機所發送的流為長流.主機端利用數據包包頭DSCP 字段通知中央控制器對該流進行重路由.具體來說:當交換機接收到帶標記的數據包時,將其轉發給中央網絡控制器,中央控制器為相應長流分配最輕負載的路徑;對于其他流量,交換機則采用ECMP 對它們進行轉發.Mahout 利用主機檢測長流,提高了檢測效率同時降低了交換機的開銷,但同時也需要修改主機內核.

由于數據中心負載均衡器容易將長流的數據包分散到各條路徑上,造成短流經歷較長的排隊延時;主動降低流速的流控方案雖減小了緩沖占用,但易引起多路徑的帶寬損失.OmniFlow[35]方案是一個在傳輸層結合負載均衡和流控來優化數據中心傳輸的方法.基于不同的網絡狀況,OmniFlow 動態地調整流量轉發路徑以充分利用帶寬,或主動調整流速限制隊列長度.OmniFlow 包括3 個模塊.

(1) 隊列監視器:首先測量主機間多路徑的排隊延時,然后根據測量結果評估當前路徑的質量,并相應地選擇優化策略(負載均衡或流量控制)以改善傳輸.若負載適中,采用負載均衡充分利用網絡帶寬;當網絡嚴重飽和時,使用流控方法快速排空隊列.

(2) 負載均衡模塊:重新路由流量到緩存隊列長度低于給定閾值的路徑.

(3) 流量控制模塊:檢測到所有路徑的隊列長度超過給定閾值時,降低流速以減輕網絡擁塞.OmniFlow 在不損失長流吞吐率的同時降低了短流的延時.

Shafiee 等人[36]提出一種基于流級別的擁塞感知的數據中心網絡負載均衡方法,該方法根據鏈路利用率為鏈路動態調整權重,并將新生成的流量放置在網絡中的最小權重路徑上傳輸.作者在理論和實踐上證明了該算法具有良好的負載均衡性能,并證明了該算法能漸近地最小化網絡開銷.該算法不受流量模式的限制,且在不同的數據中心網絡狀態下良好地運行.雖然該算法的復雜度較低,但其性能會受到權重更新和最小權重路徑計算速度的影響.

以上方案利用中央控制器實現網絡流量的全局負載均衡,容易造成兩個問題:一方面,由于控制周期過長,無法應對毫秒級甚至微秒級的突發流量;另一方面,難以保證長流識別準確性,無法避免數據包排隊問題.

3.1.2 細粒度控制的中央控制器負載均衡機制

Fastpass[37]是一種細粒度的集中式傳輸控制架構,實現了多路徑傳輸的低排隊延時和高利用率.Fastpass 使用中央控制器為每個數據包分配發送時隙和傳輸路徑來提升網絡利用率和避免擁塞,有效降低了排隊延時.收到終端主機向控制器發送的請求后,控制器為終端主機分配傳輸數據時隙;然后,控制器采用ToR 著色算法為已分配時隙的數據包分配路徑.但Fastpass 的性能取決于發送時隙的利用率.當發送時隙被浪費時,很容易降低鏈路利用率.另外,Fastpass 為每包分配時隙和路徑,難以大規模部署和擴展.

SAPS[38]方案是一個基于軟件定義網絡的包分散機制.SAPS 借助中央控制器檢測鏈路故障,并建立對稱的虛擬拓撲.虛擬拓撲對于一條流來說,其源端和目的端之間的所有路徑具有對稱的帶寬和延時.每條流的數據包被分散到一個虛擬拓撲中.每條流依據其流大小與虛擬拓撲的二分帶寬選擇虛擬拓撲.其中,短流和長流分別映射到擁有更小和更大的二分帶寬的虛擬拓撲中.SAPS 可在非對稱拓撲中實現高性能.

組播不僅能降低任務完成時間,也能提高吞吐量.但由組播流量引起的網絡阻塞嚴重影響數據中心的性能.在胖樹拓撲的數據中心中,組播流量更容易造成負載不均衡和突發的流量沖突.MSaSDN[39]方案提出了一種面向胖樹數據中心的組播調度算法.MSaSDN 方案首次構建了軟件定義胖樹數據中心中組播阻塞模型,并通過鏈路權重定義鏈路阻塞代價.SDN 控制器在接收到組播請求后,根據收集的網絡信息計算鏈路阻塞代價,選擇具有最小阻塞代價的鏈路作為最優路徑.MSaSDN 方案借助SDN 控制策略可以防止對其他子網中組播流量的干擾,降低網絡阻塞概率.

3.1.3 區分長短流調度方式的中央控制器負載均衡機制

數據中心絕大部分數據流量是由少量的長流產生,大量的短流則通常都有嚴格的完成期限.吞吐量敏感的長流和延時敏感的短流之間存在資源競爭問題.

RAPIER[40]方案是一個任務敏感的優化系統.RAPIER 為了降低平均任務完成時間,結合路由和調度機制,構建了一個聯合優化模型.RAPIER 使用中央控制器確定任務中每條流的轉發路徑、轉發時間和服務速率,以最優化平均任務完成時間.當新任務到達時,RAPIER 為新任務中每條流計算路由路徑和傳輸速率.當已存在的任務完成時,網絡資源被釋放,RAPIER 再重新分配帶寬.RAPIER 主要處理數據敏感的大任務,而延時敏感的獨立流和小任務直接以ECMP 的方式路由.相比于只關注流調度的方案,RAPIER 提升了任務的性能.

FDALB[41]方案是一個感知流大小分布的負載均衡機制.FDALB 在主機端測量流大小分布,檢測并標記長流.當一條流的已發送字節數超過一個閾值時,其數據包包頭將被標記.一旦一條流結束,FDALB 重新計算長短流區分的閾值.交換機在接收到被標記的包時,將其轉發給中央控制器.中央控制器收到被標記的包后,基于全局的擁塞信息為其做負載均衡決策.為了防止長流同步到達交換機時,中央控制器為它們選擇相同的路徑帶來的碰撞問題,FDALB 使用了一個貪婪輪詢算法調度長流到有最大共享剩余帶寬的路徑上傳輸.交換機在接收到短流的包時,直接以ECMP 的方式傳輸.FDALB 方案減少了流碰撞事件數量,同時實現了高可擴展性.但是FDALB 僅感知發送端本地的流量分布,沒有考慮其他發送端的流量,難以計算得到最優的區分長短流閾值.

Freeway[42]方案是一個區分長短流調度方式的機制.為了避免長短流間的資源競爭,Freeway 將長短流分別隔離到高帶寬路徑和低延時路徑上傳輸.Freeway 利用控制器收集流量和路徑狀態信息,動態地調整低延時路徑和高帶寬路徑的數量,以保證短流的完成期限和長流的吞吐率.Freeway 的路徑分割算法依據實時短流負載情況變化調節低延時路徑的數量.Freeway 基于M/G/1 排隊理論為短流建立了隊列模型,以SLA(service-level agreement)定義的短流完成期限為約束,分析了低延時路徑的最高延時閾值.當低延時路徑的平均延時超過2 倍閾值時,增加低延時路徑數量;否則,將低延時路徑調整為高吞吐量路徑,分配給長流以增加可用帶寬.在Freeway中,短流采用本地調度策略ECMP 算法,而長流用中心調度的方式調度.Freeway 將長短流隔離在不同的路徑上傳輸,能有效地解決長短流的資源競爭問題.但由于采用了流級別的調度方式,無法靈活使用多路徑.

OFLoad[43]是一種基于OpenFlow 的數據中心網絡動態負載平衡方案,可實現數據中心的自動路由配置和負載優化.OFLoad 在主機上利用應用層信息區分和標記長流和短流.在OpenFlow 交換機上首先執行ECMP 路由策略,然后定期向控制器發送流信息.控制器為長流和短流采用不同的路由規則.對于長流,控制器將其分配到一條利用率最低的路徑上傳輸.同時,控制器收集到同一目的ToR 交換機的短流,并依據路徑負載為這些短流分配路徑,使得負載重的路徑被分配較少量的短流.屬于同一條短流的數據包在一條路徑上傳播,以避免亂序問題.OFLoad 可有效解決長流阻塞短流的問題.

除了將長短流分配到不同的路徑上傳輸,學者們也提出將長短流隔離在不同的優先級隊列中來保證長短流的性能[24,47].然而,區分優先級隊列的閾值直接影響網絡性能.由于流量的動態性和流大小的多樣性,無法采用固定的優先級閾值,AuTO[44]采用了強化學習的方法實現自動的流量優化.AuTO 的中央系統收集各主機上的流信息,使用了深度強化學習技術來確定長短流的優先級和長流的發送速率與發送路徑.為了最小化短流的延時,短流被給予高的優先級,同時直接以ECMP 的方式傳輸;為了保證長流的吞吐率,中央系統單獨給長流分配發送速率和發送路徑.AuTO 解決了短流被長流阻塞的問題,同時也保證了長流的吞吐量,但AuTO 依賴于機器學習方法的準確性,高動態和強突發的流量會增加AuTO 的復雜性.

數據中心中,SDN 控制器通常被用來為流量分配路徑.新流或需要重路由的流在交換機上無法匹配流表項時,會向控制器發送packet-in 消息請求分配路徑.每條流的路由建立會消耗控制器的內存,同時,頻繁的packet-in事件易引起過大的延時.為了降低控制器的內存和延時開銷,控制器通常只重路由流大小大于給定靜態閾值的長流來減輕ECMP 的哈希沖突問題.但理想情況下,任何一條流都應該被路由到最佳路徑上傳輸.SOFIA[45]設計了一種最佳流量分割控制策略.控制器利用在線學習算法根據流大小分布計算區分長短流的最佳閾值,并統一通告給所有交換機.交換機根據分割閾值判定可重路由的流.SOFIA 減少了packet-in 消息延遲,降低了路由開銷和鏈路擁塞程度.

3.1.4 針對多個中央控制器的負載均衡機制

大型數據中心網絡通常被分割成多個區域,每個區域分別由一個控制器監測和重路由流量.多個控制器能有效分擔負載,但也帶來了控制器間負載不均衡的問題.LBDC[46]首次提出數據中心中分布式控制器的負載平衡問題,并證明該問題是NP 完全的.同時,LBDC 給出了集中式和分布式的貪婪方法來遷移交換機的控制權,以解決控制器間負載不均衡的問題.集中式和分布式方案分別利用了全局網絡視圖和本地信息,在控制器間流量不均衡時遷移交換機的控制權,將具有最大流量的交換機移交給負載最輕的控制器管理.

3.2 基于主機的負載均衡機制的研究

雖然集中式的負載均衡方案可利用中央控制器收集全局流量信息,根據全局信息實現最優的負載均衡決策,但是獲取和維護全局信息需要一定的部署開銷,較大的反饋和控制延時也會降低動態突發流量下的集中式負載均衡性能.另外,還需要部署額外的網絡組件,增加實施成本.基于主機的負載均衡方案將負載均衡操作轉移到分布式的主機上進行,降低了部署開銷.近年來,學術界提出了多種基于主機的方案,見表2,它們的解決思路可分為:①FlowBender[48]、CLOVE[49]、ALB[50]、Hermes[51]、ELAB[52]等重路由方法;② MPTCP[53]、FUSO[54]、DCMPTCP[55]、DC2-MTCP[56]、MMPTCP[57]、Presto[58]、VMS[59]、DumbNet[60]、Flicr[61]等流量切分協議;③DRB[62]、JUGGLER[63]、NDP[64]、CAPS[65]、MP-RDMA[66]等細粒度調度機制.

Table 2 Comprehensive comparison of host-based load balancing mechanisms表2 基于主機的負載均衡機制的綜合對比

Table 2 Comprehensive comparison of host-based load balancing mechanisms (Continued)表2 基于主機的負載均衡機制的綜合對比(續)

3.2.1 基于重路由的主機負載均衡機制

FlowBender[48]是一個基于主機的負載均衡機制.針對ECMP 的哈希碰撞問題,FlowBender 動態地重路由遭遇擁塞的流.FlowBender 利用ECN 和TCP 超時信號檢測擁塞和鏈路故障.類似于DCTCP 的標記機制,當交換機隊列長度超過一個給定閾值時,所經過的數據包的ECN 字段被標記.若一條流中被標記的包的數量超過給定閾值時,FlowBender 重路由該流.FlowBender 在交換機中配置哈希函數,將TTL(time to live)的值作為哈希函數的額外輸入值.當FlowBender 檢測到擁塞時,在發送主機上修改包頭的TTL 字段,重新計算哈希值來實現重路由.FlowBender 感知路徑擁塞,實現對擁塞流的重路由,有效減輕了哈希碰撞的影響.但由于路徑選擇的隨機性和被動性,重新選擇的路徑難以取得最優效果.

CLOVE[49]是一個部署在軟件交換機上的負載均衡算法,軟件交換機部署在源端主機的虛擬機管理器上.CLOVE 在物理交換機上使用ECMP 路由,利用源路由機制發現等價多路徑.CLOVE 使用ECN 或INT 技術[67-69]來檢測路徑的擁塞狀況,在軟件交換機上,通過改變包頭五元組將流換到最好的路徑上.為了防止換路帶來的數據包亂序問題,CLOVE 采用包簇作為調度粒度.CLOVE 是數據中心中,第1 個虛擬化技術下感知擁塞的數據平面負載均衡器,不用修改物理交換機或虛擬機,但是INT 技術通用性不強,僅使用ECN 來檢測擁塞也不夠準確.

針對CLOVE-ECN 擁塞檢測不準確的問題,ALB[50]提出了一個基于準確擁塞反饋的自適應負載均衡方案.ALB 采用基于延時的擁塞檢測,準確地將包簇轉發至輕擁塞的路徑.ALB 的源端主機上部署了虛擬交換機,在虛擬交換機上采用源路由機制實現多路徑傳輸.ALB 利用DPDK 技術[70]在TCP 數據包頭可選字段寫入時間戳,準確地測量每一條流的RTT 和單向延時,并且解決了源和目的主機時間不同步問題.但是,軟件交換機的處理時間可能影響延時檢測的準確性.

Hermes[51]采用主動的擁塞檢測和謹慎的路由決策以降低數據包亂序影響.Hermes 利用了ECN、延時和探測包來檢測路徑擁塞和失效狀態,預估切換路徑的收益來決定是否切換路徑,以緩解盲目切換路徑導致的亂序影響,避免鏈路狀態和擁塞窗口不匹配的問題.Hermes 主要由感知模塊和重路由模塊兩個模塊組成,如圖3 所示.感知模塊利用RTT 和ECN 兩種擁塞信號感知網絡擁塞和鏈路故障.當RTT 和ECN 信號都顯示擁塞輕時,該路徑被認為是非擁塞路徑;當檢測的RTT 和ECN 信號都顯示重擁塞時,該路徑被認為是擁塞路徑;其他情況,該路徑被認為是灰色路徑.另外,當Hermes 檢測到某條路徑上的流超時事件超過3 次或者收不到任何ACK 包時,該路徑被認為是故障路徑,重路由時會忽略此類路徑.重路由模塊采用包級別的調度粒度以及時反應網絡擁塞.為了防止擁塞不匹配和數據包亂序問題,Hermes根據路徑狀態和流狀態來做重路由決策.只有新流出現或流遭遇超時,或者當前路徑被認定為擁塞路徑時,Hermes 才觸發重路由機制.而且,Hermes 只重路由低于一定發送速率的長流,同時要保證切換的路徑是有收益的.Hermes 適用于非對稱網絡,但是重路由的決策過于保守,易導致鏈路利用率低.

Fig.3 Schematic diagram of Hermes圖3 Hermes 原理圖

ELAB[52]是一種基于主機端的負載均衡機制,不但易于部署,而且能動態感知網絡擁塞.ELAB 部署在主機系統協議棧的網絡層和傳輸層之間,首先將數據包進行封裝,加入隧道包頭;然后,通過改變隧道包頭的五元組在主機上實現主動路由.ELAB 在主機進行第1 次通信時探測路徑狀態,再以較長的周期反復探測以感知網絡拓撲的變化.ELAB 主機端維護路徑上限帶寬、實際發送速率和可用帶寬這3 個狀態.其中,上限帶寬初始化為鏈路物理帶寬,然后依據是否收到ECN 標記包,以實際發送速率來更新上限帶寬.在收到ECN 標記包的一段時間后,主機端在擁塞路徑上發送一組探測包以重新探測上限帶寬.實際發送速率由接收端的數據包接收速率決定.可用帶寬為上限帶寬和實際發送速率的差值.最后,ELAB 主機端按照可用帶寬比例,以比例輪詢的方式在各條路徑上分配流量.ELAB 機制無需修改交換機,實現了路徑擁塞狀態敏感的負載均衡.

3.2.2 流量切分的主機負載均衡機制

MPTCP[53]是一種基于主機的多路徑傳輸控制協議,在發送主機上,將原本的單條數據流劃分成多條并行的子流在不同路徑上傳輸.MPTCP 在發送端和接收端之間建立多條子流,各子流擁有獨立的序號空間和擁塞窗口,執行類似TCP 的加性增窗乘性減窗策略,可自適應地將流量從擁塞路徑上轉移到非擁塞路徑上,從而實現多路徑的負載均衡.盡管MPTCP 提升了長流的性能,但在丟包情況下,它嚴重加劇了延時敏感短流的拖尾時間.當路徑發生擁塞的時候,短流在擁塞路徑上的子流很容易發生全窗丟失而觸發超時事件.而MPTCP 的子流僅僅處理自身的丟包事件,無法快速解決超時問題,導致長的拖尾延時,從而影響整體的流完成時間.

FUSO[54]改進了MPTCP 協議,能更快速地恢復丟包.FUSO 利用輕擁塞子流的空閑擁塞窗口快速重傳其他子流沒有確認的數據包,避免了拖尾子流的影響,減少流傳輸的總體完成時間.當發送端發現應用層沒有新的數據包發送,同時傳輸層擁有空閑擁塞窗口的時候,擁塞最輕的子流會重傳擁塞最重子流的未確認的包.此外,MPTCP 的接收端有一個共享緩沖區,每條子流擁有一個映射到該共享緩沖區的虛擬接收緩沖區.FUSO 的接收端直接將恢復的包放在共享緩沖區,加快數據的提交.

MPTCP 使用子流均衡網絡中的流量,每條子流維護獨立的擁塞窗口,最大化每條路徑的吞吐量,提升了數據中心中數據傳輸性能.但MPTCP 不適用于ToR 內的流和多對一模式下的短流.一方面,同一ToR 內的主機對之間只有一條路徑,多條子流同時發送到一條路徑上會增加鏈路擁塞;另一方面,增加多對一短流的子流數會加重網絡擁塞,短流的子流過小又容易遭遇丟包超時.DCMPTCP[55]方案是對MPTCP 的改進:首先,使用TCP 協議控制ToR 內流量,消除不必要的子流減少開銷;然后,DCMPTCP 依據已發送字節數評估流大小.短流用一條子流傳輸所有的數據以減輕多條子流造成的突發丟包問題.對于ToR 間的流量,當一條路徑上發生擁塞時,發送端的所有子流共享擁塞信息并減小擁塞窗口.

為了充分利用數據中心網絡的鏈路帶寬,多路徑TCP 將一條流切分為多條子流,在多條并行路徑上傳輸.但是:當短流被切分為多條子流時,每條子流的擁塞窗口過小,在遭遇丟包時易發生超時,嚴重影響短流的延時;而當長流被切分為多條子流時,擁塞路徑上的子流也容易阻塞整體傳輸.DC2-MTCP[56]作為一個多路徑傳輸協議,利用網絡編碼技術來快速恢復丟失和被阻塞的數據包.發送端首先通過監測數據包的丟失事件,推測路徑質量,以選擇合適的包進行編碼:若路徑間質量差異小,使用前向糾錯編碼技術對總發送窗口中最后若干個未被確認的包進行編碼,以加快數據包恢復;若路徑間質量差異大,選擇總發送窗口中最先若干個未被確認的包進行后向糾錯編碼,以減少編碼開銷.然后,將編碼包分配給不同的子流.DC2-MTCP 依據路徑的質量調整長流的編碼冗余度:輕擁塞的子流主動傳輸更多的冗余包,以恢復重擁塞子流的丟包;在高質量路徑上傳輸更多的編碼包,以均衡冗余負載.對于無法準確感知路徑質量的短流,通過歷史統計信息來調整編碼冗余度.DC2-MTCP 降低了短流的延時,同時提高了長流的吞吐量.

針對數據中心長流和短流各自的性能需求[71],MMPTCP[57]采用包分散和子流傳輸相結合的方式,提高網絡鏈路利用率.在初始階段,使用隨機包分散方法快速利用所有可用路徑資源,有效降低了延時敏感短流的完成時間;當已發送字節大于一定閾值時,采用MPTCP 協議來傳輸,MMPTCP 的長流被分割成多條子流,保證了較高的吞吐率.包分散的方法易帶來數據包亂序問題,可通過動態調節快速重傳門限值來防止由數據包亂序引起的虛假重傳.MMPTCP 根據拓撲信息調節快速重傳門限值,當源端發送的流量需要通過核心層交換機時,采用較高的快速重傳門限;當流量僅在同一ToR 交換機內傳輸時,采用較低的快速重傳門限.MMPTCP 使用胖樹尋址方案作為設置快速重傳門限的基礎,每個源端通過檢查源IP 地址和目的IP 地址來推斷其流量將穿越的網絡拓撲層.當主機對間的流量在同一ToR 交換機下傳輸時,采用默認的快速重傳閾值3;當主機對間的流量必須經過匯聚層和核心層交換機時,則使用較高的閾值.

在虛擬化多租戶數據中心,客戶通常會部署自定義虛擬機.各虛擬機管理器(如hypervisor)下的虛擬交換機可利用多條等價路徑實現負載均衡,而無需物理網絡中的特殊功能或修改客戶虛擬機TCP/IP 協議棧,有利于移植與擴展.

Presto[58]使用軟件交換機將流切分成64KB 的數據切片.Presto 利用中央控制器收集拓撲信息,并將信息轉發給在主機上的軟件交換機.控制器首先將網絡分割成一組生成樹,每個軟件交換機對應一個生成樹.然后為每一個生成樹中的每一個軟件交換機分配一個唯一的轉發標簽,并安裝相關的轉發規則.為了實現有效的負載均衡,軟件交換機以輪詢的方式訪問影子MAC 地址,使得數據切片均勻地分布在網絡中.雖然小于64KB 的流不會發生亂序,但大于64KB 的流仍然可能亂序.Presto 修改的GRO(generic receive offload)算法區分了丟包和亂序.當發生亂序時,因為亂序的包還在網絡中,修改的GRO 不直接提交原來的段,而是等待亂序包到達后再提交給上層.由于數據切片內不會發生亂序,當屬于同一個數據切片中的包出現空缺時,Presto 認為這是丟包引起.此時,GRO 立即向上層提交數據段.當流切片的邊界出現空缺,無法判斷是丟包還是亂序時,Presto 則依據是否超時判斷丟包.

虛擬多信道散射VMS[59]方案是一個基于虛擬交換機的負載均衡機制.VMS 通過在發送端改變五元組,將一條流的包分散到多條轉發路徑上;接收端接收到數據包后,改回原來的五元組,并重新排序數據包以避免亂序.VMS 估算每一條轉發路徑的可用帶寬,用虛擬窗口大小表示,在TCP 包頭中設置窗口大小,調節流傳輸速率.VMS 根據不同路徑的虛擬窗口大小,自適應地為數據包選擇轉發路徑.VMS 在虛擬機交換機上部署,不需要修改網絡協議棧和主機底層協議,可近似實現MPTCP 的性能.但是VMS 兩端都需支持虛擬交換機,同時,軟件交換機的處理延時大,影響延時敏感流的性能.

為了簡化數據平面交換機的操作,DumbNet[60]在主機上實現拓撲發現、網絡路由和故障處理.主機使用源路由對數據包進行轉發,數據包的包頭包含一組代表其傳輸路徑的端口號;交換機僅依據數據包攜帶的端口號轉發數據包,完全實現了網絡數據平面無狀態化.DumbNet 使用基于主機的機制來收集路徑信息,按照廣度優先搜索算法發送探測包到其他主機來發現拓撲結構.然后,主機將路徑信息存儲在中央控制器中,由中央控制器維護全局拓撲信息和優化轉發路由.同時,主機從中央控制器獲得所有的可用路徑,并存儲在主機緩存中,以避免由鏈路故障引起的通信中斷問題.最后,主機在數據包的包頭寫入其傳輸路徑信息.DumbNet 的每臺主機維護了流信息,并存儲了多條可選路徑信息,實現了包簇級別的負載均衡.

Flicr[61]是一個針對直連網絡的主機端負載均衡方案.直連網絡是指ToR 交換機之間直接相連的網絡拓撲,其包含了多條不同長度的路徑.Flicr 利用ECN 和TCP 重傳超時檢測路徑擁塞和故障.每條流開始發送時被路由到最短路徑,而當發生擁塞時被重新路由.Flicr 以RTT 為周期做路由決策,并以固定大小的包簇作為重路由的粒度以均衡負載.具體來說,Flicr 使用了交換機上的擴展哈希功能和VLAN 標簽,將交換機上的可用端口分配給最短路徑和非最短路徑的兩個轉發表,然后將兩組VLAN 標簽值映射到這兩個轉發表.交換機依據包頭的VLAN標簽值,在對應的路由表中查找轉發端口.Flicr 部署在主機端,根據擁塞信號更新數據包包頭字段的VLAN 標簽值,以重路由流量.Flicr 考慮了端到端的擁塞信息,可適用拓撲和流量不對稱場景.

主動式的流量切分負載均衡可以將任意長度的流切分成多段數據來實現負載均衡,可在一定程度上減少長流堵塞短流的問題,同時提高了網絡鏈路的利用率.但是,流量切分方案容易發生擁塞路徑上的拖尾問題.

3.2.3 細粒度調度的主機負載均衡機制

大多數負載均衡方案都以提高網絡利用率為目標,沒有同時考慮低延時和高吞吐量的需求.細粒度的負載均衡方案較好地平衡兩個目標.DRB[62]是一個部署在胖樹和VL2 拓撲的分布式負載均衡機制,以數據包作為調度粒度.DRB 選擇交錯路徑傳輸數據包,以避免連續的數據包被轉發到同一條鏈路引起的隊列堆積問題.例如,在胖樹拓撲中,發送主機將第1 個數據包隨機發送至一個匯聚交換機,然后為下一個數據包以輪詢的方式選擇下一個匯聚交換機,以避免連續的數據包轉發至同一個核心交換機.DRB 將數據包均勻地分配到各個路徑上,充分利用了網絡資源,避免了交換機隊列堆積,降低了拖尾延時.

JUGGLER[63]是用來解決數據中心中負載均衡機制下數據包亂序問題的方案.GRO(generic receive offload)合并接收的有序數據包提交給上層,以減少每個數據包的CPU 處理開銷.但數據包亂序會引起很高的CPU 開銷.JUGGLER 在網絡堆棧的入口GRO 層盡可能多地對數據包進行排序.JUGGLER 先緩存活躍流的亂序數據包以等待亂序包達到,再有序地提交給上層.JUGGLER 可解決嚴重亂序問題,減少CPU 的開銷,但其需要修改網絡協議棧.

NDP[64]采用包級別的轉發方式,均勻地將流量分布到所有平行路徑上傳輸,加快傳輸速度,實現了低延時和高吞吐量的目標.NDP 的發送端對所有可用路徑隨機排序,然后按隨機的順序在每條路徑上發送一個數據包,發完一輪數據后重新排序路徑,有效避免了多個發送方同時選擇相同的路徑傳輸.NDP 采用了剔除數據包負載保留包頭的方式來避免數據包丟失.當交換機的隊列長度超過一定閾值(比如8 個數據包)時,數據包的負載被剔除,只保留其數據包頭,有效降低了排隊延時.數據包頭優先正常數據包出隊,驅動快速重傳,有效降低了重傳延時.同時,NDP 是一個接收端驅動的方案.接收端根據接收的數據包驅動響應包(PULL 包),發送端以接收的響應包來發送數據包或重傳包,可保證數據包的發送速率與接收端的鏈路速率匹配,實現了高吞吐率.

為了消除數據包亂序的影響,CAPS[65]提出了基于編碼的自適應包分散機制,在傳輸層和網絡層之間增加了數據包編碼層,利用編碼包恢復亂序的數據包.為了利用多路徑和防止短流遭遇線端阻塞,CAPS 對短流的數據包進行編碼,并將其散射到所有路徑上.同時,為了提高長流的吞吐量,長流在短流的ON 階段用ECMP 傳輸;而在短流OFF 階段,則使用所有路徑以包粒度傳輸.

CAPS 由3 個模塊組成.

· 第一,編碼模塊.發送端使用前向糾錯編碼技術(forward error correction,簡稱FEC)[72]對短流的數據包進行編碼,每k個數據包被編碼成k+r個編碼包,其中產生了r個冗余包.冗余包影響解碼速率和網絡負載開銷,因此,CAPS 根據實時網絡狀況調節冗余包的數量,以實現收益的最大化.

· 第二,包散射模塊.為了減輕長短流間的相互影響,CAPS 對長短流采取不同的調度策略:短流使用隨機包散射(RPS)方案隨機散射到所有路徑上;而長流與短流共存時,長流使用ECMP 路由機制避免亂序,否則使用RPS 機制.

· 第三,解碼模塊.接收端在網絡層獲得任意k個編碼包后,解碼出k個原始數據包,提交給上層.

基于編碼技術的負載均衡方案可有效地減輕數據包亂序的問題,但是會增加網絡中冗余包的數量,加重網絡擁塞.

RDMA 因其低時延、高吞吐量和低CPU 開銷的特性被廣泛部署使用,但目前的RDMA 采用單條路徑傳輸機制,無法利用數據中心中豐富的并行路徑資源.MP-RDMA[66]方案為RDMA 提供了一種多路徑傳輸機制,采用了3 種新的技術解決RDMA 網卡芯片內存容量有限的問題.

(1) 采取一個多路徑的ACK-clocking 機制來分配流量.具體來說,發送方依據接收的每個ACK 所攜帶的ECN 標志位來調整擁塞窗口:若ECN 標志位為0,則擁塞窗口增加1;若ECN 標志位為1,則擁塞窗口減半.

(2) 使用一個亂序感知的路徑選擇機制,主動剔除慢路徑并自適應地選擇一組快速且延遲相似的路徑.

(3) 利用同步機制,以確保在需要時按順序更新內存.

與單路徑RDMA 相比,MP-RDMA 僅為每個連接狀態增加66B 額外內存大小,可以顯著提高異常情況下的健壯性,并改善整體網絡利用率.

3.3 基于交換機的負載均衡機制的研究

集中式負載均衡方案部署開銷大,反饋和控制延時長;基于主機的負載均衡方案則需要修改主機協議棧.因此,目前主流的數據中心網絡負載均衡策略是通過在交換機上快速感知網絡擁塞,采用不同的調度粒度將網絡流量發送到不同的路徑上.近年來,學術界提出了多種基于交換機的方案,見表3,它們的解決思路可按調度粒度劃分為:①WCMP[73]、Expeditus[74]、TinyFlow[75]、DiFS[76]、DFFR[77]、Beamer[78]、iLoad[79]、Al-Tarazi[80]、Dart[81]等流級別的調度方法;② Detail[82]、RPS[83]、DRILL[84]、GRR[85]、QDAPS[86]、RMC[87]、OPER[88]等包級別的調度方法;③Flare[89]、CONGA[90]、HULA[91]、Multi-hop CONGA[92]、LetFlow[93]、Luopan[94]和MLAB[95]等包簇級別的調度方法;④ AG[96]、TLB[97]等自適應粒度的調度方法.

Table 3 Comprehensive comparison of switch-based load balancing mechanisms表3 基于交換機的負載均衡機制的綜合對比

Table 3 Comprehensive comparison of switch-based load balancing mechanisms (Continued 1)表3 基于交換機的負載均衡機制的綜合對比(續1)

Table 3 Comprehensive comparison of switch-based load balancing mechanisms (Continued 2)表3 基于交換機的負載均衡機制的綜合對比(續2)

3.3.1 流級別的交換機負載均衡

由于ECMP 不感知路徑的擁塞狀態和流量特征,容易造成多條數據流在路徑上發生哈希沖突.為了避免路徑流量的不均衡,加權等價多路徑路由WCMP[73]利用中央控制器得到的網絡拓撲和流量信息,根據路徑的帶寬容量為每條路徑分配權重,以加權公平方法將流量哈希到不同的路徑.WCMP 可以改善ECMP 中哈希沖突的問題,同時適用不對稱網絡.但是作為一種流粒度的負載均衡方法,WCMP 不夠靈活,不能依據網絡擁塞信息對流進行重路由.

擁塞感知負載均衡方案要求知道源目的端之間所有路徑的實時擁塞信息,通常由ToR 交換機維護從其自身到其他ToR 交換機之間所有路徑的端到端擁塞狀態信息.雖然可以通過數據包攜帶擁塞狀態,但這種信息反饋方法難以在復雜的3 層CLOS 拓撲中使用.Expeditus[74]方案是一個適用于3 層網絡架構的分布式擁塞感知的負載均衡協議.Expeditus 首先通過監測本地出端口和進端口的鏈路負載,確保擁塞狀態的實時性.然后,Expeditus 使用兩階段路徑選擇機制來匯總跨交換機的擁塞信息并做負載均衡決策.

· 第1 階段,只有源和目的ToR 交換機選擇從ToR 交換機到匯聚層的最好的路徑.源ToR 交換機發送其出端口的擁塞信息給目的ToR 交換機,目的ToR 交換機將接收的擁塞信息與本地進端口擁塞信息相結合,選出到匯聚層的最佳路徑.

· 第2 階段,被選擇的匯聚層交換機以同樣的方式根據2 層和3 層的擁塞信息選擇最佳的核心層交換機.最終,ToR 和匯聚層交換機保存路徑選擇的結果.

Expeditus 為每條流在其TCP 三次握手期間做路徑選擇,可防止數據包亂序問題,同時也不會引入延時開銷.

針對ECMP 不區分長短流帶來的線端阻塞和拖尾延時的問題,以及哈希碰撞帶來的帶寬利用不足的問題,TinyFlow[75]將長流分割成多條10KB 的短流,讓所有的短流以ECMP 的路由方式均勻分布在所有路徑上.TinyFlow 主要包括兩個部分:長流檢測和動態隨機路由.在TinyFlow 中,ToR 交換機通過采樣與主機相連的端口的流量檢測流信息.TinyFlow 利用OpenFlow 實現動態隨機路由.當監測到長流時,交換機隨機選擇一個不同的出端口傳輸該流,同時修改流表、重置字節數.TinyFlow 可降低短流的完成時間,同時提高長流的吞吐率.但是,TinyFlow 易造成長流亂序的問題.

DiFS[76]方案將數據中心中的流量沖突分為本地沖突和遠端沖突.在交換機一條出口鏈路上遭遇的并且可以通過本地調整傳輸路徑解決的沖突,稱為本地沖突;從多個核心交換機經過同一匯聚交換機到同一ToR 交換機引起的流量沖突,稱為遠端沖突.DiFS 的每個交換機采用分布式貪婪路徑分配算法將流量均勻分配到所有出口鏈路,以避免本地流量沖突.同時,每個交換機運行不均衡檢測算法監測進口鏈路的流量.如果檢測到流量沖突,交換機將發送顯式適應請求(EAR)消息給流的發送交換機,建議其更改轉發路徑.收到EAR 消息后,發送交換機運行顯式適應算法,避免遠端流量沖突.DiFS 作為分布式流量調度算法,可擴展性強,但也存在路徑振蕩問題,需要較長的收斂時間.

DFFR[77]方案是一種分布式自適應負載均衡算法,從理論上最大化匯聚層網絡利用率.已存在的分布式算法利用重路由流量來達到負載均衡的效果,這會引起路徑振蕩問題或者TCP 亂序問題.DFFR 通過維護每個交換機上每個出端口的流量信息,不采用重路由和流量分割,而是所有交換機將流量均勻分配給到同一目的ToR交換機的所有路徑,從而使得網絡達到最佳平衡,最大程度地利用所有帶寬.DFFR 在理論上和理想的情況下可以實現最優平衡,但其分布式的方案難以適應高動態和強突發的數據中心流量.同時在不對稱網絡下,難以只根據本地信息實現理想的負載均衡.

數據中心負載均衡器(MUX)通過一組動態后臺服務器實現了請求的分發,均衡多個服務器之間的請求分布,避免單個服務器出現過載.現在,負載均衡方法在MUX 上保存了每個連接所選服務器的狀態信息,保證每個連接的數據都發送到同一個服務器,但是存在MUX 與服務器之間的狀態不匹配問題.當MUX 和服務器數量同時發生變化時,會使連接中斷.當請求連接數量很多時,負載均衡器的吞吐量下降.Beamer[78]不需要在MUX 中保存每條流的狀態,而是利用存儲在后臺服務器中的連接狀態確保連接不會丟失.當服務器接收到一個無連接狀態的數據包時,會將其轉發到另一臺保持該數據包所在連接狀態的服務器.Beamer實現了穩定哈希.連接先被哈希映射到一組固定的桶上,每個桶能映射到任何一個服務器.當服務器池發生變化時,Beamer利用控制器更新并保存服務器和桶之間的新映射,MUX 再把流量分配到新服務器,保證了不中斷、平滑的流量遷移.Beamer 能高效處理增加、移除MUX 和服務器的情況.

iLoad[79]是一種基于可編程數據平面的綠色數據中心負載均衡體系結構,其中部署了iLoad 的服務器向可編程交換機發送能源可用性信息.交換機根據該信息構建哈希表,以均衡服務器的工作負載與可用能源,使得可用能源多的服務器能承擔更多的工作負載.

數據中心現有的大多數節能方案側重于最大程度地降低能耗,而忽視了網絡傳輸性能.Al-Tarazi 等人[80]首先證明了數據中心的最小化能耗問題是一個混合整數線性規劃問題,提出了啟發式節能算法,然后通過負載均衡機制提升網絡傳輸性能.該節能算法盡可能地關閉所有空閑的端口和交換機,最小化活躍交換機和鏈路的數量,以最大程度地降低能耗.該方案同時使用了負載均衡機制在活躍鏈路上分配負載.該機制將流量負載分配到一個隨機選擇的活躍交換機,同時確保該交換機出口鏈路的可用帶寬能滿足流量負載的帶寬需求,又不會造成該鏈路的利用率過載.該機制可有效緩解延時、丟包和鏈路擁塞問題.

在基于RDMA 的數據中心中,現有的大部分擁塞控制機制需要通過多次迭代才能調節速率至目標速率,收斂速度較慢.Dart[81]方案將擁塞分為接收端擁塞和網內擁塞,以分治的思想快速緩解擁塞.其中,接收端擁塞的產生原因是同一接收端的并發流匯聚于連接接收端的最后一跳鏈路,網內擁塞是由不同接收端的流在網絡中其他鏈路上發生碰撞而產生.對于接收端的擁塞,接收端通過顯式分配速率的方式快速調節發送方的發送速率;對于網內擁塞,Dart 在硬件交換機部署按序流偏轉機制對流進行重路由,以快速響應擁塞.當某條流遇到擁塞時,交換機為該流選取其他替代路徑,以避開擁塞鏈路.為了避免亂序和減少CPU 開銷,Dart 只對部分短流進行路徑偏轉.對于發生網內擁塞的長流,則采用DCQCN[98]機制緩解擁塞.

流級別的負載均衡方法將同一條流的數據包在相同路徑上傳輸,能有效地避免亂序問題.但在高動態和強突發的網絡流量下,靜態負載均衡方法不但容易發生擁塞沖突導致拖尾,而且無法靈活切換路徑,難以充分利用網絡帶寬.

3.3.2 包級別的交換機負載均衡

為了充分利用網絡帶寬,許多負載均衡方案以數據包為調度粒度.Detail[82]是一個跨層的方案,如圖4 所示,通過快速檢測下層的擁塞狀態,驅動上層的路由決策,以減少拖尾流完成時間.Detail 利用鏈路層信息減少丟包,在網絡層執行包級別的負載均衡以均勻流量來減少拖尾程度,在傳輸層關閉TCP 協議的快速恢復和重傳機制來抵抗包亂序帶來的虛假擁塞通知,在應用層提升延時敏感流的優先級以保證其性能.

具體來說,在鏈路層,Detail 使用優先級流控機制(PFC)[99]構建了一個無損結構.交換機監控入口隊列占用情況,當隊列長度超過一定閾值時,交換機發送暫停消息(pause)給上一跳,要求其停止發送數據包;當隊列長度減小,交換機發送重啟消息(unpause)給上一跳,要求其恢復數據包傳輸.通過這種快速響應,無損結構可確保數據包不會因擁塞而丟失.在網絡層,Detail 根據出端口隊列占用信息,動態地為每個數據包選擇擁塞最輕的下一跳.由于鏈路層的無損結構避免了網絡擁塞丟包,Detail 關閉TCP 協議的快速恢復和重傳機制來避免數據包亂序觸發的虛假重傳.在應用層設置延時敏感流和延時不敏感流的優先級,確保高優先級的延時敏感流先被轉發.

Fig.4 Schematic diagram of Detail圖4 Detail 原理圖

相對于復雜的跨層方法,RPS[83]方案實現了一個簡單的包級別負載均衡,在交換機上隨機地將數據包發送到所有的可用發送路徑,提高了鏈路利用率.RPS 不要求修改主機,得到了很多商用交換機的支持.RPS 可以提高網絡利用率,保證負載均衡,但是它無法適應非對稱拓撲,易遭受數據包亂序問題.由于TCP 無法區分亂序包和丟失的包,亂序包會導致擁塞窗口降窗,從而降低TCP 的性能.為了解決非對稱問題,RPS 采用了隊列管理機制限制隊列長度,減小隊列間的延時差異,以減輕數據包亂序程度.

為了更快速地緩解突發流量引起的擁塞,DRILL[84]提出了一個針對微突發流量的負載均衡策略.由于基于全局流量信息的負載均衡系統的控制周期很長,可能無法檢測和緩解生命周期短暫而又容易引起丟包的微突發流量.DRILL 僅利用本地信息快速做決策,通過比較當前隨機選擇的兩個端口和上一輪最好端口的隊列長度,選擇最小隊列長度的端口作為當前數據包的轉發端口.DRILL 可以及時地解決微突發流量帶來的擁塞問題,但是只依據本地交換機緩存隊列長度判斷路徑狀態,不能準確感知全局的擁塞信息,無法避免亂序問題.為了解決拓撲不對稱帶來的亂序問題,DRILL 將不對稱的網絡拓撲分割成多個對稱的子拓撲,在每個子拓撲里執行基于本地隊列的負載均衡決策.同時,DRILL 根據每個子拓撲的路徑容量為其分配權重,按權重將流量負載分配到各個子拓撲,以均衡流量負載.DRILL 根據交換機本地隊列長度快速地執行數據包級別的轉發決策,可實現微秒級別的負載均衡,有效地解決了微突發流量帶來的擁塞問題.

全局輪詢GRR[85]方案是一個適用于胖樹拓撲的包級別負載均衡路由算法.假設每個時隙容納一個數據包.在每個時隙中,GRR 為每個主機選擇從服務器到一個主干交換機端口的路由路徑,且任何路徑都不會相互交叉.GRR 使用了一種快速轉發且沒有緩存隊列的直通轉發交換機.數據包通過直通轉發交換機從源服務器發送到主干交換機.每個時隙內,路由路徑以輪詢的方式更新,實現了每包的負載均衡.GRR 方案可以保證100%的吞吐量,但是它依賴于直通轉發交換機.當交換機的端口變多,交換矩陣變得復雜時,難以實現理想的直通交換.

包級別的負載均衡方案可以充分利用多路徑資源,提高網絡的利用率.但在非對稱拓撲下,包級別的方案的魯棒性不強,極易發生亂序問題,導致TCP 性能下降.QDAPS[86]方案設計了一種排隊延時敏感的包粒度負載均衡方案,以對抗數據包亂序問題.QDAPS 在交換機上根據同一條流的上一個數據包的剩余排隊時間為該流當前數據包選擇合適的出端口隊列,使數據包能夠有序到達接收端.

QDAPS 由3 個模塊組成.

· 第一,估計隊列延時.當交換機接收了一個新包時,QDAPS 根據該包所在隊列的實時隊列長度估計其排隊延時.QDAPS 只需記錄每條流最新到達包的排隊延時.

· 第二,解決包亂序.QDAPS 為流的第1 個數據包選擇最短隊列,然后在后續到達的數據包選擇出端口時保證了該出端口的排隊延時大于該流上一個數據包的剩余排隊時間,使得該流的數據包按序轉發.

· 第三,重路由長流.由于QDPAS 的每個數據包總是排在該流上一個數據包的后面,長流易經歷較長的排隊延時.當隊列長度超過某一閾值時,QDAPS 重新選擇最短出端口隊列,防止出端口隊列堆積的問題.重路由長流一方面降低長流的排隊延時,另一方面增加亂序降窗的概率,因此,QDAPS 選取了合適的重路由閾值以權衡排隊延時收益和亂序開銷.

QDAPS 作為包級別的負載均衡方案,增加了調度的靈活度,能快速地提升鏈路利用率;同時,根據交換機隊列延時信息選擇合適的出端口隊列,有效地避免了亂序問題.但是QDAPS 要為每條流最新到達包記錄排隊延時,受交換機有限的狀態內存的限制.另外,QDAPS 需要為每個數據包計算非亂序路徑,無法忽略大規模流量下的計算開銷.

在數據中心的非對稱網絡拓撲下,負載均衡機制容易出現亂序問題.由于缺乏顯式的亂序反饋,當發送端收到重復ACK 的數量大于預先設定的閾值時,發送端誤認為網絡出現擁塞從而觸發快速重傳.這些不必要的快速重傳勢必降低鏈路利用率,增加流的完成時間.RMC[87]方案顯式反饋包亂序,并采用編碼技術來減少拖尾時間.交換機根據本地隊列長度和全局路徑延遲主動地標識亂序包,避免不必要的快速重傳.發送端依據亂序包的占比計算冗余編碼包的數量,減少拖尾時間.

數據包級別的細粒度負載均衡機制可以充分利用多條路徑,從而實現高鏈路帶寬利用率和均衡流量.但是網絡拓撲不對稱時的包丟失問題導致了較大的流完成時間,造成了傳輸性能的下降.雖然基于網絡編碼的解決方案可以有效地解決亂序問題,但也會引入過多的冗余編碼包,帶來過多的流量開銷,導致較長的排隊延遲甚至丟包.為了解決這個問題,OPER[88]提出了一種具有自適應能力的冗余編碼包替換機制.在嚴重擁塞時,OPER 在交換機緩存中用新到達的數據包替換冗余編碼包,來避免冗余包產生的額外排隊延遲;否則,OPER 不替換或者少量替換冗余編碼包,保證亂序情況下的健壯性.OPER 極大地減少了網絡擁塞時編碼包導致的排隊延遲,提升了負載均衡機制的傳輸性能.

3.3.3 包簇級別的交換機負載均衡

流級別的負載均衡方案可有效避免數據包亂序,但易發生擁塞碰撞且無法充分利用多路徑資源.包級別的負載均衡方案充分利用了多路徑資源,但極易發生亂序問題.包簇級別負載均衡的切換粒度介于以上兩類之間,可有效保證鏈路利用率和降低數據包亂序程度.包簇一般是由包間時間間隔區分的,當包間時間間隔大于某個值時,則產生一個新的包簇,由交換機來重新選擇路由.

FLARE[89]為了避免亂序問題,僅當兩個連續數據包間的時間間隔大于路徑延時的最大差異時,才將下一包簇發送到其他的路徑上.FLARE 實時測量所有路徑的延時,保證流量切割的動態性和準確性,但同時也帶來了很大的測量和計算開銷.

CONGA[90]是一種擁塞感知的負載均衡方案,采用包簇作為調度粒度,如圖5 所示.

Fig.5 Schematic diagram of CONGA圖5 CONGA 原理圖

CONGA 利用DRE(discounting rate estimator)技術測量和量化鏈路的擁塞程度.用VXLAN[100]封裝的數據包在網絡傳輸過程中不斷地依據路徑上交換機的最重擁塞信息來更新包頭攜帶的路徑擁塞量化值.源和目的ToR 交換機各自維護一張擁塞信息表,其中:目的ToR 交換機解析正向數據包包頭中的路徑擁塞量化值,并記錄在擁塞信息表中;由反向傳輸的數據包將各條路徑的擁塞信息攜帶給源ToR 交換機.源ToR 交換機接收到反向數據包后,更新其擁塞信息表.此外,源ToR 交換機還維護了一張包簇表,記錄了活躍包簇的序號和所選的路徑.源ToR 交換機根據擁塞信息表和包簇表為每個包簇選擇最輕擁塞路徑.CONGA 基于端到端的路徑狀態反饋信息實現了全局擁塞感知的負載均衡,能夠感知路徑的擁塞和失效,可適用于非對稱網絡.但是CONGA 需要存儲大量路徑信息,并使用定制的交換機,使得CONGA 難以大規模部署;另外,從遠端交換機得到的反饋可能無法準確反映實時路徑狀態.

HULA[91]采用可編程交換機實現擁塞感知的負載均衡,克服了CONGA 的擴展性問題.一方面,HULA 交換機僅通過鄰居交換機維護到目的交換機的最佳下一跳路徑,無需記錄所有路徑的鏈路利用率,從而降低了維護路徑狀態的開銷;另一方面,HULA 利用P4 語言實現了在可編程交換機上運行的原型,不需要定制的交換機硬件,便于修改和擴展.具體地,HULA 定期發送探測包到所有可用路徑,以收集全局鏈路利用率信息.基于探測包反饋信息,每個交換機選擇路徑利用率最小的下一跳路徑,并將其通告給所有鄰居節點.同時,每個交換機維護一張擁塞信息表用來存儲到目的地的最佳下一跳路徑,有效消除了路徑爆炸對交換機的存儲壓力.另外,HULA使用探測包主動獲得路徑擁塞信息,感知網絡拓撲的變化.探測包由ToR 交換機生成,它們經過的每個交換機會更新擁塞信息表.為了避免亂序,HULA 也選擇包簇作為調度粒度,為每一個包簇選擇最佳路徑.HULA 雖然解決了CONGA 的可擴展性問題,但由于HULA 只選擇最佳下一跳路徑,容易發生羊群效應,導致在最佳路徑上發生擁塞.同時,最佳路徑的更新速度取決于探測頻率,而頻繁使用探測包會降低網絡的有效利用率.

CONGA 方案主要均衡Leaf-Spine 拓撲結構中單跳路徑上的網絡流量.單跳路徑是指數據包首先從與發送端相連的ToR 交換機上行鏈路向核心交換機傳輸,然后從核心交換機的下行鏈路向與接收端連接的ToR 交換機傳輸.但當路徑中的某條鏈路發生擁塞時,發送方誤認為整條單跳路徑擁塞.當所有單跳路徑均發生擁塞時,發送端將認為所有鏈路都發生了擁塞.而實際上,此時仍然可能存在部分非擁塞鏈路.Multi-hop CONGA[92]在所有單跳路徑負載重時,使用兩跳路由路徑繞過擁塞鏈路,通過利用相對較長傳輸路徑上的非擁塞鏈路來緩解局部流量壓力.Multi-hop CONGA 利用數據包攜帶的延時信息判定路徑的擁塞程度:首先,在可選的單跳路徑中選擇最輕擁塞路徑作為傳輸路徑;當所有單跳路徑的延時超過一定閾值時,搜索最輕負載的兩跳路徑作為傳輸路徑;當所有兩跳路徑都擁塞時,則使用最輕擁塞的單跳路徑作為傳輸路徑.為了降低計算的復雜性和提高網絡利用率,Multi-hop CONGA 采用包簇作為調度粒度.作為全局擁塞感知的負載均衡機制,Multi-hop CONGA 可解決非對稱網絡的問題,但是數據包中攜帶反饋信息過多,容易浪費帶寬.

為了完全避免交換機檢測路徑擁塞的開銷,LetFlow[93]利用數據包間的自然屬性自動地感知路徑擁塞.當流在某條路徑上遭遇擁塞時,其數據包間的間隔會增長,自然形成具有時間間隔的包簇.LetFlow 按時間間隔閾值來區分包簇,并將包簇隨機發送到其他路徑.由于間隔閾值的選取一般大于最大路徑差異,LetFlow 可以避免亂序,有效對抗非對稱問題.LetFlow 不需要獲得全局擁塞情況,相比于CONGA 等全局擁塞信息感知的方案,可擴展性更好.但由于LetFlow 調度的隨機性,無法取得最優負載均衡性能.

以上依據包間隔來被動地劃分包簇的負載均衡方法,難以適應快速變化的網絡流量,而且不合理的間隔閾值容易造成鏈路空閑或過于頻繁的路徑切換.Luopan[94]是一個基于采樣的負載均衡方案.Luopan 采用固定大小的包簇作為調度單元,包簇大小被定為服務器限制的最大TSO 大小64KB.針對在源目的交換機之間存在多條等價路徑,Luopan 定期采樣部分路徑,然后將包簇直接轉發到最小隊列長度的路徑上以實現負載均衡.

具體來說,源端交換機定期發送少量探測包到目的交換機,以探測幾條隨機路徑的擁塞情況.探測包包頭包括路徑編號PID、包類型Type 和量化擁塞指標QCM 這3 個字段.每一個探測包遍歷所在路徑所有交換機出端口的隊列長度,并將隊列信息累計值存儲在包頭的QCM 字段.目的端交換機接收到探測包時,立即生成對應ACK 反饋包,將擁塞信息發送給源端交換機.當源端交換機依據收到的路徑擁塞信息更新擁塞信息表,并為每個包簇選擇最佳路徑傳輸.作為一個擁塞感知的方案,Luopan 降低了流完成時間,增加了非對稱拓撲環境下的魯棒性.同時,相比于CONGA 等感知整個網絡擁塞的方案,Luopan 還減小了擁塞信息探測和存儲的開銷,具有更好的擴展性.

MLAB[95]方案是一個模塊化負載感知的負載均衡方案.MLAB 首先提出了一個分布式數據驅動的反饋機制,在所有交換機的每個端口部署了一個負載檢測器,由經過的數據包反饋給ToR 交換機以檢測遠端負載.為了避免亂序問題,采用了包簇作為調度粒度,基于全局負載信息為包簇作路由決策.然后,MLAB 將網絡分割為多個路由域,每個域中包含在兩個ToR 交換機之間同一條路徑上的所有的匯聚交換機和核心交換機.從ToR 交換機的角度看,每個域就是一個黑盒,用于傳輸它們的數據給另一個ToR 交換機.每個域中的路由算法相互獨立,域內的負載信息只能給域中的交換機使用,域外的交換機只能通過該域出端口獲得其負載信息.因此,數據包只需攜帶域內最重的負載信息,減少了數據包的開銷,降低了通信存儲更新的難度.MLAB 方案便于部署和模塊化升級.但其簡化了遠端的負載信息,每跳選擇最輕的出端口不一定得到全局的最輕負載路徑.

3.3.4 自適應調度粒度的交換機負載均衡

由于動態流量、鏈路故障和異構交換設備,數據中心網絡容易出現拓撲不對稱問題.在不對稱的網絡拓撲下,流級別和包簇級別的負載均衡方案采用較大的路徑切換粒度,可有效防止亂序問題,但網絡利用率較低.包級別的負載均衡器采用細的路徑切換粒度,可充分利用各條路徑,但易產生亂序問題,無法獲得最優性能.AG 方案[96]根據拓撲不對稱程度自適應調節路徑切換的粒度:在拓撲不對稱程度高的情況下,AG 增加切換粒度以減輕亂序影響;在拓撲不對稱程度低的情況下,AG 降低切換粒度以獲取高的鏈路利用率.AG 利用探測包定期測量交換機間的單向延時以獲得準確的路徑擁塞狀態信息,計算最佳的調度粒度大小,并為每個調度單元隨機分配一條傳輸路徑以防止同步問題.

隨著延遲敏感型和吞吐率導向型應用程序的流量需求不斷增加,如何有效地平衡多路徑之間的流量以提升用戶的體驗和服務的質量,成為大型數據中心網絡中一個至關重要的問題.雖然近年在DCN 中出現了很多負載均衡設計,現有的負載均衡方法并不感知長流和短流混合的流量特性,也沒有考慮不同類型流的需求,為不同類型的流都使用相同的粒度切換路徑.TLB[97]提出了一種數據中心網絡中路徑切換粒度自適應的負載均衡方法,交換機根據數據流的已發送數據量區分長流和短流:對于短流,以數據包為粒度選擇隊列長度最短的出端口轉發其新到達的數據包;對于長流,則在滿足短流延時截止期限的前提下,根據短流到達強度計算長流切換路徑的隊列長度閾值.若某條長流在交換機出端口的隊列長度大于或等于長流切換路徑的隊列長度閾值,則選擇隊列長度最短的出端口轉發該長流新到達的數據包.TLB 減小了短流平均完成時間,同時提高長流吞吐率,但在非對稱拓撲下存在亂序問題.

3.4 小 結

基于中央控制器的方案通過中央控制器收集和分析全網的路徑信息和流量信息,并集中式地選擇傳輸路徑.基于主機的負載均衡方案利用主機感知所有轉發路徑的擁塞信息,顯式地控制每條流的路由路徑.基于交換機的負載均衡機制依據交換機上的隊列長度或者ToR 交換機之間的擁塞信息,為各調度單元選擇不同的出端口.總體上,基于中央控制器的、基于主機的和基于交換機的負載均衡機制各有優點和缺點,見表4.

Table 4 Comprehensive comparison of different categories of load balancing mechanisms表4 不同類型負載均衡機制的綜合對比

Table 4 Comprehensive comparison of different categories of load balancing mechanisms (Continued)表4 不同類型負載均衡機制的綜合對比(續)

4 發展趨勢和展望

針對數據中心網絡的負載均衡問題,已經有了多種改進方案來緩解路徑擁塞、提高利用率和降低傳輸延時,最終提升整體性能.但我們看到,在數據中心網絡流量特性和應用需求下,目前改進方案還存在以下一些關鍵的問題.

· 在負載均衡的控制機理方面,設計擁塞狀態的快速感知方法和切換粒度的動態調節機制仍然是關鍵問題.感知端到端路徑上的擁塞狀態,可獲取準確的全局負載信息,但其反饋周期過長,難以適應快速突發的網絡流量;感知交換機本地緩存狀態可快速獲取局部負載信息,但可能與全局擁塞狀態不符,容易導致錯誤的負載均衡行為.同時,路由的切換粒度也影響負載均衡性能:當切換粒度過大時,易發生網絡利用率不足的問題;否則,容易導致數據包亂序問題.因此,如何進一步優化負載均衡的控制機理仍然值得研究.

· 在擁塞控制和負載均衡的一體化設計方面,存在著傳輸層和網絡層之間狀態不匹配的問題.目前的擁塞控制算法僅依據當前路徑上的擁塞狀態調整速率.而負載均衡做重路由操作時,新路徑狀態可能與當前路徑不一致,容易發生發送速率與路徑擁塞狀態不匹配的問題.例如,重路由到空閑路徑,發送速率過低會導致鏈路利用率低;而重路由到擁塞路徑時,發送速率過高又會進一步加劇網絡擁塞.從跨層設計的角度,如何實現網絡層和傳輸層的協調聯動,是整體性能提升的關鍵.

· 隨著軟件定義網絡技術在負載均衡機制中的不斷普及應用,如何降低SDN 中央控制器處理信息的開銷和如何解決控制器間同步性問題變得十分重要.SDN 負載均衡的決策依托于網絡狀態采集,而現有的信息采集是通過節點主動發送狀態信息或者通過探測報文探測狀態信息.探測周期、報文格式和狀態信息不統一,增加了控制器的處理難度[101].另外,SDN 控制器的TCAM 內存有限,過多的探測信息不但增加了網絡流量負載,同時增加了控制器處理的延遲[45].在大規模數據中心中,單個控制器的計算能力有限,需要多個控制器協同[102,103].當多個控制器做決策時,控制器間的同步性也是一個重要的問題.

· 目前,RDMA[98,104-108]已經被廣泛部署到數據中心中,以提升傳輸效率.但一旦發生亂序,RDMA 的goback-to-zero[108]或go-back-to-N[108]機制需重傳全部數據包,使得RDMA 只能執行流級別的負載均衡,容易導致鏈路利用率降低.雖然文獻[66]在專用網卡使用類似于MPTCP 的多條并行子流進行傳輸,但是專用網卡增加了大規模部署的難度.因此,如何在基于RDMA 技術的數據中心中設計高效的負載均衡方法,也是值得關注的研究方向.