基于FPGA的多通道流量控制研究與實(shí)現(xiàn)

賀孟

（中國電子科技集團(tuán)公司第三十研究所 四川 成都 610041）

在網(wǎng)絡(luò)通信系統(tǒng)中，為了控制網(wǎng)絡(luò)和信道資源的使用，避免網(wǎng)絡(luò)和信道出現(xiàn)瓶頸，特別是在多個(gè)連接共享網(wǎng)絡(luò)信道資源情況下，對每一個(gè)連接合理分配其所需的帶寬，進(jìn)行業(yè)務(wù)量管理的作用就會(huì)更加重要。有關(guān)業(yè)務(wù)帶寬分配有兩種方法：定數(shù)論的多路復(fù)用和統(tǒng)計(jì)的多路復(fù)用。其中按照用戶要求的比特率特點(diǎn)將業(yè)務(wù)劃分為以下幾種主要的類型：恒定比特率（CBR），變比特率（VBR），不指明比特率，可用比特率。

為了適應(yīng)這些不同業(yè)務(wù)的流量控制要求，各種流量控制算法被提出和改進(jìn)。這些算法利用軟件重用性在CPU中實(shí)現(xiàn)起來比較容易，但同時(shí)也是以犧牲實(shí)時(shí)性和增加CPU工作負(fù)荷為代價(jià)的，尤其是在系統(tǒng)CPU工作負(fù)荷大的情況下，用軟件實(shí)現(xiàn)流量控制算法將大大降低流控單元實(shí)時(shí)性，這樣在多個(gè)連接共享網(wǎng)絡(luò)資源時(shí)，將很容易造成信道資源浪費(fèi)，造成擁塞，降低網(wǎng)絡(luò)性能。而隨著EDA技術(shù)的發(fā)展，使用FPGA來實(shí)現(xiàn)流量控制器，既可滿足實(shí)時(shí)流控的要求，也能顯著提高系統(tǒng)性能。

在這篇文章中，首先介紹了常見的幾種流量控制算法，然后針對FPGA的特點(diǎn)提出了一種基于矩陣虛調(diào)度算法的令牌桶流量控制機(jī)制，最后給出了FPGA實(shí)現(xiàn)的結(jié)果。

1 流量控制技術(shù)

流量控制技術(shù)可以確保用戶以合理的速率傳輸數(shù)據(jù)，是預(yù)防網(wǎng)絡(luò)擁塞提高網(wǎng)絡(luò)性能的一種方法，應(yīng)用不同的流量控制策略可以解決包交換網(wǎng)絡(luò)中諸如流分類問題隊(duì)列管理問題，隊(duì)列調(diào)度問題及流量整形問題。文中提出了一種矩陣虛調(diào)度算法，并結(jié)合令牌控制技術(shù)實(shí)現(xiàn)了針對包傳輸和包交換的高效流量控制技術(shù)。

1.1 漏桶算法和令牌桶算法

漏桶算法是比較常見的一種流量整形算法，該算法強(qiáng)行限制數(shù)據(jù)的傳輸速率，即數(shù)據(jù)傳輸速率是固定的參數(shù)，顯然這種算法不能有效使用網(wǎng)絡(luò)資源，例如當(dāng)網(wǎng)絡(luò)中沒有發(fā)生擁塞時(shí)，漏桶算法不能使某一個(gè)單獨(dú)的數(shù)據(jù)流突發(fā)到端口速率。因此漏桶算法對于存在突發(fā)特性的流量來說缺乏效率[1]。

在漏桶算法的基礎(chǔ)上提出了令牌桶算法。令牌桶被看作是一個(gè)存放令牌的容器，對其預(yù)先設(shè)定一定的容量，按照預(yù)先設(shè)定的速率向桶中放置令牌，當(dāng)桶中令牌滿時(shí)多余令牌溢出，令牌桶中令牌量不再增加。與傳統(tǒng)的漏桶算法比較，令牌桶算法的優(yōu)點(diǎn)是能夠限制突發(fā)的流量使數(shù)據(jù)包以比較均勻的速度向外發(fā)送[2]。而基于令牌桶算法的流量控制的效果主要由數(shù)據(jù)流隊(duì)列的令牌分配算法和流量輸出調(diào)度算法決定，而為了支持多隊(duì)列的網(wǎng)絡(luò)輸出要求，又提出了多令牌桶算法來滿足流量控制需求[3]。

