陳果，張濰豐

?

ELAB：基于端系統(tǒng)的新型擁塞感知負(fù)載均衡機(jī)制

陳果，張濰豐

（湖南大學(xué)信息科學(xué)與工程學(xué)院，湖南 長沙 410082）

良好的負(fù)載均衡機(jī)制是有效利用數(shù)據(jù)中心網(wǎng)絡(luò)帶寬的必備條件?，F(xiàn)有的等價多路徑路由（ECMP）的負(fù)載均衡方法由于負(fù)載均衡粒度過粗，且不具備對路徑擁塞狀態(tài)感知的能力，因此負(fù)載均衡效率較低。為解決此問題，近年來出現(xiàn)了一系列細(xì)粒度且具備擁塞感知能力的負(fù)載均衡研究工作。然而，這些研究或者需要修改交換機(jī)硬件以實(shí)時搜集網(wǎng)絡(luò)各部位的擁塞情況，難以部署；或者雖不需要修改交換機(jī)硬件，僅需對端系統(tǒng)的軟件進(jìn)行修改，但由于缺乏準(zhǔn)確的網(wǎng)絡(luò)擁塞信息而導(dǎo)致負(fù)載混合效果不佳。針對該問題，提出了一種實(shí)現(xiàn)于端系統(tǒng)上的軟件解決方案ELAB，該方案不需要對網(wǎng)絡(luò)中的硬件進(jìn)行修改，就可以達(dá)到良好的負(fù)載均衡效果。ELAB創(chuàng)造性地采用了基于可用帶寬的方式進(jìn)行流量負(fù)載均衡，相比于現(xiàn)有的基于端系統(tǒng)的方法，ELAB性能提升達(dá)20%。

數(shù)據(jù)中心網(wǎng)絡(luò)；負(fù)載均衡；基于邊緣；擁塞感知

1 引言

數(shù)據(jù)中心承載著人們?nèi)粘Ｉ钪兴玫降母鞣N各樣的互聯(lián)網(wǎng)服務(wù)，已成為當(dāng)前云計算時代最重要的基礎(chǔ)設(shè)施之一。為滿足日益增長的性能需求，數(shù)據(jù)中心網(wǎng)絡(luò)（DCN, data center network）作為連接數(shù)據(jù)中心內(nèi)所有計算和存儲資源的“交通樞紐”，需要提供越來越高的網(wǎng)絡(luò)帶寬以支持?jǐn)?shù)據(jù)中心內(nèi)部的大量通信需求[1]。因此，現(xiàn)有數(shù)據(jù)中心網(wǎng)絡(luò)多采用基于Clos結(jié)構(gòu)的密集網(wǎng)絡(luò)拓?fù)浼軜?gòu)[2]，通過大量的并行路徑，為數(shù)據(jù)中心提供極高的內(nèi)部網(wǎng)絡(luò)帶寬。

為了有效地利用整個網(wǎng)絡(luò)的帶寬，目前，在實(shí)際環(huán)境中多采用等價多路徑路由（ECMP, equal cost multi-path）[3]負(fù)載均衡機(jī)制將網(wǎng)絡(luò)流量分發(fā)到DCN內(nèi)部的多條并行路徑上進(jìn)行傳輸。在ECMP機(jī)制中，網(wǎng)絡(luò)中的每個交換機(jī)對途經(jīng)數(shù)據(jù)分組頭部的五元組（源IP、目的IP、源端口、目的端口、協(xié)議號）通過散列函數(shù)計算散列值，隨后根據(jù)散列值為數(shù)據(jù)分組選擇傳輸路徑，將不同的數(shù)據(jù)流散列至不同并行路徑上。然而，ECMP方法主要存在以下2個問題：1) 基于流（五元組）進(jìn)行負(fù)載均衡的粒度過粗，常常由于散列沖突導(dǎo)致網(wǎng)絡(luò)負(fù)載不均衡；2) 缺少對路徑擁塞狀態(tài)的感知，因此無法在網(wǎng)絡(luò)出現(xiàn)非對稱的情況下根據(jù)各路徑的狀況進(jìn)行流量分發(fā)。針對ECMP的這2個問題，近年來，出現(xiàn)了一系列工作研究如何為數(shù)據(jù)中心網(wǎng)絡(luò)提供更細(xì)粒度且具備擁塞感知能力的負(fù)載均衡機(jī)制[4-8]。

