趙國(guó)鴻，胡勇庭，李 韜，孫志剛

(國(guó)防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院，湖南 長(zhǎng)沙 410073)

基于描述符的輸出調(diào)度IP核的設(shè)計(jì)與實(shí)現(xiàn)

趙國(guó)鴻，胡勇庭，李 韜，孫志剛

(國(guó)防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院，湖南 長(zhǎng)沙 410073)

輸出調(diào)度是實(shí)現(xiàn)QoS支持的重要技術(shù)?；趫?bào)文的輸出調(diào)度技術(shù)由于實(shí)現(xiàn)簡(jiǎn)單等優(yōu)點(diǎn)，廣泛應(yīng)用于各種QoS部件的設(shè)計(jì)與實(shí)現(xiàn)中。然而，基于報(bào)文的輸出調(diào)度由于需要緩存大量待調(diào)度報(bào)文，因此增加了設(shè)備的芯片面積和實(shí)現(xiàn)成本。針對(duì)上述問(wèn)題，提出了一種基于描述符的輸出調(diào)度技術(shù)，通過(guò)對(duì)攜帶報(bào)文長(zhǎng)度信息的描述符進(jìn)行調(diào)度，在保證系統(tǒng)性能的前提下，可有效降低輸出調(diào)度的存儲(chǔ)空間需求。還介紹了基于此種輸出調(diào)度算法的IP核設(shè)計(jì)與實(shí)現(xiàn)，介紹了模塊的外部接口、參數(shù)配置以及內(nèi)部處理流程。最后，通過(guò)實(shí)驗(yàn)驗(yàn)證了此IP核的可行性。

QoS；輸出調(diào)度；描述符；IP核

1 引言

近年來(lái)互聯(lián)網(wǎng)應(yīng)用的快速發(fā)展，不僅需要網(wǎng)絡(luò)設(shè)備的處理速率不斷提升，而且要求網(wǎng)絡(luò)處理設(shè)備提供必需的服務(wù)質(zhì)量QoS(Quality of Service)保證。服務(wù)質(zhì)量[1,2]QoS是指網(wǎng)絡(luò)能夠提供有保證的、可預(yù)測(cè)的數(shù)據(jù)服務(wù)。輸出調(diào)度是QoS的一項(xiàng)最基本技術(shù)，輸出調(diào)度技術(shù)可以按照用戶實(shí)際需要分配硬件資源，在網(wǎng)絡(luò)發(fā)生擁塞時(shí)區(qū)分服務(wù)不同的用戶。目前對(duì)輸出調(diào)度算法的研究比較成熟，最早的輸出調(diào)度方法是先來(lái)先服務(wù)FCFS(First Come First Served)的方式，后來(lái)為了區(qū)別不同的優(yōu)先級(jí)用戶又出現(xiàn)了嚴(yán)格優(yōu)先級(jí)隊(duì)列PQ(Priority Queue)調(diào)度算法，由于PQ算法對(duì)用戶并不公平，低優(yōu)先級(jí)的隊(duì)列可能長(zhǎng)時(shí)間無(wú)法占用到硬件資源，因此出現(xiàn)了基于輪循的DRR[3]算法以及基于虛擬時(shí)鐘[4]的WFQ[5]算法；為了完善WFQ算法，出現(xiàn)了W2FQ[6]算法，為了公平調(diào)度不同流對(duì)多種資源的需求，又出現(xiàn)了DRFQ[7]算法。

目前，大多數(shù)的網(wǎng)絡(luò)設(shè)備都采用了基于報(bào)文的輸出調(diào)度方式，這種方式實(shí)現(xiàn)簡(jiǎn)單、高效。報(bào)文在處理單元處理完畢后被發(fā)送到輸出調(diào)度部件，經(jīng)過(guò)調(diào)度后輸出到網(wǎng)絡(luò)接口。在網(wǎng)絡(luò)中存在突發(fā)流量時(shí)，調(diào)度部件需要緩存大量報(bào)文，而網(wǎng)絡(luò)設(shè)備芯片上的存儲(chǔ)空間比較受限，增加外部存儲(chǔ)將會(huì)導(dǎo)致芯片面積與成本的大幅提高。存儲(chǔ)資源的大量占用是基于報(bào)文的輸出調(diào)度方法的最大缺點(diǎn)。

