基于FPGA的多通道流量控制研究与实现

贺孟

（中国电子科技集团公司第三十研究所 四川 成都 610041）

在网络通信系统中，为了控制网络和信道资源的使用，避免网络和信道出现瓶颈，特别是在多个连接共享网络信道资源情况下，对每一个连接合理分配其所需的带宽，进行业务量管理的作用就会更加重要。有关业务带宽分配有两种方法：定数论的多路复用和统计的多路复用。其中按照用户要求的比特率特点将业务划分为以下几种主要的类型：恒定比特率（CBR），变比特率（VBR），不指明比特率，可用比特率。

为了适应这些不同业务的流量控制要求，各种流量控制算法被提出和改进。这些算法利用软件重用性在CPU中实现起来比较容易，但同时也是以牺牲实时性和增加CPU工作负荷为代价的，尤其是在系统CPU工作负荷大的情况下，用软件实现流量控制算法将大大降低流控单元实时性，这样在多个连接共享网络资源时，将很容易造成信道资源浪费，造成拥塞，降低网络性能。而随着EDA技术的发展，使用FPGA来实现流量控制器，既可满足实时流控的要求，也能显著提高系统性能。

在这篇文章中，首先介绍了常见的几种流量控制算法，然后针对FPGA的特点提出了一种基于矩阵虚调度算法的令牌桶流量控制机制，最后给出了FPGA实现的结果。

1 流量控制技术

流量控制技术可以确保用户以合理的速率传输数据，是预防网络拥塞提高网络性能的一种方法，应用不同的流量控制策略可以解决包交换网络中诸如流分类问题队列管理问题，队列调度问题及流量整形问题。文中提出了一种矩阵虚调度算法，并结合令牌控制技术实现了针对包传输和包交换的高效流量控制技术。

1.1 漏桶算法和令牌桶算法

漏桶算法是比较常见的一种流量整形算法，该算法强行限制数据的传输速率，即数据传输速率是固定的参数，显然这种算法不能有效使用网络资源，例如当网络中没有发生拥塞时，漏桶算法不能使某一个单独的数据流突发到端口速率。因此漏桶算法对于存在突发特性的流量来说缺乏效率[1]。

在漏桶算法的基础上提出了令牌桶算法。令牌桶被看作是一个存放令牌的容器，对其预先设定一定的容量，按照预先设定的速率向桶中放置令牌，当桶中令牌满时多余令牌溢出，令牌桶中令牌量不再增加。与传统的漏桶算法比较，令牌桶算法的优点是能够限制突发的流量使数据包以比较均匀的速度向外发送[2]。而基于令牌桶算法的流量控制的效果主要由数据流队列的令牌分配算法和流量输出调度算法决定，而为了支持多队列的网络输出要求，又提出了多令牌桶算法来满足流量控制需求[3]。

硬件实现这两种算法都较软件困难，一般是采用对信道进行多令牌调度和对业务源进行漏桶控制的算法。多令牌调度缺点是调度控制复杂，漏桶控制缺点是信道利用率不高。当需要服务的通道和队列数很多时，这两种算法的实现都存在资源利用庞大，系统工作频率不高，设计难度大的缺点。

1.2 虚调度算法

虚调度算法是通用信元速率算法（GCRA）的一种。GCRA由ITU-T I.371定义，用于判断用户流量或网络流量是否遵守连接合同，即是否满足一致性。GCRA有两种等效的算法，分别称为虚调度算法VS（Virtual Scheduling）和连续状态漏桶算法CLB （Continuous stateLeakyBucket）。GCRA带有2个参数:增量 I（Increment）和允许增量极限 L（Limit）[4]。

本文将通用的虚调度算法加以改进，将其应用到包传输和交换网络的输出端，算法原理如图1所示。

图1 虚调度算法模型Fig.1 Model of the virtual scheduling algorithm

1）初始化，当第n组包发起输出请求时，按输出队列要求输出，同时记录每包的发送时刻 ta（n），tb（n）。 根据相应的流量参数 I和 L，计算每组包的 n+1包发送时刻 ta（n）+I，tb（n）+I。

2）在时刻 ta（n）+I，tb（n）+I检查内存中有无待发送包，有则发送并记录发送时刻 ta（n+1），tb（n+1）和下一包发送时刻 ta（n+1）+I，tb（n+1）+I无则返回初始化。

