任秀江，斯添浩，周建毅，謝向輝

(1.江南計(jì)算技術(shù)研究所,江蘇 無(wú)錫 214083;2.數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室,江蘇 無(wú)錫 214125)

1 引言

隨著高性能計(jì)算機(jī)系統(tǒng)規(guī)模的快速增長(zhǎng)，互連網(wǎng)絡(luò)已經(jīng)成為提升現(xiàn)代高性能計(jì)算系統(tǒng)性能的技術(shù)瓶頸[1]。高性能互連網(wǎng)絡(luò)設(shè)計(jì)的目標(biāo)是以盡量小的物理開(kāi)銷獲得更低的報(bào)文傳輸延遲以及更高的網(wǎng)絡(luò)吞吐率。在一個(gè)拓?fù)浣Y(jié)構(gòu)和路由算法確定的互連網(wǎng)絡(luò)中，擁塞控制機(jī)制對(duì)提高網(wǎng)絡(luò)性能有著重要作用?，F(xiàn)有的擁塞控制技術(shù)大多基于有損網(wǎng)絡(luò)，網(wǎng)絡(luò)擁塞形成后都是通過(guò)直接丟包的方式反饋擁塞信息[2,3]。傳統(tǒng)計(jì)算機(jī)網(wǎng)絡(luò)中的擁塞控制技術(shù)，大多在擁塞發(fā)生后才能啟動(dòng)擁塞控制[4 - 6]，從擁塞形成到控制機(jī)制達(dá)成效果的延遲較大。這一點(diǎn)不適合應(yīng)用于高性能互連網(wǎng)絡(luò)，因?yàn)樵诟咝阅苡?jì)算系統(tǒng)中，持續(xù)的低延遲事件可能會(huì)因?yàn)橐粋€(gè)小的長(zhǎng)延遲操作導(dǎo)致的連鎖反應(yīng)而降低應(yīng)用的性能[7,8]。一個(gè)理想的擁塞控制機(jī)制能夠合理地分配網(wǎng)絡(luò)通信資源，避免資源的閑置浪費(fèi)，同時(shí)通過(guò)合理的通信任務(wù)調(diào)度，及時(shí)避免通信熱點(diǎn)形成，減少因?yàn)橘Y源競(jìng)爭(zhēng)導(dǎo)致的通信等待，提高網(wǎng)絡(luò)整體通信性能。研究適合高性能互連網(wǎng)絡(luò)的擁塞控制技術(shù)，對(duì)提高高性能計(jì)算系統(tǒng)性能至關(guān)重要。

本文對(duì)高性能互連網(wǎng)絡(luò)中的擁塞過(guò)程進(jìn)行研究，提出了一種基于網(wǎng)絡(luò)包延遲偏差的硬件動(dòng)態(tài)擁塞控制機(jī)制CMDPD(Congestion-control Mechanism based-on Deflection of Packet Delay)，在通信源節(jié)點(diǎn)按目標(biāo)節(jié)點(diǎn)統(tǒng)計(jì)記錄的網(wǎng)絡(luò)包平均傳輸延遲，基于實(shí)時(shí)網(wǎng)絡(luò)包傳輸延遲與已記錄的平均傳輸延遲偏移差值(即偏差)預(yù)判網(wǎng)絡(luò)擁塞狀態(tài)，通過(guò)切換通信目標(biāo)等方式減少對(duì)擁塞目標(biāo)注入量，降低對(duì)擁塞目標(biāo)的通信競(jìng)爭(zhēng)，達(dá)到擁塞避免的目的。通過(guò)網(wǎng)絡(luò)包級(jí)延遲的快速反饋機(jī)制預(yù)判擁塞，主動(dòng)避免的方法減少網(wǎng)絡(luò)熱點(diǎn)的形成，減少網(wǎng)絡(luò)包等待，及時(shí)切換通信目標(biāo)的方法能夠提高網(wǎng)絡(luò)吞吐量，平衡網(wǎng)絡(luò)整體性能。

2 相關(guān)研究

網(wǎng)絡(luò)擁塞是指通信請(qǐng)求對(duì)網(wǎng)絡(luò)資源的需求超過(guò)了網(wǎng)絡(luò)固有容量的一種持續(xù)過(guò)載的網(wǎng)絡(luò)狀態(tài)。互連網(wǎng)絡(luò)最重要的性能參數(shù)就是延遲和吞吐率[9]，發(fā)生擁塞后，網(wǎng)絡(luò)包傳輸延遲增加，網(wǎng)絡(luò)的吞吐率下降，網(wǎng)絡(luò)整體性能降低。

根據(jù)發(fā)生擁塞后網(wǎng)絡(luò)報(bào)文是否可以被丟棄，互連網(wǎng)絡(luò)分為有損網(wǎng)絡(luò)和無(wú)損網(wǎng)絡(luò)兩大類。有損網(wǎng)絡(luò)通過(guò)丟包、慢啟動(dòng)等操作緩解擁塞[10]。無(wú)損網(wǎng)絡(luò)不會(huì)發(fā)生丟包，但當(dāng)出現(xiàn)網(wǎng)絡(luò)資源競(jìng)爭(zhēng)時(shí)，也會(huì)因?yàn)榕抨?duì)發(fā)生網(wǎng)絡(luò)包延遲增加、網(wǎng)絡(luò)吞吐率降低的情況。當(dāng)網(wǎng)絡(luò)通信熱點(diǎn)持續(xù)存在時(shí)，網(wǎng)絡(luò)性能也將大打折扣。高性能互連網(wǎng)絡(luò)屬于無(wú)損網(wǎng)絡(luò)，對(duì)延遲、吞吐率有更高的要求，解決高性能互連網(wǎng)絡(luò)中擁塞控制更具挑戰(zhàn)性。