將負(fù)載均衡的單元切分為比數(shù)據(jù)流更細(xì)的粒度較為容易，有基于小流（flowlet）[9]、流信元（flowcell）[10]、數(shù)據(jù)分組[11]等多種方式，但提供高效的動態(tài)擁塞感知能力卻一直是研究難點(diǎn)。依據(jù)負(fù)載均衡機(jī)制實(shí)現(xiàn)擁塞感知的位置，可將現(xiàn)有研究方案分為2類：基于網(wǎng)絡(luò)的擁塞感知[4-6]和基于邊緣的擁塞感知[7-8]?；诰W(wǎng)絡(luò)的擁塞感知以CONGA（congestion aware balancing）[6]為代表。此類方案依賴于在網(wǎng)絡(luò)中交換機(jī)各端口上進(jìn)行實(shí)時的流量監(jiān)控，判斷路徑的擁塞程度。由于是對網(wǎng)絡(luò)內(nèi)部進(jìn)行檢測，基于網(wǎng)絡(luò)的擁塞感知可以動態(tài)地選擇擁塞程度較輕的路徑。然而，需要對現(xiàn)有交換機(jī)硬件做較大改動，因此難以在實(shí)際DCN環(huán)境中進(jìn)行部署?；谶吘壍膿砣兄訡love[7]和Hermes[8]為代表。這類方案實(shí)現(xiàn)在端系統(tǒng)上只需修改端系統(tǒng)軟件代碼即可完成，易于部署。然而，由于缺乏對網(wǎng)絡(luò)路徑實(shí)時狀況的準(zhǔn)確監(jiān)測信息，因此只能通過往返時延（RTT, round-trip time）或者顯示擁塞控制通知（ECN, explicit congestion notification）等信號來猜測最優(yōu)路徑，進(jìn)行啟發(fā)式選路。這些信號往往只能從側(cè)面反映路徑的狀態(tài)，而不能準(zhǔn)確地表明路徑的擁塞程度，尤其是在信號反饋時延較長時對路徑擁塞程度的判斷更加不準(zhǔn)確。因此，這類方案在復(fù)雜的真實(shí)網(wǎng)絡(luò)狀況下往往性能表現(xiàn)不佳。

由上述分析可知，目前缺乏一種易于部署的具備良好動態(tài)擁塞感知能力的負(fù)載均衡機(jī)制?；诖?，本文提出了一種基于邊緣的利用可用帶寬進(jìn)行擁塞感知的負(fù)載均衡機(jī)制（ELAB，edge-based load balancing according to path available bandwidth）。ELAB結(jié)合了已有基于網(wǎng)絡(luò)和基于邊緣2類方案的優(yōu)點(diǎn)，較好地解決了目前負(fù)載均衡擁塞感知的難點(diǎn)。ELAB實(shí)現(xiàn)在端系統(tǒng)上，不需要對現(xiàn)有網(wǎng)絡(luò)硬件做任何修改。ELAB接收端通過檢測數(shù)據(jù)分組到達(dá)速率，實(shí)時計算各條路徑的傳輸速度，從而輔助發(fā)送端判斷出各條路徑的可用帶寬。基于此，ELAB可以在不修改現(xiàn)有網(wǎng)絡(luò)硬件的情況下，在端系統(tǒng)上實(shí)現(xiàn)效果良好的擁塞感知負(fù)載均衡。

本文在網(wǎng)絡(luò)仿真平臺NS2上實(shí)現(xiàn)了ELAB，并將其與現(xiàn)有基于邊緣的擁塞感知方法Clove和Hermes進(jìn)行對比。實(shí)驗結(jié)果表明，在非對稱網(wǎng)絡(luò)情況下ELAB的吞吐率較Clove和Hermes提高了10%~20%。

2 相關(guān)工作

數(shù)據(jù)中心網(wǎng)絡(luò)的負(fù)載均衡是近年來相關(guān)領(lǐng)域的研究重點(diǎn)，出現(xiàn)了一系列的相關(guān)工作成果。依據(jù)是否具備全局的動態(tài)擁塞感知能力，負(fù)載均衡的方法可總結(jié)為2類：靜態(tài)負(fù)載均衡與動態(tài)擁塞感知的負(fù)載均衡。

靜態(tài)負(fù)載均衡具有代表性的方法研究主要有Presto[10]、DRB[11]和Packet Spray[12]。這類工作主要通過減小負(fù)載均衡調(diào)度的粒度（如以分組為單位）來實(shí)現(xiàn)負(fù)載均衡最優(yōu)的目標(biāo)，流量均衡過程中不對網(wǎng)絡(luò)狀態(tài)進(jìn)行感知。在對稱的網(wǎng)絡(luò)結(jié)構(gòu)中，靜態(tài)負(fù)載均衡方法能有效地提升負(fù)載均衡的效果，然而因為缺乏動態(tài)感知擁塞的能力，在網(wǎng)絡(luò)出現(xiàn)非對稱的情況下（如鏈路故障）表現(xiàn)不佳。

動態(tài)擁塞感知的負(fù)載均衡動態(tài)地監(jiān)測網(wǎng)絡(luò)的擁塞狀態(tài)，從而做出相應(yīng)的選路決策。該類型工作又可進(jìn)一步細(xì)分為以下2類。

1) 集中式擁塞感知的負(fù)載均衡，其典型代表有Hedera[13]、MicroTE[14]和Mahout[15]。這類工作通過集中式控制的方式，監(jiān)控網(wǎng)絡(luò)中各部位的負(fù)載信息以及數(shù)據(jù)流情況，隨后將數(shù)據(jù)流重新路由到負(fù)載低的路徑上。得益于全局的集中式控制，這類工作可以很好地均衡調(diào)度數(shù)據(jù)中心網(wǎng)絡(luò)中的長流。但其主要的缺陷在于集中式的監(jiān)控和調(diào)度時延太長。具體來說，集中式方法從感知到網(wǎng)絡(luò)路徑狀態(tài)的變化，到做出集中式調(diào)度，往往需要經(jīng)歷數(shù)十秒甚至更長的時延[13]，難以適應(yīng)突發(fā)短流的負(fù)載均衡需求（微秒級）。而本文提出的ELAB機(jī)制能在數(shù)十微秒內(nèi)感知路徑擁塞并做出相應(yīng)的負(fù)載均衡調(diào)整。