如在发送时刻有多个序列的包请求发送，ta（n）+I=tb（n）+I，按队列输出要求依次发送，同时在每个序列包发送时间检查下一序列包发送间隔是否在包发送极限要求内，即tb（n）+T≤tb（n）+L，此处T为b序列的第二包实际发送时刻，如在发送极限要求内则发送，如超出发送极限要求，则提升b序列的队列发送优先级。

1.3 矩阵虚调度令牌桶控制算法

针对包传输和交换网络中需支持队列和通道数越来越多的情况，令牌桶算法已不能满足网络的链路输出要求，而且硬件实现非常不易。

而采用虚调度算法进行流量参数控制，一种办法是为每个队列建立虚调度算法单元，另一种办法是采用流的方式对所有队列进行流量参数计算。前一种当需要服务的序列通道数很多时将消耗大量的资源，且系统工作频率较低，后一种虽然消耗资源少工作频率高但计算周期长，信道资源利用率低。

FPGA非常适于各种算数运算和并行处理，同时其逻辑结构非常适于完成矩阵运算，依据这个特性，文中提出了矩阵虚调度算法的令牌桶控制机制，非常易于实现极大数量队列输出的流量控制需求的包传输和交换网络QoS算法。

矩阵虚调度算法的模型如图2，矩阵的行对应带有虚调度算法单元的令牌，列对应待输出包。其工作原理就是当多个队列的数据包或信元进入交换网络时，即为每个队列动态分配一个带有虚调度算法的令牌，矩阵会在一个很短的时间段里完成所有队列的虚调度算法的计算，根据计算结果来完成令牌桶的动态调度，算法周期短，只要输出信道允许，几乎可以实现接近满带宽的信道利用。

图2 矩阵虚调度算法令牌桶调度模型Fig.2 Matrix virtual scheduling calculate decree token bucket scheduling model

该算法的特点是服务的通道和队列数量大，信道利用率极高，硬件资源消耗小，扩展度高。

2 流量控制模型

首先给出应用该控制器的工作条件：

参数定义：n为输入连接数；Pi某个连接的峰值数据速率（bps）；M 控制器最大输出数据速率（bps）；αi某个连接平均传输时间和总的传输时间比；

图3为并发256个连接情况下的K值图，由图可知K≥1是定数论的多路复用，K＞1是统计的多路复用。同时，平均输入信源到达率应小于控制器的服务率，即ρ≤1，否则信道将被堵塞[5]。

同时由公式2可知，在输出总带宽一定，连接峰值数据速率一定情况下，有效降低传输时间比α，能使流量控制器输入连接数提高。

图3 K值图Fig.3 K value figure

事实上，采用窗口调度和业务源漏桶方法，即便上述条件满足，由于输入信源的高突发性和高离散性，仍会存在控制器输出空闲而缓存信元不能及时送出的情况。这里利用FPGA的并行运算和流水线设计的优势，提出了一个结合令牌桶调度机制，入口出口统计的GCRA虚调度算法矩阵设计模型，几乎达到了多路复用利用率的理论最大值。

整个流量控制模型分为3个单元：GCRA算法矩阵单元；令牌桶调度输出队列单元；信道统计计算单元。

采用令牌桶调度的考虑是输入信源连接的数量可能非常大，比如ATM交换网路服务的虚连接数可以为几K条，如果实现对所有连接独立流控，FPGA的资源不可能满足，因此采用令牌桶调度机制来动态满足输入多连接的流控需求，到达控制器的输入信源只有从令牌桶获得令牌才能进入数据缓存待发，理论上可以满足无数条输入连接的流控需求。

GCRA虚调度算法的设计方案是：某条合法连接的输入信源进入网络后，就会从令牌桶得到一个令牌，并将数据存入数据缓存。

该令牌对应的连接的数据发送间隔应当符合其期望的发送间隔，即以该条连接发送信元时记下该信元的发送时刻，且以此时刻为基准计算出该连接下一个信元应该发送的理论时刻值，在理论发送的时刻的抖动抖动容限内检查缓存中是否有该条连接的待发信元，有则加入发送队列。