2.1 被動(dòng)擁塞控制技術(shù)

在擁塞發(fā)生后再采取控制的技術(shù)稱為被動(dòng)擁塞控制技術(shù)。

比較成熟的被動(dòng)擁塞控制技術(shù)有ECN(Explicit Congestion Notification)擁塞控制技術(shù)等。ECN擁塞控制技術(shù)最早于1994年基于TCP/IP被提出，能夠避免不必要的報(bào)文丟棄，減少了TCP連接中由于報(bào)文丟棄而增加的額外延遲[11]。2001年惠普實(shí)驗(yàn)室提出了基于IB(InfiniBand)網(wǎng)絡(luò)的擁塞控制技術(shù)ECN[12]，利用ECN反饋機(jī)制對(duì)源節(jié)點(diǎn)進(jìn)行報(bào)文注入抑制。文獻(xiàn)[13]提出了一種基于IB網(wǎng)絡(luò)的端到端的擁塞控制機(jī)制，利用消息層級(jí)的應(yīng)答機(jī)制控制擁塞擴(kuò)散。文獻(xiàn)[14]提出了一種基于標(biāo)記的擁塞控制技術(shù)，由路由器打入擁塞標(biāo)記。文獻(xiàn)[15]提出了結(jié)合分離擁塞流和非擁塞流的方法和基于ECN機(jī)制的網(wǎng)絡(luò)注入抑制策略。文獻(xiàn)[10]中重點(diǎn)對(duì)IB網(wǎng)絡(luò)中的擁塞控制進(jìn)行了改進(jìn)，將擁塞通知改為停止發(fā)包指令，源節(jié)點(diǎn)的發(fā)包重啟動(dòng)操作由擁塞的目標(biāo)節(jié)點(diǎn)通過(guò)特殊的喚醒包Guidance包進(jìn)行。

文獻(xiàn)[16]注意到ECN無(wú)法避免擁塞的產(chǎn)生，結(jié)合未來(lái)高速互連網(wǎng)絡(luò)的發(fā)展趨勢(shì)，提出了一種基于預(yù)約的擁塞避免技術(shù)SRP(Speculative Reservation Protocol)，即通過(guò)提前預(yù)約目的節(jié)點(diǎn)的通信資源避免因資源競(jìng)爭(zhēng)的網(wǎng)絡(luò)擁塞。這種方法能夠避免由于目的節(jié)點(diǎn)資源競(jìng)爭(zhēng)引起的擁塞，卻不能解決由于路徑競(jìng)爭(zhēng)引起的擁塞。文獻(xiàn)[10]則在SRP的基礎(chǔ)上提出了CRP(Channel Reservation Protocol)技術(shù)，在預(yù)約目的節(jié)點(diǎn)資源的同時(shí)將關(guān)鍵路徑上的路徑資源一起預(yù)約，預(yù)約的方法能夠避免熱點(diǎn)節(jié)點(diǎn)和熱點(diǎn)路徑上產(chǎn)生擁塞，較好地解決了樹(shù)飽和效應(yīng)。

2.2 主動(dòng)擁塞控制技術(shù)

網(wǎng)絡(luò)擁塞是一個(gè)整體、動(dòng)態(tài)的問(wèn)題，單純地通過(guò)增加硬件資源并不能從根本上解決擁塞問(wèn)題，有時(shí)候增加的網(wǎng)絡(luò)資源反而會(huì)增加網(wǎng)絡(luò)的擁塞程度。主動(dòng)擁塞控制技術(shù)就是基于采用動(dòng)態(tài)方法解決網(wǎng)絡(luò)擁塞的思想，提前控制每個(gè)報(bào)文的傳輸，使得擁塞不可能發(fā)生，因此也叫做擁塞避免技術(shù)。早期的擁塞避免與應(yīng)用的通信特征緊密結(jié)合，雖然能夠取得較好的優(yōu)化效果，但針對(duì)性強(qiáng)，不是一種普適做法。近些年來(lái)，也有一些研究開(kāi)始嘗試在網(wǎng)絡(luò)通信的底層進(jìn)行主動(dòng)擁塞控制。

文獻(xiàn)[17]針對(duì)胖樹(shù)網(wǎng)絡(luò)，從交換機(jī)的角度降低網(wǎng)絡(luò)擁塞，使用IB中的VL(Virtual Lane)降低由于頭堵塞和緩沖阻塞導(dǎo)致的擁塞。文獻(xiàn)[10]中采用了前瞻策略在數(shù)據(jù)傳輸開(kāi)始前，將網(wǎng)絡(luò)資源規(guī)劃分配好，從根本上避免競(jìng)爭(zhēng)擁塞的發(fā)生。這種技術(shù)很難適應(yīng)現(xiàn)代并行計(jì)算系統(tǒng)，現(xiàn)在多用于QoS(Quality of Service)[18]。其他的一些可以減緩或推遲擁塞的策略，例如全自適應(yīng)路由[19]和負(fù)載平衡技術(shù)[20]，它們根據(jù)網(wǎng)絡(luò)狀態(tài)動(dòng)態(tài)調(diào)整路由策略。這些技術(shù)能夠推后、延緩擁塞的發(fā)生，但不能從根本上避免擁塞發(fā)生后的網(wǎng)絡(luò)性能下降。

