陳果，張濰豐

?

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

陳果，張濰豐

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

良好的負(fù)載均衡機(jī)制是有效利用數(shù)據(jù)中心網(wǎng)絡(luò)帶寬的必備條件。現(xiàn)有的等價(jià)多路徑路由（ECMP）的負(fù)載均衡方法由于負(fù)載均衡粒度過(guò)粗，且不具備對(duì)路徑擁塞狀態(tài)感知的能力，因此負(fù)載均衡效率較低。為解決此問(wèn)題，近年來(lái)出現(xiàn)了一系列細(xì)粒度且具備擁塞感知能力的負(fù)載均衡研究工作。然而，這些研究或者需要修改交換機(jī)硬件以實(shí)時(shí)搜集網(wǎng)絡(luò)各部位的擁塞情況，難以部署；或者雖不需要修改交換機(jī)硬件，僅需對(duì)端系統(tǒng)的軟件進(jìn)行修改，但由于缺乏準(zhǔn)確的網(wǎng)絡(luò)擁塞信息而導(dǎo)致負(fù)載混合效果不佳。針對(duì)該問(wèn)題，提出了一種實(shí)現(xiàn)于端系統(tǒng)上的軟件解決方案ELAB，該方案不需要對(duì)網(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)前云計(jì)算時(shí)代最重要的基礎(chǔ)設(shè)施之一。為滿足日益增長(zhǎng)的性能需求，數(shù)據(jù)中心網(wǎng)絡(luò)（DCN, data center network）作為連接數(shù)據(jù)中心內(nèi)所有計(jì)算和存儲(chǔ)資源的“交通樞紐”，需要提供越來(lá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]，通過(guò)大量的并行路徑，為數(shù)據(jù)中心提供極高的內(nèi)部網(wǎng)絡(luò)帶寬。

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

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

由上述分析可知，目前缺乏一種易于部署的具備良好動(dòng)態(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)上，不需要對(duì)現(xiàn)有網(wǎng)絡(luò)硬件做任何修改。ELAB接收端通過(guò)檢測(cè)數(shù)據(jù)分組到達(dá)速率，實(shí)時(shí)計(jì)算各條路徑的傳輸速度，從而輔助發(fā)送端判斷出各條路徑的可用帶寬?；诖?，ELAB可以在不修改現(xiàn)有網(wǎng)絡(luò)硬件的情況下，在端系統(tǒng)上實(shí)現(xiàn)效果良好的擁塞感知負(fù)載均衡。

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

2 相關(guān)工作

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

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

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

1) 集中式擁塞感知的負(fù)載均衡，其典型代表有Hedera[13]、MicroTE[14]和Mahout[15]。這類工作通過(guò)集中式控制的方式，監(jiān)控網(wǎng)絡(luò)中各部位的負(fù)載信息以及數(shù)據(jù)流情況，隨后將數(shù)據(jù)流重新路由到負(fù)載低的路徑上。得益于全局的集中式控制，這類工作可以很好地均衡調(diào)度數(shù)據(jù)中心網(wǎng)絡(luò)中的長(zhǎng)流。但其主要的缺陷在于集中式的監(jiān)控和調(diào)度時(shí)延太長(zhǎng)。具體來(lái)說(shuō)，集中式方法從感知到網(wǎng)絡(luò)路徑狀態(tài)的變化，到做出集中式調(diào)度，往往需要經(jīng)歷數(shù)十秒甚至更長(zhǎng)的時(shí)延[13]，難以適應(yīng)突發(fā)短流的負(fù)載均衡需求（微秒級(jí)）。而本文提出的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ò)擁塞情況的時(shí)延，使其可以更好地應(yīng)對(duì)網(wǎng)絡(luò)擁塞變化。但正如前文所述，這類工作或者需要修改交換機(jī)硬件以實(shí)時(shí)搜集網(wǎng)絡(luò)各部位的擁塞情況，難以部署，如CONGA；或者雖僅需對(duì)端系統(tǒng)的軟件進(jìn)行修改，但無(wú)法達(dá)到良好的負(fù)載均衡效果，如Clove和Hermes。通過(guò)本文實(shí)驗(yàn)可見(jiàn)，現(xiàn)有最新的基于端系統(tǒng)的負(fù)載均衡機(jī)制的性能皆遠(yuǎn)低于理論最優(yōu)性能。而本文提出的ELAB機(jī)制在現(xiàn)有方法的基礎(chǔ)上顯著地提升了性能，將網(wǎng)絡(luò)平均流完成時(shí)間優(yōu)化了10%~20%。