針對(duì)以上問(wèn)題，本文提出了一種基于描述符的輸出調(diào)度技術(shù)，在不降低設(shè)備處理性能的基礎(chǔ)上大幅減少了存儲(chǔ)資源的消耗。由于輸出調(diào)度廣泛應(yīng)用于網(wǎng)絡(luò)設(shè)備中，因此為了降低網(wǎng)絡(luò)設(shè)備的開(kāi)發(fā)成本以及難度，本文還利用這種基于描述符的輸出調(diào)度技術(shù)設(shè)計(jì)了一個(gè)輸出調(diào)度IP核[8,9]。用戶可以配置不同的參數(shù)，使輸出調(diào)度IP核實(shí)現(xiàn)不同的功能。本文第2節(jié)從理論上分析基于描述符的輸出調(diào)度的優(yōu)點(diǎn)；第3節(jié)介紹輸出調(diào)度IP核的接口信息以及參數(shù)配置；第4節(jié)介紹IP核內(nèi)部的工作流程；第5節(jié)給出實(shí)驗(yàn)結(jié)果以及分析；第6節(jié)為結(jié)束語(yǔ)。

2 基于描述符的輸出調(diào)度設(shè)計(jì)

2.1 主要思想

如圖1所示，網(wǎng)絡(luò)設(shè)備中基于報(bào)文的輸出調(diào)度方式通常包括以下基本流程：

(1) 處理單元讀取主存中的報(bào)文進(jìn)行處理。

(2) 處理單元將處理完成的報(bào)文描述符發(fā)送到存取控制單元。

(3) 存取控制單元根據(jù)接收的描述符構(gòu)造讀請(qǐng)求，從主存儲(chǔ)器中讀取出待調(diào)度報(bào)文。

(4) 輸出調(diào)度器對(duì)待調(diào)度報(bào)文進(jìn)行調(diào)度。

(5) 將調(diào)度后的報(bào)文發(fā)送到網(wǎng)絡(luò)中。

Figure 1 Procedure of packet-based output scheduling圖1 基于報(bào)文的調(diào)度輸出流程

針對(duì)目前網(wǎng)絡(luò)設(shè)備中報(bào)文調(diào)度時(shí)存儲(chǔ)資源消耗較大的問(wèn)題，基于描述符的報(bào)文輸出調(diào)度流程如圖2所示，可以分為以下幾個(gè)步驟：

(1) 處理單元讀取主存中的報(bào)文進(jìn)行處理。

(2) 輸出調(diào)度器接收來(lái)自處理單元的報(bào)文描述符，對(duì)報(bào)文描述符進(jìn)行調(diào)度。

(3) 輸出調(diào)度器將調(diào)度后的報(bào)文描述符發(fā)送到存取控制單元。

(4) 存取控制單元根據(jù)接收的描述符構(gòu)造讀請(qǐng)求，從主存儲(chǔ)器中讀取出待調(diào)度報(bào)文。

(5) 將調(diào)度后的報(bào)文發(fā)送到網(wǎng)絡(luò)中。

Figure 2 Procedure of descriptor-based output scheduling圖2 基于描述符的調(diào)度輸出流程

2.2 理論分析

本節(jié)將著重于分析基于描述符的輸出調(diào)度方式在存儲(chǔ)資源消耗以及系統(tǒng)性能方面的特點(diǎn)。

2.2.1 存儲(chǔ)資源消耗

調(diào)度輸出器中所使用的緩存空間如圖3所示，存儲(chǔ)空間可以分為輸入隊(duì)列以及輸出隊(duì)列。多個(gè)輸入隊(duì)列中攜帶的多條流調(diào)度輸出到輸出隊(duì)列中。

Figure 3 Architecture of output scheduler圖3 輸出調(diào)度器結(jié)構(gòu)圖

如果考慮用描述符的方式，一般以太網(wǎng)報(bào)文的大小從64字節(jié)至1500字節(jié)不等，我們?nèi)?00字節(jié)作為平均值，而一個(gè)描述符只需要8個(gè)字節(jié)就可以存儲(chǔ)報(bào)文在I/O操作以及隊(duì)列調(diào)度時(shí)所需各種摘要信息，這樣原本250 Mb的存儲(chǔ)空間采用描述符的方式壓縮后只需要2.5 Mb。