文獻(xiàn)[21]中認(rèn)為，網(wǎng)絡(luò)包的通信環(huán)回延遲RTT(Round-Trip Time)的變化非常適合作為網(wǎng)絡(luò)擁塞狀態(tài)變化的反饋信息，使用RTT作為網(wǎng)絡(luò)擁塞狀態(tài)的反饋信息具有充分的合理性?；诖死碚摚芯咳藛T提出了大量基于RTT的擁塞控制協(xié)議。TCP Vegas[22]可以根據(jù)RTT的變化來(lái)判斷網(wǎng)絡(luò)的擁塞狀態(tài)，受其啟發(fā)其他一些基于延遲的擁塞控制算法也相繼被提出來(lái)，如FAST TCP[23]、Compound TCP[24]等。文獻(xiàn)[25]中認(rèn)為如果RTT的反饋時(shí)間小于控制執(zhí)行的延遲，則不可能實(shí)現(xiàn)擁塞控制。文獻(xiàn)[7]提出的TIMELY(Transport Informaed by MEasurement of Latenc Y)機(jī)制，將長(zhǎng)消息進(jìn)行細(xì)粒度分段傳輸，根據(jù)每段傳輸延遲對(duì)數(shù)據(jù)注入進(jìn)行控制，通過(guò)分段將通信過(guò)程細(xì)粒度化。

2.3 擁塞控制技術(shù)小結(jié)

擁塞的本質(zhì)是競(jìng)爭(zhēng)，解決競(jìng)爭(zhēng)的主要方法是減少對(duì)通信熱點(diǎn)的注入，控制擁塞擴(kuò)散。被動(dòng)的擁塞控制技術(shù)都是基于擁塞已經(jīng)發(fā)生后的補(bǔ)償操作，雖然能夠緩解擁塞程度，但不能避免擁塞的發(fā)生。主動(dòng)擁塞控制技術(shù)理論上能夠防止擁塞的發(fā)生，但由于網(wǎng)絡(luò)擁塞的整體性和動(dòng)態(tài)性的特征，基于資源預(yù)分配的技術(shù)很難取得預(yù)期的效果；一些研究已經(jīng)表明，RTT能夠反映網(wǎng)絡(luò)擁塞狀態(tài)，如何能夠根據(jù)RTT實(shí)時(shí)判定網(wǎng)絡(luò)狀態(tài)還受到一些條件限制，例如RTT的精確性、RTT反饋的粒度以及擁塞控制執(zhí)行的反應(yīng)時(shí)間等。主動(dòng)擁塞控制技術(shù)的難點(diǎn)和挑戰(zhàn)在于預(yù)先發(fā)現(xiàn)網(wǎng)絡(luò)擁塞狀態(tài)，及時(shí)啟動(dòng)擁塞控制措施，解決這兩點(diǎn)對(duì)實(shí)現(xiàn)高性能互連網(wǎng)絡(luò)的擁塞控制具有重要意義。

3 網(wǎng)絡(luò)擁塞的模擬與分析

高性能互連網(wǎng)絡(luò)屬于無(wú)損網(wǎng)絡(luò)，沒(méi)有復(fù)雜的網(wǎng)絡(luò)丟包機(jī)制，網(wǎng)絡(luò)擁塞的發(fā)生主要是形成通信熱點(diǎn)導(dǎo)致的。對(duì)高性能互連網(wǎng)絡(luò)中的通信熱點(diǎn)的形成過(guò)程可以推測(cè)為：初始時(shí)，網(wǎng)絡(luò)中路徑空閑，通信資源充足，網(wǎng)絡(luò)包傳輸過(guò)程中的沖突較少，網(wǎng)絡(luò)包傳輸延遲低；隨著網(wǎng)絡(luò)注入量的增加，通信競(jìng)爭(zhēng)增加，資源排隊(duì)增多，網(wǎng)絡(luò)包傳輸延遲會(huì)逐漸遞增，此過(guò)程中網(wǎng)絡(luò)吞吐率也是處于逐漸遞增的過(guò)程；在通信熱點(diǎn)形成后，網(wǎng)絡(luò)包的傳輸延遲會(huì)繼續(xù)增大為一個(gè)極大值，網(wǎng)絡(luò)吞吐量會(huì)下降為一個(gè)近似穩(wěn)定值，這個(gè)穩(wěn)定值的大小取決于通信熱點(diǎn)的處理能力。

本節(jié)中，將采用網(wǎng)絡(luò)模擬器對(duì)無(wú)損網(wǎng)絡(luò)中通信熱點(diǎn)的通信模式進(jìn)行模擬，通過(guò)對(duì)網(wǎng)絡(luò)包延遲、網(wǎng)絡(luò)吞吐量的變化進(jìn)行跟蹤記錄，分析網(wǎng)絡(luò)擁塞的形成過(guò)程。

3.1 網(wǎng)絡(luò)拓?fù)浜湍M環(huán)境說(shuō)明