2) 分布式擁塞感知的負(fù)載均衡，除前文提到的CONGA[6]、Clove[7]、Hermes[8]外，具有代表性的工作還有Flowtune[16]、DRILL[5]等。分布式的方式大大降低了這類工作獲取網(wǎng)絡(luò)擁塞情況的時延，使其可以更好地應(yīng)對網(wǎng)絡(luò)擁塞變化。但正如前文所述，這類工作或者需要修改交換機(jī)硬件以實(shí)時搜集網(wǎng)絡(luò)各部位的擁塞情況，難以部署，如CONGA；或者雖僅需對端系統(tǒng)的軟件進(jìn)行修改，但無法達(dá)到良好的負(fù)載均衡效果，如Clove和Hermes。通過本文實(shí)驗可見，現(xiàn)有最新的基于端系統(tǒng)的負(fù)載均衡機(jī)制的性能皆遠(yuǎn)低于理論最優(yōu)性能。而本文提出的ELAB機(jī)制在現(xiàn)有方法的基礎(chǔ)上顯著地提升了性能，將網(wǎng)絡(luò)平均流完成時間優(yōu)化了10%~20%。

3 研究思路

本節(jié)首先簡單介紹現(xiàn)有基于邊緣的負(fù)載均衡機(jī)制如何進(jìn)行擁塞感知，通過一個簡單的例子論述現(xiàn)有機(jī)制選路性能不佳的原因；然后，分析基于可用帶寬分配的負(fù)載均衡機(jī)制能很好地解決該問題，從而引出ELAB的設(shè)計出發(fā)點(diǎn)；最后，討論如何在端系統(tǒng)中探測可用帶寬，介紹ELAB的設(shè)計思路。

3.1 現(xiàn)有基于邊緣的負(fù)載均衡機(jī)制

現(xiàn)有基于邊緣的具備動態(tài)擁塞感知能力的負(fù)載均衡機(jī)制主要有2個代表性的方法：Clove和Hermes。與基于網(wǎng)絡(luò)的方法不同，基于邊緣的方法無法準(zhǔn)確、實(shí)時地獲取網(wǎng)絡(luò)中各路徑的擁塞程度，因此多采用RTT或ECN等信號來推測路徑的擁塞程度。

下面通過一個簡單的例子，說明現(xiàn)有利用RTT或ECN信號的方法無法做出最佳的選路決策?？紤]如圖1所示情形（以下簡稱簡單情形），網(wǎng)絡(luò)中存在2條并行路徑，其中路徑2的帶寬為6 Gbit/s，路徑1因為發(fā)生故障帶寬降為3 Gbit/s。存在一個TCP流經(jīng)過這2條并行路徑發(fā)送數(shù)據(jù)。為了考察網(wǎng)絡(luò)負(fù)載均衡的性能，假設(shè)該流入口和出口帶寬無限大，從而排除輸入/輸出端口的影響，使帶寬瓶頸出現(xiàn)在網(wǎng)絡(luò)中。在仿真環(huán)境中，流量產(chǎn)生端和接收端到葉子交換機(jī)1/葉子交換機(jī)2的帶寬設(shè)置為10 Gbit/s，該網(wǎng)絡(luò)中每一跳的時延根據(jù)實(shí)際數(shù)據(jù)中心環(huán)境設(shè)置為20 μs，端到端時延為160 μs，葉子交換機(jī)至骨干交換機(jī)的鏈路出口隊列長度設(shè)置為1.8 MB（3倍帶寬時延積），ECN閾值設(shè)置為600 KB（1倍帶寬時延積）。圖中spine表示骨干交換機(jī)，leaf表示葉子交換機(jī)。

圖1 簡單情形下的網(wǎng)絡(luò)負(fù)載均衡

對圖1所示簡單情形網(wǎng)絡(luò)采用不同的負(fù)載均衡方案進(jìn)行仿真，不同方案下網(wǎng)絡(luò)帶寬利用率如圖2所示。

圖2 簡單情形下各負(fù)載均衡機(jī)制的網(wǎng)絡(luò)帶寬利用率對比

理論上最優(yōu)的負(fù)載均衡情況下，該TCP流應(yīng)將網(wǎng)絡(luò)中所有并行路徑完全利用，利用率達(dá)到100%。然而，Clove和Hermes這2種方法都遠(yuǎn)沒有達(dá)到最優(yōu)的網(wǎng)絡(luò)利用率，具體原因如下。

圖3 簡單情形下Clove中2條路徑的流速比（路徑1流速:路徑2流速）

2) 在Hermes中，初始階段2條路徑的RTT都很?。o排隊時延），也沒有ECN，因此流量以1:1分到2條路徑上。當(dāng)TCP流速度增至6 Gbit/s，即2條路徑速度皆為3 Gbit/s時，路徑1的RTT開始上升并收到ECN，被判斷為壞路。此時TCP流收到ECN降速并重新進(jìn)入線性增速階段。Hermes會將后續(xù)的流量全部分發(fā)至路徑2。直至TCP流吞吐量達(dá)到6 Gbit/s時，路徑2也會出現(xiàn)ECN且RTT上升，被判斷為壞路，此時TCP流收到ECN再次降速。流量在2條路徑之間振蕩，而無法保持以最優(yōu)的比例1:2同時將2條并行路徑完全利用。圖4展示了Hermes對2條路徑分配的流量速度比例（路徑1流速:路徑2流速）。如圖4所示，雖然Hermes分配速度比例的振蕩中心在0.5附近，但流量一直在2條路徑之間大幅切換。這會導(dǎo)致某條路徑被用滿時TCP流收到ECN降速，而此時另一條路徑負(fù)載還比較輕。因此，Hermes也無法同時完全利用2條并行路徑，達(dá)到最優(yōu)的9 Gbit/s吞吐量。