假設(shè)輸出調(diào)度器中的隊(duì)列數(shù)量為m，每個(gè)隊(duì)列中存儲(chǔ)的報(bào)文個(gè)數(shù)為k，輸出調(diào)度器的總存儲(chǔ)空間為B，報(bào)文的長(zhǎng)度取平均值800字節(jié)。如果采用基于報(bào)文的調(diào)度方式，則B=800*k*m；如果采用基于描述符的調(diào)度方式，描述符的長(zhǎng)度為8 B，則B=8*k*m?；趫?bào)文與基于描述符的調(diào)度方式在存儲(chǔ)空間上的對(duì)比如圖4所示。

Figure 4 Storage contrast圖4 存儲(chǔ)空間對(duì)比圖

可見(jiàn)，描述符輸出調(diào)度方式與直接調(diào)度報(bào)文相比，可節(jié)省大量存儲(chǔ)空間。

2.2.2 處理性能分析

本小節(jié)將著重分析基于報(bào)文的輸出調(diào)度方式與基于描述符的輸出調(diào)度方式在處理性能上的差異。相關(guān)參數(shù)如表1所示。

Table 1 Analysis parameters instruction

(1)基于報(bào)文的輸出調(diào)度方式。

若采用直接對(duì)報(bào)文進(jìn)行輸出調(diào)度的方式，各階段性能分析如下：

①提取報(bào)文，包括：

a處理單元通告存取控制單元所需處理的發(fā)送描述符的基地址及個(gè)數(shù)，根據(jù)描述符的基地址和長(zhǎng)度，存取控制單元啟動(dòng)一次DMA讀請(qǐng)求描述符操作，存取控制單元向報(bào)文I/O引擎發(fā)送報(bào)文描述符。

b 存取控制單元向主存發(fā)送報(bào)文讀請(qǐng)求。

c 系統(tǒng)向存取控制單元返回報(bào)文。

②輸出調(diào)度器中的入隊(duì)操作，將報(bào)文根據(jù)其所屬流的不同優(yōu)先級(jí)插入不同隊(duì)列中，所需時(shí)間記為T(mén)pkt_in_queue。

③輸出調(diào)度器中的出隊(duì)操作，不同隊(duì)列中的報(bào)文調(diào)度后輸出，所需時(shí)間記為T(mén)pkt_out_queue。

記報(bào)文I/O的速率為Si/o，則Si/o等于總線帶寬除以每個(gè)報(bào)文在發(fā)送過(guò)程中占用的實(shí)際位數(shù)，因此:

整個(gè)系統(tǒng)的處理速率為:

min{Si/o,1/Tpkt_in_queue,1/Tpkt_out_queue}

(2)基于描述符的輸出調(diào)度方式。

若采用基于描述符的輸出調(diào)度，相關(guān)性能分析如下：

①處理單元通告存取控制單元所需處理的發(fā)送描述符的基地址及個(gè)數(shù)，根據(jù)描述符的基地址和長(zhǎng)度，存取控制單元啟動(dòng)一次DMA讀請(qǐng)求描述符操作，處理單元向存取控制單元發(fā)送報(bào)文描述符。

②輸出調(diào)度器中的入隊(duì)操作，將描述符根據(jù)其所屬流的不同優(yōu)先級(jí)插入不同隊(duì)列中，所需時(shí)間記為T(mén)desp_in_queue。

③輸出調(diào)度器中的出隊(duì)操作，不同隊(duì)列中的報(bào)文調(diào)度后輸出，所需時(shí)間記為T(mén)desp_out_queue。

④輸出調(diào)度器利用報(bào)文描述符向主存發(fā)送報(bào)文讀請(qǐng)求。

⑤處理單元向存取控制單元返回報(bào)文。

基于描述符的調(diào)度方式與基于報(bào)文的調(diào)度方式相比，報(bào)文I/O的傳輸速率不變，整個(gè)系統(tǒng)的處理速率為:

min{Si/o,1/Tdesp_in_queue,1/Tdesp_out_queue}