拓?fù)浣Y(jié)構(gòu)是互連網(wǎng)絡(luò)的基礎(chǔ)，直接影響著網(wǎng)絡(luò)的性能。文獻(xiàn)[26]中對(duì)近些年Top500前10名系統(tǒng)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的統(tǒng)計(jì)，高性能計(jì)算領(lǐng)域最主要應(yīng)用的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為Torus、Fat-tree、Dragonfly及其變形網(wǎng)絡(luò)等。例如，日本的Tofu網(wǎng)絡(luò)可以看作是Torus網(wǎng)絡(luò)的變形結(jié)構(gòu)，天河一號(hào)采用的是Fat-tree網(wǎng)絡(luò)的變形網(wǎng)絡(luò)[27]，Cray公司的XC30系統(tǒng)采用了Dragonfly網(wǎng)絡(luò)結(jié)構(gòu)[28]。按照傳統(tǒng)的計(jì)算機(jī)網(wǎng)絡(luò)分類，Torus和Dragonfly屬于直接網(wǎng)絡(luò)，F(xiàn)at-tree屬于間接網(wǎng)絡(luò)[20]。我們選擇Dragonfly作為直接網(wǎng)絡(luò)代表，F(xiàn)at-tree作為間接網(wǎng)絡(luò)代表，建立模擬環(huán)境進(jìn)行模擬實(shí)驗(yàn)。

OMNeT++(Objective Modular Network TestBed in C++)是一種優(yōu)秀的離散事件模擬平臺(tái)，近年在學(xué)術(shù)界和工業(yè)領(lǐng)域應(yīng)用廣泛。OMNeT++具備強(qiáng)大完善的圖形界面接口和可嵌入式模擬內(nèi)核，可以在多種操作系統(tǒng)上運(yùn)行，支持層次式開(kāi)發(fā)，可以方便地定義互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和各個(gè)模塊的功能。圖1所示為OMNeT++的建模流程示意圖。

Figure 1 Modeling process of OMNeT++圖1 OMNeT++的建模流程

基于OMNeT++4.6版本，開(kāi)發(fā)了一個(gè)周期精度的模擬器MESim(Message Engine Simulator with cycle-level accuracy)，MESim中實(shí)現(xiàn)了可配置的節(jié)點(diǎn)消息引擎模塊MEU(Message Engine Unit)，可以通過(guò)參數(shù)配置選擇實(shí)現(xiàn)不同通信模式的消息，配合網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)配置，實(shí)現(xiàn)不同消息機(jī)制在不同拓?fù)浣Y(jié)構(gòu)互連網(wǎng)絡(luò)中的模擬。

3.2 傳輸延遲精確測(cè)量

傳統(tǒng)基于延遲反饋的擁塞控制機(jī)制對(duì)網(wǎng)絡(luò)包傳輸延遲的精度要求高。TCP協(xié)議中網(wǎng)絡(luò)包傳輸延遲RTT采用源方軟件時(shí)間戳[29]的方式實(shí)現(xiàn)，這種方法得到的測(cè)量值中包含了很多其他因素，還包含了主機(jī)處理的等待時(shí)間，某些情況下這些額外的延遲會(huì)對(duì)延遲測(cè)量值產(chǎn)生較大影響，造成不必要的網(wǎng)絡(luò)狀態(tài)反復(fù)誤判。

為了保證網(wǎng)絡(luò)包傳輸延遲測(cè)量的準(zhǔn)確性，一些研究中提出采用硬件精確測(cè)量技術(shù)。文獻(xiàn)[8,30]中給出了基于網(wǎng)絡(luò)接口芯片支持的網(wǎng)絡(luò)包傳輸延遲測(cè)量方法，不需要軟件的參與。采用硬件時(shí)間戳的方法，能夠去除軟件的影響，可以提高延遲測(cè)量精度，但測(cè)量值中還是包含了響應(yīng)包的傳輸延遲。

在MESim模擬器中，網(wǎng)絡(luò)包控制信息中添加網(wǎng)絡(luò)延遲字段。如圖2所示，對(duì)路由器模塊進(jìn)行修改，在路由器的輸入端口和輸出端口之間進(jìn)行延遲計(jì)時(shí)，網(wǎng)絡(luò)包每經(jīng)過(guò)一級(jí)路由器，由路由器將延遲累加到網(wǎng)絡(luò)延遲字段中，這樣在目標(biāo)節(jié)點(diǎn)接收到網(wǎng)絡(luò)包時(shí)，網(wǎng)絡(luò)延遲字段中記錄的就是精確的網(wǎng)絡(luò)包傳輸延遲。

Figure 2 Structure of router with accumulative transmission delay圖2 累計(jì)傳輸延遲的路由器模塊結(jié)構(gòu)

3.3 模擬結(jié)果分析

模擬實(shí)驗(yàn)中定義了一種熱點(diǎn)消息模式(hot_node)，即網(wǎng)絡(luò)中所有節(jié)點(diǎn)集中向網(wǎng)絡(luò)中10%的節(jié)點(diǎn)發(fā)起通信。模擬過(guò)程中設(shè)定每個(gè)網(wǎng)絡(luò)包到達(dá)目標(biāo)節(jié)點(diǎn)后都能被接收處理，網(wǎng)絡(luò)包傳輸延遲定義為從源節(jié)點(diǎn)發(fā)出網(wǎng)絡(luò)包到網(wǎng)絡(luò)包到達(dá)目標(biāo)節(jié)點(diǎn)的延遲，由3.2節(jié)中所述的路由器累計(jì)延遲獲得。實(shí)驗(yàn)過(guò)程中，MESim按時(shí)間段統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)發(fā)出的網(wǎng)絡(luò)包平均傳輸延遲(avg_delay)、最大傳輸延遲(max_delay)和網(wǎng)絡(luò)吞吐量。模擬器的其他配置參數(shù)，網(wǎng)絡(luò)數(shù)據(jù)通路位寬32字節(jié)，網(wǎng)絡(luò)包最大長(zhǎng)度2 048字節(jié)。

Table 1 Network structure simulation list

