基于FPGA的轮询合路的设计和实现

摘  要：针对高密度接口设计中基于字节处理和整包处理的转换问题，本文提出了分片轮询调度和改进式欠账轮询调度相结合的调度策略，该策略在很大程度上保证了公平性和稳定性。仿真结果显示，该设计完全符合要求。
关键词：调度  分片轮询  欠账轮询  FPGA

1、 引言
    4X2.5G线路接口卡是T比特路由器的一种重要接口，属于高密度线路接口，这种接口是当前路由器设计中的一个重点和难点。所谓高密度，指的是在一块绕路接口卡上提供多个接口。之所以出现高密度线路接口的需求，是因为互联网的规模不断的扩大，对路由器的接入能力提出了日益增大的需求，如果还沿用单板单接口的设计方法将导致路由器的物理规模不断的扩大，不符合现代设备发展的趋势。在4X2.5G线路接口卡的设计中，笔者采用单片多路的SDH处理芯片S19202集中完成物理层的处理，然后根据整体设计方案在其后端进行数据的技术处理。针对多路报文在送往转发单元时的公平性和稳定性需求，以及SDH芯片S19202的特点，提出了输入报文合路采用分片轮询(Cell Round Robin Scheduling;CRR)和改进的欠账式轮询调度(Defect Round Robin Scheduling;DRR)相结合的调度策略。这种调度策略保证了4路POS接口之间的公平性和整包处理的稳定性，并且在工程上易于实现。本文第2节详细阐述了该调度策略的设计与实现过程，第3节对全文进行了总结。

2、 轮询调度的设计与实现
    在4X2.5G线路接口卡的设计中，采用了AMCC公司的SDH处理芯片S19202进行链路层数据处理，该芯片的特点是4个接口共享同一组接收总线和同一组发送总线，另外提供通道选择信号来指示当前工作的线路接口号，其输入端每个接口的缓存大小最大只有1k字节，根本不足以缓存一个长的整包(最长包可达到1500字节)。针对这个特点，设计中使用了在S19202后端的FPGA进行分片轮询和整包接收的处理，保证了4个接口的公平性和稳定性；针对4个接口的报文共享一条到转发的通路时，由于各接口的报文长度差异，可能造成的不公平和不稳定，提出了一种改进式欠账轮询的调度策略。通过分片轮询和改进式欠账轮询的结合使用，保证了4个接口合路的公平性和稳定性。

 
图1  输入合路模块中的轮询调度策略

    输入合路模块中联合调度策略的原理如图1所示，对SDH芯片S19202送出的4路数据进行分片逐个轮询，并缓存进相应通道的整包接收FIFO，相应通道若没有数据则轮空，转入下一通道；整包轮询合路调度则逐个轮询4个整包FIFO，若该FIFO有整包，则在每一轮询周期发送一个整包，否则轮空。

    在该联合调度策略中，分片轮询调度比较容易实现，仅需在FPGA实现的最前端设计一个轮询机，利用SDH芯片S19202提供的通道指示信号(在FPGA设计用SRX_CHANNEL表示)对每个通道进行固定的轮询访问，有数据则存入相应的通道整包接收FIFO即可。而整包调度是使每个通道得到服务的公平性和稳定性的关键，它直接决定着接收服务的通道所得到的服务带宽、时延以及时延抖动等性能指标，因此本文把研究重点放在了整包调度的设计与实现上。

    目前，在整包调度上，主要的调度算法有先到先服务(FCFS)、逐包调度(PRR)、公平排队、虚时钟、加权循环服务(WRR)等多种策略。由于多数调度方式在包长不定的IP网络中实现时遇到了困难，为此，M.Sheedhar等提出了适用于IP网络的欠帐式循环调度(DRR)，该算法由于其较低的实现复杂度、良好的公平性及稳定性而被经常采用。

    但是，DDR算法直接用于高密度线卡设计中会有一定的问题。首先，DRR算法是针对集成服务网络中不同业务需求而提出的，在一般应用中由于队列数较多，所以需要减小队列数，而在我们的设计中只有4个队列，所以不需要减小队列数；其次，在线卡设计中合路报文的包长无法直接给出，如果一定要加上包长则需用多加一级缓存，这就增大了设计复杂度也提高了成本；同样由于经典DDR算法严格要求储蓄计数器值大于队头包长才输出，这种不允许带宽透支只允许盈余的要求会导致出现有包但是无法输出的现象。

    根据4X2.5G线路接口的实际情况和DDR算法的思想，我们可以给出如下适合高密度POS接口使用的改进式欠账式循环调度策略：
1) 逐包轮询；
 

    采用这种改进的DRR算法下，可以保证在变长包的情况下，各个接口的整包缓存队列在报文合路时公平的带宽，确保合路调度的稳定运行。

    DRR整包轮询合路的基本工作过程为：轮询4个整包缓存队列，每读取一个整包都判断该包是否是协议包，如果是协议包，则按照上交CPU报文格式送协议FIFO，如果是需要转发的报文，则按照转发报文格式送数据报文FIFO。

    调度机轮询到某个队列时，为该队列的储蓄计数器加上40；然后判断该队列是否为空，如果为空，则马上转向下一个队列；如果非空，则判断当前该队列是否有整包，如果当前该队列无整包，则转到下一个队列；否则，如果该队列目前有整包则输出该队列的队头包到合路队列，同时该路的储蓄计数器的值要减去输出报文的长度；然后重复上述过程，直到该队列无整包或者队列的储蓄计数器的值小于40时跳转到下一队列服务，其详细工作流程如图2 所示：

 
图2  改进的DRR合路调度流程图
   DRR合路调度单元已在ALTERA公司的quartusII4.1环境下用VHDL编程实现，其仿真波形如图3所示：
 
图3  DRR合路调度单元仿真波形图

    仿真结果显示这种采用分片轮询和欠账轮询的结合的合路调度策略设计可以达到性能需求，确保变长分组合路调度的公平性和稳定性。

3、 结束语
    根据SDH芯片的S19202的特点和性能要求，通过在FPGA内部编程实现分片轮询和改进式欠账轮询结合的调度策略，保证了4X2.5G线路接口卡输入端各个接口合路的公平性和稳定性。经测试该设计性能稳定，整个工作流程简单实用，符合设计要求。

参考文献：
1 stratix_GX_datasheet. Altera公司，2003
2 Stratix Device Handbook. Altera公司，2004
3 s19202cbi30_ganges_prod_rev3.1_cust. AMCC公司，2004
4 S3485_DS0181_v4_03. AMCC公司，2004
5边计年,薛宏熙.用VHDL设计电子线路[M].北京：清华大学出版社，2000