圖4 簡單情形下Hermes中2條路徑流速比（路徑1流速:路徑2流速）

3.2 基于可用帶寬的負(fù)載均衡

由上述實(shí)驗分析可知，現(xiàn)有基于邊緣的方法無法做出最優(yōu)負(fù)載均衡決策，其原因在于，僅通過RTT或ECN信號無法準(zhǔn)確地反映一條路徑的擁塞程度。具體來說，一條路徑只有被完全利用出現(xiàn)擁塞時才有可能出現(xiàn)ECN或RTT上升，此時再根據(jù)相關(guān)信號來選擇其他路徑為時已晚，TCP已經(jīng)出現(xiàn)降速，因此無法達(dá)到最優(yōu)吞吐量。此外，即使Clove刻意隱藏ECN信號，雖可避免在探測到某一條路徑擁塞時立即出現(xiàn)TCP降速，但仍無法知道其他路徑當(dāng)前的擁塞程度，因此同樣不能以最優(yōu)的比例進(jìn)行流量分配，后續(xù)依然無法使所有路徑同時被完全利用。

若想使網(wǎng)絡(luò)中數(shù)據(jù)流的吞吐量最大，最優(yōu)的負(fù)載均衡決策需要讓網(wǎng)絡(luò)中所有并行鏈路利用率相等（即同時完全利用）。要實(shí)現(xiàn)這一目標(biāo)，可以通過基于各條路徑當(dāng)前的可用帶寬比例進(jìn)行流量分配。

同樣地，考慮圖1所示的簡單情形。如果嚴(yán)格按照實(shí)時可用帶寬的比例進(jìn)行流量分配，由圖2可知，采用基于帶寬的方案TCP流的吞吐量可以達(dá)到最優(yōu)的9 Gbit/s，達(dá)到99.8%的網(wǎng)絡(luò)利用率。

因此，基于以上觀察，本文所提出的方案ELAB采用基于可用帶寬分配流量的負(fù)載均衡原則。

3.3 在端系統(tǒng)中探測可用帶寬

現(xiàn)有的商用網(wǎng)絡(luò)設(shè)備不支持直接在網(wǎng)絡(luò)中監(jiān)測各路徑的可用帶寬。若想設(shè)計一種易于部署、不需要對現(xiàn)有網(wǎng)絡(luò)硬件進(jìn)行修改的負(fù)載均衡機(jī)制，需要在端系統(tǒng)上對網(wǎng)絡(luò)路徑的可用帶寬進(jìn)行探測，這也是ELAB的設(shè)計難點(diǎn)所在。

4 ELAB詳細(xì)設(shè)計

本節(jié)將介紹ELAB機(jī)制的詳細(xì)設(shè)計，描述ELAB如何在邊緣上利用可用帶寬進(jìn)行擁塞感知的負(fù)載均衡。

4.1 設(shè)計綜述

ELAB算法實(shí)現(xiàn)在端系統(tǒng)上，不需要對現(xiàn)有網(wǎng)絡(luò)硬件進(jìn)行修改，其結(jié)構(gòu)如圖5所示。ELAB作為中間層，實(shí)現(xiàn)在端系統(tǒng)協(xié)議棧中的網(wǎng)絡(luò)層和傳輸層之間，通過隧道封裝/解封裝的方式在端系統(tǒng)上實(shí)現(xiàn)負(fù)載均衡選路。ELAB對上層傳輸層完全保持透明，不需要對現(xiàn)有傳輸層協(xié)議做任何修改。

在發(fā)送端，ELAB將傳輸層發(fā)來的數(shù)據(jù)分組進(jìn)行隧道封裝，加入一個傳輸層隧道分組頭（L4 tunnel header）用于選路。因為現(xiàn)有數(shù)據(jù)中心網(wǎng)絡(luò)硬件皆采用ECMP的選路方式（即對數(shù)據(jù)分組頭的五元組進(jìn)行散列選路），所以在不改變已有網(wǎng)絡(luò)硬件的前提下，可以通過改變隧道頭中五元組的方式來在端系統(tǒng)上進(jìn)行主動選路。本文中每個不同的隧道五元組在被稱為一條虛擬路徑（VP, virtual path）。如前文所述，ELAB為每一對通信節(jié)點(diǎn)之間維護(hù)一個VP狀態(tài)表，不斷監(jiān)測各條VP上的可用帶寬，從而進(jìn)行擁塞感知的動態(tài)選路。

在接收端，ELAB將接收到的數(shù)據(jù)分組去除隧道頭，將數(shù)據(jù)分組還原后交給上層協(xié)議處理。同時，它也為每一對通信節(jié)點(diǎn)之間維護(hù)一個VP狀態(tài)反饋表。該表的功能是記錄每個虛擬路徑上最近一段時間內(nèi)接收到的數(shù)據(jù)分組數(shù)量，并在適當(dāng)時將這個信息送至發(fā)送端以計算路徑擁塞狀態(tài)。

圖5 ELAB總體結(jié)構(gòu)

