（计算机科学与技术专业论文）高性能路由器内部流控机制的研究.pdf

莺密科学技术大举研究生陵学毽 叁文 摘要 嚣联阚规模的不灏扩大以及各静大数摅篷业务豹出现对路滋器分组处理能力的要 求太大疆嵩。路蠹_ 器蚕蠢楚楚单露蓑发摄文，还需要在签理避糕申考虑簸务震交、濂量 整懑、预测和防止网络摊塞等问题。 本文首先通过对商性能路由器体系结构的分析，指出流量控制技术在高性能路由器 设计中越来越重要，赢接影响路由器的整体性能和丢包率。然质通过对路由器内都秘种 存耱缓狰区结魏进孬分掇，提塞臻垂器内熬滤羹控囊l 参考模型以及适合该模型鹣滚耱凝 制。本文还详细分耩了嘲络处理器论坛n p s i 规范中的流控技术，介绍了核心路囱器率 流控技术的实现。文章墩后针对高性能路山器的发展趋势，对集群路由器中采用的流控 机制进行了大量的模拟和分析。本文的主鼹煲献包括： ( 1 ) 针对目前对路由嚣滚控方露研究誉是很多，作者详缨她好纳分析和比较了历 我鼹邀器辩流控懿疲瘸篱壤闯逶； ( 2 ) 提出了路由器内部缓冲区之问的三种关系模型，在此基础上认为路由器内部 缓冲关系是三种不同方溅的叠加，宜于采用多种流控机制，并给出了相应的几种流控机 制参考方案； ( 3 ) 最嚣对集黪鼹囊器蠹邦滚控规刹磷究激了丈量豹比较麓邂熬。未毅分摄王 謦， 为敷惹更深入的研究褥供了育价值的资料。 综上所述，本文针对高性能路由器中的流控问题进行了一系列的研究，研究成果对 下一代高性能路由器体系结构研究和实现技术具有重要意义。 关键字：高性麓蹄囊器，滚控杌裁，n 黼i ，集群路由嚣 第1 页 莓蘸辩学技术犬擘辑究生院学叠论文 a b s t r a c t 戢记a y 也es c 蛆eo fi 藕拇m e ti se ) 学a n 碰n g 擞迸越越黟b i g 托鞠臣ca 瓣婶p e 翻n g ，w 拯e h 跳l t 猿t h e 彘s 娃_ e 毒。氆ep a c k 成酗i v e 翠e a p a c 匆o fr a u t c rb e 接g h e 蔓撕羲键) e 氇ef m l 拄- f 莪贰o n l y c a nd e l i v e rp k e ts i i i l p l yb u ta l s oc a nc 叫s i 妇q o s ，f i o wr e b i l i l 如d e f e n d i n gc o n g e s t i o ne t ci n d i s p o s a l 轴t b i s p a p e 毛w e 嚣t a n a l y z e dm ea r c 撕t e c 咖o fh 曲p e r f o 黼a n c e f o u 缸b a s e do n i t ， w e 勤 l 藏d 氇采王l o w 双壤蜘 溉狂蜓霉瑶sw 墩秘。瓣 鞫爹。癌赫h e 珏d e s l 嚣聂珏g 毯g hp 嚣f 瓣鑫携c e u t e ra i l di tc 倒髓d i 粥c 娃ya 舔蛾也ew 量l 醴ep e r 幻r m 翘c ea n dt h o 托f i oo fp a c k e tl o s s t h e 娃 t l l r o u g l lm e 锄a l y s i so f m eb u 任hs t n l c t i l r eo f r o u t e rw ep m p o s e dt 1 1 0r e f 酹即c em o d e lo f f l o w c o n t r o li nr o u t e ra n d 鹬g o c i a t c dn o wc o n t r 0 1m e c h a l l i s m i nn l i sp 轴p 婀，、ea l s o 删y z e dt l l e 矗o wc 蹦拄。差毫e 曲瘟q u 燧攮n p s is p e c i 垂主e 蕊鲫渤i 拄j d d w i n g 娃悖i h 瓣e n 女e n lo f 丑g wc 蜘l 穗 c o 撺瑚玺e 矗i 珏氆ee n do f t 嫩s 辫p e r ，啪礅a d e 彘es 呈m 谨a 畦。珏a n 瘥a 黝l y s l sa b o u tc l 瑾；耄c f 羚h 饴r i nt e n no f t 圭l ed e v e l o p m e n t 订e n do f h i g hp e r f o r m a n c er o u t e r t h em _ a i nc o n t r i b u t e si nm i sp a p e ra sf o l l o w - ( 1 ) t h c r ew e r en om a n ys t l l d i e so nn o w n t r 0 1o fr o u t 既s ow es u m m 撕z e da n d e o 嫩p 嫩d 盎e 抟唾疰糟m e 嫩o f p 弱 u 耋e r s ( 2 ) w eg i v e nt l l eb l l l 掩rs l m e t u r eo fr o u t 找b a s e do nj t ，w ep r o p o s e dm a tt h e f ew a s 搬e o v e “a po fd i 肠伽b u 舭r s t h eb e s ts 嚣l e c t i o nw a st oa d o p td i 疏r e n tn o wc o n t r o l m o c h a n i s m s w eh a v e 西v e ns e v e r a lf e f h c n c e k 釉e so f n o wc o n 订o lm e c h a n i s m l 竺! 竺! l ： 甲i 匣i = 寓i 图卜3 单机分布式交换结构 多机互连的集群结构：从前面的3 代路由器结构变迁过程，可以看到系统的 并行化是路由器发展的重要方向。到单机分布式交换结构为止，先足多个线卡的 并行操作和主板分离开来，然后是多条数据流通路的并行操作在单机基础上的并 行化工怍已经进行的非常彻底了。要想进一步提高系统的交换容量，需要更高层 次的体系结构革新。为此，提出了多机互连的集群结构。将专用的集群路由器节 点或常规路由器或计算机等节点以某种方式连接起来组成的单映像。1 路由器叫 集群路由器。集群路由器的构成见图1 4 。 集群路由器具有以下四个特点： ( 1 ) 多个节点组成 组成集群路由器的节点，可以是专用的集群路由器节点，也可以是普通的常 规路由器，甚至可以是运行路由转发软件的通用p c 计算机。 ( 2 ) 节点可独立运行 由于每个组成节点都包含有完整的路由、转发和交换功能，所以从单个节点 运行到多个节点组合运行的配置都是可接受的，这决定了集群路由器具有良好的 规模可伸缩性。 ( 3 ) 节点间互连方式灵活 第3 页 国防科学技术大学研究生院学位论文 集群路由器并没有对节点的互连方式进行限制，集群路由器的具体实现结构 具有多样性。实现结构的多样性保证了集群路由器在应用中扩展的灵活性。 ( 4 ) 单映像特性 单映像特性是指集群路由器在逻辑上的外部视图是一台完整的路由器，而不 是一个具有拓扑结构的网络。或者说，从集群路由器所在网络中任意一个路由器 ( 不包括集群路由器自身) 的角度看，集群路由器应该表现为网络中的一个路由 节点，而不是具有拓扑结构的子网。 燕群路由罂 图卜4 集群路由器的构成 1 2路由器内部流控机制应用 1 2 。1 流控基本原理 网络除了可为信息提供高速率、高带宽的传输功能外，更为重要的是能灵活 地支持现有的和将来可能出现的各种业务，并对各种业务提供服务质量保证，使 网络达到很高的资源利用率。要达到这些目的需要对不同业务的数据运用不同的 流量控制机制。概括地说流量控制就是为了防止发送端速率超过接收端接收的能 力而导致数据丢失而采取的一系列控制机制。 下图卜5 是流量控制基本原理的示意图，链路来的数据首先缓存在发送方缓 存区内( 图中的发送m e 1 ) ，然后通过发送器s 发送出去。同样，接收方首先接收 数据进入缓冲区( 图中的接收m e m ) ，然后接收器r 再对缓冲区的数据进行处理。 当接收器r 处理数据的速率v 2 小于发送方的发送速率v l 时，数据将被缓存在接 收方缓存区内，如果不调节发送器s 的数据发送速率，接收缓冲区就会很快充满， 产生拥塞而引起数据的丢失。因此流量控制的基本工作原理就是通过接收方的反 馈信息来调节发送方的发送能力。 第4 页 国防科学技术大学研究生院学位论文 图卜5 流量控制基本原理 从流控基本原理可以看出，只要v 1 v 2 且接收m e m 容量有限，就有数据拥塞 的可能。拥塞比较严重时将导致数据丢失，为了减小数据丢失机会有必要对其进 行流量控制。同样，路由器内部也设置了存储缓冲区，也存在拥塞的可能，尤其 是遇到突发业务时为了防止缓冲区快速充满导致数据溢出，很有必要对路由器内 部进行流量控制。 1 2 2流控在路由器中的应用 第一代路由器中流控的应用 图卜1 中，通信线卡完成数据的物理层以及数据链路层的收发操作，得到的 数据报文通过总线送交到集中式内存进行存储，经过路由选路成功后的数据报文 再通过总线送到目的线卡，发送出去。图l 一6 为图卜1 将存储器抽象出来的简化 图，该图示意了第一代路由器存储器组织结构和报文收发流程。1 号线卡来的数 据通过总线送到集中式内存m e m o r y 后经选路成功后扶n 一1 号线卡送出，整个过 程只在单一存储器m e m o r y 中缓冲。由于采用总线结构，无多个并发数据流产生， 每次只有单个数据流进入m e m o r y 缓冲。这种结构其典型交换容量通常小于 o 5 g b i t s ，选择适当容量的存储器将不会导致数据拥塞，故而在该结构中未考 虑流控需求。 图卜6 第一代路由器内部存储器组织结构 第二代路由器中流控的应用 图卜7 为图卜2 将存储器抽象出来的简化图，该图示意了第二代路由器存储 器组织结构和报文收发流程。到达一块线卡的数据报文，在本地线卡m e i 进行存 储和转发判决，输出端口在本线卡内部的数据直接出线卡送到目的端口，只有路 由之后目的端口在其他线卡的数据需要通过总线送到其他线卡上去。由于是总线 结构，无并发数据流产生，每次只能在线卡之间建立一个数据连接通路( 图卜7 第5 页 国防科学技术大学研究生院学位论文 中为1 号和n l 号线卡通路) ，因此交换容量受限制。在典型的应用中，这种结 构的交换容量一般小于5 g b i t s ，故而两个线卡m e m 之间无流控措施。另外，在 这个系统中，主板基本上不参与路由转发操作，而主要负责整个系统的管理操作 和路由计算等任务。它负责运行路由协议和邻居节点进行路由交换，生成路由表， 并将用于转发判决的转发表发布到各个线卡m e m 上去。图卜7 中带箭头的虚线示 意了该过程。主板m e m o r y 只保存的是转发表等小容量信息无大量数据流需要存 储，因此，不易发生阻塞，也无需在主板】i l e m o r y 与线卡m e 之问进行流控。 图卜7 第二代路由器内部存储器组织结构 第三代路由器中流控的应用 从第三代起路由器都摈弃了总线结构而采用了新的交换结构，其交换容量得 到了大大的提升，同时对存储器的要求也提高了。为了适应互联网流量的突发特 性，减小数据分组的丢失率，从第三代起路由器在内部设置了多个缓冲区“。图 卜8 为图卜3 将存储器抽象出来的简化图，该图示意了第三代路由器内部存储器 的缓冲区抽象组织结构，同时也示意了报文收发流程。 入靖蹦l 靖臼群 蕊订，f 司一 ： j x ： li，i 叶薮磊h、五i h i 1 _ j1 j 7 图卜8 第三代路由器内部缓冲区抽象结构 从图上可以看出有三种不同的缓冲区即输入m e m 、交换m e m 和输出m e m ，其 中第一、二种缓冲区在交换结构入边配置，第三种缓冲区在交换结构出边配置。 输入 i e l 为数据进入线卡需要存储而设置的数据缓冲区，交换m e m 为报文在输入 端等待交换调度时的排队缓冲区，输出m e m 为报文经交换调度后根据需要在输出 端口设置的排队缓冲区。 其中交换m e m 通常设置为v o q 队列即不把所有的信元排在一个输入队列里， 而是给每个输入到每个输出都建一个缓冲队列“，设置v o q 的作用是避免链头 h o l ( h e a do fl i n e ) 阻塞“，同时也为实现基于端口的流控提供条件：输出m e m 第6 页 国防科学技术大学研究生院学位论文 根据信元重组的需要还可划分出一个专门的缓冲区，如本文第三章中提到的v i q 缓冲区。 在基于n p 的路由器中，报文收发基本处理过程为，通信线卡n i c 完成数据 的物理层以及数据链路层的收发操作，得到的数据报文进入本地线卡存储器内进 行输入缓冲。网络处理器n p 主要完成网络层及以上的数据分组处理，交换芯片接 收n p 来的数据进入交换队列( 如v o q ) ，交换芯片利用收到的数据中的控制信息 ( 如目的i p 地址) 决定数据存入哪个队列，最后由仲裁调度机制将数据通过交 换结构送出到目的端口。 由于是交换结构，可以有多个数据流并发产生，每次能在线卡之问建立多个 数据连接通路( 图卜7 标识了1 号线卡和n 号线卡之间的两条数据通路) 。因此 交换容量较前面两代大大提高，这种结构的典型容量从前面两代的几个g b i t s 上升到了几十乃至上百个g b i t s ，不能不考虑各个缓冲区的阻塞问题。采用 c r o s s b a r 或共享缓存作为交换结构除了遇到h o l 阻塞外还可能遇到其他两种阻 塞“”即输入阻塞( 如图卜7 中交换m e m 中的v o q 阻塞) 和输出阻塞( 如图卜7 中的输出m e m 阻塞) 。 前面提到了实际应用中一般用v o q 机制来解决头阻塞问题。为了解决输入阻 塞和输出阻塞，文献 1 6 中提出了两种解决方案。第一是带优先级的v o q 队列， 第二是提高交换结构的加速比。无论是对v o q 划分优先级还是提高加速比都将增 加软件管理和硬件实现复杂度，当路由器有很多端口，当端口速率达到g b i t s 或更高时，很难实现高加速比“”。因，! ，为了有效解决阻塞问题，需要在各缓冲 区之间采用恰当的流量控制机制以减小数据阻塞几率，增强系统适应数据突发的 能力，提高路由器整体性能。这正足路由器内部流控之作用所在。 第四代路由器中流控的应用 新一代核心路由器的体系结构通常都是基于集群设计的，在集群结构中，多 个机柜通过多级交换网络连接在一起整合成一个新的大型路由器。交换网络的拓 扑结构有很多种方案，例如常见的有3 dt o r u s “”结构、c 1 0 s “”结构和b e n e s 。” 结构等。这种集群结构，在理论上可以进行无限制扩展，这样，只要进行扩展， 就可以支持不断增加的网络流量需求。因此，集群路由器的应用前景十分广阔， 这种体系结构的路由器正成为当今研究的热点。内存的访问速度、调度策略和速 度以及服务质量控制，交换网络等等都先后成为新一代集群路由器体系结构的关 键问题。在静态互联的t 比特交换网络中，报文从源端口( 源节点) 交换到目的 端口( 目的节点) ，需要经过某条路径，其所经过的路径是由交换网络路由算法 决定的。交换网络路由算法应能迅速地将报文传递到目的节点，并能在多条路径 上进行负载平衡，减少拥塞，提高交换网络的总吞吐量。本文的主要目的不是研 究报文的路由问题，而是分析报文在路由器节点中交换所需的流量控制问题。 第7 页 国防科学技术大学研究生院学位论文 考虑两个机柜互连的简单情况，图卜9 为集群路由器内部缓冲区抽象组织结 构示意图。从图中可以看出每台机柜有四种不同的缓冲区即输入m e m 缓冲区、交 换m e m 缓冲区、输出m e m 缓冲区和内连m e m 缓冲区前三种缓冲区与图卜8 类似， 内连m e m 为其中一台机柜的内部输出端口与另一台机柜的内部输入端口相连组 成的机柜间内部互连端口缓冲区。两台机柜通过内部互连整合成一台多端口( 外 部输入输出端口增倍) 的单映像大型路由器。 图卜9 集群路由器内部缓冲区组织结构 该图同时示意了集群路由器结构的报文收发流程。从上图标识的两条数据通 路可以看出整个收发流程为：源端报文经过路由选择得到目的端口，当目的端口 在本地机柜时，通过交换调度直接从本地机柜的外部输出端口送出，当目的端口 不在本地机柜时，需要通过内部互连端口( 该端口的队列缓冲区为内连m e m 缓冲 区) 送到下一个机柜，再经过路由选择决定送往合适的机柜和相应端口，接着反 复这个过程直到报文被送往目的端口。由于内连端口数比较少，当有多个报文的 目的端口不在本地机柜时，将使得内连端口显得非常繁忙。如果持续相当长的时 间，而到某个目的端口的交换速率不可能无限大，数据不能被及时调度。因此， 容易在内部输入端口产生阻塞现象。很显然，在这种情况下，多个外部输入端口 的报文都要通过少量的内部输出端口，数据不能被及时调度的话，在输入端也会 发生拥塞，且可能性更大。因此，为了避免数据丢失，需要在集群路由器内部易 发生拥塞的缓冲区之间引入恰当的流控机制，并且较前面几种体系结构，集群结 构对流控的要求更高，实现起来也更复杂。 1 3本文研究内容及贡献 本文主要针对高性能路由器中流量控制问题进行研究。首先对基于速率和基 于信用以及反压技术三种流控控方式进行了深入的研究，在此基础上分析了路由 器内部适宜采用的流控技术；然后详细地介绍并总结归纳了n p s i 流控技术，在 g f 9 2 0 0 路由器内部实现了基于n p s i 的流控机制；最后对高性能集群路由器内部 队列拥塞情况设置了几种有代表性的场景进行了大量的模拟分析，得出了一些有 价值的结论。 第8 页 国防科学技术大学研究生院学位论文 本文的主要贡献和创新工作包括：针对目前对路由器流控方面研究不是很 多，作者详细地归纳分析和比较了历代路由器对流控的应用需求问题；提出了路 由器内部缓冲区之间的三种关系模型，在此基础上认为路由器内部缓冲是三种不 同方式的叠加，宜于采用多种流控机制，并给出了相应的几种流控机制参考方案； 最后对集群路由器内部流控机制研究做了大量的比较基础的模拟分析工作，为以 后更好的研究提供了有价值的资料。 1 4本文组织结构 论文共分五章。 第一章为绪论，介绍课题背景及意义和研究内容。 第二章为路由器内部流控机制分析，介绍了三种流控方式，给出了路由器内 部缓冲区关系模型和具体流控技术参考方案。 第三章介绍了n p s i 流控技术和g f 9 2 0 0 路由器中的流控实现。 第四章为集群路由器内部流控的研究和相关模拄试验。 最后一章总结已经完成的工作，并指出进一步的研究方向。 第9 页 国防科学技术大学研究生院学位论文 第二章路由器内部流控机制 网络由有限的资源所组成，这些有限的资源包括网络节点内的信息缓存器、 节点处理器等等，无限制的信息流进入网络会导致拥塞。同样，路由器内部也存 在大量的缓存器也会面临拥塞的情况。当报文到达路由器时，它们被存储在相应 端口的缓存器中进行输入排队，路由器的相关功能模块查看每一个收到的报文， 通过路由信息作出一个调度选择的决定，将报文调度到合适的输出端口缓存器中 进行输出排队。从结果上看，这就是统计时分复用，如果报文到达太快以致于来 不及处理它们( 即作出路由选择以及调度选择的决定) 或者比报文能够从输出缓 存中被清除得更快，那么到达的的报文最终将会没有存储区可存放，当到达一个 饱和状态时就会有数据丢失。因此，为了消除发送端发送速率大于接收端接受速 率的差异，不至于发送速率过快导致有限的缓冲区快速充满，必须对路由器采用 恰当的流控机制，减小丢包率，以提高路由器整体性能。 本章研究路由器内部的流控机制，2 1 节介绍三种典型的流控机制，2 2 节 重点分析路由器内部流机制的选择，2 3 节重点讨论第三代高性能路由器内部的 流控机制。 2 1典型流控机制 2 1 1基于速率的流控机制 基于速率的流量控制方式1 1 ( r a t e 曲a s e df l o wc o n t r 0 1 ) 是一种端到端的 流量控制机制，通过反馈数据分组所历的排队拥塞状况来控制源端的数据发送速 率。图2 1 中所示为一种简单的控制模型，它是只有一个队列的情况。其中x ( t ) 为输人速率，y 为恒定的输出速率，q ( t ) 为缓冲区队列长度，m 为正向传输累积 延迟，n 是反向传输累积延迟。 图2 一l 单队列基于速率流量控制模型 我们可以描述一种基于速率的流量控制机制如下：我们假设当缓冲区队列长 度小于某一阀值f 1 时，反馈回来的流控信息将线性增加输入速率x ( t ) ；相反， 当缓冲区队列长度大于某一阀值f 2 时，输入速率将按指数减小，即按照以下公 第1 0 页 国防科学技术大学研究生院学位论文 式调节输入速率x ( t ) 。式中，k 0 为线性增加系数；b 为指数减少系数。 出“) ，衍： 七 g u h ) 门 ( 1 ) 、 一x ( f ) 卢g ( f n ) ，2 下图2 2 中显示了基于上述流量控制模型的输入速率x ( t ) 随时间t 变化的 规律曲线。假设缓冲器起始为空，输入速率x ( t ) 线性增加，增加的速率为k 。当 x ( t ) 到达输出速率y 的时候，缓冲区开始缓存数据。但由于累积延迟m ，缓冲器 只能在时问m 之后即时刻b 开始缓冲，此时到达缓冲器的输人速率将大于或等于 y 。当缓冲区缓存的数据量达到阀值f 2 时，反馈的流控信息将依据方程( 1 ) 减 小输入速率x ( t ) 。同样由于存在反向传输延迟只能在时间n 之后即时刻d 开始 减小传输速率。一旦缓冲区内的数据减少到阀值f 1 后，反殒的流控信息又会指 示源端提高输入速率x ( t ) ，这个信息将在时间n 后即时刻f 到达数据发送源端， 从而完成一个循环，接下去将重复这个过程。 x ( t ) x t 曹f 2 y x f l l ，、 ， 、 、 ， 、 ，。 | | | t 图2 2x ( t ) 一t 关系曲线 这只是一种简单的基于速率的流量控制模型，其速率控制参数比较简单。实 际应用中针对不同的需求会有不同的速率控制参数，流量控制粒度以及机制实现 的复杂度等等。 2 1 2 基于信用的流控机制 另一种广为采用的流量控制方式是基于信用的流量控制方式恤1 ( c r e d it _ b a s e df l o wc o n t r 0 1 ) 。其基本思想就是发送端在向链路上发送任何数 据分组之前，都需要接收从接收端传来的信用( c r e d i t ) 信息。发送端依据信用值 第l l 页 国防科学技术大学研究生院学位论文 大小决定发送数据分组的数量。一般来说信用值大于等于链路传输速率乘以链路 往返传输时延。图2 3 给出了基于信用流控机制的基本工作原理。数据接收方首 先发送信用值到数据发送方，通知可用缓冲区容量，发送方收到信用后，根据信 用值决定发送的数据分组数量。 信用通告 发送方壬、接收方 厂= = 孑掣童墅5 = i 一ji 一j 一信用大小缓存 图2 3 基于信用的流控模型 基于信用的流量控制模型相对于图 1 中基于速率的流量控制模型来说，反 馈信息不再是调节发送方的发送速率x ( t ) ，而是调节发送方可以发送的数据分 组数量。下面给出一种简单的基于信用的流量控制机锘4 例子。 圈圆圆硼豳函 信用 图2 4 基于信用的滑窗式流控机制 如图2 4 所示，开始时发送端赋予7 个帧的信用量被允许发送7 个帧，每发 送个帧，窗口减小l 。发送端发出了o 、1 、2 号三帧后，发送窗口减小到包含 3 6 号。此时，接收端对o 一2 号帧确认，在发回的确认帧中设置a c k ( 2 ) ，c r e d i t 5 ， 信用量大小为5 ，信用量大小代表了流控的粒度。即允许发送端在收到a c k 后可 以继续发送5 个帧( 即从3 7 号) 。但由于确认帧返回时延，发送端在收到 a c k ( 2 ) ，c r e d i t 5 之前，已经发送了第3 、4 帧，使窗口相应地减少。在收到信 用后，发送窗口就只能增加l ，即包含5 7 号。然后发送端将5 、6 、7 三帧连续 发送出去，就消耗了它的信用量，发送窗口减小到o ，等待收到下一个信用。当 收到a c k ( 7 ) ，c r e d i t 7 后，恢复到原来的窗口。 2 1 3基于反压的流控机制 反压机制“”提供了一种最直接的保护接收接口的数据不至于溢出的方法。反 第1 2 页 国防科学技术大学研究生院学位论文 压技术产生的效果类似于流过管道的流体产生的反压现象。当管道末端被关闭 时，流体就向源头产生压力，从而阻断( 或减慢) 流动。 图2 - 5 队列之问相互作用 考虑图2 5 这种缓冲区节点间的队列互相作用情况。节点相邻的每一个节点 都管理着大量的队列。如果节点6 阻止从节点5 来的报文流量，这就引起结点5 到结点6 的端口的输出缓存空间耗尽。同样节点5 也有可能阻止从节点4 来的报 文流量。这样，拓扑上一处的拥塞可以很快地扩散到一个地区或整个拓扑网络， 显然需要一种妥善的流控机制以便对整个拓扑网络上的通信量进行管理。一种有 效的流控机制是采用反压原理，避免热点。若缓冲节点6 正发生拥塞，那么节点 6 就可以使来自节点5 ( 或节点3 ，或两者一起) 的报文流减慢或停止。若这一 限制措施持续下去，则节点5 就可以减慢或暂停从其输入链路上接收报文流。这 种流量控制将反向传播到各信源端，这些源端就会限制新的报文流进入网络。 反压可以有选择地应用到某些逻辑连接上，以便从一个节点到下一个节点之 间的流量只在这些逻辑连接上受限或停止。通常是选择通信量最大的一部分逻辑 连接采用反压机制。在这种情况下，流量的限制就沿此连接反向传播到源站。 反压机制多采用二进制控制方法。如拥塞节点在转发数据分组时对分组的某 一比特位置1 表示拥塞，置0 表示不拥塞，当源站报文收到一条逻辑连接上的拥 塞指示位，它就减慢或停止该连接上的通信流量。 2 1 4三种流控机制比较 这三种流量控制机制各有优缺点。 理想的情况下，基于信用的流控机制可保证无数据分组丢失，即使遇到突发 业务流时，排队长度也不会超出信用值所规定的范围；而基于速率的流控方式当 遇到突发业务流时，排队长度急剧增加，从而引起缓存溢出，有可能造成数据分 组的丢失。由于基于信用的流控机制需要为每一条逻辑连接保持一个排队队列， 这就需要较大的缓存空间，因此不适合有多个逻辑连接队列的情况，否则会使得 缓冲区设计变得复杂。基于速率的流控方案在适配卡的设计上比信用策略复杂， 第1 3 页 国防科学技术大学研究生院学位论文 相应的硬件成本也高，基于信用的流量控制在l a n 环境中可以实现低成本的网络 适配器和较高的性能。因此，是采用基于速率机制好还是采用基于信用机制好， 要看具体应用和实现复杂度而定。 遇到图2 5 这种队列情形，除了对相邻节点采用基于速率和基于信用的流控 机制外，还需要一个妥善的全局性流控机制以便对整个拓扑网上的通信量进行管 理。基于信用的流控机制不适予多个逻辑连接队列的情况，基于反压的机制是一 种很好的解决方案。但反压机制用在允许使用逐跳( 从一个节点到下一个相邻的 节点) 流量控制的网络设施中如路由器的存储节点之间，因此用途比较有限。反 压机制可以说是一种类似于基于速率的机制，但基于速率的方案提供一个明确的 速率上限，对速率的参数的控制也比较严格。 2 2路由器内部流控机制选择 从前面分析看出不同的流控机制使用在不同的应用环境中，路由器内部有多 个缓冲区，有直接相邻的有不相邻的还有交叉的，它们之间的不同关系各自形成 了流控在路由器内部的不同应用环境，决定着在路由器内部使用何种流控机制。 因此在选择路由器内部流控机制前有必要先分析路由器内部缓冲区之问的关系。 通过前面对路由器内部缓冲区组织结构分析，可以将路由器内部缓冲区归纳 为三种关系即直接缓冲关系、间接缓冲关系和交叉缓冲关系。分别见图2 6 ( a ) 、 2 6 ( b ) 和2 6 ( c ) 所示。直接缓冲是指两个缓冲区直接相邻，如n p 到交换结构之 间缓冲；间接缓冲是指两缓冲区不直接相邻，如输入到输出缓冲以及两个输入之 间的缓冲。交叉缓冲关系如输入经过交换结构到输出这整个“网络”之问的全局 缓冲关系。 臣 产坚任乎 柚囊藏挂冲蓑薰 曰哩螋乎 b ) 蝴攮鬟抻羹薹 ( c 蹙x 囊净燕量 图2 6 路由器内部缓冲区间的关系 三种缓冲模型有着各自的特点，对流控的影响也不同。其中直接缓冲关系适 合运用采用反压的机制和基于信用的机制，间接缓冲关系适合运用采用反压的机 第1 4 页 国防科学技术大学研究生院学位论文 制，交叉缓冲关系其实是直接和间接缓冲在路由器中特定的的组合关系，通过交 换m e m 联系在一起。另外，三种缓冲关系还可以实现某种形式的转换。 例如，通过流控h u b 可将间接缓冲转化为直接缓冲，如图2 7 所示。这样转 化的优点是可以将在间接缓冲关系上采用适宜的流控机制带来的效果转换为在 直接缓冲关系上实施恰当的流控机制带来的效果。间接缓冲关系实施的反压机制 用途有限，通过图2 7 这种关系转换，那么就可以运用基于信用的流控机制来达 到更好的流控效果。 处 艘 怼 瓣 图2 - 7 路由器内部缓冲区间的关系转换 对于高性能i p 路由器的内部设计来说，路由器内部各处理节点问已经具有了 相对独立的缓冲区队列设置，所以我们认为基于信用的流量控制机制较适宜i p 路由器内部采用；而采用基于速率的流控机制在实现上较基于信用的流控机制更 为复杂，且硬件实现代价也较高，因此在路由器内部很少考虑这种复杂的流控机 制。 由于路由器内部是三种方式韵霞加，因此必须使用多种流控棚制。直接相连 缓冲区之间可以采用反压机制和基于信用的机制，间接相连缓冲区之问可以采用 反压机制。 2 3路由器内部流控机制参考模型 图卜7 给出了第三代路由器体系结构通用缓冲区组织结构，下面给出一种基 于网络处理器n p 的路由器内部缓冲区组织结构及简化的路由器体系结构示意 图，见图2 8 。 第1 5 页 国防科学技术大学研究生院学位论文 线卡l 娩卡n 图2 - 8 基于n p 的路由器内部流控机制 绪论中已经简要分析在本地线卡m e m 和交换芯片的v o q 队列之有大量数据 流时，在v o q 队列的数据来不及调度严重时会发生输入阻塞，为了适应互联网流 量的突发特性避免数据阻塞v o q ，需要引入流控机制。这之间的流控属于网络处 理器n p 和交换芯片之间的流控，记为n p f a b r i c 流控。n p f a b r i c 流控允许交 换芯片向n p 通告它的全局队列存储器( v o q ) 中的空闲空间信息。这允许n p 决 定怎样最好利用剩余的存储空问，以避免拥塞发生。除此之外，之仨各线卡之间 引入了n p _ n p 流控。该流控机制允许各线卡交互队列长度信息，根据队列长度分 配各自i n p u t 到各个0 l l t p u t 的带宽以此来调节各线卡发往目的端口的数据传 送能力，避免该数据通路上相应排队缓冲区数据接收能力大于处理能力而发生数 据溢出。例如当n 号线卡上的排队缓冲区将满时，通过n p 之间互相反馈流控信 息( 通告信用量) ，l 号线卡得知n 号卡状态后( 无信用收到或收到信用量为o 的流控信息) 就停止往该号线卡发送数据，以减小拥塞的可能性。下图描述了基 于n p 的路由器内部流控模型，其中n p 和f a b r i c 是直接缓冲关系，n p 和n p 是 问接缓冲关系。 图2 9 基于n p 的路由器内部流控模型 针对以上流控模型，我们给出了一种路由器内部数据处理模块之间流量控制 第1 6 页 国防科学技术大学研究生院学位论文 机制的参考方案，见图2 1 0 所示。图中的发送端和接收端可以是i p 路由器内部 数据通路上的各种网络处理模块，例如n p 到交换结构f a b r i c ，交换结构f a b r i c 到n p ，还可以是跨越交换结构的n p 到n p 的流量控制机制。本模型图给出了三 种流控方式，即链路级流控( l i n k l e v e lf 1 0 wc o n t r 0 1 ) ，类流控( c l a s s b a s e d f 1 0 wc o n t r 0 1 ) 和全局流控( g 1 0 b a lf 1 0 wc o n t r 0 1 ) 。其中链路级流控在交换 网络入口和出口是必须的，其余为可选机制。从本章2 2 1 讨论得知流控是采用 多种方式分级实施的，可以在链路级流控基础之上加载其他流控技术。为了实现 组播功能可以加载组播流控，为了支持子端口粒度寻址可以加载子端口流控等等 技术。类流控机制是对业务流量的各个类进行反压流控。下面着重介绍链路级流 控和全局流控，其具体实现见下一章。 图2 一l o 路由器内部n p f a b r i c 之问流控参考方案 链路级流控机制控制数据传送能否在数据链路上进行。数据传送能力由接收 端发向源端的流控信息上的固定d r ( d a t ar e a d y ) 位来控制，d r 位置l 即x o n 状 态表示f a b r i c 准备接收数据；d r 位置0 即x o f f 状态，表示f a b r i c 不准备接收 数据。链路级流控机制其实是一种前面提到的反压机制。 全局流控采用一种基于信用的流控机制，接收端的全局拥塞信息能被传回到 源端。我们以n p 到交换结构f 之间的数据传输为例来说明全局流控机制。交换 网接收n p 来的数据进入队列，交换网利用收到的数据中的控制字信息决定数据 存入哪个队列。全局流控允许交换网络向n p 通告它的全局队列存储器中的空闲 空间信息。在共享存储交换网中资源可以被动态分配，这允许n p 决定怎样最好 利用剩余的存储空间。全局流控消息通过流控帧格式中的全局状态位 g l o b a l s t a t u s 来设置传输交换网络能接受的数量。在此，g 1 0 b a 上一s t a t u s 位就 相当于标识了链路控制的信用值，其值就表示通告的信用量大小。 第1 7 页 国肪科学技术人学研究生院学位论文 2 4本章小结 本章首先介绍了流量控制技术中常用的三种控制方式，提出了路由器内部缓 冲区之间的关系，然后分析得出由于路由器内部是三种不同缓冲关系的叠加，因 此必须使用多种流控方式。最后着重讨论了基于网络处理器n p 的第三代高性能 路由器内部流控机制，提出了流控模型及流控机制参考方案。路由器内部流控机 制的具体实现见下一章。 第1 8 页 国防科学技术大学研究生院学位论文 第三章n p s i 流控技术及其应用 n p s i 删( n e t w o r kp r o c e s s i n gf o r u ms t r e 鲫i n gi n t e r f a c e ) 流接口协议是标 准化组织网络处理论坛( n e t w o r kp r o c e s s i n gf o r u m ) 在通用交换接口c s i x l 1 0 8 的基础上制定的。它规定了接口如何支持在一对包括物理层( p h y ) 器件( 如s o n e t 成帧器映射器或以太网m a c 器件) ，网络处理器n p ( n e t w o r kp r o c e s s o r ) ， 网络协处理器( n e t w o r kc o p r o c e s s o r ) ，和交换网( s w i t c hf a b r i c ) 等网络处 理设备之间进行业务传输。 目前的第三代高性能核心路由器普遍采用了基于网络处理器的路由器体系 结构。n p s i 规范提供了在相邻的网络处理设备之间进行数据和控制信息传输的 机制。因此可以利用n p s i 实施恰当的流控技术来实现路由器流量管理以及拥塞 控制等功能，提高路由器整体性能，满足核心路由器要求。 本章首先详细分析了n p s i 流控技术，包括n p 卜f a b r i c 模式下的链路级流控、 全局流控等和n p e n p e 模式下基于信用的流控机制。最后介绍了g f 9 2 0 0 高性能 i p v 6 路由器内部实现的流控机制。 3 1n p s i 流接口简介 3 1 1n p s i 流接口模型 目前，网络处理论坛制定了三种满足特定应用需求的n p s i 模型，分别是： 网络处理单元与交换结构即n p e f a b r i c ，网络处理单元与网络处理单元即 n p e n p e 和网络处理单元与物理层设备即n p e f r a i n e r 三种模型。这三种模型之 问是相互独立的。图3 一l 给出了包含这三种模式的n p f 系统块图。 图3 一ln p f 系统块图 第1 9 页 国防科学技术大学研究生院学位论文 3 1 2n p s i 基本特性 n p s i 提供一个具有带内控制和成帧信息的数据通路和一个说明流控信息的 带外状态通路。它允许数据流的单向传输，其基本特性主要有： 两个相邻设备之间的点到点连接； 数据通路： 一1 6 比特宽的数据通路； 源同步，在最小3 1 1 m h z ( 6 2 2 m b p s 每个比特通道) 下双边缘时钟； 一与s p i 一4 2l v d s 电气兼容，支持的速率可达到1 3 g b p s ； 一带内数据双工与前后文流控，分组描述与错误控制编码。 状态流控通路： 2 或4 比特宽的状态通路： 源同步，双边缘时钟； 一带内帧和错误控制编码。 支持基于分组和基于信元的协议； 支持8 英寸f r 4 加一个连接器的板级连接。 n p s i 中n p e f r 锄e r 的接口遵守o s 论坛的s p i 一4 2 规范。对于n p e f a b r i c 模式，n p s l 支持4 0 9 6 个出端口，每个端口可有2 5 6 种类型服务，该模式还支持 组播和单播，数据端口支持基于端口和子端口的双工方式工作。对于n p e - n p e 模式，可以支持多达2 5 6 个端口，并可以扩展到更大数量端口。该模式还支持 s p i 一5 的池状态机制，这使得它可以支持全双工数据传输的不同粒度的流控。 3 1 3n p s i 流接口信号 n p s i 流接口规范是在通用交换接口c s i x l 1 的基础上制定的，它提供了在 相邻的网络处理设备之间进行数据和流量控制信息传输的机制。它有效综合了数 据包交换接口s p i 一4 2 和通用交换接口c s i x l 1 这两个现有的1 0 g b p s 标准，并 弥补了其中制约交换结构性能和互操作性能的不足。该接口能满足1 0 g b p s 以上 的数据传输速率要求，并保证良好的信号完整性、流量控制和组播功能。 c s i x l 1 没有任何带外流量控制( 状态) 信道，它需要将所有的流量控制信息 作为数据通路的一部分在带内进行传输。其最大缺点是数据通路带宽中相当大的 一部分被流量控制信息占用。这种方法的优点是不需要单独的控制总线，但是该 流量控制总线相当窄，在拥塞状况下对数据通路吞吐率的增加具有优势。 n p s i 和s p i 一4 2 采用带外流量控制信道，它提供了独立于数据通路之外的 流量控制带宽。这就使得设备的单向业务处理应用不需要考虑另一个设备的流控 第2 0 页 国防科学技术大学研究生院学位论文 管理信息。然而，s p i 一4 2 在实现流量控制信道时允许两种不兼容的选择方案： l v d s 和l v t t l 可以达到满数据通路时钟速率，而l v t t l 只能达到数据通路时钟 速率的2 5 。如果选择l s ( 这是n p s i 标准中所要求的) ，可能会使流量控制带 宽提高四倍。通过设置流量控制总线宽度为4 位( 也可以设置为2 位) 而不是 s p i 一4 2 所允许的2 位，n p s i 进一步改善了这方面的性能。图3 2 为n p s i 的接 口信号。数据通路包括了时钟、数据和控制帧信号( 包括d c i k ，d a t 1 5 ：0 和c t l ) 流控状态通道包括时钟和流控状态信号( s c l k 和s t a t 1 ：o 或s t a t 4 ：o ) 。 图3 2n p s i 的接口信号 表3 1 对n p s i 信号进行了总结。 表3 一ln p s i 信号 信号信号名功能描述 d c l k数据时钟时钟与数据和控制信号关联 d a t 1 5 ：o 数据有用于包复用和包描述的带内控制字数据有效 载荷通路，在d c l k 上升和下降沿被驱动 c t l控制当一控制字在d a t 1 5 ：o 上出现时，c t l 为高， 否则为低。在d c l k 上升和下降沿被驱动。控制 字和数据字由c t l 信号区分 s c l k状态时钟与状态s t a t 相关联的时钟 s t a t 1 ：o 状态与帧和错误控制代码相关的流控信息，在s c l k 上升和下降沿被驱动 3 2n p s i 中的流控技术 按3 1 1 节关于n p s i 不同模式的划分将n p s i 中的流控技术分为三种，本文 只分析和课题紧密相关的n p e f a b r i c 与n p e n p e 模式下的流控技术。这两种模 式下的流控信息是在状态总线上传输的。在状态总线上，从数据接收端发送到发 送端的流控信息成为状态帧。每个状态帧包含一个成帧码( f r a m i n gc o d e ) ，两 个或多个流控信息位和一个两比特的d i p 一2 代码。图3 3 给出了公共状态信道格 式。 第2 l 页 国防科学技术大学研究生院学位论文 l 状态帧 1 d ip i1两比特或更多1 | 2 1状态信息 i 图3 2 公共状态信道格式 状态帧的发送方式如下：首先是成帧码o o b l l ，然后是流控状态信息，紧跟