（通信与信息系统专业论文）链路故障情况下多级交换结构的流量分配方法.pdf

摘要 摘要 目前的高性能路由器普遍采用了多级多平面的交换架构，比如思科的c r s 1 高性能路由器和d u n es a n d 交换芯片。这种多级多平面交换结构具有扩展性强、 可靠性高等优点。但由于在交换结构内部会出现多个数据信元竞争同一个输出端 口的情况，交换结构也存在发生内部拥塞的可能。针对可能造成内部拥塞这一问 题，实际的交换结构中都设置了少量的缓存。 由于高性能路由器经常2 4 小时不中断地运行，当交换结构内部出现故障时， 必须有一套完善的机制来检测并处理故障。本文的重点在于介绍交换结构的故障 检测方法并且提出一种可以保持交换平面内部负载均衡的流量分配算法，然后结 合p u s h 和p u l l 这两种调度机制对算法进行仿真验证。 首先介绍思科c r s 1 的p u s h 调度机制以及d u n es a n d 交换芯片的p u l l 调度 机制。p u s h 调度机制的思路是：当输入模块中有数据信元需要发送时，立刻将其 发送到交换结构中，除非从交换结构收到流量控制信息；p u l l 调度机制的思路是： 输出模块维持一个令牌生成器，输入模块中有数据信元但没有令牌时，必须先向 输出模块发送队列状态信息获得令牌，然后才能向交换结构发送数据。 故障检测思路为：交换平面内的每个交换模块单元以及输出模块都会源源不 断地接收来自“上游 的信元，如果暂时没有数据信元发送，“上游”模块单元就 向与之相连的模块单元发送一种特殊形式的“空信元，“下游 的模块单元收到 信元后，对其进行判断。如果为数据信元，则按照数据信元的目的i d 号码将其转 发到相应的输出链路中；如果收到的是“空 信元，则不对其进行转发，而是将 “空”信元丢弃；如果在规定的时间内某个模块单元既没有从某个输入端口收到 数据信元，又没有收到“空”信元，则这个模块就判定该输入端口所在的链路出 现故障。 对于多级多平面交换结构而言，当一个或多个交换平面内部出现链路故障后， 交换系统的处理能力会受到影响。如果不采取处理措施，随着输入流量的不断增 正，包含链路故障的交换平面可能会发生拥塞。为了解决这个问题，本文提出了 一种流量分配算法并且结合3 级c l o s 交换结构进行说明。流量分配算法的思路是： 每个输入模块单元为它的输出端口维持一张路由表和两种标记字段，其中，第一 种标记字段用于记录交换平面内第一级链路故障的位置，第二种标记字段用于记 l 摘要 录交换平面内第二级链路故障的位置；一旦输入模块接收到一个包含故障指示的 控制分组，并且故障发生在交换结构内部，输入模块便记录故障的位置，然后根 据流量分配算法来控制流量的发送。流量分配算法可以根据各个交换平面的处理 能力来调整流量的发送，有利于保持各交换平面的负载均衡。 最后，通过搭建o p n e t 网络仿真平台，并分别采用d u n es a n d 交换芯片的p u l l 调度机制和思科c r s 1 路由器的p u s h 调度机制对流量分配算法进行了仿真。结果 表明，采用流量分配算法后，信元的平均时延以及交换结构的缓存使用等都会得 到一定的改善；在负荷较大时，故障链路所在交换平面出现拥塞的概率明显降低。 关键词：多级多平面，故障检测，流量分配，负载均衡，拥塞 a b s t r a c t a b s t r a c t a tp r e s e n t ，m a n yh i g hp e r f o r m a n c er o u t e r si n c l u d i n gc i s e oc r s 1s e r i e sc a r r i e r r o u t e ra n dd u n en e t w o r ks a n ds w i t c ha r c h i t e c t u r ea r ea l l u s i n gm u l t i p l a n e m u l t i - s t a g es w i t c hf a b r i c t h i ss w i t c hf a b r i ci sm o r es c a l a b l ea n dr e l i a b l e ，b u ti ts t i l l c o u l dn o tb ea v o i do fc o n g e s t i o nb e c a u s em a n yd a t ac e l l sm a yc o m p e t eo n eo u t p u tp o r t t ot h i sp o i n t ，t h ea c t u a l l ys w i t c hf a b r i cu s u a l l yu s em u l t i p l a n em u l t i - s t a g eb u f f e r e d s w i t c hf a b r i c b e c a u s eo fh i g hp e r f o r m a n c er o u t e ra l w a y sr u n n i n g2 4h o u r se v e r yd a y , i tr e q u e s t s a p e r f e c ts c h e m et od e t e c ta n dd e a l 、析t l lt h ef a i l u r ew h e ns w i t c h f a b r i ch a v i n gs o m ef a u l t l i n k s t h i sp a p e rp a ya t t e n t i o nt of a i l u r ed e t e c t i o na n dp r o p o s eaa l g o r i t h mw h i c hc a n d i s t r i b u t et r a f f i ca c c o r d i n gt oe a c hs w i t c hp l a n e sc a p a c i t y , t h e nw eb u i l tt w od i f f e r e n t o p n e ts i m u l a t i o nm o d e l sa c c o r d i n gt op u s hs c h e d u l i n gs c h e m ea n dp u l ls c h e d u l i n g s c h e m et ov a l i d a t et h ea l g o r i t h m f i r s tw ew i l li n t r o d u c ec i s c oc r s - 1r o u t e r sp u s hs c h e d u l i n gs c h e m ea n dd u n e n e t w o r ks a n ds w i t c ha r c h i t e c t u r e sp u l ls c h e d u l i n gs c h e m e i np u s hs c h e d u l i n g s c h e m em o d e ，w h e no n el mh a ds o m ed a t ac e l l s ，i tc a ns e n di tt os w i t c hf a b r i c i m m e d i a t e l ye x c e p tt h a ti mr e c e i v e dc o n t r o lm e s s a g ef r o ms w i t c hf a b r i c i np u l l s c h e d u l i n gs c h e m em o d e ，w h e no n ei mh a ds o m ed a t ac e l l sb u ti th a dn oc r e d i t ，i tw i l l g e n e r a t eq u e u ec o n t r o lc e l l sa n ds e n dt h e mt oo m w h i c hk e e p sac r e d i tg e n e r a t o rt og e t c r e d i t s ，t h e ni ts e n d sd a t at os w i t c hf a b r i c n e x tw ew i l li n t r o d u c et h ef a i l u r ed e t e c t i o no ft h em u l t i - p l a n em u l t i - s t a g eb u f f e r e d s w i t c hf a b r i c t od e t e c tt h ef a u l tl i n k s ，w en e e dak i n do fe e l lc a l l e d “e m p t yc e l l ”i n s w i t c hf a b r i c ，i ft h e r ei sn od a t a , i mw i l lg e n e r a t ee m p t yc e l l sa n ds e n dt h e mt os w i t c h p l a n e s i ne a c hs w i t c hp l a n e ，s e 3w i l lr e c e i v ee m p t yc e l lf r o ms e 2 ，s e 2w i l lr e c e i v e e m p t yc e l lf r o ms e1 ，a n ds e 1w i l lr e c e i v ee m p t yc e l lf r o mi m i fo n es er e c e i v e dd a t a c e l l s ，i tw i l lf o r w a r dt h e ma c c o r d i n gt h e i ri d ；i fo n es er e c e i v e de m p t yc e l l s ，i tw i l l d i s c a r dt h e m b e s i d e s ，i fo n es es u c ha ss e 2d on o tr e c e i v e da n yc e l l sa tas p e c i a lt i m e f r o mo n ei n p u tp o r tc o n n e c t i n gt os e 1 ；i ts h o w st h e r ea r ef a i l u r el i n k sb e t w e e ns e 2a n d s e 】 i i i a b s t r a c t f o rm u l t i - p l a n em u l t i s t a g eb u f f e r e dp a c k e ts w i t c hs y s t e m ，t h es w i t c hc a p a b i l i t y w i l lb ei n f l u e n c e dw h e no n eo rm o r es w i t c hp l a n e sh a v i n gs o m ef a i l u r el i n k s i fw ed o n o t h i n gt ot h i sp o i n t ，t h es w i t c hp l a n ec o n t a i n i n gf a i l u r el i n k sm a yb ec o n g e s t e dw h e n i n p u tt r a f f i cb e c o m el a r g e r t os o l v et h i sp r o b l e m , w ep r o p o s eaf l o wd i s t r i b u t i o n a l g o r i t h ma n di n t r o d u c ei tc o m b i n e 、舫m3s t a g ec l o ss w i t c hf a b r i c f l o wd i s t r i b u t i o n a l g o r i t h m b a s i ci d e a ：e a c hi mk e e p so n er o u t et a b l ea n dt w ok i n d so fm a r k i n gf i e l d ， o n ef i e l dr e c o r dt h el o c a t i o no ff a i l u r el i n k sb e t w e e ns e la n ds e 2a n dt h eo t h e rf i e l d r e c o r dt h ef a i l u r el i n k sb e t w e e ns e 2a n ds e 3 o n c ea ni mr e c e i v e dac o n t r 0 1c e l l c o n t a i n i n gaf a u l ti n d i c a t i o na n dt h ef a u l to c c u r r e di ns w i t c hf a b r i c ，i tw i l lr e c o r dt h e l o c a t i o no ft h ef a i l u r ea n dd i s t r i b u t et r a f f i ca c c o r d i n gt os w i t c hp l a n e sc a p a c i t y a tl a s t ，t ot e s tt h ep e r f o r m a n c eo ft h ef l o wd i s t r i b u t i o na l g o r i t h m ，w eb u i l tt w o d i f f e r e n to p n e ts i m u l a t i o nm o d e l sa c c o r d i n gt oc i s c oc r s - 1r o u t e r sp u s hs c h e d u l i n g s c h e m ea n dd u n en e t w o r ks a n ds w i t c ha r c h i t e c t u r e sp u l ls c h e d u l i n gs c h e m e 1 1 1 e s i m u l a t i o ns h o w st h a tt h ea l g o r i t h mc a nr e d u c et h ea v e r a g ed e l a ya n dt h eb u f f e rs i z eo f s w i t c hf a b r i c ，a n dt h em e r i tb e c o m em o r ea n dm o r es i g n i f i c a n t 谢t l lt h ei n p u tl o a d i n c r e a s i n g k e y w o r d s ：m u l t i - p l a n em u l t i s t a g e ，f a i l u r ed e t e c t i o n ，t r a f f i cd i s t r i b u t i o n , l o a db a l a n c e ， c o n g e s t i o n i v 图目录 图目录 图1 1 高性能路由器的基本组成3 图2 1 多级c l o s 交换系统7 图2 2v o q 与输出端口的匹配l o 图2 3 仿真模型11 图2 - 4v o q 使用情况1 3 图2 5s e l 平均缓存使用对比1 4 图2 - 6s e 2 平均缓存使用对比1 4 图2 7s e 3 平均缓存使用对比15 图2 8o m 平均缓存使用对比1 6 图2 - 9 端到端平均时延对比1 6 图2 1 0v o q 使用情况1 8 图2 1 1s e l 平均缓存使用对比1 9 图2 1 2s e 2 平均缓存使用对比。1 9 图2 13s e 3 平均缓存使用对比2 0 图2 1 4o m 平均缓存使用对比一2 0 图2 1 5 端到端平均时延对比一2 1 图2 1 6c i s e o 调度的端到端时延( 未进行反压) 2 3 图2 1 7d u n e 调度的端到端时延2 3 图2 1 8c i s c o 调度的端到端时延( 进行反压) 。2 4 图3 1 折叠式三级交换系统示意图2 5 图3 2 线卡及交换结构的结构框图2 6 图3 3 第一级交换单元结构框图2 7 图3 4 第二级交换单元结构框图2 8 图3 5 第三级交换单元结构框图2 9 图3 - 6 多级c l o s 交换系统3 0 图3 - 7 利用广播机制处理错误指示3 2 图3 8 含有错误指示消息的控制报文结构( s e 1 到s e 2 ) 3 3 图3 - 9 含有错误指示消息的控制报文结构( s e 2 经s e 3 到i o 接口) 3 3 v i i 图目录 图3 1o 广播机制3 3 图4 1 多级c l o s 交换系统3 6 图4 2 存在故障的多级c l o s 交换系统3 7 图4 3 输入模块中的数据结构示意图3 8 图4 4 输入模块的路由选择示意图3 8 图4 5 路由选择流程图3 9 图4 - 6 输入模块的路由分发表4 1 图4 7 第一种标记字段。4 2 图4 8 第二种标记字段4 2 图4 9 控制报文格式4 3 图4 1 0 标记字段的更新流程4 4 图4 1 l 反馈指示的更新流程4 6 图4 1 2 路由分发表的更新流程4 7 图4 1 3 第一级交换单元的路由分发表4 8 图4 1 4 路由分发表的更新流程4 9 图4 1 5 路由处理流程5 1 图4 1 6 存在链路故障的多级多平面交换系统5 2 图5 1 仿真总体架构5 4 图5 2s r c 节点模型5 5 图5 3 信元格式。5 5 图5 - 4i m 节点模型5 5 图5 5 队列状态信元格式5 6 图5 - 6c r e d i t 信元格式5 6 图5 7s e l 节点模型5 6 图5 8s e 2 节点模型5 7 图5 - 9s e 3 节点模型5 7 图5 10s i n k 节点模型5 8 图5 1 1s e 3 节点模型。5 8 图5 1 2 仿真参考模型6 3 图5 1 3v o q 使用情况6 5 图5 1 4s e l 平均缓存使用对比6 5 图5 1 5s e 2 平均缓存使用对比。6 6 v l i i 图目录 图5 1 6s e 3 平均缓存使用对比6 6 图5 17o m 平均缓存使用对比6 7 图5 1 8 端到端平均时延对比6 7 图5 1 9 信源速率为1 8 g b p s 输入端到输出端时延( 未采用流量分配算法) 。6 8 图5 2 0 信源速率为1 8 g b p s 输入端到输出端时延( 采用流量分配算法) 6 8 图5 21v o q 使用情况7 0 图5 2 2s e l 平均缓存使用对比7 0 图5 2 3s e 2 平均缓存使用对比7 1 图5 2 4s e 3 平均缓存使用对比7 1 图5 2 5o m 平均缓存使用对比7 2 图5 2 6 端到端平均时延对比7 2 图5 2 7 信源速率为1 8 g b p s 输入端到输出端时延( 未采用流量分配算法) 。7 3 图5 2 8 信源速率为1 8 g b p s 输入端到输出端时延( 采用流量分配算法) 7 3 i x 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 虢j - 吼砷年姗弓日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：拉导师签名：j 碎皿 日期：弘勺c 7 年皇月1 3 目 第一章绪论 第一章绪论 互联网络主要由交换节点以及相应的通信线路互联而成。常用的交换节点有 集线器、网桥、交换机和路由器等，其中最重要的交换节点就是路由器【l 】。 随着互联网络用户的不断扩张以及网络应用的不断发展，互联网流量呈逐年 飞速上升的趋势，这就对网络容量提出了越来越高的要求。 1 1 背景说明 近年来，随着w d m ( 波分复用) 技术特别是d w d m ( 密集波分复用) 技术的 不断发展，光纤带宽的增长以每7 个月翻一番甚至更高的速度增长【2 j 。目前，采用 d w d m 技术的光纤传输速度已经可以达到1 0 0 g b p s 甚至更高【3 j 。光纤通信技术的发 展使得传输线路不再是一个瓶颈。 路由器是一种特殊的专用计算机，它的计算能力服从摩尔定律【4 】，只能达到每 2 年提高一倍，而线路的速度每7 个月提高一倍。因此，路由器的计算速度已经成 为制约互联网络发展的关键瓶颈。 对于拥有庞大交换业务的大型节点来说，采用单级c r o s s b a r 结构的路由器已经 逐渐变得变得力不从心。为了改变这一现状，越来越多的高性能路由器采用了多 级多平面交换结构的设计理念【5 】。目前，c i s c o 公司的c r s 1 高性能路由器以及d u n e 公司s a n d 交换芯片都采用了多级多平面的交换结构。 c i s c oc r s 1 路由器是c i s c o 公司近几年推出的一款具有代表性意义的高性能 核心节点路由器，其最大交换容量可以达到9 2 t b p s 。c i s c oc r s 1 路由器主要由两 个组件构成：线卡机架和交换机架。线卡机架主要包括线卡、路由处理器等，交 换机架主要由多级交换结构组成。c i s c oc r s 1 可以采用两种配置：单机架系统和 多机架系统。单机架系统将多级交换功能集成到了一个线卡上，可以提供1 2 t b p s 的交换容量和1 6 个4 0 g b p s 的线卡插槽；多机架系统最多可以容纳7 2 个线卡机箱， 它们之间通过8 个交换矩阵互联，最高可以提供1 1 5 2 个4 0 g b p s 线卡插槽和9 2 t b p s 的总交换容量【6 】【7 】。 c i s c oc r s 1 系统一个重要的优点是采用了一种基于b e n e s 架构的、针对分组 网络优化的三级交换结构。这种交换结构的独特之处在于，它可以利用固有的组 电子科技大学硕士学位论文 播复制功能和集成化优先级队列，改进传统的三级b e n e s 架构。利用它的组播复 制功能，运营商可以在不影响系统或网络性能的情况下，向大量客户提供同一服 务。另外，这种交换结构还采用了流量加速技术，它可以将流量速度提升2 5 0 ， 确保c i s c oc r s 1 中不会发生系统拥塞f 8 】f 9 】【1 们。 d u n e 公司s a n d 交换芯片采用双器件解决策略，它是d u n e 公司在网络和存 储平台领域首次使用相同的芯片组建立一个全能力交换芯片，将其使用的生命周 期扩展至8 年以上。s a n d 交换芯片的功能有：双器件的策略支持输入输出的流 量管理和非阻塞交换；在不降低时延、抖动和损耗等性能的基础上支持任何流量 模式；通过增加端口数( - - n 几千) 和端口速率( 由1 1 g b p s 和5 0 g b p s 增加到2 1 0 g b p s 和2 7 0 g b p s ) 使得其吞吐量可升级；支持基于硬件的、反应时间低于l l m s 的、自 恢复的交换；支持对数据包的检测、隔离和修复；可升级、支持低于2 1 0 m s 的基 于d r a m 存储的片内流量管理；单个流的队列调度同时支持不同的q o s 规则，包 括a t m 等级、i p 和m p l s 区分服务、t d m ；支持5 0 b y t e s 到1 1 kb y t e s 的变长分 组。d u n es a n d 结构配合它的f ：a p 系列芯片，最高的交换容量也可以达到9 0 t b p s 。 另外，s a n d 结构提供的容错功能非常强大，s a n d 芯片组可以在故障产生的1 0 m s 内检测到故障并对产生故障的部分进行隔离。同时，s a n d 还支持在软件层面上 作一些设置，使得故障的恢复更容易1 1 1 【1 2 】【13 1 。 1 2 高性能路由器的组成 如图1 1 所示，路由器在逻辑上可以抽象为4 个部分，输入端口、交换结构、 输出端口和路由处理器。 2 第一章绪论 图1 - l 高性能路由器的基本组成 通常情况下，输入端口与输出端口、以及路由处理器都集成在线卡上实现。 数据报文进入输入端口后，先进行路由查表，然后确定输出端口。对高性能 路由器而言，路由查表在每个线卡上进行【1 4 1 。 交换结构是连接输入端口和输出端口之间的桥梁，它是基于交换技术和原理， 在多个输入和输出之间完成交换功能的一个或一组芯片【l5 1 。交换结构主要有 c r o s s b a r 交换结构和多级交换结构。与单级c r o s s b a r 交换结构不同，多级交换结构 是由多个交换单元互联而成的，交换单元与普通c r o s s b a r 交换开关类似，提供输 入输出的连接。通过互联多个小的交换单元就可以制造一个大型的、可扩展的交 换结构。多级交换结构之间的不同取决于交换单元的互联方式，目前常用的多级 交换结构有多级c l o s 交换结构和多级b e n e s 交换结构等。 输出端口的主要作用是存储报文，并向出口链路进行调度。 路由处理器的主要功能是运行路由协议，生成路由转发表，并且控制报文的 转发等。 1 3 交换结构 线卡和交换结构是路由器中两个很重要的器件。线卡是数据进出路由器的端 口，它提供了从物理层和更高层到交换结构的接口。交换结构为线卡提供了数据 通道，使得数据包能从进入的线卡转发到目的线卡。为了能够有效的扩展交换结 3 电子科技大学硕士学位论文 构的容量，在高端路由器中，普遍采用多级交换结构。 常见的多级交换结构有c l o s 结构、b e n e s 结构、c a n t o r 结构等。目前对其它 结构的研究也很多，参见【1 7 】【1 8 】【1 9 1 ，c l o s 结构具有扩展性强和容错性能高等优点， 在大容量路由器交换网络设计中受到了越来越多的青睐 2 0 1 ，本文主要研究的是多 级多平面c l o s 交换结构。 在多路径交换中，从某个输入到某个输出端的路径有多条，c l o s 结构是典型 的多级多路径结构1 2 ，1 9 5 3 年3 月，c h a r l e sc l o s 在( ( b e l ls y s t e mt e c h n i c a l j o u r n a l ) ) 上发表了著名的论文c as t u d yo f n o n b l o c k i n gs w i t c h i n gn e t w o r k s ) ) 2 2 j 。 c l o s 在论文中提出了一种具有创新意义的交换结构，并精确地证明在交换容量相 同的情况下，这种交换结构支持构建严格意义上的无阻塞交换，其中包含的交叉 点比纵横交换的要少。例如，c l o s 表明，严格的无阻塞1 0 0 0 x 1 0 0 0 纵横交换需要 1 0 0 0 0 0 0 个交叉点，而c l o s 交换结构仅需要18 6 7 3 7 个交叉点，更大容量的交换 甚至会减少更多的交叉点。在c l o s 的论文发表后的5 0 多年里，交换技术不断发 展，但是c l o s 提出的体系结构在大容量交换结构的开发中继续发挥着重要作用 2 3 1 o c l o s 无阻塞交换结构分为严格无阻塞( s t r i c t l yn o n b l o c k i n g ，s n b ) 和可重排无 阻塞( r e a r r a n g e a b l en o n b l o c k i n g 。r n b ) 。如果交换结构不改变现有的连接，就能 在空闲输入链路到空闲输出链路之间建立一个连接，那么这个交换结构就是s n b 否则，就是i 矾b 。 实际上，相对于由单级c r o s s b a r 构成的严格无阻塞交换结构来说，多级严格 无阻塞c l o s 交换结构已经节省了很多的资源，但是相比于多级可重排无阻塞c l o s 交换结构来说，严格无阻塞c l o s 交换结构仍然要多花费不小的链路资源和硬件资 源，同时也会在一定程度上增加转发表的负担；另外，由于交换结构一般不会一 直处于全负荷工作状态，使用严格无阻塞c l o s 结构会产生一定的资源浪费。因此， 在采用c l o s 交换结构的高性能路由器中，一般采用的是多级可重排无阻塞c l o s 交换结构( 目前使用最多的是3 级可重排无阻塞c l o s 交换结构) ，由于可重排无 阻塞c l o s 交换结构有时候可能会造成阻塞，而目前的重排序算法尚不成熟，普遍 的解决方案是在交换结构中加入少量的缓存来降低可能发生阻塞的概率。 1 4 主要研究内容 随着网络业务流量的增多，电信运营商和大型网络公司对路由器性能的要求 4 第一章绪论 也越来越高，对路由器性能的要求已经不单单是交换能力的大小，还包括可管理 性、易扩展性、可靠性等多个方面的内容。目前，大部分运营商都将路由器的可 靠性与稳定性作为第一要求，比如要求路由器能够在3 分钟内重启，系统管理软 件可以不中断地进行升级，电信网络要求至少9 9 9 9 9 的可靠性等。 本文主要针对大容量高性能路由器采用的交换结构进行分析，特别是对多级 多平面的c l o s 交换结构进行可靠性方面研究，主要包括以下三个方面的内容： 第一：交换结构发生链路故障时，如何快速准确地将故障情况通报所有可能 受到其影响的交换模块。研究内容包括链路故障的检测，产生包含故障链路的流 量控制信息，修改更新路由分发表等，最终形成一个故障链路检测机制。 第二：检测到链路故障后，针对不同的情况，做出不同的合适的处理方式， 并且保证各交换平面流量的负载均衡。研究内容包括针对输入模块与交换平面之 间的链路故障、交换平面内部第一级交换模块单元与第二级交换模块单元之间以 及第二级交换模块单元与第三级交换模块单元之间的链路故障、交换平面与输出 模块之间的链路故障分别做出合适的处理，并且保证流量发送的负载均衡，最终 形成一种保证各交换平面负载均衡的流量分配方法。 第三：通过搭建o p n e t 网络仿真平台，并分别采用d u n es a n d 交换芯片的p u l l 调度机制和思科c r s 1 路由器的p u s h 调度机制对流量分配算法进行了仿真验证。 另外，本文还对c i s e oc r s 1 路由器采用的p u s h 类型的调度机制和d u n e s a n d 交换芯片采用的基于令牌的p u l l 类型的调度机制进行了仿真对比与分析。 1 5 章节安排 下面介绍章节组织架构，本文共分为六章。 第一章为绪论部分，首先提出研究背景，简要介绍了c i s c oc r s 1 路由器和d u n e s a n d 交换芯片，阐述了高性能路由器的逻辑组成，然后对高性能路由器中的线卡 和交换结构进行说明。同时，对本文的主要研究内容进行说明，给出了本文的研 究思路和研究方法。 第二章主要介绍c i s c oc r s 1 高性能核心路由器采用的p u s h 调度机制以及 d u n e s a n d 交换芯片的p u l l 调度机制，并且采用o p n e t 仿真平台对这两种调度机制 进行分析对比。p u s h 调度机制的思路是：当输入模块中有数据信元需要发送时， 立刻将其发送到交换结构中，除非从交换结构收到流量控制信息；p u l l 调度机制 的思路是：输出模块维持一个令牌生成器，输入模块中有数据信元但没有令牌时， 5 电子科技大学硕士学位论文 必须先向输出模块发送队列状态信息获得令牌，然后才能向交换结构发送数据。 在仿真分析时，一共取三种仿真场景：第一种情况是c i s c o 的交换结构4 倍加速而 d u n e 的交换结构不加速；第二种情况是c i s c o 和d u n e 的交换结构都进行4 倍加速； 第三种情况是c i s c o 和d u n e 的交换结构都不进行加速。其中，前两种情况比较的是 常规情况下的时延以及缓存占用情况等，第三种情况主要分析c i s c o 的p u s h 调度方 式的反压控制效果，然后与d u n es a n d 交换芯片的p u l l 调度方式的仿真结果进行对 比分析。 第三章主要介绍多级交换结构的故障检测机制及其改进方法，并对这些检测 机制、实现方法进行分析。针对d u n e 文档中通过发送可达性信元来进行故障检测 方法的缺点，给出了一种通过发送“空 信元进行故障检测的方法。故障检测思 路为：交换平面内的每个交换模块单元以及输出模块都会源源不断地接收来自“上 游 的信元，如果暂时没有数据信元发送，“上游”模块单元就向与之相连的模块 单元发送一种特殊形式的“空”信元，“下游 的模块单元收到信元后，对其进行 判断。如果为数据信元，则按照数据信元的目的i d 号码将其转发到相应的输出链 路中；如果收到的是“空 信元，则不对其进行转发，而是将“空信元丢弃； 如果在规定的时间内某个模块单元既没有从某个输入端口收到数据信元，又没有 收到“空”信元，则这个模块就判定该输入端口所在的链路出现故障。 第四章主要根据第三章的故障检测机制和方法，提出一种流量分配算法并且 结合3 级c l o s 交换结构对流量分配算法进行说明。流量分配算法的思路是：每个 输入模块单元为它的输出端口维持一张路由分发表和两种标记字段，其中，第一 种标记字段用于记录交换平面内第一级链路故障的位置，第二种标记字段用于记 录交换平面内第二级链路故障的位置；一旦输入模块接收到一个包含故障指示的 控制分组，并且故障发生在交换结构内部，输入模块便记录故障的位置，然后根 据流量分配算法来控制流量的发送。流量分配算法可以根据各个交换平面的处理 能力来调整流量的发送，有利于保持各交换平面的负载均衡。 第五章主要对第四章的流量分配算法进行仿真验证，通过搭建o p n e t 仿真平 才，并参照c i s c oc r s 1 高性能路由器以及d u n es a n d 交换芯片的调度机制对流量 分配算法进行仿真验证。仿真结果表明，采用流量分配算法后，数据信元的输入 端到输出端时延以及交换结构的缓存使用等都会得到一定的改善；在负荷较大时， 故障链路所在交换平面出现拥塞的概率明显降低。 第六章对全文进行总结并提出下一步的研究方向。 6 第二章多级交换结构的调度机制 当前的高性能核心路由器大多采用了多级多平面的交换结构，这种交换结构 具有易扩展强，可靠性高等特点，但是也存在造成交换结构内部拥塞的可能。当 出现拥塞时，通常采用“p u s h 调度机制或“p u l l 调度机制产生控制消息来通知 输入模块( i m ) 进行处理。 2 1p u l l 与p u s h 调度机制 思科的c r s 1 系列高性能核心路由器，以及d u n e 公司s a n d 交换芯片均采 用了多级多平面交换架构，但调度机制有所不同，c r s 1 路由器采用的是p u s h 类 型的调度机制，而d u n e 公司s a n d 交换芯片则采用了p u l l 类型的调度机制。 图2 - 1 多级c l o s 交换系统 7 电子科技大学硕士学位论文 图2 1 给出了一个简单的多级多平面c l o s 交换系统，它由i m 模块、交换结构、 o m 模块三部分组成，交换结构采用的是可重排无阻塞c l o s 网络架构【2 5 1 。其中， i m 模块和o m 模块的数目均为1 2 个，每个i m 模块有3 个输出端口，分别连接交 换结构中的三个交换平面，每个交换平面是一个三级c l o s 网络，第一级和第三级 由4 个3 3 的交换单元组成，第二级由3 个4 x 4 的交换单元。 在i m 中，数据分组首先被切割为数据信元，然后才进行发送。在o m 中，需 要将数据信元组合为数据分组。 c i s c o 公司的c r s 1 高性能路由器采用“p u s h ”调度机制，它的各主要模块的 调度思路如下： i m ( 输入模块) ：当v o q 中有数据信元需要发送时，如果当前没有收到 这个v o q 对应的流量控制信息，则可以直接选择输出端口并发送数据信元；如果 收到对应的流量控制信息，则根据流量控制信息信息减小数据信元的发送。 c m ( 中间级模块) ：由各交换平面组成，主要负责数据信元及控制信元的 转发，s e l 对数据信元直接进行转发，s e 2 和s e 3 需要根据数据信元的目的o m 地址进行转发。另外，s e 2 和s e 3 为它的每条输出链路维持一段缓存，用于存放 相应的数据信元，当数据信元所占缓存大小超过一定门限( 表明接收的数据信元 过多，需要通知i m 减小数据信元的发送) ，就产生流量控制信息并且将其组播或 广播到相应的i m 。 o m ( 输出模块) ：o m 的主要作用是接收由交换结构发来的数据信元。 d u n e 的s a n d 交换芯片采用“p u l l 调度机制，它的各主要模块的调度思路 如下： i m ( 输入模块) ：i m 为它的每个v o q 都维持应该令牌计数器。当v o q 中有数据信元需要发送时，首先判断其对应的令牌计数器的数值，如果令牌计数 器数值非负，则选择空闲输出端口并且发送数据，并且更新相应的令牌计数器的 数值；如果令牌计数器数值为负数，则暂停发送数据。同时，i m 需要向o m 发送 队列状态信元来请求令牌，这个队列状态信元可以是周期性产生，也可以异步产 生1 2 6 1 。 c m ( 中间级模块) ：由