高旭超,李海華

(上海交通大學(xué) 電子信息與電氣工程學(xué)院,上海 200240)

0 引 言

以太網(wǎng)通信因?yàn)榫哂袔捀摺⒊杀镜?、安全可靠等?yōu)點(diǎn),近些年來被廣泛的應(yīng)用在汽車、工業(yè)控制等領(lǐng)域[1,2]。與傳統(tǒng)的以太網(wǎng)應(yīng)用不同,這些應(yīng)用場景對以太網(wǎng)數(shù)據(jù)傳輸性能提出了新的要求[3]。例如,車載自動(dòng)駕駛系對數(shù)據(jù)的實(shí)時(shí)性要求非常高[4],系統(tǒng)中關(guān)鍵控制數(shù)據(jù)的丟失和延遲會造成潛在的安全隱患。區(qū)分服務(wù)(DiffServ)模型針對實(shí)時(shí)業(yè)務(wù)定義了加速轉(zhuǎn)發(fā)的逐跳行為,為時(shí)延敏感的實(shí)時(shí)業(yè)務(wù)供低時(shí)延、低時(shí)延抖動(dòng)、低丟包率、保證帶寬的“三低一保證”服務(wù)質(zhì)量[5]。為了在以太網(wǎng)通信中實(shí)現(xiàn)區(qū)分服務(wù)模型對實(shí)時(shí)業(yè)務(wù)的支持,隊(duì)列調(diào)度是其中的關(guān)鍵[6]。

在目前常用的調(diào)度策略中,DRR(deficit round robin)調(diào)度器因?yàn)槠淞己玫墓叫院涂蓴U(kuò)展性,被廣泛地應(yīng)用在網(wǎng)絡(luò)的核心交換節(jié)點(diǎn)上[7]。但是與此同時(shí),DRR調(diào)度無法保證隊(duì)列中分組的時(shí)延性能[8],所以無法滿足實(shí)時(shí)業(yè)務(wù)對服務(wù)質(zhì)量的要求。

針對上述問題,本文對DRR調(diào)度器進(jìn)行了改進(jìn),設(shè)計(jì)了IDRR(insertable DRR)調(diào)度器。IDRR對鏈路中的實(shí)時(shí)業(yè)務(wù)和非實(shí)時(shí)業(yè)務(wù)采取不同的調(diào)度策略。調(diào)度非實(shí)時(shí)業(yè)務(wù)時(shí),調(diào)度器采用DRR調(diào)度進(jìn)行出隊(duì)調(diào)度；對于實(shí)時(shí)業(yè)務(wù),以實(shí)時(shí)業(yè)務(wù)的排隊(duì)時(shí)間為參考標(biāo)準(zhǔn),當(dāng)隊(duì)列中分組的排隊(duì)時(shí)間超過一定值時(shí),實(shí)時(shí)業(yè)務(wù)可以進(jìn)行插隊(duì)并提前得到服務(wù)。實(shí)時(shí)業(yè)務(wù)和非實(shí)時(shí)業(yè)務(wù)同時(shí)請求調(diào)度時(shí),插隊(duì)調(diào)度和DRR調(diào)度交替進(jìn)行。

目前有許多針對DRR調(diào)度器的研究和改進(jìn),大部分都是通過網(wǎng)絡(luò)仿真器來研究其性能[7,9,10]。本文在現(xiàn)場可編程門陣列(FPGA)實(shí)現(xiàn)了以太網(wǎng)交換機(jī)中的IDRR調(diào)度器的硬件電路設(shè)計(jì)并通過Ixia以太網(wǎng)測試平臺對該調(diào)度模塊進(jìn)行了測試。測試結(jié)果表明,與DRR調(diào)度器相比,IDRR調(diào)度器可以在不增加復(fù)雜度的前提下,有效地降低實(shí)時(shí)業(yè)務(wù)的時(shí)延和時(shí)延抖動(dòng),滿足區(qū)分服務(wù)模型的要求。

1 區(qū)分服務(wù)與隊(duì)列調(diào)度

1.1 區(qū)分服務(wù)模型對數(shù)據(jù)的分類

