一文詳解DCQCN擁塞控制算法

作者：李豪 ? ? 本文精讀《Congestion Control for Large-Scale RDMA Deployments》論文，就是在這篇論文中微軟和Mellanox提出DCQCN擁塞控制算法，打開(kāi)了RDMA在數(shù)據(jù)中心規(guī)模化部署的大門(mén)。雖然距論文發(fā)表已有八、九年，經(jīng)典仍值得回味，今天我們細(xì)細(xì)閱讀之。 ?

? 01 摘要和背景介紹

現(xiàn)代(2015年)數(shù)據(jù)中心應(yīng)用需要網(wǎng)絡(luò)具備：1. 高吞吐量(40Gbps) ，2. 超低延遲(每跳 < 10 μs)、3. 低CPU開(kāi)銷(xiāo)。標(biāo)準(zhǔn)TCP/IP協(xié)議棧不滿(mǎn)足這些要求，但是RDMA(Remote Direct Memory Access)技術(shù)可以。 ? 當(dāng)前RDMA在數(shù)據(jù)中心部署主要使用RoCE v2協(xié)議，該協(xié)議依賴(lài)PFC(Priority-based Flow Control)來(lái)保證網(wǎng)絡(luò)的無(wú)損，即不發(fā)生丟包。但是PFC性能表現(xiàn)不佳，主要缺點(diǎn)包括：1. 對(duì)頭阻塞(head-of-line blocking) 2. 不公平。 ? 網(wǎng)絡(luò)無(wú)損是需要付出代價(jià)的！ ? 為了解決這些問(wèn)題，我們引入DCQCN算法，這是一個(gè)端到端的擁塞控制算法，專(zhuān)門(mén)為RoCE v2量身打造；同時(shí)我們對(duì)于如何調(diào)參給出一些建議，包括交換機(jī)buffer水線(xiàn)配置以及該算法的其他參數(shù)。 ? 端到端(end-to-end)，從發(fā)送方到接收方，比如從client到server。點(diǎn)到點(diǎn)(point-to-point)，網(wǎng)絡(luò)上相鄰的一跳，比如相鄰兩個(gè)交換機(jī)。 ? 雖然RDMA技術(shù)在HPC領(lǐng)域使用悠久且廣泛，但是在數(shù)據(jù)中心部署RDMA卻很有挑戰(zhàn)。，其中一個(gè)重要挑戰(zhàn)是擁塞控制，數(shù)據(jù)中心的RDMA對(duì)擁塞控制有如下要求： ?

在無(wú)損網(wǎng)絡(luò)環(huán)境下可以有效工作

簡(jiǎn)單到可以實(shí)現(xiàn)在網(wǎng)卡上（而非操作系統(tǒng)里）

RDMA最早使用Infiniband技術(shù)實(shí)現(xiàn)，IB使用私有的協(xié)議棧、專(zhuān)用硬件。IB在數(shù)據(jù)鏈路層(L2)使用逐跳(hop-by-hop)的credit-based流控來(lái)避免丟包，基于這個(gè)不丟包的L2，IB的傳輸層(L4)可以非常簡(jiǎn)單和高效。 ? 難就難在IB的這套協(xié)議棧和硬件設(shè)備不能直接照搬到數(shù)據(jù)中心，因?yàn)閿?shù)據(jù)中心網(wǎng)絡(luò)是以太網(wǎng)，二者不兼容。如果同時(shí)在數(shù)據(jù)中心搭建兩套網(wǎng)絡(luò)又太貴，所以RoCE v2橫空出世，允許基于傳統(tǒng)以太網(wǎng)實(shí)現(xiàn)RDMA，具體做法是將IB的傳輸層作為UDP的payload，完全不使用IB的數(shù)據(jù)鏈路層。 ? IP頭用來(lái)做路由，UDP頭用來(lái)做ECMP。 ?