本文在沒有特殊說明的情況下，所有的討論均為一對通信節(jié)點(diǎn)之間。通信節(jié)點(diǎn)對可以通過源/目的IP地址來進(jìn)行標(biāo)識。所有的ELAB節(jié)點(diǎn)間通信為雙向通信，即每一個節(jié)點(diǎn)既是ELAB發(fā)送端，也是ELAB接收端。

4.2 ELAB數(shù)據(jù)分組頭部格式

ELAB數(shù)據(jù)分組結(jié)構(gòu)如圖6(a)所示。ELAB在原來數(shù)據(jù)分組的網(wǎng)絡(luò)層頭部和傳輸層頭部之間加入了一個傳輸層隧道頭（L4 tunnel header）。此外，ELAB在發(fā)送端和接收端之間還需傳輸一些必要的信息以計算路徑的擁塞狀態(tài)，因此，ELAB在傳輸層隧道分組頭之后插入了一個自定義的ELAB信息頭（ELAB info header），具體分組格式如圖6(b)所示。

圖6 ELAB數(shù)據(jù)分組結(jié)構(gòu)及ELAB信息頭格式

傳輸層隧道頭在保持現(xiàn)有網(wǎng)絡(luò)ECMP路由不變的情況下，在端系統(tǒng)上選擇不同的網(wǎng)絡(luò)傳輸路徑?，F(xiàn)有數(shù)據(jù)中心網(wǎng)絡(luò)通常采用的傳輸層隧道格式有VXLAN[17]和SSTP[18]等。本文為描述簡單，ELAB采用了分組頭長度最小的UDP隧道頭。具體地，在原有數(shù)據(jù)分組的三層分組頭和四層分組頭之間插入一個新UDP頭部，其內(nèi)容如下：1) 用一個特殊的UDP目的端口號來標(biāo)識該流量是ELAB產(chǎn)生的流量；2) 將UDP頭中不同的源端口號作為不同VP的標(biāo)識。因此，ELAB通過對不同數(shù)據(jù)分組設(shè)置不同的UDP隧道頭中的源端口號，即可實(shí)現(xiàn)主動選路。

ELAB信息頭用于在ELAB發(fā)送端和接收端之間傳輸計算擁塞狀態(tài)所需的必要信息。此處先僅對各字段的含義做簡要介紹，后文將詳細(xì)介紹在發(fā)送端和接收端如何設(shè)置這些字段以及如何利用這些字段計算各路徑的擁塞狀態(tài)。ELAB信息頭具體包括如下字段。

1) VP_ID（16位）和 VP_RCnt（16位）。用于接收端反饋某條虛擬路徑在最近一段時間內(nèi)接收到的數(shù)據(jù)分組數(shù)量。VP_ID表示當(dāng)前所反饋的VP的標(biāo)識。VP_RCnt為VP狀態(tài)反饋表中該VP接收的數(shù)據(jù)分組數(shù)目。

2) Reserved（14位）。保留字段，暫未使用。

3) B（1位）和E（1位）。這2個標(biāo)志位皆由ELAB接收端反饋時設(shè)置。E位表示最近在該虛擬路徑上是否接收到被ECN標(biāo)記的數(shù)據(jù)分組。B位表示該數(shù)據(jù)分組中是否攜帶有路徑探測速率的反饋信息。

4) Burst_ID（16位）。由發(fā)送端設(shè)置。若該數(shù)據(jù)分組為路徑速率探測分組，則發(fā)送端將該字段設(shè)置為該探測分組的探測序號。

5) VP_RBurst_Rate（32位）。可選字段，由接收端反饋時設(shè)置。當(dāng)B位為1時，該字段表示該路徑的探測速率；B位為0時，無該字段。

4.3 虛擬路徑空間的選取

本節(jié)簡單介紹ELAB對虛擬路徑空間的選取。前文提到利用傳輸層隧道頭中的源端口號作為虛擬路徑的標(biāo)識。然而，不同的虛擬路徑可能被底層網(wǎng)絡(luò)的ECMP路由散列到同一條物理路徑之上。如果盲目地選擇一段源端口號范圍作為傳輸中使用的虛擬路徑空間，則既有可能無法覆蓋網(wǎng)絡(luò)中所有的并行路徑，也有可能導(dǎo)致大部分虛擬路徑對應(yīng)的是少數(shù)相同的物理路徑，這2種情況都會嚴(yán)重地影響選路效率。針對此問題，ELAB采用了經(jīng)典Paris traceroute機(jī)制[19]，在初始化階段對虛擬路徑進(jìn)行探測，從而選出對應(yīng)不同物理路徑的虛擬路徑。

在新通信節(jié)點(diǎn)對之間產(chǎn)生流量時，ELAB會對該通信節(jié)點(diǎn)對之間的虛擬路徑空間進(jìn)行初始化。初始化時，隨機(jī)產(chǎn)生源端口號，向目的地址發(fā)送一組帶有不同源端口號的traceroute。借助這些traceroute的反饋信息，即可知道不同源端口號經(jīng)過的具體路徑。為了完善虛擬路徑表，需要隨機(jī)產(chǎn)生多組源端口號不同的探測分組，盡可能地將網(wǎng)絡(luò)中所有的并行路徑探測出來。當(dāng)反饋回的物理路徑信息與已完成探測的虛擬路徑不一致時，即被認(rèn)為是新的并行物理路徑，加入虛擬路徑空間中。