逐跳行為(per-hop behavior,PHB)是區(qū)分服務(wù)模型對特定業(yè)務(wù)流轉(zhuǎn)發(fā)和調(diào)度的行為描述。網(wǎng)絡(luò)交換設(shè)備實(shí)現(xiàn)區(qū)分服務(wù)的機(jī)制就是根據(jù)PHB的定義將各個(gè)業(yè)務(wù)流分類聚集,再根據(jù)PHB對業(yè)務(wù)流的行為描述和優(yōu)先級進(jìn)行調(diào)度和轉(zhuǎn)發(fā)。

其中,加速轉(zhuǎn)發(fā)(expedited forwarding,EF)針對網(wǎng)絡(luò)傳輸過程中的實(shí)時(shí)業(yè)務(wù),EF業(yè)務(wù)應(yīng)該作為優(yōu)先級最高的業(yè)務(wù)被調(diào)度[11]；確保轉(zhuǎn)發(fā)(assured forwarding,AF)的逐跳行為要求網(wǎng)絡(luò)為不超過帶寬限制的AF業(yè)務(wù)提供轉(zhuǎn)發(fā)質(zhì)量保證,這種業(yè)務(wù)模型著眼于保證業(yè)務(wù)帶寬,不涉及時(shí)延和時(shí)延抖動(dòng)；盡力轉(zhuǎn)發(fā)(best effort,BE)是網(wǎng)絡(luò)中的缺省服務(wù),網(wǎng)絡(luò)不對BE業(yè)務(wù)流的服務(wù)質(zhì)量做任何保證。當(dāng)鏈路出現(xiàn)阻塞時(shí),網(wǎng)絡(luò)只為BE業(yè)務(wù)保留少量帶寬,以防止其“饑餓”[12]。

1.2 以太網(wǎng)二層協(xié)議對優(yōu)先級的定義

以太網(wǎng)二層交換機(jī)主要通過IEEE 802.3Q中定義的VLAN標(biāo)簽對流量進(jìn)行優(yōu)先級區(qū)分。802.3Q中定義的以太網(wǎng)VLAN幀格式如圖1所示[5]。

圖1 IEEE 802.1Q 幀格式

VLAN幀的TPID(tag protocol identifier)字段固定為0x8100,TCI(tag control information)中的PCP(priority codepoint)字段為3 bit的優(yōu)先級。根據(jù)802.3Q協(xié)議,4隊(duì)列調(diào)度模塊的PCP解碼定義和服務(wù)質(zhì)量如表1所示。網(wǎng)絡(luò)控制流量是網(wǎng)絡(luò)中優(yōu)先級最高的流量類型,網(wǎng)絡(luò)需要為其提供“三低一保證”的服務(wù)質(zhì)量；音視頻流量和關(guān)鍵應(yīng)用流量為需要網(wǎng)絡(luò)提供盡力轉(zhuǎn)發(fā)的服務(wù)質(zhì)量；最后,網(wǎng)絡(luò)通信系統(tǒng)不為盡力轉(zhuǎn)發(fā)的業(yè)務(wù)提供服務(wù)質(zhì)量保證。

表1 PCP字段解碼定義與服務(wù)質(zhì)量

1.3 隊(duì)列調(diào)度

為了對網(wǎng)絡(luò)中不同的業(yè)務(wù)流實(shí)現(xiàn)區(qū)分服務(wù),首先要對進(jìn)入交換節(jié)點(diǎn)的各個(gè)分組進(jìn)行分類和排隊(duì),然后使用調(diào)度器對各個(gè)隊(duì)列進(jìn)行調(diào)度。目前在交換機(jī)中常用的隊(duì)列調(diào)度策略為WRR，DRR，WFQ等。WFQ調(diào)度器具有很好的公平性,但是因?yàn)槠渚哂蠴(N2)的復(fù)雜度,導(dǎo)致這種調(diào)度器很難部署在網(wǎng)絡(luò)的核心交換節(jié)點(diǎn)；WRR調(diào)度器的復(fù)雜度為O(1),所以很容易在大型交換機(jī)和路由器中實(shí)現(xiàn)[9]。WRR調(diào)度根據(jù)每個(gè)隊(duì)列的權(quán)值(weight)來區(qū)分各個(gè)隊(duì)列,權(quán)值代表該隊(duì)列在每次循環(huán)中可以得到服務(wù)數(shù)量的上限,權(quán)值越高隊(duì)列的占用鏈路帶寬也就越高。當(dāng)各個(gè)隊(duì)列中的分組長度相等時(shí),WRR調(diào)度器可以提供很好的公平性,保障低優(yōu)先級的業(yè)務(wù)可以得到一定的帶寬。但是當(dāng)隊(duì)列中分組長度不相等時(shí),較長的分組會得到更多的服務(wù),從而造成隊(duì)列實(shí)際占用的帶寬與該隊(duì)列的權(quán)值不一致。