圖3為兩種網(wǎng)絡(luò)結(jié)構(gòu)、不同網(wǎng)絡(luò)規(guī)模下熱點(diǎn)通信模擬結(jié)果，橫坐標(biāo)為模擬過(guò)程中20個(gè)等時(shí)間間隔的數(shù)據(jù)統(tǒng)計(jì)時(shí)間。左圖為模擬各階段中網(wǎng)絡(luò)包最大傳輸延遲與平均傳輸延遲的曲線，中間圖為網(wǎng)絡(luò)包最大傳輸延遲對(duì)平均傳輸延遲的偏移比例曲線，右圖為各統(tǒng)計(jì)時(shí)間段內(nèi)的網(wǎng)絡(luò)包吞吐量曲線。

從左側(cè)的四個(gè)模擬曲線可以看到，隨著網(wǎng)絡(luò)通信熱點(diǎn)的逐漸形成，網(wǎng)絡(luò)包最大傳輸延遲和平均傳輸延遲都在增加，最大傳輸延遲近似線性的規(guī)律逐漸增大，平均傳輸延遲增長(zhǎng)速度緩慢一些。右側(cè)的吞吐率曲線增長(zhǎng)一段時(shí)間后基本維持在一個(gè)較為穩(wěn)定的區(qū)間范圍，這符合熱點(diǎn)通信形成過(guò)程的預(yù)期。

中間圖是網(wǎng)絡(luò)包最大傳輸延遲相對(duì)平均傳輸延遲的偏移量(Deflection)從四個(gè)模擬結(jié)果圖中都可以發(fā)現(xiàn)其曲線走勢(shì)與網(wǎng)絡(luò)吞吐率非常相似，而且四個(gè)曲線都在Deflection曲線達(dá)到2之后逐漸趨于穩(wěn)定。利用這一特征，可以使用網(wǎng)絡(luò)包傳輸延遲偏移來(lái)預(yù)測(cè)網(wǎng)絡(luò)狀態(tài)。

Figure 3 Throughput and delay curves for the four interconnection networks in hot spot communication mode圖3 四種互連網(wǎng)絡(luò)熱點(diǎn)通信模式下吞吐率、延遲曲線

4 基于延遲偏移的擁塞控制CMDPD

很多研究都表明，精確的網(wǎng)絡(luò)延遲能夠反映出網(wǎng)絡(luò)擁塞狀態(tài)。從上一小節(jié)中的熱點(diǎn)通信模擬結(jié)果可以看到，網(wǎng)絡(luò)包最大傳輸延遲的偏移曲線Deflection走勢(shì)與網(wǎng)絡(luò)吞吐量近似。基于這些分析和模擬實(shí)驗(yàn)結(jié)果，在通信端的數(shù)據(jù)傳輸引擎中加入網(wǎng)絡(luò)包延遲記錄模塊PDRU(Packet Delay Recoding Unit)，累計(jì)網(wǎng)絡(luò)包平均傳輸延遲，并計(jì)算傳輸延遲偏移量，通過(guò)偏移量判定通信目標(biāo)的擁塞狀態(tài)，對(duì)網(wǎng)絡(luò)注入進(jìn)行控制，達(dá)到網(wǎng)絡(luò)擁塞避免的目的。

4.1 數(shù)據(jù)傳輸引擎結(jié)構(gòu)修改

圖4所示為MESim模擬器中的數(shù)據(jù)傳輸引擎結(jié)構(gòu)。數(shù)據(jù)傳輸引擎由發(fā)送部件、接收部件兩大部分構(gòu)成。發(fā)送部件將產(chǎn)生、提交的消息拆分為網(wǎng)絡(luò)包，提交注入互連網(wǎng)絡(luò)；接收部件從互連網(wǎng)絡(luò)接收網(wǎng)絡(luò)包，然后產(chǎn)生相應(yīng)的響應(yīng)包，發(fā)送給網(wǎng)絡(luò)包來(lái)源節(jié)點(diǎn)。

對(duì)接收部件進(jìn)行修改，增加網(wǎng)絡(luò)包延遲記錄模塊PDRU，PDRU內(nèi)設(shè)置與發(fā)送部件內(nèi)網(wǎng)絡(luò)包懸掛個(gè)數(shù)相同的延遲懸掛，延遲懸掛以全相連方式進(jìn)行組織管理，每個(gè)條目記錄一個(gè)目標(biāo)節(jié)點(diǎn)的累計(jì)網(wǎng)絡(luò)包傳輸延遲。

修改后的數(shù)據(jù)傳輸引擎工作過(guò)程如下:

(1)網(wǎng)絡(luò)包發(fā)送過(guò)程：

①接收到消息傳輸請(qǐng)求，分配網(wǎng)絡(luò)包懸掛；

②網(wǎng)絡(luò)包懸掛查詢PDRU，獲得發(fā)送許可后，提交發(fā)包請(qǐng)求；

③網(wǎng)絡(luò)包仲裁部件選擇允許發(fā)送的網(wǎng)絡(luò)包，提交互連網(wǎng)絡(luò)。

(2)網(wǎng)絡(luò)包接收過(guò)程：

①接收部件從互連網(wǎng)絡(luò)接收到網(wǎng)絡(luò)包；

②產(chǎn)生響應(yīng)包，攜帶網(wǎng)絡(luò)包中的傳輸延遲Tdelay，發(fā)送回來(lái)源節(jié)點(diǎn)。

(3)響應(yīng)包接收過(guò)程：

①?gòu)幕ミB網(wǎng)絡(luò)接收響應(yīng)包；