值得注意的是，以上虛擬路徑空間的初始化探測在新通信對之間第一次出現(xiàn)流量時進(jìn)行，后續(xù)過程中僅需以極低的頻率周期性地探測即可（為應(yīng)對網(wǎng)絡(luò)拓?fù)渥兓?，引入的網(wǎng)絡(luò)開銷很低。

4.4 基于可用帶寬的選路

本節(jié)將具體介紹ELAB如何根據(jù)可用帶寬動態(tài)地選路。

4.4.1 選路函數(shù)

在ELAB發(fā)送端，為每一條虛擬路徑維護(hù)上限帶寬、實(shí)際發(fā)送速度以及可用帶寬幾個狀態(tài)，分別如下。

具體做法為在每次有數(shù)據(jù)分組從發(fā)送端發(fā)出時，ELAB都會以上述比例輪詢地從各條VP中選擇一條，將數(shù)據(jù)分組從該VP發(fā)送出去。

4.4.2 路徑發(fā)送速度R的探測

ELAB發(fā)送端依賴于接收端的配合來實(shí)時探測每條路徑的實(shí)時發(fā)送速度。ELAB接收端為每一對通信節(jié)點(diǎn)之間維護(hù)一個VP狀態(tài)反饋表。該表的功能是記錄每個虛擬路徑上最近一段時間內(nèi)接收到的數(shù)據(jù)分組的數(shù)量。具體來說，ELAB接收端每收到一個數(shù)據(jù)分組時，會將其對應(yīng)的VP接收數(shù)量加1；而每當(dāng)接收端有數(shù)據(jù)分組發(fā)回發(fā)送端時，ELAB會以輪詢的方式依次將VP狀態(tài)反饋表中各條VP收到的數(shù)據(jù)分組數(shù)量反饋給發(fā)送端，同時將該輪反饋過的VP接收到的數(shù)據(jù)分組數(shù)量清零。

4.4.3 路徑上限帶寬B的探測

如2.3節(jié)所述，網(wǎng)絡(luò)可能出現(xiàn)故障或者有其他流競爭，所以需要動態(tài)地對VP的上限帶寬進(jìn)行探測。發(fā)送端對于第條VP的上限帶寬B的更新有如下3種方式。

1) 初始化。B在初始階段被初始化為鏈路的物理帶寬，利用該值初始化能夠減少選路穩(wěn)定的時間。鏈路的物理帶寬可由網(wǎng)絡(luò)管理員手動輸入。

2) ECN重置。當(dāng)一條個路徑收到ECN標(biāo)記，則說明該路徑當(dāng)前處于滿負(fù)載的狀態(tài)。基于這一點(diǎn)，可以根據(jù)當(dāng)前該路徑上的實(shí)際發(fā)送速率來估計其上限帶寬。具體地，當(dāng)收到接收端發(fā)回的數(shù)據(jù)分組中E字段被置位時，則將該路徑的上限帶寬B更新為R。

5 實(shí)驗評價

5.1 實(shí)驗環(huán)境介紹

在NS2[20]網(wǎng)絡(luò)仿真平臺上實(shí)現(xiàn)了ELAB機(jī)制。為了對比性能，在NS2中還實(shí)現(xiàn)了目前已有的2個基于邊緣的動態(tài)擁塞感知算法—Clove和Hermes。因為CONGA等方法需要修改網(wǎng)絡(luò)硬件，無法滿足本文的需求，所以故不做對比。

5.2 專門實(shí)驗深入分析ELAB

5.2.1 簡單非對稱場景

第2節(jié)中對ELAB在圖1中所示的場景進(jìn)行評價，從圖2所示的仿真結(jié)果可以看到，ELAB的網(wǎng)絡(luò)帶寬利用率達(dá)到了87%。

圖7展示了ELAB對2條路徑路所分配的流量速度比例（路徑1流速∶路徑2流速）。可以看出，可見ELAB的算法能很好地模擬出基于可用帶寬的分配。

圖7 簡單情形下ELAB中2條路徑路所分配的流速比（路徑1流速:路徑2流速）

5.2.2 非對稱網(wǎng)絡(luò)下與其他流競爭的場景

除上述簡單非對稱場景外，本文還進(jìn)一步設(shè)計了非對稱網(wǎng)絡(luò)下與其他流競爭的場景（以下簡稱競爭場景），來評估ELAB的性能。實(shí)驗網(wǎng)絡(luò)如圖8所示。

圖8 非對稱網(wǎng)絡(luò)下與其他流競爭的場景

圖9展示了競爭場景下各方法的平均流完成時間（FCT, flow completion time）對比。圖中各方法的流完成時間均對基線方法ECMP進(jìn)行了歸一化?？梢钥吹?，在此場景下，ELAB的性能依然最佳，相比于ECMP、Clove和Hermes分別將流完成時間縮短了31%、24%、3%。

圖9 競爭場景中各方法的平均流完成時間對比

圖10展現(xiàn)了競爭場景下各方法中2條流1和2各自的分路比例隨時間的變化。其中比例計算方式皆為經(jīng)spine1發(fā)送的流量:經(jīng)spine2發(fā)送的流量。從圖10可知，ELAB中2主要將流量分配至經(jīng)spine2的好路徑，而避開了經(jīng)spine1的故障路徑；同時1也相應(yīng)地將主要流量分配至經(jīng)spine1的路徑，從而避免了與2在spine2上競爭。因此，ELAB能在此情景下取得較好的平均流完成時間。相反，不論是Clove還是Hermes，從圖10都能看出對于2條路徑的分流比例并不合理。其中2還會頻繁地將流量發(fā)送至故障路徑spine1上，因此流完成時間不佳。