硬件實(shí)現(xiàn)這兩種算法都較軟件困難，一般是采用對信道進(jìn)行多令牌調(diào)度和對業(yè)務(wù)源進(jìn)行漏桶控制的算法。多令牌調(diào)度缺點(diǎn)是調(diào)度控制復(fù)雜，漏桶控制缺點(diǎn)是信道利用率不高。當(dāng)需要服務(wù)的通道和隊(duì)列數(shù)很多時(shí)，這兩種算法的實(shí)現(xiàn)都存在資源利用龐大，系統(tǒng)工作頻率不高，設(shè)計(jì)難度大的缺點(diǎn)。

1.2 虛調(diào)度算法

虛調(diào)度算法是通用信元速率算法（GCRA）的一種。GCRA由ITU-T I.371定義，用于判斷用戶流量或網(wǎng)絡(luò)流量是否遵守連接合同，即是否滿足一致性。GCRA有兩種等效的算法，分別稱為虛調(diào)度算法VS（Virtual Scheduling）和連續(xù)狀態(tài)漏桶算法CLB （Continuous stateLeakyBucket）。GCRA帶有2個(gè)參數(shù):增量 I（Increment）和允許增量極限 L（Limit）[4]。

本文將通用的虛調(diào)度算法加以改進(jìn)，將其應(yīng)用到包傳輸和交換網(wǎng)絡(luò)的輸出端，算法原理如圖1所示。

圖1 虛調(diào)度算法模型Fig.1 Model of the virtual scheduling algorithm

1）初始化，當(dāng)?shù)趎組包發(fā)起輸出請求時(shí)，按輸出隊(duì)列要求輸出，同時(shí)記錄每包的發(fā)送時(shí)刻 ta（n），tb（n）。 根據(jù)相應(yīng)的流量參數(shù) I和 L，計(jì)算每組包的 n+1包發(fā)送時(shí)刻 ta（n）+I，tb（n）+I。

2）在時(shí)刻 ta（n）+I，tb（n）+I檢查內(nèi)存中有無待發(fā)送包，有則發(fā)送并記錄發(fā)送時(shí)刻 ta（n+1），tb（n+1）和下一包發(fā)送時(shí)刻 ta（n+1）+I，tb（n+1）+I無則返回初始化。

如在發(fā)送時(shí)刻有多個(gè)序列的包請求發(fā)送，ta（n）+I=tb（n）+I，按隊(duì)列輸出要求依次發(fā)送，同時(shí)在每個(gè)序列包發(fā)送時(shí)間檢查下一序列包發(fā)送間隔是否在包發(fā)送極限要求內(nèi)，即tb（n）+T≤tb（n）+L，此處T為b序列的第二包實(shí)際發(fā)送時(shí)刻，如在發(fā)送極限要求內(nèi)則發(fā)送，如超出發(fā)送極限要求，則提升b序列的隊(duì)列發(fā)送優(yōu)先級。

1.3 矩陣虛調(diào)度令牌桶控制算法

針對包傳輸和交換網(wǎng)絡(luò)中需支持隊(duì)列和通道數(shù)越來越多的情況，令牌桶算法已不能滿足網(wǎng)絡(luò)的鏈路輸出要求，而且硬件實(shí)現(xiàn)非常不易。

而采用虛調(diào)度算法進(jìn)行流量參數(shù)控制，一種辦法是為每個(gè)隊(duì)列建立虛調(diào)度算法單元，另一種辦法是采用流的方式對所有隊(duì)列進(jìn)行流量參數(shù)計(jì)算。前一種當(dāng)需要服務(wù)的序列通道數(shù)很多時(shí)將消耗大量的資源，且系統(tǒng)工作頻率較低，后一種雖然消耗資源少工作頻率高但計(jì)算周期長，信道資源利用率低。

FPGA非常適于各種算數(shù)運(yùn)算和并行處理，同時(shí)其邏輯結(jié)構(gòu)非常適于完成矩陣運(yùn)算，依據(jù)這個(gè)特性，文中提出了矩陣虛調(diào)度算法的令牌桶控制機(jī)制，非常易于實(shí)現(xiàn)極大數(shù)量隊(duì)列輸出的流量控制需求的包傳輸和交換網(wǎng)絡(luò)QoS算法。