雖然RoCE v2不再依賴(lài)IB的數(shù)據(jù)鏈路層，但卻繼承了IB的無(wú)損網(wǎng)絡(luò)約束，因此提出了PFC(Priority-based Flow Control)。PFC通過(guò)讓直接上游暫停發(fā)送數(shù)據(jù)的方式來(lái)避免交換機(jī)buffer溢出。 ? 直接告訴上游端口，立即暫停發(fā)送任何數(shù)據(jù)！非常的粗暴。這里的上游可以是交換機(jī)或者網(wǎng)卡。 ? PFC是交換機(jī)端口級(jí)別的，不區(qū)分具體的流（flow，即連接），一旦暫停就會(huì)暫停端口上所有的連接。這種粒度顯然太粗了，會(huì)導(dǎo)致?lián)砣麛U(kuò)散，進(jìn)而導(dǎo)顯著的致性能下降。雖然PFC可以區(qū)分交換機(jī)隊(duì)列（交換機(jī)的每個(gè)端口有8個(gè)隊(duì)列），但也于事無(wú)補(bǔ)，因?yàn)椴豢赡芙o每個(gè)鏈接都是用一個(gè)單獨(dú)的隊(duì)列。 ? 解決 PFC 局限性的根本辦法是采用流級(jí)別的擁塞控制協(xié)議，協(xié)議需要滿(mǎn)足以下要求： ?

在無(wú)損、L3 路由（網(wǎng)絡(luò)層，即IP層）、數(shù)據(jù)中心網(wǎng)絡(luò)上運(yùn)行。

主機(jī)端低CPU開(kāi)銷(xiāo)。

起步速度要快，即無(wú)擁塞的時(shí)候流滿(mǎn)速啟動(dòng)。

(2015年)當(dāng)前常見(jiàn)的擁塞控制算法均無(wú)法滿(mǎn)足以上要求，比如QCN，DCTCP，iWarp， TCP-Bolt等。 ?

QCN不支持L3層網(wǎng)絡(luò)

DCTCP和iWarp起步速度太慢(slow start)

DCTCP和TCP-Bolt使用軟件實(shí)現(xiàn)，CPU占用太高

因此DCQCN橫空出世，該算法值依賴(lài)交換機(jī)的RED和ECN功能，算法其余的部分都是現(xiàn)在主機(jī)側(cè)的網(wǎng)卡上，該算法的特點(diǎn)為： ?

快速收斂到公平

高鏈路利用率

較低的隊(duì)列堆積

較低的隊(duì)列震蕩

02 DCQCN的必要性

傳統(tǒng)TCP堆棧性能不佳

TCP協(xié)議棧在吞吐、CPU消耗、延遲等方面全面落后于RDMA。 ?

圖(a)：吞吐方面，小包的時(shí)候TCP無(wú)法打滿(mǎn)帶寬，因?yàn)榇丝藽PU成為了瓶頸。而RDMA在小包時(shí)也可以打滿(mǎn)帶寬。

圖(b)：CPU占用方面，為了打滿(mǎn)40G帶寬，TCP使用了16個(gè)線(xiàn)程，總共占用了整機(jī)20%的CPU時(shí)間。而RDMA的client側(cè) CPU占用不超過(guò)3%，server側(cè)CPU幾乎沒(méi)有CPU占用。

圖(c)：延遲方面，TCP的延遲為25.4微秒，而RDMA READ/WRITE延遲為1.7微秒，RDMA SEND延遲為2.8微秒。

PFC 有局限

RoCE v2依賴(lài)PFC來(lái)保障不發(fā)生丟包，PFC可以避免以太網(wǎng)交換機(jī)和網(wǎng)卡出現(xiàn)緩沖區(qū)溢出。具體做法是：交換機(jī)或者網(wǎng)卡監(jiān)測(cè)自己的ingress隊(duì)列，一旦隊(duì)列超過(guò)特定閾值則發(fā)送一個(gè)PAUSE消息給相鄰上游，上游收到PAUSE消息之后會(huì)停止整個(gè)端口的報(bào)文發(fā)送，直到收到RESUME消息再重新開(kāi)始。 ? PFC有八個(gè)隊(duì)列，每個(gè)隊(duì)列都可以獨(dú)立進(jìn)行上述步驟。 ? 這里主要的問(wèn)題是作用于端口（+優(yōu)先級(jí)）而不是作用于流（flow，即鏈接），這可能會(huì)導(dǎo)致head-of-line blocking等問(wèn)題，導(dǎo)致網(wǎng)絡(luò)性能變差。 ?