由于報(bào)文長(zhǎng)度遠(yuǎn)遠(yuǎn)大于報(bào)文描述符的長(zhǎng)度，因此在輸出調(diào)度器內(nèi)部的入隊(duì)以及出隊(duì)操作時(shí)，基于描述符的輸出調(diào)度方式在從主存中讀取數(shù)據(jù)以及向主存中寫(xiě)入數(shù)據(jù)時(shí)的延遲都會(huì)較小，即:

Tdesp_in_queue

Tdesp_out_queue

由于在大部分網(wǎng)絡(luò)設(shè)備調(diào)度輸出的時(shí)候，通常情況下報(bào)文I/O的傳輸速率或處理單元的處理速率是限制系統(tǒng)性能的重要因素，而調(diào)度模塊的處理速率相比快很多，因此兩種處理方式在處理速率上是近乎相等的。

而對(duì)于相同大小的輸入緩沖隊(duì)列，由于基于描述符的方式可以存放更多的報(bào)文，調(diào)度模塊可以更好地緩存突發(fā)流量，減少丟包現(xiàn)象的發(fā)生。額外緩存下來(lái)的報(bào)文會(huì)在模塊相對(duì)空閑的時(shí)候被調(diào)度輸出，這樣在系統(tǒng)遭遇突發(fā)流量的時(shí)候可以提高系統(tǒng)吞吐率。

3 接口設(shè)計(jì)以及參數(shù)配置

在實(shí)例化輸出調(diào)度IP核時(shí)，會(huì)通過(guò)參數(shù)傳遞的方式對(duì)輸出調(diào)度IP核支持的隊(duì)列數(shù)目以及每個(gè)隊(duì)列中緩存的描述符個(gè)數(shù)進(jìn)行初始化。

輸出調(diào)度IP核的外部接口如圖5所示，其中,輸出調(diào)度IP核與處理單元和存取控制單元用FIFO連接，輸出調(diào)度IP核接收來(lái)自處理單元的描述符,經(jīng)調(diào)度處理后發(fā)送到存取控制單元，存取控制單元從主存中取出報(bào)文發(fā)送。圖中的txdesRAM用于緩存報(bào)文描述符；headRAM用于存儲(chǔ)不同優(yōu)先級(jí)隊(duì)列頭部報(bào)文描述符在txdesRAM中的存儲(chǔ)位置；tailRAM則用于存儲(chǔ)不同優(yōu)先級(jí)隊(duì)列尾部報(bào)文描述符在txdesRAM中的存儲(chǔ)位置；管理模塊負(fù)責(zé)配置此輸出調(diào)度IP核可能用到的參數(shù)。

Figure 5 Interface of output scheduling IP core圖5 輸出調(diào)度IP核接口圖

輸出調(diào)度IP核與txdesRAM、tailRAM以及headRAM的接口為Alter的RAM。IP核的標(biāo)準(zhǔn)接口與處理單元和存取控制單元的接口為兩個(gè)FIFO接口。在與管理單元的接口中，test信號(hào)是檢測(cè)信號(hào)，在IP核出現(xiàn)故障時(shí)檢測(cè)其內(nèi)部狀態(tài)，test信號(hào)由IP核內(nèi)部重要狀態(tài)寄存器以及子模塊狀態(tài)機(jī)運(yùn)轉(zhuǎn)中的當(dāng)前狀態(tài)拼接而成。queue_wren為寫(xiě)有效信號(hào)，該信號(hào)置1時(shí)，寫(xiě)入的隊(duì)列發(fā)送額度有效。queue_id為欲配置的隊(duì)列編號(hào)。queue_q表示為隊(duì)列配置的發(fā)送額度。scheduling_mode信號(hào)用于調(diào)節(jié)輸出調(diào)度模塊的輸出調(diào)度算法選擇，其中00代表嚴(yán)格優(yōu)先級(jí)算法，01代表輪循算法，10代表差額輪循算法，11為保留位。

在輸出調(diào)度IP核工作之前，會(huì)先根據(jù)接收的管理模塊的配置信息為每個(gè)隊(duì)列分別設(shè)置發(fā)送額度，對(duì)txdes RAM的存儲(chǔ)空間進(jìn)行分配，對(duì)head RAM以及tail RAM中的內(nèi)容進(jìn)行初始化。