矩陣虛調(diào)度算法的模型如圖2，矩陣的行對應(yīng)帶有虛調(diào)度算法單元的令牌，列對應(yīng)待輸出包。其工作原理就是當(dāng)多個(gè)隊(duì)列的數(shù)據(jù)包或信元進(jìn)入交換網(wǎng)絡(luò)時(shí)，即為每個(gè)隊(duì)列動(dòng)態(tài)分配一個(gè)帶有虛調(diào)度算法的令牌，矩陣會(huì)在一個(gè)很短的時(shí)間段里完成所有隊(duì)列的虛調(diào)度算法的計(jì)算，根據(jù)計(jì)算結(jié)果來完成令牌桶的動(dòng)態(tài)調(diào)度，算法周期短，只要輸出信道允許，幾乎可以實(shí)現(xiàn)接近滿帶寬的信道利用。

圖2 矩陣虛調(diào)度算法令牌桶調(diào)度模型Fig.2 Matrix virtual scheduling calculate decree token bucket scheduling model

該算法的特點(diǎn)是服務(wù)的通道和隊(duì)列數(shù)量大，信道利用率極高，硬件資源消耗小，擴(kuò)展度高。

2 流量控制模型

首先給出應(yīng)用該控制器的工作條件：

參數(shù)定義：n為輸入連接數(shù)；Pi某個(gè)連接的峰值數(shù)據(jù)速率（bps）；M 控制器最大輸出數(shù)據(jù)速率（bps）；αi某個(gè)連接平均傳輸時(shí)間和總的傳輸時(shí)間比；

圖3為并發(fā)256個(gè)連接情況下的K值圖，由圖可知K≥1是定數(shù)論的多路復(fù)用，K＞1是統(tǒng)計(jì)的多路復(fù)用。同時(shí)，平均輸入信源到達(dá)率應(yīng)小于控制器的服務(wù)率，即ρ≤1，否則信道將被堵塞[5]。

同時(shí)由公式2可知，在輸出總帶寬一定，連接峰值數(shù)據(jù)速率一定情況下，有效降低傳輸時(shí)間比α，能使流量控制器輸入連接數(shù)提高。

圖3 K值圖Fig.3 K value figure

事實(shí)上，采用窗口調(diào)度和業(yè)務(wù)源漏桶方法，即便上述條件滿足，由于輸入信源的高突發(fā)性和高離散性，仍會(huì)存在控制器輸出空閑而緩存信元不能及時(shí)送出的情況。這里利用FPGA的并行運(yùn)算和流水線設(shè)計(jì)的優(yōu)勢，提出了一個(gè)結(jié)合令牌桶調(diào)度機(jī)制，入口出口統(tǒng)計(jì)的GCRA虛調(diào)度算法矩陣設(shè)計(jì)模型，幾乎達(dá)到了多路復(fù)用利用率的理論最大值。

整個(gè)流量控制模型分為3個(gè)單元：GCRA算法矩陣單元；令牌桶調(diào)度輸出隊(duì)列單元；信道統(tǒng)計(jì)計(jì)算單元。

采用令牌桶調(diào)度的考慮是輸入信源連接的數(shù)量可能非常大，比如ATM交換網(wǎng)路服務(wù)的虛連接數(shù)可以為幾K條，如果實(shí)現(xiàn)對所有連接獨(dú)立流控，F(xiàn)PGA的資源不可能滿足，因此采用令牌桶調(diào)度機(jī)制來動(dòng)態(tài)滿足輸入多連接的流控需求，到達(dá)控制器的輸入信源只有從令牌桶獲得令牌才能進(jìn)入數(shù)據(jù)緩存待發(fā)，理論上可以滿足無數(shù)條輸入連接的流控需求。

GCRA虛調(diào)度算法的設(shè)計(jì)方案是：某條合法連接的輸入信源進(jìn)入網(wǎng)絡(luò)后，就會(huì)從令牌桶得到一個(gè)令牌，并將數(shù)據(jù)存入數(shù)據(jù)緩存。

該令牌對應(yīng)的連接的數(shù)據(jù)發(fā)送間隔應(yīng)當(dāng)符合其期望的發(fā)送間隔，即以該條連接發(fā)送信元時(shí)記下該信元的發(fā)送時(shí)刻，且以此時(shí)刻為基準(zhǔn)計(jì)算出該連接下一個(gè)信元應(yīng)該發(fā)送的理論時(shí)刻值，在理論發(fā)送的時(shí)刻的抖動(dòng)抖動(dòng)容限內(nèi)檢查緩存中是否有該條連接的待發(fā)信元，有則加入發(fā)送隊(duì)列。