DRR調(diào)度改善了WRR調(diào)度中變長分組帶來的公平性問題,該調(diào)度策略給每個(gè)隊(duì)列分配的是每次服務(wù)過程中此隊(duì)列可以被服務(wù)的赤字(deficit),如果隊(duì)列的赤字大于隊(duì)列中需要被調(diào)度的分組的長度,這個(gè)分組就可以得到服務(wù)；否則調(diào)度器就調(diào)度下一個(gè)非空隊(duì)列,而當(dāng)前隊(duì)列的赤字將保留到下次循環(huán)使用。DRR調(diào)度器和WRR一樣具有O(1)復(fù)雜度,但是在某些情況下,高優(yōu)先級隊(duì)列中的分組可能需要等待低優(yōu)先級的隊(duì)列中的分組完成調(diào)度之后才能得到服務(wù),所以調(diào)度器無法保證高優(yōu)先級隊(duì)列的時(shí)延性能[8]。

為了在不增加復(fù)雜度的前提下改善DRR調(diào)度中實(shí)時(shí)業(yè)務(wù)的時(shí)延性能。本文首先研究了以太網(wǎng)通信中支持區(qū)分服務(wù)的DRR調(diào)度器,設(shè)計(jì)并實(shí)現(xiàn)了相應(yīng)的硬件電路,然后在此基礎(chǔ)上設(shè)計(jì)并實(shí)現(xiàn)了IDRR調(diào)度器。

2 調(diào)度模塊的設(shè)計(jì)與實(shí)現(xiàn)

隊(duì)列調(diào)度模塊結(jié)構(gòu)框圖如圖2所示,主要包括分類器,儲存隊(duì)列、調(diào)度器和時(shí)間發(fā)生模塊四部分。當(dāng)新的以太網(wǎng)分組到達(dá)時(shí),如果分類器檢測到分組為VLAN TAG類型,則根據(jù)其PCP字段中定義的優(yōu)先級將分組入隊(duì),若為非VLAN TAG類型的分組,則將其歸為BE業(yè)務(wù)。與此同時(shí),分類器會給所有屬于EF業(yè)務(wù)的分組打上時(shí)間戳。隊(duì)列管理模塊維護(hù)管理EF,AF1,AF2,BE四個(gè)隊(duì)列,隊(duì)列的優(yōu)先級依次降低,其中EF隊(duì)列儲存時(shí)延敏感的實(shí)時(shí)業(yè)務(wù)分組,兩個(gè)AF隊(duì)列儲存要求帶寬保證的非實(shí)時(shí)業(yè)務(wù),BE隊(duì)列儲存只需盡力而為的非關(guān)鍵數(shù)據(jù)分組。隊(duì)列管理模塊除了保存分組數(shù)據(jù)之外,也會為每個(gè)分組保存其數(shù)據(jù)長度,針對EF業(yè)務(wù),隊(duì)列管理模塊還會為其保存時(shí)間戳中的信息。時(shí)間發(fā)生模塊為分類器和調(diào)度器提供統(tǒng)一的系統(tǒng)時(shí)間。在后續(xù)調(diào)度時(shí),調(diào)度器根據(jù)時(shí)鐘模塊給出的系統(tǒng)時(shí)間和EF分組中的時(shí)間戳計(jì)算出EF業(yè)務(wù)分組在隊(duì)列中的等待時(shí)間。

圖2 隊(duì)列調(diào)度模塊結(jié)構(gòu)框圖