5.3 大規(guī)模仿真實(shí)驗

本文構(gòu)造了一個大規(guī)模leaf-spine拓?fù)渚W(wǎng)絡(luò)。如圖11所示，在該拓?fù)浣Y(jié)構(gòu)中有4個核心層交換機(jī)節(jié)點(diǎn)和4個接入層交換機(jī)節(jié)點(diǎn)。每個核心層交換機(jī)與所有的接入層交換機(jī)相連，組成了一個全鏈接的網(wǎng)絡(luò)。每個接入層交換機(jī)與16臺底部主機(jī)相連，整個網(wǎng)絡(luò)共有64臺主機(jī)。交換機(jī)之間的鏈路帶寬為40 Gbit/s，交換機(jī)與主機(jī)之間的鏈路帶寬為10 Gbit/s。交換機(jī)的緩沖隊列長度設(shè)置為3 MB，并且ECN閾值設(shè)置為緩存隊列長度的30%。網(wǎng)絡(luò)中每一跳的時延設(shè)置為20μs。本文將利用這種拓?fù)浣Y(jié)構(gòu)分別評估各方法在對稱網(wǎng)絡(luò)和非對稱網(wǎng)絡(luò)（網(wǎng)絡(luò)中某些鏈路出現(xiàn)故障）下的負(fù)載均衡性能。

圖10 競爭場景中各方法的路徑流速比隨時間的變化

圖11 大規(guī)模網(wǎng)絡(luò)仿真

根據(jù)真實(shí)數(shù)據(jù)中心的網(wǎng)頁搜索（Web-search）[8]流量記錄，在該網(wǎng)絡(luò)拓?fù)渲猩闪髁俊Ｓ捎诒疚难芯康氖秦?fù)載平衡對網(wǎng)絡(luò)性能的影響，因此以圖11左半部分網(wǎng)絡(luò)的32臺主機(jī)為每個流量的源主機(jī)，在圖11右半部分網(wǎng)絡(luò)的不同的位置隨機(jī)選擇每個流量的目的主機(jī)，從而使所有流量都經(jīng)過網(wǎng)絡(luò)。通過調(diào)整節(jié)點(diǎn)生成流量的間隔長度來達(dá)到不同的網(wǎng)絡(luò)負(fù)載強(qiáng)度。遵循先前工作的慣例，本文使用FCT作為主要的性能衡量指標(biāo)。

5.3.1 對稱網(wǎng)絡(luò)

圖12展示了大規(guī)模網(wǎng)絡(luò)情形下各機(jī)制的平均流完成時間（對ECMP進(jìn)行歸一化）。從圖12可知，無論在輕度負(fù)載還是重度負(fù)載情況下，ELAB、Clove和Hermes表現(xiàn)都類似，稍微優(yōu)于ECMP。ELAB整體較Clove、Hermes有1%~3%的優(yōu)勢。

圖12 對稱網(wǎng)絡(luò)中，不同負(fù)載下各機(jī)制的平均流完成時間（大規(guī)模仿真）

5.3.2 非對稱網(wǎng)絡(luò)

圖13展示了該情形下各機(jī)制的平均流完成時間（對ECMP進(jìn)行歸一化）。從圖13可知，在網(wǎng)絡(luò)負(fù)載較輕時，ELAB、Clove和Hermes都表現(xiàn)類似，優(yōu)于ECMP。當(dāng)負(fù)載高于0.5時，ELAB開始呈現(xiàn)出明顯的優(yōu)勢，平均流完成時間較Clove和Hermes分別降低了7%~22%和17%~26%。

圖13 非對稱網(wǎng)絡(luò)中，不同負(fù)載下各機(jī)制的平均流完成時間（大規(guī)模仿真）

6 結(jié)束語

人們對網(wǎng)絡(luò)帶寬需求的日益增高，也對數(shù)據(jù)中心網(wǎng)路的負(fù)載均衡機(jī)制提出了更高的要求。當(dāng)前生產(chǎn)環(huán)境中采用的ECMP負(fù)載均衡機(jī)制選路粒度粗，缺乏動態(tài)擁塞感知能力，性能不佳?，F(xiàn)有其他細(xì)粒度且具備動態(tài)擁塞感知能力的方案，或需要對網(wǎng)絡(luò)硬件進(jìn)行修改，難以部署；或僅需修改端系統(tǒng)軟件，但擁塞感知不準(zhǔn)，性能不佳。本文提出的ELAB方案是一種基于邊緣的利用可用帶寬進(jìn)行擁塞感知的負(fù)載均衡機(jī)制，既不需要對網(wǎng)絡(luò)硬件進(jìn)行改動，又能準(zhǔn)確感知擁塞實(shí)現(xiàn)良好的負(fù)載均衡效果。實(shí)驗結(jié)果表明，在非對稱網(wǎng)絡(luò)情形下，ELAB能將現(xiàn)有方法的吞吐量提升10%以上。ELAB利用可用帶寬進(jìn)行流量分配的思路，解決了現(xiàn)有方法的難點(diǎn)，為數(shù)據(jù)中心網(wǎng)絡(luò)的負(fù)載均衡機(jī)制提供了一種新的思路。