4 處理流程

本IP核支持嚴(yán)格優(yōu)先級(jí)調(diào)度算法(PQ)、輪循調(diào)度算法(RR)以及差額輪詢(xún)(DRR)輸出調(diào)度算法。嚴(yán)格優(yōu)先級(jí)調(diào)度算法(PQ)即根據(jù)隊(duì)列的不同優(yōu)先級(jí)，采取高優(yōu)先級(jí)隊(duì)列先輸出、低優(yōu)先級(jí)隊(duì)列后輸出的算法。輪循算法調(diào)度(RR)即每個(gè)隊(duì)列輸出一個(gè)報(bào)文后輪循下一個(gè)隊(duì)列輸出。差額輪詢(xún)調(diào)度算法(DRR)為每個(gè)隊(duì)列設(shè)置不同的發(fā)送額度Qi，并為每個(gè)隊(duì)列設(shè)置差額計(jì)數(shù)器DCi。系統(tǒng)每次輸出前會(huì)順序輪詢(xún)不同隊(duì)列，每次輪詢(xún)到一個(gè)隊(duì)列，會(huì)將該隊(duì)列的差額與發(fā)送額度相加，得到新的差額值。隊(duì)列每發(fā)送出去一個(gè)報(bào)文，差額值會(huì)減去報(bào)文長(zhǎng)度，當(dāng)剩余差額值小于待發(fā)送報(bào)文長(zhǎng)度時(shí)，則隊(duì)列無(wú)法輸出，輪詢(xún)下一個(gè)隊(duì)列。IP核主要的狀態(tài)存儲(chǔ)器包括：

Queue_num[i]:用于存儲(chǔ)優(yōu)先級(jí)為i的隊(duì)列的描述符個(gè)數(shù)。

Queue_state：記錄所有隊(duì)列的當(dāng)前發(fā)送狀態(tài)，第i位對(duì)應(yīng)優(yōu)先級(jí)為i的隊(duì)列，對(duì)應(yīng)位為1代表隊(duì)列有描述符需要調(diào)度輸出，為0代表無(wú)描述符需要調(diào)度輸出。

輸出調(diào)度IP核可以分為接收數(shù)據(jù)和發(fā)送數(shù)據(jù)兩個(gè)子模塊。

4.1 接收數(shù)據(jù)

接收一個(gè)報(bào)文描述符，根據(jù)描述符中的優(yōu)先級(jí)信息獲取描述符需要插入的隊(duì)列號(hào)。利用Queue_num[i]判斷對(duì)應(yīng)隊(duì)列是否已滿，若已滿，則丟棄該報(bào)文描述符。若對(duì)應(yīng)隊(duì)列還有剩余存儲(chǔ)位置，則根據(jù)描述符中所包含的報(bào)文優(yōu)先級(jí)信息訪問(wèn)tail RAM，獲取報(bào)文描述符在txdes RAM中的存儲(chǔ)位置，將報(bào)文描述符寫(xiě)入到txdes RAM中，對(duì)tail RAM存儲(chǔ)的隊(duì)列尾部存儲(chǔ)位置內(nèi)容進(jìn)行更新，將Queue_num[i]加1，Queue_state指定位置寫(xiě)1。接收、處理一個(gè)報(bào)文描述符的流程如圖6所示。

Figure 6 Flowchart of receiving data圖6 接收數(shù)據(jù)流程圖

根據(jù)接收數(shù)據(jù)的處理流程，接收數(shù)據(jù)模塊的狀態(tài)機(jī)如圖7所示。

Figure 7 State machine of receiving data圖7 接收數(shù)據(jù)模塊狀態(tài)機(jī)

receive_initial:初始化tail RAM以及txdes RAM，狀態(tài)跳轉(zhuǎn)到receive_idle。

receive_idle：若連接fifo中有數(shù)據(jù)，則從FIFO中取出一個(gè)數(shù)據(jù)，狀態(tài)跳轉(zhuǎn)到receive_readtail；若無(wú)數(shù)據(jù)，則狀態(tài)跳轉(zhuǎn)回receive_idle。

receive_readtail：根據(jù)隊(duì)列優(yōu)先級(jí)讀取tailtable中的值。