如在该时刻有多个令牌满足发送条件，则根据优先级决定发送顺序。如果无待发信元，则清除该令牌和连接的对应关系，将该令牌重新放入令牌桶待分配。由此可见，令牌的产生速率不是固定的，而是跟随输入信源到达率变化的。

信道统计计算单元是对出入口的连接数据速率进行统计计算，以监测流量控制器是否满足业务量管理要求，并将统计结果反馈回基本算法单元，以达到动态调整服务队列的流量的效果。

3 多通道流量控制IP核的实现

该流量控制IP核的原理框图如图4所示，除用于数据缓存单元的SSRAM外，其他全部在FPGA里实现。基本设计参数为最大输入连接数n=4 096，令牌桶容量为256个，最小量化刻度为16个系统时钟周期。

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

首先针对每个连接都建立一个配置参数表，该表存放该连接的流控参数权重等信息，该表可以重构动态调整流量参数以实现VBR，当一个合法连接的输入信源进入网络后，令牌桶分配单元将为该连接分配一个令牌，同时根据配置参数表的值建立该令牌的运行参数表。

根据FPGA并行运算的特点，建立了一个16×16的GCRA算法矩阵，采用分时复用和流水线设计方法，只需16个基本GCRA算法单元和16个时钟周期就可以同时对256个令牌完成GCRA运算，判断出有效的令牌，再根据令牌的运行参数表决定下一个被服务的令牌，并将该令牌对应的虚连接数据从数据缓存单元提出，这些运算调度采用流水线设计都可以在20个系统时钟发送周期内完成，这样在当前信元发送时，也就可以计算出下一个要服务的令牌，同时该令牌的数据已在输出FIFO中准备好，只要信道空闲就可立即发送下一个令牌信元，从而最大限度的利用信道资源。

定时器提供整个模块的定时和节拍控制信息，所有的子单元必须严格按照定时器给出的信息运行以保证时序的准确。

GCRA的基本算法单元是高度模块化，只需在顶层程序中修改参数就可很方便的修改基本单元数量和运行节拍数，从而改变矩阵的结构，以实现更灵活的令牌桶，满足各种应用需求[6]。原理框图如图5所示。

图5 GCRA算法单元原理框图Fig.5 Unit GCRA algorithm principle block diagram

出口入口统计单元对出入口数据速率进行统计计算，并将结果通过主机接口报给上层，当出现输入信源到达率大于控制器的服务率，数据缓存即将溢出时，既可通知上层软件干预，也可根据配置参数表的优先级控制字，阻塞低优先级的输入连接。

根据该方案编写了FPGA程序，FPGA设计采用vhdl语言，使用Synopsys公司的synplify pro编译出网表文件，该网表文件可以被后端工具直接调用，在Mentor公司的Questasim环境下完成了功能仿真和验证。

设计选用了Xilinx公司的spartan-3adsp系列和Virtex-5系列芯片分别进行了电路物理验证，实现了一个16×16的算法矩阵的流量控制IP核，表1是不同器件平台的资源消耗情况。由于该IP模块是全语言设计，并进行了高度模块化，用户只需修改相应参数就可以针对不同的网络队列数量和器件平台资源大小改变矩阵规模，以适应实际需求。

表1 FPGA资源利用报告Tab.1 FPGA resource utilization report

4 结论

文中在研究分析GCRA虚调度算法的基础上，设计了一个GCRA算法矩阵，并结合令牌桶调度机制在FPGA中实现了一个通用的全硬件多通道流量控制IP核。并在一型网络接入设备加以应用。该流量控制IP核具有逻辑精简、运算效率高、占用资源少、模块化程度高，可扩展性好的特点，可以很方便的嵌入各种网络通信交换和接入设计中。

[1]张轶博，李伟，雷振明.一种改进的以太网流控算法[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技术中令牌桶算法实现方式比较[J].中兴通信技术，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]牛淼，蒋林.基于多令牌桶流量整形算法的研究与实现[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中的应用研究与实现[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]汪一鸣，吴红卫，翁桂荣，等.ATM网络中VBR复用器的硬件实现[J].通信技术，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]刘宇.异步传输模式测试仪中业务量整形器的实现[J].国外电子测量技术，2008，27（4）:21-22.LIU Yu.Realization of traffic shaperin ATM tester[J].Foreign Electronic Measurement Technology，2008，27（4）:21-22.