PFC的問(wèn)題 ?

不公平問(wèn)題(unfairness)：因?yàn)镻FC沒(méi)有區(qū)分具體的流，而是無(wú)腦的停掉整個(gè)端口流量，這會(huì)導(dǎo)致多個(gè)發(fā)送方之間的不公平問(wèn)題。上圖中Figure 3展示的是4個(gè)發(fā)送方的吞吐情況，非常的不均衡。 ? 無(wú)辜流問(wèn)題(victim flow)：這個(gè)是指一組發(fā)送方-接收方之間(Figure4中的VS和VR)本沒(méi)有擁塞，但是由于受到另一組有擁塞的發(fā)送方-接收方(H1~H32和R)的干擾，進(jìn)而導(dǎo)致VS發(fā)生降速。這主要是因?yàn)镻FC有級(jí)聯(lián)效應(yīng)，一個(gè)沒(méi)有擁塞的流可能被別的擁塞路徑波及到。 ? 而已有方案都不能解決上述PFC導(dǎo)致的問(wèn)題，因此本文提出DCQCN算法。 ?

ECMP(Equal-cost multi-path routing)不足以解決上述問(wèn)題：雖然ECMP會(huì)使得流在交換機(jī)鏈路上盡可能均勻分布，但不能保證沒(méi)有沖突。

PFC的多隊(duì)列機(jī)制也不夠：因?yàn)镻FC只有8個(gè)隊(duì)列，單個(gè)隊(duì)列內(nèi)的流仍然會(huì)遇到上述問(wèn)題。

03 DCQCN算法

算法過(guò)程

DCQCN 是一種基于速率的端到端擁塞協(xié)議，它建立在 QCN 和 DCTCP 之上。DCQCN 的大部分功能是現(xiàn)在網(wǎng)卡上（而不是交換機(jī)上，或者操作系統(tǒng)上）。如前文所述，DCQCN有以下特點(diǎn)： ?

在無(wú)損、L3 路由（網(wǎng)絡(luò)層，即IP層）、數(shù)據(jù)中心網(wǎng)絡(luò)上運(yùn)行。

主機(jī)端低CPU開(kāi)銷(xiāo)。

起步速度要快，即無(wú)擁塞的時(shí)候流滿(mǎn)速啟動(dòng)。

DCQCN中的三種角色 DCQCN中有三個(gè)角色，分別是：

RP(reaction point): 即發(fā)送方網(wǎng)卡

CP(congestion point): 即交換機(jī)

NP(notification point): 即接收方網(wǎng)卡

上述三種角色上的具體算法分別為： ? CP交換機(jī)上的算法：交換機(jī)上的算法和DCTCP一樣，當(dāng)交換機(jī)的egress隊(duì)列超過(guò)特定閾值時(shí)開(kāi)始對(duì)到來(lái)的報(bào)文（按照一定概率）標(biāo)記ECN。這通過(guò)交換機(jī)的RED(Random early detection)功能完成，幾乎所有的交換機(jī)都支持該功能，因此DCQCN不需要對(duì)交換機(jī)做改動(dòng)。

CP交換機(jī)上的算法 ? NP接收方網(wǎng)卡上的算法：當(dāng)ECN標(biāo)記后的報(bào)文到達(dá)接收方網(wǎng)卡，這表明網(wǎng)絡(luò)上發(fā)生了擁塞，接收方網(wǎng)卡將該信息轉(zhuǎn)換為CNP(Congestion Notification Packets)后反饋給發(fā)送方。CNP是RoCE v2規(guī)范中定義的擁塞通知方式。 ? NP上的算法主要用于決定CNP報(bào)生成的頻率，比如可以每收到一個(gè)ECN就反饋一個(gè)CNP，也可以規(guī)定50us內(nèi)最多反饋一個(gè)CNP。 ? CNP是區(qū)分流的，對(duì)于每個(gè)流NP算法流程如下圖：