②將響應(yīng)包中的來(lái)源節(jié)點(diǎn)號(hào)、攜帶的Tdelay提交給PDRU。

Figure 4 Structure of data transmission engine圖4 數(shù)據(jù)傳輸引擎結(jié)構(gòu)框圖

4.2 網(wǎng)絡(luò)注入控制

PDRU接收響應(yīng)包反饋，對(duì)發(fā)送部件更新網(wǎng)絡(luò)包發(fā)送許可信號(hào)，通過(guò)發(fā)送許可信號(hào)完成對(duì)網(wǎng)絡(luò)注入的控制。PDRU內(nèi)每個(gè)延遲懸掛條目的內(nèi)容如表2所示。

PDRU的核心功能是利用最近返回的網(wǎng)絡(luò)包傳輸延遲和已記錄的平均傳輸延遲計(jì)算延遲偏移Deflection，根據(jù)Deflection更新網(wǎng)絡(luò)包發(fā)送控制參數(shù)，由發(fā)送控制參數(shù)控制對(duì)目標(biāo)節(jié)點(diǎn)的網(wǎng)絡(luò)包注入頻率。Loop_cunter是一個(gè)循環(huán)計(jì)數(shù)器，每個(gè)時(shí)鐘節(jié)拍累加1，當(dāng)累加值等于Average_delay*Send_ctrl_para時(shí)恢復(fù)為0，只有當(dāng)Loop_cunter為0時(shí)才允許向目標(biāo)節(jié)點(diǎn)發(fā)送網(wǎng)絡(luò)包。

Table 2 Content of delay buffer within PDRU

當(dāng)PDRU接收一個(gè)新的響應(yīng)包時(shí)，其處理過(guò)程如下：

(1)根據(jù)響應(yīng)包的來(lái)源節(jié)點(diǎn)，查找延遲懸掛中的匹配條目；

(2)使用當(dāng)前響應(yīng)包中攜帶的傳輸延遲Tdelay和條目中保存的Average_delay計(jì)算延遲偏移Deflection；

(3)根據(jù)延遲偏移Deflection更新條目Send_ctrl_para；

(4)根據(jù)Deflection值，更新All_delay、Packet_num。

第3、4步中兩個(gè)內(nèi)容的更新分離，是考慮到出現(xiàn)個(gè)別網(wǎng)絡(luò)包的傳輸延遲突然增大的情況，這種突增的延遲值如果不加區(qū)分地更新到條目中，對(duì)平均傳輸延遲的影響會(huì)比較大。因此，PDRU在接收到Deflection值較大的網(wǎng)絡(luò)包延遲時(shí)，只更新發(fā)送控制參數(shù)，這樣能夠減少偶發(fā)的異常網(wǎng)絡(luò)傳輸延遲值的影響范圍。

5 CMDPD的模擬實(shí)驗(yàn)與分析

5.1 模擬實(shí)驗(yàn)說(shuō)明

如上一節(jié)所述原理和結(jié)構(gòu)修改，在MESim模擬器中實(shí)現(xiàn)了CMDPD機(jī)制。在模擬器中設(shè)置了兩個(gè)參數(shù)init0和init1，參數(shù)組合init0-init1作為PDRU對(duì)Send_ctrl_para和All_delay、Packet_num內(nèi)容的更新條件。

(1)當(dāng)Deflection>init1時(shí)，允許更新Send_ctrl_para為Deflection值；

(2)當(dāng)Deflection

(3)當(dāng)init0

依然選擇Fat-tree和Dragonfly兩種網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行模擬。在第3節(jié)中的模擬實(shí)驗(yàn)中發(fā)現(xiàn)3種規(guī)模的Fat-tree的實(shí)驗(yàn)結(jié)果趨勢(shì)相近，因此實(shí)驗(yàn)中只對(duì)256個(gè)節(jié)點(diǎn)的Fat-tree結(jié)構(gòu)進(jìn)行模擬。為了更真實(shí)地模擬高性能互連網(wǎng)絡(luò)的擁塞狀態(tài)，除了熱點(diǎn)通信模式外，還選擇all-to-all通信模式和隨機(jī)通信模式生成測(cè)試激勵(lì)，其中all-to-all通信模式采用了兩種算法實(shí)現(xiàn)。具體測(cè)試激勵(lì)說(shuō)明如表3所示。

5.2 模擬結(jié)果與分析

根據(jù)前面熱點(diǎn)通信模擬結(jié)果，選擇了整數(shù)集合{6,8,10,15}和{10,12,14,16,18,20,25,30,35,40}作為init0和init1的實(shí)驗(yàn)參數(shù)，對(duì)不同的參數(shù)組合init0-init1進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)中固定運(yùn)行100萬(wàn)拍，MESim模擬器記錄網(wǎng)絡(luò)整體的網(wǎng)絡(luò)包吞吐量，并統(tǒng)計(jì)網(wǎng)絡(luò)包的最大傳輸延遲和平均傳輸延遲，最后通過(guò)比較不同參數(shù)組合下的統(tǒng)計(jì)數(shù)據(jù)分析實(shí)驗(yàn)結(jié)果。

Table 3 Description of the test items for the simulation

Figure 5 Throughput comparison for CMDPD圖5 CMDPD模擬吞吐量對(duì)比

圖5所示為CMDPD不同init0-init1參數(shù)下的吞吐量模擬結(jié)果柱形圖，“基準(zhǔn)”內(nèi)容為沒(méi)有采用CMDPD的對(duì)比模擬結(jié)果。