IDRR調(diào)度器由DRR調(diào)度器改進(jìn)而來[13],調(diào)度器為每個(gè)隊(duì)列維護(hù)一個(gè)赤字計(jì)數(shù)器DC(deficit counter),并使用圖3所示的ActiveList來追蹤當(dāng)前的非空隊(duì)列。當(dāng)隊(duì)列i狀態(tài)由空變?yōu)榉强諘r(shí),將i加入ActiveList尾部。調(diào)度器每次調(diào)度出現(xiàn)在ActiveList頭部的隊(duì)列。隊(duì)列i完成一次出隊(duì)調(diào)度后,將隊(duì)列i從AcitiveList中出隊(duì),如果此時(shí)隊(duì)列非空,則將隊(duì)列i重新加入ActiveList尾部。

圖3 DRR調(diào)度中ActiveList操作

IDRR調(diào)度器狀態(tài)機(jī)如圖4所示,為了防止惡意EF流量長時(shí)間占用出口帶寬,導(dǎo)致低優(yōu)先級隊(duì)列餓死,在調(diào)度器中設(shè)置標(biāo)志位INSERT_ENABLE,以確保在EF隊(duì)列和非EF隊(duì)列同時(shí)出現(xiàn)調(diào)度請求時(shí),調(diào)度器可以交替進(jìn)行插隊(duì)調(diào)度和DRR調(diào)度。調(diào)度器復(fù)位后進(jìn)入IDLE狀態(tài),此時(shí)調(diào)度器檢查EF隊(duì)列中分組的等待時(shí)間,如等待時(shí)間大于設(shè)定的閾值Thr且INSERT_ENABLE為1,狀態(tài)機(jī)進(jìn)入INSERT_EF狀態(tài)進(jìn)行插隊(duì)調(diào)度,并且在插隊(duì)調(diào)度完成后將INSERT_ENABLE置0。調(diào)度器進(jìn)入CHK狀態(tài)后開始根據(jù)DRR調(diào)度策略對ActiveList中頭部的隊(duì)列i進(jìn)行出隊(duì)調(diào)度。如果隊(duì)列i積累的赤字大于帶調(diào)度的分組長度,則進(jìn)入DEQUE狀態(tài)進(jìn)行出隊(duì)調(diào)度,否則將直接進(jìn)入AL_SHIFT狀態(tài),將i從ActiveList頭部出隊(duì)。在AL_SHIFT狀態(tài)中,調(diào)度器檢查隊(duì)列i的狀態(tài),若隊(duì)列i非空,則將隊(duì)列i重新加入ActiveList尾部,使其繼續(xù)等待調(diào)度。

圖4 IDRR調(diào)度器狀態(tài)轉(zhuǎn)移圖

3 硬件方案與測試環(huán)境

本文使用的FPGA開發(fā)板為Xilinx公司的VC707,選用裕太車通的YT8010國產(chǎn)芯片作為PHY芯片,使用MII接口與PHY芯片通信。所有交換機(jī)模塊和調(diào)度模塊均在Xilinx的vivado集成開發(fā)環(huán)境下使用Verilog語言開發(fā)。

基于FPGA的以太網(wǎng)交換機(jī)系統(tǒng)如圖5所示。外接的以太網(wǎng)PHY芯片通過MII接口向交換機(jī)的端口傳送以太網(wǎng)分組,接收端口的MAC對收到的以太網(wǎng)分組進(jìn)行儲存和校驗(yàn),并將數(shù)據(jù)分組轉(zhuǎn)換為32位的并行數(shù)據(jù)。交換機(jī)確定該分組的目的端口之后,通過端口間的高速交換總線將該數(shù)據(jù)分組發(fā)送到目的端口中的調(diào)度模塊進(jìn)行排隊(duì)調(diào)度。最后由目的端口的MAC將調(diào)度后的分組轉(zhuǎn)換為4位MII接口數(shù)據(jù)發(fā)送給外部的PHY芯片。

圖5 以太網(wǎng)交換機(jī)架構(gòu)

本文使用的網(wǎng)絡(luò)測試工具為Ixia公司的以太網(wǎng)測試儀。如圖6(a)所示,通過軟件控制Ixia測試儀向交換機(jī)發(fā)送網(wǎng)絡(luò)流量,在接收端對網(wǎng)絡(luò)流量進(jìn)行采集,將接收到的以太網(wǎng)流量與發(fā)端的流量進(jìn)行對比,即可統(tǒng)計(jì)出通信鏈路的性能。本文使用的網(wǎng)絡(luò)測試拓?fù)浣Y(jié)構(gòu)如圖6(b)所示,圖中BE,AF2,AF1和EF流的帶寬分別為6,5,4,2 Mbps,交換機(jī)出口帶寬為10 Mbps。4個(gè)以太網(wǎng)業(yè)務(wù)流的分組長度均是符合均勻分布的隨機(jī)值。