receive_stalone：讀取RAM空轉(zhuǎn)的第一個(gè)周期。

receive_staltwo：讀取RAM空轉(zhuǎn)的第二個(gè)周期。

receive_insert：根據(jù)從tailtable中讀取的數(shù)據(jù)將描述符插入到txdestable對(duì)應(yīng)位置中。

4.2 發(fā)送數(shù)據(jù)

根據(jù)隊(duì)列狀態(tài)寄存器Queue_state判斷要輸出的隊(duì)列，判斷方法如下：假設(shè)共有m條隊(duì)列，編號(hào)由1至m，上一次輪詢(xún)發(fā)送的隊(duì)列編號(hào)為m，若采用的是DRR或者RR算法，則將Queue_state循環(huán)向右移動(dòng)x位，而后由低位向高位找出第一個(gè)為1的數(shù)據(jù)位，設(shè)為y，則此次需要輪詢(xún)發(fā)送的隊(duì)列編號(hào)i=(x+y)%m。而若采用的是PQ算法，則由高位到低位選取第一個(gè)為1的數(shù)據(jù)位作為輸出的隊(duì)列號(hào)。

獲取發(fā)送隊(duì)列編號(hào)i后，將隊(duì)列的剩余差額DCi加上隊(duì)列的發(fā)送額度Qi(若不是采取DRR算法，則省略此步)，根據(jù)編號(hào)i訪問(wèn)head RAM獲取隊(duì)列頭部報(bào)文描述符在txdes RAM中的存儲(chǔ)位置，訪問(wèn)txdes RAM獲取待發(fā)送的報(bào)文描述符。若采取的不是DRR算法，則更新?tīng)顟B(tài)信息，Queue_num[i]減1，若Queue_num[i]等于0，則將Queue_state的對(duì)應(yīng)位置0，將head RAM的第i位加1，輸出報(bào)文描述符，重新選擇下一個(gè)輸出隊(duì)列進(jìn)行輸出；若采用的是DRR算法，則用報(bào)文描述符中攜帶的報(bào)文長(zhǎng)度信息與差額DCi進(jìn)行比較，若長(zhǎng)度信息大于DCi，則輪詢(xún)下一個(gè)隊(duì)列；若長(zhǎng)度信息小于DCi，則將此報(bào)文描述符發(fā)送出去，并將DCi減去報(bào)文長(zhǎng)度，Queue_num[i]減1，若Queue_num[i]等于0，還須將Queue_state的第i位置為0，而后繼續(xù)輸出次隊(duì)列的數(shù)據(jù)，直到剩余差額DCi小于待發(fā)送報(bào)文長(zhǎng)度。發(fā)送數(shù)據(jù)時(shí)的流程圖如圖8所示。

Figure 8 Flowchart of sending data圖8 發(fā)送數(shù)據(jù)流程圖

根據(jù)圖8的處理流程，發(fā)送數(shù)據(jù)模塊的狀態(tài)機(jī)如圖9所示，其狀態(tài)描述如下：

send_initial：初始化head RAM，狀態(tài)跳轉(zhuǎn)到send_idle。

send_idle：讀取Queue_state，若其為0，代表無(wú)隊(duì)列可以輸出，狀態(tài)跳轉(zhuǎn)回send_idle；若Queue_state不為0，且使用的調(diào)度算法為DRR或者RR算法，則將Queue_state循環(huán)向右移位,移動(dòng)位數(shù)如4.2節(jié)所述。

send_match：根據(jù)Queue_state選擇輸出隊(duì)列號(hào)，并讀取對(duì)應(yīng)的head_RAM值。

send_stalone：讀RAM表空轉(zhuǎn)的第一個(gè)周期，狀態(tài)跳轉(zhuǎn)到send_staltwo。

send_staltwo：讀RAM表空轉(zhuǎn)的第二個(gè)周期，若申請(qǐng)讀RAM的是send_match狀態(tài)，則狀態(tài)跳轉(zhuǎn)到send_rdhead；若讀RAM的是send_rdhead或send_output狀態(tài)，則狀態(tài)跳轉(zhuǎn)到send_output。

send_rdhead：根據(jù)從head RAM中讀取出的head位置讀取txdes RAM相應(yīng)位置，狀態(tài)跳轉(zhuǎn)到send_stalone。

