核心路由器的多端口线卡调度

作者：廖鹰 刘明 吕平

引言

线路接口卡是核心路由器访问线路与访问设备间的一种设备接口，主要实现路由器接口上物理层和链路层的功能，必须实现无丢包线速处理，是路由器的关键部件之一。线卡主要关注以下几个方面：排队(如FIFO、Modified Deficit Round Robin)、拥塞控制(如加权随机早期检测)及其它特性(如访问列表、访问速率、数据流统计)。

IPv6路由器系统结构主要由线路接口、多功能转发处理、高速交换网络、内部通信、主控和网管等部分组成。ATM多端口线卡作为IPv6核心路由器的重要线路接口，需要提供8个双向的155MbpsATM光接口，支持64个永久虚连接。多端口线卡中多路数据的合路与分路需要建立一个良好的调度机制来保证数据包的线速处理与每一路数据的公平性。本文对ATM多端口线卡输入和输出两个流向上的数据包调度进行了研究，提出了一种具有一定通用性的多端口线卡调度策略的设计实现方案。

输入处理流向的调度策略

在对多端口线卡输入处理流向调度策略的分析中，我们以ATM多端口线卡为研究对象。ATM多端口线卡支持8个ATM155M光接口，其中每接口支持 8个永久虚连接。

ATM多端口线卡需要对64路数据进行有效的调度，实现Gbps的线速处理。8路共64个虚连接ATM信元经商用芯片PMC5380完成链路层处理后以共享总线形式向输入链路控制威廉希尔官方网站 传送；64路虚连接信元流分路缓存形成完整CPCS-PDU后合路输出，再经过AAL5适配处理，送到转发处理。根据输入处理流程，由于ATM芯片内部的FIFO缓存容量比较小，以及AAL5的处理机制，与路由器系统整包处理的机制产生了矛盾，因此必须在输入链路的控制威廉希尔官方网站 内部设置64个较大的FIFO用来缓存整包，其中每一路FIFO用于缓存一个虚连接的数据包。因此高效公平的进行8路信元读取、分路和64个虚连接FIFO输出数据合路处理成为了必须要解决的问题。

为了保证8路64个虚连接的ATM信元传送及处理的公平性，满足路由器整包处理的需求，提出了基于信元的公平分片轮询调度(Cell Round Robin Scheduling；CRR)和逐包轮询调度(Packet Round Robin Scheduling；PRR)相结合的调度策略，如图1所示。



图1 输入链路控制威廉希尔官方网站 中的调度策略

采取基于信元的公平分片轮询调度主要基于三方面考虑：一是基于信元操作，符合AAL5处理的需求；二是在采用ATM方式时，PM5380内部的 FIFO只能够缓存4个信元，深度有限；三是固定长度包的轮询调度，其理论研究较成熟，也较易于实现，相比不定长包调度可以避免更多的意外情况，能够确保较好的性能。

采取逐包轮询调度，是为了解决AAL5中信元的处理机制路由器系统整包处理的机制之间的矛盾。在信元输入处理时，将信元净荷按其所属的虚连接在相应的虚连接FIFO中依次缓存，直到虚连接FIFO中至少有一个完整CPCS-PDU才能被读取；在虚连接FIFO的输出侧，采用逐包轮询调度的方式对64 个虚连接FIFO进行读取。在输入流向的处理中，我们通过信元净荷在虚连接FIFO中缓存，待完整CPCS-PDU构成后再逐包轮询调度输出的方式解决了上述问题。
整个输入调度的实现参照图1，逐个轮询调度左侧PM5380内部的8个队列，采用分片轮询的方式，若轮询到某一队列时，其队列深度大于53个字节 (信元长度)，且对应的虚连接FIFO未满，则输出，否则该队列轮空，切换到下一个队列；同时轮询调度右边的64个队列，采用逐包轮询调度的方法，在64 个虚连接FIFO的输出侧进行高速切换读取数据。

ATM多端口线卡输入处理流向的调度策略具有一定的通用性，可以根据实际的情况，对于支持的ATM接口和虚连接数量进行改变：输入的8个信元流可根据需要支持的接口数量由ATM接口中的8个变成16个、32个甚至更多，对更多接口的输入信元流同样能够采用分片轮询调度，根据不同虚连接提取出信元净荷在虚连接FIFO中进行缓存；而虚连接FIFO的数量也可以根据我们需要支持的虚连接数量进行改变，采用逐包轮询调度同样能够支持更多的虚连接。

输出流向的调度策略

在ATM多端口线卡输出处理流向上，由高速交换网络送来的数据传送速率最高可达2.5Gbit/s，远大于线路接口输出速率1244Mbit/s (8×155Mbit/s)。以往的解决方案对这一问题进行了回避，采用“不能处理则丢包”的方法。这样虽然降低了实现的难度，但对于高速交换网络满负荷传送数据的情况，显得无能为力，无法满足QoS要求和对实时业务提供支持。由此可见，缓存管理机制和调度策略在此的重要性。

我们在以往解决方案的基础上进行了改进，提出了基于门限的调度策略(Threshold Based Scheduling Policy；TBSP)、带有优先级的逐包轮询调策略(Racket Round Robinwith Priority；PPRR)、分类随机早期探测机制(Classification Based Random Early Detection；CBRED)和公平分片轮询调度策略(Cell Round Robin Scheduling；CRR)相结合的方案。

如图2所示，图左侧是输出缓存中数据包队列，图右侧是本接口的8个线路接口FIFO，用于存储去往各个线路接口的数据包，数据包队列和线路接口 FIFO中间是调度机。根据数据包头所带的线路接口指示，数据包被送往相应的FIFO中。假设输出缓存队列队头的数据包要送往FIFO01，而FIFO1 已满不让写入，就会发生队头阻塞。此时若是采取等待直到FIFO1允许写入，就会使后续到达的数据包丢弃，如果丢弃的数据包是去往其他线路接口，而相应的 FIFO却并没有满指示，就造成了不合理丢包；若是不等待读出并直接丢弃该包，缓存器的作用便无法充分发挥。这都将导致处理的丢包率增加和吞吐量下降。为了降低系统丢包率和提高吞吐量， 我们提出了一种基于门限的调度策略(Threshold Based Scheduling Policy；TBSP)。TBSP原理如图2所示，其策略描述如下：
(1)在输出缓存中设置门限T；
(2)当队列深度小于T时，若发生队头阻塞，数据包暂时存放在输入缓存中；
(3)在队列深度到达T时若队头对应的FIFO满指示失效，则读出数据包并写入相应FIFO；
(4)当队列深度到达T时若队头对应的FIFO满指示依然有效，读出该数据包并丢弃。



图2 TBSP调度示意图