圖6 Ixia測試環(huán)境

4 測試結(jié)果與分析

圖7展示了在上述網(wǎng)絡(luò)環(huán)境下,實(shí)時(shí)業(yè)務(wù)經(jīng)DRR和IDRR調(diào)度器調(diào)度后的時(shí)延性能。圖7(a)為實(shí)時(shí)業(yè)務(wù)經(jīng)過兩種調(diào)度后的時(shí)延抖動(dòng)性能。測試結(jié)果表明,經(jīng)IDRR調(diào)度后,EF分組的時(shí)延抖動(dòng)為0.36 ms,比DRR調(diào)度降低了51.3 %,這意味著IDRR調(diào)度可以更加平滑地調(diào)度EF隊(duì)列中的分組。如圖7(b)所示,相比于DRR調(diào)度器,經(jīng)IDRR調(diào)度后,EF業(yè)務(wù)流的端到端最大傳輸時(shí)延為7.2 ms,相比DRR調(diào)度減少了3.1 ms,表明IDRR調(diào)度可以為實(shí)時(shí)業(yè)務(wù)提更好的端到端的時(shí)延保障。

圖7 DRR和IDRR調(diào)度中實(shí)時(shí)業(yè)務(wù)的時(shí)延性能

DRR和IDRR兩種調(diào)度器的交換機(jī)在Ixia以太網(wǎng)測試平臺中測試60 min后實(shí)時(shí)業(yè)務(wù)流的丟包率分別為0.27 %和0.28 %?？梢钥吹皆诮?jīng)過兩種調(diào)度后,實(shí)時(shí)業(yè)務(wù)都具有極低的丟包率(0.01 %可近似認(rèn)為實(shí)時(shí)隨機(jī)波動(dòng))。這說明IDRR調(diào)度器在改善實(shí)時(shí)業(yè)務(wù)流時(shí)延性能的同時(shí),也保證了該業(yè)務(wù)的帶寬占用。以上測試結(jié)果表明IDRR調(diào)度為實(shí)時(shí)業(yè)務(wù)提供更好的服務(wù)質(zhì)量。這是因?yàn)镮DRR調(diào)度器可以將EF隊(duì)列中的分組的調(diào)度時(shí)延LEF控制在以下范圍Thr≤LEF≤Thr+F/r。而DRR調(diào)度中EF分組經(jīng)歷的調(diào)度時(shí)延為0≤LEF≤(3F-2Φi)。其中，F(xiàn)為網(wǎng)絡(luò)中的最大幀長,Фi為隊(duì)列i的預(yù)約帶寬因子,r為鏈路帶寬。

因此,相比于DRR調(diào)度器,IDRR調(diào)度器一方面可以控制EF業(yè)務(wù)的最大調(diào)度延遲,另一方面,可以將EF業(yè)務(wù)的調(diào)度延時(shí)控制在一個(gè)比較小的區(qū)間里,從而改善了實(shí)時(shí)業(yè)務(wù)在整個(gè)通信鏈路里的最大延遲和時(shí)延抖動(dòng)。

5 結(jié) 論

在DRR調(diào)度器基礎(chǔ)的基礎(chǔ)上改進(jìn)并設(shè)計(jì)了IDRR調(diào)度器。非實(shí)時(shí)業(yè)務(wù)使用DRR調(diào)度進(jìn)行調(diào)度,而實(shí)時(shí)業(yè)務(wù)則根據(jù)分組在隊(duì)列中的等待時(shí)間來決定是否進(jìn)行插隊(duì)調(diào)度。當(dāng)存在多種業(yè)務(wù)流時(shí)競爭鏈路帶寬時(shí),兩種調(diào)度方式交替進(jìn)行。測試結(jié)果表明：相比于DRR調(diào)度,改進(jìn)后的調(diào)度器在保持了低復(fù)雜度的同時(shí),很好地提高了網(wǎng)絡(luò)中關(guān)鍵業(yè)務(wù)的實(shí)時(shí)性,可以方便地部署在車載和工業(yè)以太網(wǎng)中。