基于NP体系结构的路由器内部流量控制技术研究＊

李海涛 丁宜栋

（海军计算技术研究所 北京 100841）

1 引言

目前的高性能IP路由器普遍采用了基于网络处理器NP（Network Processor）的体系结构［1］，如图1所示。

图1 核心路由器体系结构图

为了适应互联网流量的突发特性，减小数据分组的丢失率，路由器内部一般在网络处理器和交换网络（Switch Fabric）上设置了缓冲区，如图1所示，在网络处理器上设置了输入排队缓冲区和输出排队缓冲区，在交换网络内部设置了虚拟输出队列VOQ或共享存储器缓冲区［2～5］。由于路由器内部在数据转发路径上设置了多个缓冲区，不能不考虑各个缓冲区的阻塞问题［6］，因此需要在各缓冲区之间采用恰当的流量控制机制以提高系统整体适应数据突发的能力。

2 流量控制基本原理及方式

2.1 流量控制基本原理

网络除了可为信息提供高速率、高带宽的传输功能外，更为重要的是能灵活地支持现有的和将来可能出现的各种业务，并对各种业务提供服务质量（Qos）保证，使网络达到很高的资源利用率。要达到这些目的需要对不同业务的数据运用不同的流量控制和拥塞控制机制。概括地说流量控制就是为了避免网络出现拥塞而采取的一系列操作［7～8］。

图2 流量控制棊本原理

图2是流量控制基本原理的示意图，当发送方的数据发送速率超过接收方的数据处理速率时，数据将被缓存在缓冲区内，如果不调节发送方数据发送的速率或数量，缓冲区就会充满，产生拥塞而引起数据丢失。因此流量控制的基本工作原理就是通过接收方的反馈信息来调节发送方的发送能力。流量控制技术按调节发送方数据发送的速率或数量可分为基于速率和基于信用两种方式。

2.2 基于速率的流量控制

基于速率（Rate－based）［9］的流量控制方式是一种端到端的流量控制机制，通过反馈数据分组所经过节点的网络状况来控制源端的数据发送速率。图3中所示为一种简单的控制模型，为只有一个队列的情况。其中x（t）为输入速率，y为输出速率，q（t）为缓冲区内队列长度。m为正向传输累积延迟，n是反向传输累积延迟。k为线性增加系数，β为指数减少系数。为了问题的简单性，我们假设当队列小于某一阈值f1时，反馈回来的流控信号将线性增加输入速率x（t）。相反，当队列大于某一阈值f2时，输入速率将按指数减小。

以上讨论了一种简单的基于速率的流量控制模型，其速率控制参数比较简单。实际应用中针对不同的需求会有不同的速率控制参数，流量控制粒度以及机制实现的复杂度等。

2.3 基于信用的流量控制

基于信用（Credit－based）［10］的流量控制机制就是源端在向链路上发送任何数据分组之前，都需要接收从接收端传来的信用（Credit）信息。源端依据信用值大小决定发送数据的数量。一般来说信用值大于等于链路传输速率乘以链路往返传输时延。图4给出了基于信用流控机制的基本模型。数据接收方首先发送信用到数据发送方，通知可用缓冲区容量，发送方收到信用后，根据信用值决定发送的数据分组数量。

图3 单队列基于速率流量控制模型

图4 基于信用的流控模型

下面给出一种基于信用量分配方案的滑动窗口流量控制例子。如图5所示。

图5 信用量分配方案的滑动窗U流量控制

开始时发送端赋予七个帧的信用量被允许发送七个帧，每发送一个帧，窗口减小1。发送端发出了0、1、2号三个帧后，发送窗口减小到包含3～6号。此时，接收端对0～2号帧确认，在发回的确认帧中设置 ACK（2），Credit［5］，信用量大小为5，信用量大小代表了流控的粒度。即允许发送端在收到ACK后可以继续发送五个帧（即从3～7号）。但由于确认帧返回时延，发送端在收到ACK（2），Credit［5］之前，已经发送了第3～4帧，使窗口相应地减少。在收到信用后，发送窗口就只能增加1，即包含5～7号。然后发送端将5～7三帧连续发送出去，就消耗了它的信用量，发送窗口减小到0，等待收到下一个信用。当收到ACK（7），Credit［7］后，恢复到原来的窗口。

图5只给出了发送方情况，并假设数据帧和确认帧都不发生差错和失序。接收方并不需要立即确认进入的数据帧，而等到许多数据到来后发出一个累计确认。

2.4 两种流量控制比较

基于速率和基于信用两种流控方式各有优缺点。

理想的情况下，基于信用的方法可保证无信元丢失，即使遇到突发业务流时信元的排队长度也不会超出信用值所规定的范围。基于速率的方式有可能发生信元的丢失，当遇到突发业务流时，排队长度急剧增加，从而引起缓存溢出，造成信元丢失。这是因为基于信用的流控机制一旦接收到有可靠的信用就以全线速度立即传输业务流。基于速率的流控机制在接收到网络状态消息后才调整信源速率。

但基于信用的流控机制需要为每一条虚拟电路VC保持一个排队队列，这就需要较大的缓存空间，使得交换机的缓冲区设计变得复杂。因此不适应于有大量VC的情况。