在Fat-tree網(wǎng)絡(luò)中，除了hot_node模式外，其他通信模式下采用CMDPD之后，網(wǎng)絡(luò)的吞吐量都有提高，其中alltoall_round_robin通信模式的吞吐量提高10%～12%，uniform_random平均提高5.5%，uniform_random_seq_gen平均提高6%。在hot_node模式下，由于通信目標(biāo)點(diǎn)較為集中，CMDPD的控制機(jī)制雖然反映時(shí)間短，但盡管采用了切換通信目標(biāo)的流控方式，還是不能對(duì)這種過(guò)于集中的通信發(fā)揮有效控制，反映在模擬結(jié)果中，則表現(xiàn)為不同參數(shù)組合下的吞吐量變化較大。

Figure 6 Comparison of average delay of network packets for CMDPD圖6 CMDPD模擬網(wǎng)絡(luò)包平均延遲結(jié)果對(duì)比

在Dragonfly網(wǎng)絡(luò)中，hot_node和uniform_random兩種通信模式中，有組合參數(shù)下出現(xiàn)了吞吐量降低的情況，uniform_random_seq_gen通信模式下結(jié)果基本沒(méi)有變化，alltoall_round_robin通信模式的網(wǎng)絡(luò)吞吐量提高比例在4%以內(nèi)。這個(gè)結(jié)果反映了CMDPD機(jī)制對(duì)不同網(wǎng)絡(luò)拓?fù)涞倪m應(yīng)性是不同的，與Fat-tree網(wǎng)絡(luò)相比，Dragonfly網(wǎng)絡(luò)利用高階路由器的多端口降低了網(wǎng)絡(luò)直徑，網(wǎng)絡(luò)路徑上跳步減少，排隊(duì)競(jìng)爭(zhēng)引起的網(wǎng)絡(luò)傳輸延遲偏移相對(duì)較小，CMDPD機(jī)制發(fā)揮作用的余地較小。

除了統(tǒng)計(jì)網(wǎng)絡(luò)的吞吐量，模擬過(guò)程中以時(shí)間段為單位，對(duì)網(wǎng)絡(luò)包的平均傳輸延遲進(jìn)行了統(tǒng)計(jì)。如圖6所示為模擬實(shí)驗(yàn)中對(duì)網(wǎng)絡(luò)包平均傳輸延遲的結(jié)果對(duì)比曲線，其中橫坐標(biāo)為模擬過(guò)程中10個(gè)等時(shí)間間隔的統(tǒng)計(jì)時(shí)機(jī)。

在Fat-tree網(wǎng)絡(luò)中，hot_node和alltoall_round_robin通信模式下，采用CMDPD控制機(jī)制后，網(wǎng)絡(luò)包平均傳輸延遲變化幅度較大；uniform_random和uniform_random_seq_gen通信模式中，采用CMDPD后平均網(wǎng)絡(luò)傳輸延遲相比“基準(zhǔn)”降低10%～20%。

在Dragonfly網(wǎng)絡(luò)中，四種通信模式下，采用CMDPD后的網(wǎng)絡(luò)包平均傳輸延遲沒(méi)有較大變化，走向趨勢(shì)也基本相同。這個(gè)結(jié)果可以與上面的吞吐率測(cè)試結(jié)果相互印證，即CMDPD對(duì)Dragonfly網(wǎng)絡(luò)結(jié)構(gòu)適應(yīng)性不如對(duì)Fat-tree網(wǎng)絡(luò)，但測(cè)試結(jié)果表明CMDPD機(jī)制沒(méi)有對(duì)網(wǎng)絡(luò)包的傳輸延遲產(chǎn)生負(fù)面影響。

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

本文對(duì)高性能互連網(wǎng)絡(luò)中的擁塞控制進(jìn)行了研究，針對(duì)高性能互連網(wǎng)絡(luò)中的通信熱點(diǎn)問(wèn)題，提出了一種基于網(wǎng)絡(luò)包延遲偏差的硬件擁塞控制機(jī)制CMDPD，在通信端進(jìn)行注入控制?；贠MNet++平臺(tái)構(gòu)建網(wǎng)絡(luò)模擬器，在Fat-tree網(wǎng)絡(luò)和Dragonfly網(wǎng)絡(luò)中對(duì)CMDPD進(jìn)行了模擬。實(shí)驗(yàn)結(jié)果表明，F(xiàn)at-tree網(wǎng)絡(luò)中CMDPD的網(wǎng)絡(luò)吞吐量提高5%～12%，在Dragonfly網(wǎng)絡(luò)中CMDPD的效果不明顯；兩種網(wǎng)絡(luò)結(jié)構(gòu)下，采用CMDPD后的網(wǎng)絡(luò)包平均傳輸延遲沒(méi)有明顯增加。實(shí)驗(yàn)結(jié)果表明，CMDPD在網(wǎng)絡(luò)包級(jí)進(jìn)行網(wǎng)絡(luò)狀態(tài)判斷和擁塞控制，對(duì)提高網(wǎng)絡(luò)吞吐率有一定效果，沒(méi)有對(duì)網(wǎng)絡(luò)延遲造成負(fù)面影響。

本文實(shí)現(xiàn)的CMDPD擁塞控制機(jī)制，首次在網(wǎng)絡(luò)包級(jí)由硬件進(jìn)行注入控制，機(jī)制反饋迅速，不會(huì)影響更高層級(jí)的擁塞控制實(shí)現(xiàn)，但延遲偏差控制還是基于外部配置，未來(lái)研究工作可向自動(dòng)控制方向做擴(kuò)展研究。