[1] BENSON T, AKELLA A, MALTZ D A. Network traffic characteristics of data centers in the wild[C]//The 10th ACM SIGCOMM Conference on Internet Measurement. 2010: 267-280.

[2] SINGH A, ONG J, AGARWAL A. Jupiter rising: a decade of clos topologies and centralized control in google’s datacenter network[J]. ACM SIGCOMM Computer Communication Review, 2015, 45(4): 183-197.

[3] HOPPS C E. Analysis of an equal-cost multi-path algorithm[R]. Request for Comments 2992, 2000.

[4] KATTA N, HIRA M, KIM C. Hula: scalable load balancing using programmable data planes[C]//The Symposium on SDN Research. 2016: 10.

[5] GHORBANI S, GODFREY B, GANJALI Y. Micro load balancing in data centers with DRILL[C]//The 14th ACM Workshop on Hot Topics in Networks. ACM, 2015: 17.

[6] ALIZADEH M, EDSALL T, DHARMAPURIKAR S. CONGA: distributed congestion-aware load balancing for datacenters[J]. ACM SIGCOMM Computer Communication Review, 2014, 44(4): 503-514.

[7] KATTA N, HIRA M, GHAG A. CLOVE: how I learned to stop worrying about the core and love the edge[C]//The 15th ACM Workshop on Hot Topics in Networks. 2016: 155-161.

[8] ZHANG H, ZHANG J, BAI W. Resilient datacenter load balancing in the wild[C]//The Conference of the ACM Special Interest Group on Data Communication. 2017: 253-266.

[9] VANINI E, PAN R, ALIZADEH M. Let it flow: resilient asymmetric load balancing with flowlet switching[C]//USENIX Symposium on Networked Systems Design and Implementation. 2017: 407-420.

[10] HE K, ROZNER E, AGARWAL K, et al. Presto: edge-based load balancing for fast datacenter networks[J]. ACM SIGCOMM Computer Communication Review, 2015, 45(4): 465-478.

[11] CAO J, XIA R, YANG P. Per-packet load-balanced, low-latency routing for clos-based data center networks[C]//The 9th ACM Conference on Emerging Networking Experiments and Technologies. 2013: 49-60.

[12] DITTMANN G, HERKERSDORF A. Network processor load balancing for high-speed links[C]//The 2002 International Symposium on Performance Evaluation of Computer and Telecommunication Systems. 2002, 735.

[13] AL-FARES M, RADHAKRISHNAN S, RAGHAVAN B, et al. Hedera: Dynamic flow scheduling for data center networks[J]. USENIX Symposium on Networked Systems Design and Implementation, 2010, 10: 19.

[14] BENSON T, ANAND A, AKELLA A. MicroTE: fine grained traffic engineering for data centers[C]//The 17th Conference on emerging Networking Experiments and Technologies. 2011: 8.

[15] CURTIS A R, KIM W, YALAGANDULA P. Mahout: low-overhead datacenter traffic management using end-host-based elephant detection[C]//INFOCOM. 2011: 1629-1637.

[16] PERRY J, BALAKRISHNAN H, SHAH D. Flowtune: flowlet control for datacenter networks[C]//USENIX Symposium on Networked Systems Design and Implementation. 2017: 421-435.

[17] MAHALINGAM M, DUTT D, DUDA K. Virtual extensible local area network (VXLAN): a framework for overlaying virtualized layer 2 networks over layer 3 networks[R]. Request for Comments, 7348,

[18] KIM Y J, KOLESNIKOV V, KIM H. SSTP: a scalable and secure transport protocol for smart grid data collection[C]//2011 IEEE International Conference on Smart Grid Communications (SmartGridComm). 2011: 161-166.

[19] AUGUSTIN B, CUVELLIER X, ORGOGOZO B, et al. Avoiding traceroute anomalies with Paris traceroute[C]//The 6th ACM SIGCOMM conference on Internet measurement. 2006: 153-158.

[20] ISSARIYAKUL T, HOSSAIN E. Introduction to network simulator NS2[M]. Springer Science & Business Media, 2011.

ELAB: end-host-based congestion aware load balancing for data center network

CHEN Guo, ZHANG Weifeng

College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082, China

A good load balance mechanism is the key to effectively use the network of the data center network. In current production data center, ECMP is the de facto load balancing scheme. However, it has two drawbacks. 1) the load balance unit is too coarse-grained, 2) it’s not congestion aware. To solve these problems, several fine-grained and congestion-aware load balancing works have emerged in recent years. These works either need to modify the switch hardware to collect congestion in various parts of the network in real time, and it is difficult to deploy; or only need to modify the end system, but the inaccurate sense of congestion cannot achieve a good load balancing effect. A novel edge-based load balancing scheme ELAB was proposed, which addresses above existing problems and improves the network performance up to 20%.

data center network, load balancing, edge-based, congestion aware

TP393.1

A

10.11959/j.issn.1000?436x.2019054

2018?06?25；

2018?08?24

陳果（1989? ），男，湖南長沙人，博士，湖南大學(xué)副教授，主要研究方向為計算機(jī)網(wǎng)絡(luò)系統(tǒng)、數(shù)據(jù)中心網(wǎng)絡(luò)。

張濰豐（1997? ），男，廣東新會人，主要研究方向為計算機(jī)網(wǎng)絡(luò)系統(tǒng)、計算機(jī)系統(tǒng)結(jié)構(gòu)。