NP狀態(tài)機(jī) ?

RP發(fā)送方網(wǎng)卡上的算法：這是DCQCN的重頭戲。分為降速過(guò)程，升速過(guò)程，更新alpha三個(gè)部分。 ? 降速過(guò)程：當(dāng)RP上的一個(gè)流收到了CNP，該流會(huì)按照如下公式降速，并更新target rate和alpha值。

DCQCN降速過(guò)程 ?

alpha更新過(guò)程：如果RP經(jīng)過(guò)K個(gè)時(shí)間單位之后沒(méi)有收到NP發(fā)來(lái)的CNP，則RP更新一次alpha值，更新公式如下。該公式的目的是在沒(méi)有擁塞的時(shí)候逐漸降低alpha值，alpha的值區(qū)間是0~1。

alpha更新過(guò)程 ? 注意K要比CNP生成的周期要長(zhǎng)一些，本文中選擇K=55us ? 升速過(guò)程：RP采用和QCN相同的升速方式，即采用一個(gè)timer和一個(gè)byte counter決定升速的節(jié)奏。每收到B個(gè)字節(jié)之后byte counter觸發(fā)升速，每隔T個(gè)時(shí)間單位之后timer觸發(fā)升速。這兩個(gè)參數(shù)都是可調(diào)的，以便控制升速節(jié)奏。 ? 有三種升速方式，通常按照以下順序發(fā)生： ?

快速恢復(fù)(fast recover)

加性增(additive increase)

超快速增(hyper increase)

注意這里沒(méi)有slow start，一個(gè)新的流起速就按照全速發(fā)送，這么做是基于如下事實(shí)：大多數(shù)時(shí)候流傳輸?shù)臄?shù)據(jù)較少切網(wǎng)絡(luò)無(wú)擁塞，因此全速發(fā)送也不會(huì)造成網(wǎng)絡(luò)擁塞（如果真的擁塞了，最終還有PFC兜底）。 ?

DCQCN 發(fā)送方算法 ? 不同于PFC作用于端口，DCQCN是作用于流的，即每個(gè)流都獨(dú)立進(jìn)行上述的算法過(guò)程。下圖表明DCQCN很好的解決了公平性問(wèn)題和無(wú)辜流問(wèn)題(unfairness and victim flow)。

DCQCN實(shí)際表現(xiàn) ?

一些關(guān)鍵點(diǎn)討論

CNP生成：我們以高優(yōu)先級(jí)發(fā)送CNP以確保更快速的收斂。注意，通常在沒(méi)有擁塞的情況下不會(huì)生成CNP。 ? 基于速率的擁塞控制：DCQCN是一種基于速率的擁塞控制方案。我們采用基于速率的算法，因?yàn)樗然诖翱诘乃惴ǜ菀讓?shí)現(xiàn)，并且允許更細(xì)粒度的控制。 ? 參數(shù)設(shè)置：DCQCN 基于 DCTCP 和 QCN，但在關(guān)鍵方面有所不同。因此DCTCP和QCN推薦的參數(shù)設(shè)置不能盲目地與DCQCN一起使用。 ? PFC仍然是必需的：DCQCN 并不能消除對(duì) PFC 的依賴(lài)，仍需要使用PFC做兜底來(lái)避免丟包，只是DCQCN會(huì)大大降低PFC發(fā)生的頻率。 ? 硬件實(shí)現(xiàn)：NP和RP（分別指接收方和發(fā)送方）的狀態(tài)機(jī)都是現(xiàn)在網(wǎng)卡上（而非操作系統(tǒng)里），RP狀態(tài)機(jī)的實(shí)現(xiàn)需要為每個(gè)流維護(hù)以下資源： ?

一個(gè)定時(shí)器：即Timer

一個(gè)計(jì)數(shù)器：即ByteCounter

跟alpha值相關(guān)的狀態(tài)