Figure 10 Diagram of signal tap圖10 signal tap示意圖

send_output：若選取的是RR或PQ算法，則將報(bào)文描述符輸出，修改Queue_num以及Queue_state寄存器，狀態(tài)跳轉(zhuǎn)到send_stalthree。若采取的是DRR算法，則需要根據(jù)DCi與待發(fā)送報(bào)文的長(zhǎng)度進(jìn)行比較，如果DCi大于待發(fā)送報(bào)文長(zhǎng)度，但是發(fā)送出當(dāng)前描述符后隊(duì)列中無(wú)剩余報(bào)文描述符，則將報(bào)文描述符發(fā)送并修改狀態(tài)寄存器Queue_num以及Queue_state后，狀態(tài)跳轉(zhuǎn)到send_stalthree；若DCi小于待發(fā)送報(bào)文長(zhǎng)度，則不發(fā)送報(bào)文描述符，狀態(tài)跳轉(zhuǎn)到send_stalthree。如果DCi大于報(bào)文長(zhǎng)度，則將描述符輸出，修改Queue_num以及Queue_state寄存器，讀取隊(duì)列的下一個(gè)報(bào)文描述符進(jìn)行輸出判定，狀態(tài)跳轉(zhuǎn)到send_stalone。

send_stalthree：空轉(zhuǎn)一個(gè)時(shí)鐘周期，否則send_idle狀態(tài)里對(duì)Queue_state寄存器的移位操作會(huì)發(fā)生錯(cuò)誤，狀態(tài)跳轉(zhuǎn)回send_idle。

Figure 9 State machine of sending data圖9 發(fā)送數(shù)據(jù)模塊狀態(tài)機(jī)

5 實(shí)驗(yàn)結(jié)果與分析

我們使用Altera FPGA[11](現(xiàn)場(chǎng)可編程門(mén)陣,Stratix IV EP4SGX180KF40C2)實(shí)現(xiàn)了基于描述符的輸出調(diào)度IP軟核，通過(guò)使用QuartusII硬件編程工具對(duì)代碼進(jìn)行分析，綜合分析其所占用的邏輯資源情況，如表2所示。

Table 2 Logic resource consume of descriptor-based output scheduling IP core

圖10給出了系統(tǒng)運(yùn)行時(shí)QuartusII中的signal tap圖，其中numqueue對(duì)應(yīng)隊(duì)列中報(bào)文描述符的個(gè)數(shù)，tdma_des_wr表示輸出FIFO的寫(xiě)信號(hào)，當(dāng)該信號(hào)置高時(shí)，報(bào)文被調(diào)度輸出。

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

針對(duì)基于報(bào)文的輸出調(diào)度方式占用存儲(chǔ)空間大的缺點(diǎn),本文提出了一種基于描述符的報(bào)文輸出調(diào)度方式，給出了這種報(bào)文處理模式的基本流程，并通過(guò)理論分析證明基于描述符的輸出調(diào)度方式可以在大量降低存儲(chǔ)空間需求的同時(shí)，保證系統(tǒng)的性能。在此基礎(chǔ)上，對(duì)輸出調(diào)度IP核進(jìn)行了設(shè)計(jì)實(shí)現(xiàn)。該IP可以通過(guò)參數(shù)配置多種常用輸出調(diào)度算法，基于FPGA的實(shí)驗(yàn)驗(yàn)證了所設(shè)計(jì)實(shí)現(xiàn)的基于描述符的輸出調(diào)度IP核在實(shí)際應(yīng)用中的功能正確性和可行性。

[1] Zeng Liang-zhao,Benatallah B, Ngu A H H, et al. QoS-aware middleware for web services composition[J]. IEEE Transactions on Software Engineering,2004,30(5):311-327.

[2] Ran Shu-ping. A model for web services discovery with QoS[J]. ACM SIGecom Exchanges, 2003,4(1):1-10.

[3] Shreedhar M, Varghese G. Efficient fair queuing using deficit round robin[J]. ACM Transactions on Networking, 1996,4(3):375-385.

[4] Zhang Li-xia, VirtualClock:A new traffic control algorithm for packet switching networks[C]∥Proc of the ACM Symposium on Communications Architectures&Protocols, 1990:19-29.