3 研究思路

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1 設(shè)計(jì)綜述

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

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

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

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

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

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

ELAB數(shù)據(jù)分組結(jié)構(gòu)如圖6(a)所示。ELAB在原來(lái)數(shù)據(jù)分組的網(wǎng)絡(luò)層頭部和傳輸層頭部之間加入了一個(gè)傳輸層隧道頭（L4 tunnel header）。此外，ELAB在發(fā)送端和接收端之間還需傳輸一些必要的信息以計(jì)算路徑的擁塞狀態(tài)，因此，ELAB在傳輸層隧道分組頭之后插入了一個(gè)自定義的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]等。本文為描述簡(jiǎn)單，ELAB采用了分組頭長(zhǎng)度最小的UDP隧道頭。具體地，在原有數(shù)據(jù)分組的三層分組頭和四層分組頭之間插入一個(gè)新UDP頭部，其內(nèi)容如下：1) 用一個(gè)特殊的UDP目的端口號(hào)來(lái)標(biāo)識(shí)該流量是ELAB產(chǎn)生的流量；2) 將UDP頭中不同的源端口號(hào)作為不同VP的標(biāo)識(shí)。因此，ELAB通過(guò)對(duì)不同數(shù)據(jù)分組設(shè)置不同的UDP隧道頭中的源端口號(hào)，即可實(shí)現(xiàn)主動(dòng)選路。

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

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

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

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

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

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

4.3 虛擬路徑空間的選取

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

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

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

4.4 基于可用帶寬的選路

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

4.4.1 選路函數(shù)

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

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

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

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

4.4.3 路徑上限帶寬B的探測(cè)

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

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

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

5 實(shí)驗(yàn)評(píng)價(jià)

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

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

5.2 專門(mén)實(shí)驗(yàn)深入分析ELAB

5.2.1 簡(jiǎn)單非對(duì)稱場(chǎng)景

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

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

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

5.2.2 非對(duì)稱網(wǎng)絡(luò)下與其他流競(jìng)爭(zhēng)的場(chǎng)景

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

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

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

圖9 競(jìng)爭(zhēng)場(chǎng)景中各方法的平均流完成時(shí)間對(duì)比

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

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

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

圖10 競(jìng)爭(zhēng)場(chǎng)景中各方法的路徑流速比隨時(shí)間的變化

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

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

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

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

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

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

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

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

6 結(jié)束語(yǔ)

人們對(duì)網(wǎng)絡(luò)帶寬需求的日益增高，也對(duì)數(shù)據(jù)中心網(wǎng)路的負(fù)載均衡機(jī)制提出了更高的要求。當(dāng)前生產(chǎn)環(huán)境中采用的ECMP負(fù)載均衡機(jī)制選路粒度粗，缺乏動(dòng)態(tài)擁塞感知能力，性能不佳?，F(xiàn)有其他細(xì)粒度且具備動(dòng)態(tài)擁塞感知能力的方案，或需要對(duì)網(wǎng)絡(luò)硬件進(jìn)行修改，難以部署；或僅需修改端系統(tǒng)軟件，但擁塞感知不準(zhǔn)，性能不佳。本文提出的ELAB方案是一種基于邊緣的利用可用帶寬進(jìn)行擁塞感知的負(fù)載均衡機(jī)制，既不需要對(duì)網(wǎng)絡(luò)硬件進(jìn)行改動(dòng)，又能準(zhǔn)確感知擁塞實(shí)現(xiàn)良好的負(fù)載均衡效果。實(shí)驗(yàn)結(jié)果表明，在非對(duì)稱網(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? ），男，湖南長(zhǎng)沙人，博士，湖南大學(xué)副教授，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)系統(tǒng)、數(shù)據(jù)中心網(wǎng)絡(luò)。

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