如在該時(shí)刻有多個(gè)令牌滿足發(fā)送條件，則根據(jù)優(yōu)先級決定發(fā)送順序。如果無待發(fā)信元，則清除該令牌和連接的對應(yīng)關(guān)系，將該令牌重新放入令牌桶待分配。由此可見，令牌的產(chǎn)生速率不是固定的，而是跟隨輸入信源到達(dá)率變化的。

信道統(tǒng)計(jì)計(jì)算單元是對出入口的連接數(shù)據(jù)速率進(jìn)行統(tǒng)計(jì)計(jì)算，以監(jiān)測流量控制器是否滿足業(yè)務(wù)量管理要求，并將統(tǒng)計(jì)結(jié)果反饋回基本算法單元，以達(dá)到動(dòng)態(tài)調(diào)整服務(wù)隊(duì)列的流量的效果。

3 多通道流量控制IP核的實(shí)現(xiàn)

該流量控制IP核的原理框圖如圖4所示，除用于數(shù)據(jù)緩存單元的SSRAM外，其他全部在FPGA里實(shí)現(xiàn)。基本設(shè)計(jì)參數(shù)為最大輸入連接數(shù)n=4 096，令牌桶容量為256個(gè)，最小量化刻度為16個(gè)系統(tǒng)時(shí)鐘周期。

圖4 多通道流量控制IP原理圖Fig.4 Multi-channel flow control IP principle diagram

首先針對每個(gè)連接都建立一個(gè)配置參數(shù)表，該表存放該連接的流控參數(shù)權(quán)重等信息，該表可以重構(gòu)動(dòng)態(tài)調(diào)整流量參數(shù)以實(shí)現(xiàn)VBR，當(dāng)一個(gè)合法連接的輸入信源進(jìn)入網(wǎng)絡(luò)后，令牌桶分配單元將為該連接分配一個(gè)令牌，同時(shí)根據(jù)配置參數(shù)表的值建立該令牌的運(yùn)行參數(shù)表。

根據(jù)FPGA并行運(yùn)算的特點(diǎn)，建立了一個(gè)16×16的GCRA算法矩陣，采用分時(shí)復(fù)用和流水線設(shè)計(jì)方法，只需16個(gè)基本GCRA算法單元和16個(gè)時(shí)鐘周期就可以同時(shí)對256個(gè)令牌完成GCRA運(yùn)算，判斷出有效的令牌，再根據(jù)令牌的運(yùn)行參數(shù)表決定下一個(gè)被服務(wù)的令牌，并將該令牌對應(yīng)的虛連接數(shù)據(jù)從數(shù)據(jù)緩存單元提出，這些運(yùn)算調(diào)度采用流水線設(shè)計(jì)都可以在20個(gè)系統(tǒng)時(shí)鐘發(fā)送周期內(nèi)完成，這樣在當(dāng)前信元發(fā)送時(shí)，也就可以計(jì)算出下一個(gè)要服務(wù)的令牌，同時(shí)該令牌的數(shù)據(jù)已在輸出FIFO中準(zhǔn)備好，只要信道空閑就可立即發(fā)送下一個(gè)令牌信元，從而最大限度的利用信道資源。

定時(shí)器提供整個(gè)模塊的定時(shí)和節(jié)拍控制信息，所有的子單元必須嚴(yán)格按照定時(shí)器給出的信息運(yùn)行以保證時(shí)序的準(zhǔn)確。

GCRA的基本算法單元是高度模塊化，只需在頂層程序中修改參數(shù)就可很方便的修改基本單元數(shù)量和運(yùn)行節(jié)拍數(shù)，從而改變矩陣的結(jié)構(gòu)，以實(shí)現(xiàn)更靈活的令牌桶，滿足各種應(yīng)用需求[6]。原理框圖如圖5所示。

圖5 GCRA算法單元原理框圖Fig.5 Unit GCRA algorithm principle block diagram

出口入口統(tǒng)計(jì)單元對出入口數(shù)據(jù)速率進(jìn)行統(tǒng)計(jì)計(jì)算，并將結(jié)果通過主機(jī)接口報(bào)給上層，當(dāng)出現(xiàn)輸入信源到達(dá)率大于控制器的服務(wù)率，數(shù)據(jù)緩存即將溢出時(shí)，既可通知上層軟件干預(yù)，也可根據(jù)配置參數(shù)表的優(yōu)先級控制字，阻塞低優(yōu)先級的輸入連接。