[1] Lucas R, Ang J,Bergman K,et al.DOE advanced scientific computing advisory subcommittee (ASCAC) report:Top ten exascale research challenges[R].United States:ASCA,2014-02-10.

[2] Association I B T.InfiniBand architecture specification:Release 1.0[EB/OL].[2000-12-10]. http://www.infinibandta.com/.

[3] InfiniBand Trade Association Std.:InfiniBand architecture specification,Vol.1:Rel.1.2.1[S].InfiniBand Trade Association Std,2007.

[4] Thottethodi M,Lebeck A R,Mukherjee S S.Self-tuned congestion control for multiprocessor networks[C]∥Proc of International Symposium on High-Performance Computer Architecture,2001:107.

[5] Baydal E,López P,Duato J.A congestion control mechanism for wormhole networks[C]∥Proc of the 9th Euromicro Workshop on Parallel and Distributed Processing,2001:19-26.

[6] Baydal E,López P.A robust mechanism for congestion control:INC[C]∥Proc of European Conference on Parallel Processing,2003:958-968.

[7] Mittal R,Lam V T,Dukkipati N,et al.TIMELY:RTT-based congestion control for the datacenter [J].ACM SIGCOMM Computer Communication Review,2015,45(5):537-550.

[8] Using hardware timestamps with PF RING[EB/OL].[2011-11-16].http://goo.gl/oJtHCe.

[9] Wei X,Cheng J,Li H.Latency-balanced optimization of MPI collective communication across multi-clusters[C]∥Proc of Chinagrid Conference,2013:9-13.

[10] Michelogiannakis G,Jiang N,Becker D,et al.Channel reservation protocol for over-subscribed channels and destinations[C]∥Proc of the International Conference on High Performance Computing,Networking,Storage and Analysis,2013:52.

[11] Floyd S.TCP and explicit congestion notification [J].ACM SIGCOMM Computer Communication Review,1994,24(5):8-23.

[12] Turner Y, Santos J R,Janakiraman G J.An approach for congestion control in InfiniBand:HPL-2001-277R1[J].Palo Alto:HP Laboratories Palo Alto,Internet Systems and Storage Laboratory,2001.

[13] Santos J R,Turner Y,Janakiraman G.End-to-end congestion control for Infiniband[C]∥Proc of the 22nd Annual Joint Conference of the IEEE Computer and Communications,2003:1123-1133.

[14] Ferrer J L L,Baydal E,Robles A,et al.Congestion management in mins through marked and validated packets[C]∥Proc of the 15th Euromicro International Conference on Parallel,Distributed and Network-Based,2007:254-261.

[15] Duato J,Johnson I,Flich J,et al.A new scalable and cost-effective congestion management strategy for lossless multistage interconnection networks[C]∥Proc of the 11th International Conference on High-Performance Computer Architecture,2005:108-119.

[16] Jiang N, Becker D U,Michelogiannakis G,et al.Network congestion avoidance through speculative reservation[C]∥Proc of 2012 IEEE 18th International Symposium on High Performance Computer Architecture,2012:1-12.

[17] Escudero-Sahuquillo J,Garcia P J,Quiles F J,et al.A new proposal to deal with congestion in InfiniBand-based fat-trees[J].Journal of Parallel & Distributed Computing,2014,74(1):1802-1819.

[18] Kandula S,Padhye J,Bahl V.Flyways to DeCongest data center networks[C]∥Proc of the 8th ACM Workshop on Hot Topics in Networks,2009:1.

[19] Kim J,Dally W J,Abts D.Flattened butterfly:A cost-efficient topology for high-radix networks[J].ACM SIGARCH Computer Architecture News,2007,35(2):126-137.

[20] Kim J,Dally W J,Towles B,et al.Microarchitecture of a high-radix router[J].ACM SIGARCH Computer Architecture News,2005,33(2):420-431.

[21] Grigorik I. Optimizing the critical rendering[EB/OL].[2013-11-16].http://goo.gl/DvFfGo.

[22] Gran E G,Reinemo S A,Lysne O,et al.Exploring the scope of the InfiniBand congestion control mechanism[C]∥Proc of Parallel & Distributed Processing Symposium,2012:1131-1143.

[23] Jin C,Wei D X,Low S H.FAST TCP:Motivation,architecture,algorithms,performance[C]∥Proc of Joint Conference of the IEEE Computer and Communications Societies,2004:2490-2501.

[24] Tan K,Song J,Zhang Q,et al.A compound TCP approach for high-speed and long distance networks[C]∥Proc of IEEE International Conference on Computer Communications,2006:1-12.

[25] Kelly F,Raina G,Voice T.Stability and fairness of explicit congestion control with small buffers[J].ACM SIGCOMM Computer Communication Review,2008,38(3):51-62.

[26] Trobec R,Vasiljevic R,Tomasevic M,et al.Interconnection networks in petascale computer systems:A Survey[J].ACM Computing Surveys (CSUR),2016,49(3):Article 44.

[27] Yang X,Liao X,Lu K,et al.The Tianhe-1A supercomputer：Its hardware and software [J]．Journal of Computer Science and Technology,2011,26(3)：344-351．

[28] Dally W J,Towles B.Principles and practices of interconnection networks[M].San Mato:Morgan Kaufmann Publishers,2004.

[29] Dual port 10 gigabit server adapter with precision time stamping[EB/OL].[2016-10-15].http://goo.gl/VtL5oO.

[30] Mellanox for Linux[EB/OL].[2016-10-15].http://goo.gl/u44Xea.