RP上的限速是針對(duì)每個(gè)數(shù)據(jù)包粒度的。 ? NP主要用于產(chǎn)生CNP報(bào)文，在ConnectX-3 Pro每生成一個(gè)CNP需要花費(fèi)1~5微秒。對(duì)于40Gbps網(wǎng)絡(luò)，1500B MTU下接收方每50微秒最多收到166個(gè)網(wǎng)絡(luò)報(bào)文，所以NP可以同時(shí)為10~20個(gè)流生成CNP，ConnectX-4可以同時(shí)為200個(gè)流生成CNP。 ? CNP生成是一個(gè)開(kāi)銷(xiāo)比較大的動(dòng)作。上面一段話(huà)的意思是，每個(gè)流在發(fā)生擁塞是至少要在50微秒內(nèi)生成1個(gè)CNP報(bào)文，而每次生成一個(gè)CNP需要消耗5微秒，即50微秒內(nèi)只能生成10個(gè)CNP，因此ConnectX-3網(wǎng)卡最多并發(fā)為10個(gè)流生成CNP。 ? ? 04 交換機(jī)緩沖區(qū)設(shè)置 ? DCQCN需要考慮以下兩個(gè)相互沖突的約束，并基于此設(shè)置交換機(jī)緩沖區(qū)的閾值： ?

PFC不能觸發(fā)的太早，至少不能早于ECN。

PFC不能觸發(fā)的太晚，否則會(huì)導(dǎo)致丟包。

PFC生成時(shí)機(jī)主要是由交換機(jī)buffer閾值控制，本節(jié)討論閾值設(shè)置問(wèn)題。 ? Headroom buffer t_flight：發(fā)送到上游設(shè)備的PAUSE消息需要一段時(shí)間才能到達(dá)并生效。為了避免數(shù)據(jù)包丟失，PAUSE 發(fā)送方必須保留足夠的緩沖區(qū)來(lái)處理在此期間可能收到的任何數(shù)據(jù)包。這包括發(fā)送 PAUSE 時(shí)正在傳輸?shù)臄?shù)據(jù)包，以及上游設(shè)備在處理 PAUSE 消息時(shí)發(fā)送的數(shù)據(jù)包。 ? PFC閾值 t_PFC：這是在PAUSE消息發(fā)送到上游之前（即上游停止發(fā)送之前），交換機(jī)的ingress隊(duì)列可以增長(zhǎng)的最大值，每個(gè)PFC優(yōu)先級(jí)都有自己的ingress隊(duì)列（8個(gè)優(yōu)先級(jí)隊(duì)列），因此如果交換機(jī)的總buffer大小為B，交換機(jī)的端口數(shù)量為n，則： ? ECN閾值 t_ECN：一旦交換機(jī)的egress隊(duì)列超過(guò)這個(gè)閾值，則交換機(jī)開(kāi)始按照一定概率標(biāo)記ECN。顯然這個(gè)值要設(shè)置的比較合理，必須保證ECN先于PFC觸發(fā)。 ? 注意，PFC看的是ingress隊(duì)列，ECN看的是egress隊(duì)列！入口隊(duì)列和出口隊(duì)列的一個(gè)主要關(guān)系是：多個(gè)入口隊(duì)列可以將數(shù)據(jù)發(fā)往同一個(gè)出口隊(duì)列，這取決于實(shí)際流的目的地。 ? 為了確保ECN先于PFC觸發(fā)，必須考慮以下極端情況：全部egress隊(duì)列的消息都來(lái)自同一個(gè)ingress隊(duì)列，這種情況下出隊(duì)列的壓力最小，入隊(duì)列的壓力最大。因此需要保證：以上所有討論并不是為了避免觸發(fā)PFC，只是為了保證ECN先于PFC觸發(fā)。DCQCN仍然依賴(lài)PFC做兜底。 ? DCQCN算法只是基于ECN/CNP讓發(fā)送方降速而不是停止發(fā)送，而PFC的PAUSE消息比較狠，直接讓上游端口停止發(fā)送任何數(shù)據(jù)。因此PFC總是能快速消除擁塞。 ? ? 05 性能評(píng)測(cè) ? DCQCN實(shí)際效果見(jiàn)下圖，論文中最多評(píng)測(cè)了10打1的incast流量： ?