根據(jù)該方案編寫了FPGA程序，F(xiàn)PGA設(shè)計(jì)采用vhdl語言，使用Synopsys公司的synplify pro編譯出網(wǎng)表文件，該網(wǎng)表文件可以被后端工具直接調(diào)用，在Mentor公司的Questasim環(huán)境下完成了功能仿真和驗(yàn)證。

設(shè)計(jì)選用了Xilinx公司的spartan-3adsp系列和Virtex-5系列芯片分別進(jìn)行了電路物理驗(yàn)證，實(shí)現(xiàn)了一個(gè)16×16的算法矩陣的流量控制IP核，表1是不同器件平臺的資源消耗情況。由于該IP模塊是全語言設(shè)計(jì)，并進(jìn)行了高度模塊化，用戶只需修改相應(yīng)參數(shù)就可以針對不同的網(wǎng)絡(luò)隊(duì)列數(shù)量和器件平臺資源大小改變矩陣規(guī)模，以適應(yīng)實(shí)際需求。

表1 FPGA資源利用報(bào)告Tab.1 FPGA resource utilization report

4 結(jié)論

文中在研究分析GCRA虛調(diào)度算法的基礎(chǔ)上，設(shè)計(jì)了一個(gè)GCRA算法矩陣，并結(jié)合令牌桶調(diào)度機(jī)制在FPGA中實(shí)現(xiàn)了一個(gè)通用的全硬件多通道流量控制IP核。并在一型網(wǎng)絡(luò)接入設(shè)備加以應(yīng)用。該流量控制IP核具有邏輯精簡、運(yùn)算效率高、占用資源少、模塊化程度高，可擴(kuò)展性好的特點(diǎn)，可以很方便的嵌入各種網(wǎng)絡(luò)通信交換和接入設(shè)計(jì)中。

[1]張軼博，李偉，雷振明.一種改進(jìn)的以太網(wǎng)流控算法[J].計(jì)算機(jī)工程與應(yīng)用，2005（2）:149-153.ZHANG Yi-bo，LI Wei，LEI Zhen-ming.RD-RACE:An improved rate control mechanism in ethernet[J].Computer Engineering and Applications，2005（2）:149-153.

[2]李曉利，郭宇春.QoS技術(shù)中令牌桶算法實(shí)現(xiàn)方式比較[J].中興通信技術(shù)，2007，13（7）:56-60.LI Xiao-li，GUO Yu-chun.Comparison between token bucket algorithms in QoS technology[J].ZTE Communications，2007，13（7）:56-60.

[3]牛淼，蔣林.基于多令牌桶流量整形算法的研究與實(shí)現(xiàn)[J].微電子學(xué)與計(jì)算機(jī)，2011，28（11）:110-113.NIU Miao，JIANG Lin.Research and design based on multitoken bucket traffic shaping algorithm[J].Microelectronics&Computer，2011，28（11）:110-113.

[4]王喆，劉暉，羅進(jìn)文，等.GCRA及其在PCR中的應(yīng)用研究與實(shí)現(xiàn)[J].蘭州交通大學(xué)學(xué)報(bào)：自然科學(xué)版，2005，24（6）:79-82.WANG Zhe，LIU Hui，LUO Jin-wen，et al.Study of GCRA and its application in PCR[J].Journal of Lanzhou Jiaotong University：NaturalSciences，2005，24（6）:79-82.

[5]汪一鳴，吳紅衛(wèi)，翁桂榮，等.ATM網(wǎng)絡(luò)中VBR復(fù)用器的硬件實(shí)現(xiàn)[J].通信技術(shù)，2002（2）:49-52.WANGYi-ming，WUHong-wei，WENGGui-rong，etal.Hardware implementation of VBR multiplexer in ATM networks[J].Communications Technology，2002（2）:49-52.

[6]劉宇.異步傳輸模式測試儀中業(yè)務(wù)量整形器的實(shí)現(xiàn)[J].國外電子測量技術(shù)，2008，27（4）:21-22.LIU Yu.Realization of traffic shaperin ATM tester[J].Foreign Electronic Measurement Technology，2008，27（4）:21-22.