一文詳解DCQCN擁塞控制算法

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

? 01 摘要和背景介紹

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

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

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

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

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

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

主機(jī)端低CPU開銷。

起步速度要快，即無擁塞的時候流滿速啟動。

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

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

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

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

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

快速收斂到公平

高鏈路利用率

較低的隊(duì)列堆積

較低的隊(duì)列震蕩

02 DCQCN的必要性

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

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

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

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

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

PFC 有局限

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

PFC的問題 ?

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

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

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

03 DCQCN算法

算法過程

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

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

主機(jī)端低CPU開銷。

起步速度要快，即無擁塞的時候流滿速啟動。

DCQCN中的三種角色 DCQCN中有三個角色，分別是：

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

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

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

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

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

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

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

DCQCN降速過程 ?

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

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

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

加性增(additive increase)

超快速增(hyper increase)

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

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

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

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

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

一個定時器：即Timer

一個計數(shù)器：即ByteCounter

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

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

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

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

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