賀孟

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

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

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

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

1 流量控制技術(shù)

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

1.1 漏桶算法和令牌桶算法

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

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

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

1.2 虛調(diào)度算法

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

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

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

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

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

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

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

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

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

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

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

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

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

2 流量控制模型

首先給出應用該控制器的工作條件：

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

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

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

圖3 K值圖Fig.3 K value figure

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 FPGA資源利用報告Tab.1 FPGA resource utilization report

4 結(jié)論

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

[1]張軼博，李偉，雷振明.一種改進的以太網(wǎng)流控算法[J].計算機工程與應用，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ù)中令牌桶算法實現(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]牛淼，蔣林.基于多令牌桶流量整形算法的研究與實現(xiàn)[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]王喆，劉暉，羅進文，等.GCRA及其在PCR中的應用研究與實現(xiàn)[J].蘭州交通大學學報：自然科學版，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)絡中VBR復用器的硬件實現(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è)務量整形器的實現(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.