基于速率的流控方案在适配卡的设计上比信用策略复杂，相应的硬件成本也高。基于信用的流量控制在LAN环境中可以实现低成本的网络适配器和较高的性能。

3 路由器内部流量控制分析

3.1 路由器内部流控方式选择

对于高性能IP路由器的内部设计来说，路由器内部各处理节点间已经具有了相对独立的缓冲区队列设置，根据前面的分析，我们认为基于信用的流量控制机制较适宜IP路由器内部采用；而采用基于速率的流控机制在实现上较基于信用的流控机制更为复杂，且硬件实现代价也较高，因此在路由器内部很少考虑这种复杂的流控机制。

3.2 路由器内部流控机制分析

从图l中可以看出有两个地方需要进行流控，即各个NP上的FIFO队列之间需要互相通告拥塞信息以及各个VOO队列与交换网之间需要流控信息。相应地引入两种流控机制：NP－Fabric流控和NP－NP流控。

网络处理器NP和交换芯片之间的流控，记为NPFabric流 控，NP－Fabric 流控允许交换芯片向NP通告它的全局队列存储器（VOQ）中的空闲空间信息。这允许NP决定怎样最好利用剩余的存储空间，以避免拥塞发生。除此之外，还在各线卡之间引入了NP－NP流控。该流控机制允许各线卡交互队列长度信息，根据队列长度分配各自输入到各个输出的带宽，以此来调节各线卡发往目的端口的数据传送能力，避免该数据通路上相应排队缓冲区数据接收能力大于处理能力而发生数据溢出。例如当N号线卡上的排队缓冲区将满时，通过NP之间互相反馈流控信息（通告信用量），1号线卡得知N号线卡状态后（无信用或收到信用量为0的流控信息）就停止往该线卡上发送数据，以减小拥塞的可能性。下图描述了基于NP的路由器内部流控模型。

图6 基于NP的路由器内部流控模型

为了实现上述路由器内部流控模型，如图1所示，在交换网与NP之间添加了NPSI流控接口。NPSI流接口规范由标准化组织NPF（网络处理论坛）给出。该接口支持在一对包括物理层（PHY）器件（如SONET成帧器／映射器或以太网MAC器件）、网络处理器、网络协处理器和交换网的网络处理器件间进行网络业务传输。它定义了三种数据和流控传输模式即 NPE－Framer，NPE－Fabric和 NPE－NPE三种接口模式。其中NPE－NPE和NPE－Fabric接口模式也明确提出了一种基于信用的流控方案。

NPE－NPE之间（上述模型的 NP－NP），通过互相通告FIFO队列信息，各个线卡决定是否发送数据到FIFO负载比较重的线卡上去，以减小拥塞的可能性。

NPE－Fabric之间（上述模型的 NP－Fabric），可以采用一种被称为全局流控（Global Flow Control）机制来实现。交换网接收NPE来的数据进入队列，交换网利用收到的数据中的控制字（ADF）信息决定数据存入哪个队列。全局流控是在NPE－Fabric接口上的可选机制，它允许Fabric在它的全局队列（VOQ）存储器中通告空闲空间。在共享存储交换网中资源被动态分配，这允许NPE决定怎样最好利用剩余的存储空间。全局流控消息通过流控帧格式中的全局状态位global status［7：0］来传输Fabric能接受的数量。全1表示所有空间可用，全0表示无剩余空间，在此，global status［7：0］就相当于信用通告位，其值就表示通告的信用量大小。

4 结语

通过对路由器内部进行流量控制，能有效缓解路由器内部缓冲区的拥塞水平，减少数据丢包机会。对整个系统而言具有适应突发数据能力强，不易丢包，网络延迟短，网络资源综合利用率高等特点。为了实现下一代具有QOS功能路由器，还有待更进一步对这方面进行研究。

［1］Jonathan Chao.Next Generation Routers［J］.Proceedings of The IEEE，2002，90（9）：33－36.

［2］Chuang S T.Matching Output Queuing with a Combined Input／Output Queued Switch［J］.IEEE Journal on Selected Areas in Communications，1999，17（6）：1030－1039.

［3］Minkenberg C，Engbersen T.A Combined Input and Output Queued Packet－Switched System Based on PRIZMA Switch－ona－Chip Technology［J］.IEEE Communications Magazine，2000，38（12）：70－77.

［4］Stunkel C.The SP2High－Perfomance Switch［J］.IBM Systems Journal，1995，34（2）.

［5］McKeown N，The iSLIP Scheduling Algorithm for Input＿Queued Switches［J］.IEEE／ACM Trans Networking，1999，7（2）.

［6］徐恪，熊勇强，吴建平.宽带IP路由器的体系结构分析［J］.软件学报，2000，11（2）：179－186.

［7］Roberts JW.Traffic control in the BISDN［J］.Computer Networks and ISDN Systems，1993，25：1055－1064.

［8］R Epsilon，J Ke C.Williamson.Analysis of ISP IP／ATM Network Traffic Measurements［J］.ACM Performance Evaluation Review，1999，27（2）：15－24.

［9］Bolotj c，Shankar A U.Dynamical behavior of rate－based flow control mechanisms［J］.ACM SIGCOMM Computer Communication Review，1990，20（2）：35－49.

［10］Kong H T，Morris R.Credit－based flow control for ATM Networks［J］.IEEE Network Magazine，1995，9（2）：40－48.