[5] Demers A, Keshav S, Shenker S. Analysis and simulation of a fair queueing algorithm[C]∥Proc of SIGCOMM’89, 1989:1-12.

[6] Bennett J C R, Zhang Hui. WF2Q:Worst-case fair weighted fair queueing[C]∥Proc of INFOCOM’96, 1996:120-128.

[7] Ghodsi A, Sekar V, Zaharia M, et al. Multi-resource fair queueing for packet processing[C]∥Proc of SIGCOMM’12, 2012:1-12.

[8] Chauhan P,Clarke E M,Lu Y,et al.Verifying IP-core based system-on-chip designs[C]∥Proc of the 12th Annual IEEE International ASIC/SOC Conference, 1999:27-31.

[9] Varma P, Bhatia S. A structured test re-use methodology for core-based system chips[C]∥Proc of International Test Conference, 1998:294-302.

[10] Appenzeller G,Keslassy I,McKeown N.Sizing router buffer[C]∥Proc of SIGCOMM’04, 2004:284-292.

[11] Wang Cheng,Cai Hai-ning,Wu Ji-hua. The design of altera FPGA/CPLD[M]. Beijing:Posts & Telecom Press, 2005.(in Chinese)

附中文參考文獻(xiàn)：

[11] 王誠(chéng)，蔡海寧，吳繼華.Altera FPGA/CPLD設(shè)計(jì)[M]. 北京：人民郵電出版社，2005.

ZHAO Guo-hong,born in 1965,research fellow,his research interests include network communication, and routing and switching.

胡勇庭(1989-),男,黑龍江牡丹江人，碩士生，研究方向?yàn)榫W(wǎng)絡(luò)處理器、路由與交換。E-mail:yongtinghu@163.com

HU Yong-ting,born in 1989,MS candidate,his research interests include network processor, and routing and switching.

李韜(1983-),男,安徽蕭縣人，博士，助理研究員，研究方向?yàn)榫W(wǎng)絡(luò)處理器和網(wǎng)絡(luò)通信。E-mail:Taoli.nudt@gmail.com

LI Tao,born in 1983,PhD,assistant researcher,his research interests include network processor, and network communication.

孫志剛(1973-),男,江蘇東海人，博士，研究員，研究方向?yàn)橄乱淮W(wǎng)絡(luò)和高性能互連。E-mail:sunzhigang@263.com

SUN Zhi-gang,born in 1973,PhD,research fellow,his research interests include next generation network，and high performance interconnection.

Design and implementation of output scheduling IP core based on packet descriptor

ZHAO Guo-hong,HU Yong-ting,LI Tao,SUN Zhi-gang
(College of Computer,National University of Defense Technology,Changsha 410073,China)

Output scheduling is an important QoS technique. The packet-based output scheduling technique is widely used for QoS component due to its simplicity. However, large on-chip packet buffer required by the technique increases the chip area and production cost. Aiming at the problem, a novel output scheduling technique based on packet descriptor is proposed. The descriptor-based output scheduling technique can reduce storage space requirements without degrading system performance. The design and implementation of the output scheduling IP core based on this descriptor-based technique is also introduced, including the external interface of the IP core, the parameter configuration and the internal processing procedure. The experiments carried out on FPGA demonstrate the feasibility of the IP core.

QoS;output scheduling;descriptor;IP core

2013-07-05;

2013-10-16

國(guó)家973計(jì)劃資助項(xiàng)目(2009CB320503);國(guó)家863計(jì)劃資助項(xiàng)目(2011AA01A10,2011AA01A103,2013AA013505);國(guó)家自然科學(xué)基金資助項(xiàng)目(61202483)

1007-130X(2014)03-0426-07

TP393.02

A

10.3969/j.issn.1007-130X.2014.03.009

趙國(guó)鴻(1965-),男,湖南婁底人，研究員，研究方向?yàn)榫W(wǎng)絡(luò)通信、路由與交換。E-mail:ghzhao@nudt.edu.cn

通信地址：410073 湖南省長(zhǎng)沙市國(guó)防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院662教研室

Address:Section 662,College of Computer,National University of Defense Technology,Changsha 410073,Hunan,P.R.China