（通信与信息系统专业论文）大容量路由器可扩展交换结构与路由算法的研究.pdf

摘要本文是根据8 6 3 项目“高性能宽带信息示范网创新技术研究t 比特级路由器交换网络关键技术研究”的工作内容撰写。由于分仃互连式交换网络能够处理高速率的数据，并且拼j 有很好的可扩展性，符合了市场的需要，所以足t比特级路由器广泛采用的一种方案。交换网络主要包括直连网络和级连网络两大类。作为大容量路由器的交换网络，它们具有各自的优势和劣势。本文分别对这两种交换网络作了研究。本文有关直连网络的研究部分主要是对可扩展直接连接网络2 dt o r u s 在不同业务源、链路利用率、路由算法、内部链路速率下的时延、分组丢失率进行了仿真与分析，并对单结点所需输出缓存容量和丢失率的关系作了研究。对于级连网络，本文建立了一种新的类似于三级c l o s 网络，但具有良好扩展性的三级网络m r ( m a g i c 。r i n g ) 网络模型，并实现了一种基本的路由算法和几种有o o s 保证的路由算法，比较了在均匀流量模式下，不同注入流量、不同规模、不同路由算法下m r 网络的端到端时延性能，同时由于c l o s 网络是一种经典的具有良好性价比的交换网络，将m r 网络与同样规模的重配置无阻塞三级c l o s 网络进行了对比，在网络规模不是很大时，m r 网络的时延性能可以很接近c l o s 。本文给出了t 比特路由器实现的大致框架，还有很多问题，如交换网络采用何种交换机制( 电路交换、分组交换、虫孑l 交换和直通交换等) ，采用何种拥塞控制机制和流量均衡策略，以及调度算法如何保证所转发业务的服务质量( q o s ) ，组播业务如何支持等还有待于进一步研究、完善和实现。关键词：t 比特路由器直连网络级连网络丢失率路由算法a bs t r a c ta s s o c i a t e dw i t ht h en a t i o n a l “8 6 3 ”h i t e c hp r o j e c t “r e s e a r c ho nn e wt e c h n o l o g i e so fh i g hp e r f o r m a n c eb r o a d b a n di n f o r m a t i o nn e t w o r kk e yt e c h n 0 1 0 9 i e so fs w i t c h i n gf a b r i c si nt e r a b i tl e v e lr o u t e r s ”i nt h i st h e s i s ，w em a d eo u rr e s e a r c ho nt w ok i n d so fs w i t c h i n gf a b r i c ，i n c l u d i n gd i r e c tn e t w o r ka n dm u l t i s t a g en e t w o r k ，r e s p e c t i v e l y t h er e s e a r c ho nd i r e c tn e t w o r kf o c u s e so n2 dt o m s ，o n eo ft h ep o p u l a ra r c h i t e c t u r eo fd i r e c tn e t w o r k si nt h er o u t e r u n d e rd i f f e r e n tt r a f f i cs o u r c e ，l i n ku t i l i z a t i o nf a c t o ra n dr o u t i n ga l g o r i t h m s ，2 dt o r iw i t hd i f f e r e n ts i z ea r ea n a l y s e da n ds i m u l a t e di nt e r m so ft h ep a c k e tl o s sr a t ea n dd e l a ya sp e r f o r m a n c em e a s u r e m e n t i nt h ea s p e c to fm u l t i s t a g en e t w o r k s ，m a g i c r i n g ( m rf o rs h o r t ) ，an e wc o s t - e f f e c t i v es w i t c h i n gf a b r i ci sp r o p o s e da n di t ss i m u l a t i o nm o d e li sc r e a t e d ab a s i cr o u t i n ga l g o r i t h ma n ds e v e r a lo t h e rq o s g u a r a n t e e do n e sa r ep u tt o n a 。d u n d e rd i f r e r e n tr o u t i n ga l g o r i t h m sa n dt r a f f i ci n j e c t e d ，m rn e t w o r k sw i t hd i f f e r e n ts i z ei sa n a l y s e da n ds i m u l a t e di nt e r m so fd e l a ya sp e r f o r m a n c em e a s u r e m e n t a tt h es a m et i m e ，t h ep e r f o r m a n c ec o m p a r i s o no fm rn e t w o r ki sm a d ew i t hat r a d i t i o n a lt h r e es t a g er e a r r a n g e a b l yn o n b l o c k i n gc l o sn e t w o r ki nt e r a b i tl e v e lt o u t e r s b yc o m p a r i s o n ，i ti sf o u n dm rn e t w o r kc a na c h i e v et h es a m ed e l a yp e r f o r m a n c ea st h r e es t a g ec l o sn e t w o r ki nn o tv e r yl a r g es c a l e t h i st h e s i sd e s c r i b e st h em o d e lo fl a r g ec a p a c i t yr o u t e rr o u g h l y , t h e r ea r es t i l lag o o dm a n yp r o b l e m sl e f tt ob es o l v e d ，s u c ha st h ec h o i c eo fs w i t c h i n gs t r a t e g y ( 1 e ，c i r e u i ts w i t c h i n g ，p a c k e ts w i t c h i n g ，w o r m h o l eo rc u t t h r o u g hs w i t c h i n g ) ，t h ec h o i c eo fc o n g e s t i o nc o n t r o la n dt r a f f i cb a l a n c i n gm e c h a n i s m ，r o u t i n ga l g o r i t h m ss u p p o r t i n gm u l t i c a s t ，p a c k e ts c h e d u l i n gf o rg u a r a n t e e i n gd i f f e r e n tt y p eo ft r a f f i c ，a n ds oo n k e y w o r d ：t e r a b i tl e v e lr o u t e rd i r e c tn e t w o r km u l t i s t a g en e t w o r kl o s s r a t er o u t i n ga l g o r i t h m创新性声明本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及所取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其它人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切相关责任。本人签名：日期：j 卯卜7关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公稚论文的全部或部分内容，可以允许采用影印、缩印、或其它复制手段保存论文。( 保密的论文在解密后遵守此规定)本学位论文属于保密，在三年解密后适用本授权书。本人签名：垒羔孟垫日期：塑坐：lz ：导师签名：3 懈i 日期：型第1 章绪论第1 章绪论随着光宽带传输技术的发展和成熟应用，传输链路已不再是限制骨干网发展的因素，而作为网络结点的交换机或路由器却成为“瓶颈”。网络设备的生产商以及从事网络通信的研究机构纷纷把实现高速、有服务质量保证的路由器作为开发和研究的重点。国际市场上主要的t ( t e r a b it ) 比特路由器厂商有c i s c o ，a v i c i ，l u c e n t 等大型公司。典型的产品有a v i c it s r 4 0 、p l u r i st e r a p l e x 2 0和l u c e n t n x 6 4 0 0 0 等。目前，虽然我们国内还没开发出t 比特级、可以连接o c 一1 9 2 以上端口的大容量高端路由器，但是国内各大电信设备制造商和研究机构已经开始了在这方面的努力探索。研究开发具有我国自主知识产权的t 比特级高端口路由器已被列为“8 6 3 ”计划“高性能宽带信息示范网”重点研究子课题之一。1 1路由器的一般结构从图1 1 可以看出一个路由器主要由输入端口、输出端口、交换网络和路由处理器四部分组成，各部分功能如下： 输入端口是物理链路和数据分组的入口，通常由线卡( l i n ec a r d ) 提供。一个输入端口具有多种功能。第一个功能是进行输入d 数据分组的解封装。第二个功能是在转发表中查找输入分组目的地址从而决定目的端口( 称为路由查找) ，路由查找可使用一般的硬件来实现，或者通过在每块线卡上嵌入一个微处理器来完成。第三，为了提供q o s ( 服务质量) 保证，端口要将收到的分组分成几个预定义的服务级别。第四，端口可能需要运行诸如s l i p( 串行线网际协议) 和p p p ( 点对点协议) 这样的数据链路层协议或者诸如p p t p ( 点对点隧道协议) 这样的网络级协议。一旦路由查找完成，必须用交换网络将分组送到其输出端口。如果路由器采用输入排队，这样输入端口的功能还包括对公共资源( 如交换网络) 的仲裁占用。 输出端口在分组被发送到输出链路之前将分组排队，可以通过实现分组的调度算法来完成支持优先级等要求。与输入端口一样，输出端口同样要能支持p 数据分组的封装以及多种高级协议。 路由处理器可以在路由器中集中式实现，也可以在线卡中分布式实现，它主要用来计算转发表，实现路由协议，并运行对路由器进行配置和管理的软件。同时，它还处理那些目的地址不在线卡转发表中的分组。 交换网络是连接输入端口和输出端口的“桥梁”，它负责在路由处理器的控制下将输入端口分组转发到输出端口。在中、低容量路由器中常使用的交换人容龉路由器可扩展交换结构及路山算法的研究三网络有总线( b u s ) 结构、共享存储器( m e m o r ys h a r e d ) 结构以及交叉丌关( c r o s s b a r ) 结构。总线结构通过一条总线来完成输入和输出端口的连接，这种结构的最大缺点在于其交换容量受限于总线容量，在大容量路由器中对总线容量的要求太高，所以在高端大容量路由器中一般不采用这种结构。共享存储器结构将从各个输入到达的分组通过复用器被复用成单一的输入分组流写入共享存储器中，在写入时按照各个分组的目的端口而写入对应的输出队列。这种结构的最大缺点在于存储器的读写速度跟不上网络对路由器容量增长的要求，将成为发展的瓶颈。交叉开关结构( c r o s s b a r ) 分为矩阵型和全互连型( 分离通路型) ，其共同特征是复杂度随n 2 增长。前者通过交叉点丌关来提供多条并行数据通道，交叉点开关的打开或闭合由路由处理器来调度。这种方式的主要瓶颈在于调度器的速度和结点开关的速度。随着硬件工艺水平的提高和采用分布式处理，完成吉比特级交换路由器( g s r ) 的交换开关已经实用化。然而，要完成t 比特级的路由交换( t s r ) 采用单个交换开关目前还远远达不到。另外，由于交换开关的结点数和输入端口的平方成j 下比，这种结构向大容量高端口发展时，成本高、扩展性差。所以，在大容量高端路由器中选择何种交换网络拓扑是很值得研究的课题之一。图1 1 路由器结构示意图1 2国内外主要的t 比特级路由器产品火型路由器厂商均致力于丌发下一代t 比特路由器，目前成熟的t 比特级路出器产品并彳：多，国内外厂商都在积极研究和丌发这种高性能路由器的技术和产品。第1 章绪论1 2 1国外主要的t 比特路由器产品目前成熟的t 比特路由器产品主要有a v i c it s r 4 0 、p l u r i st e r a p l e x 2 0 和j u n i p e rt 6 4 0 、l u c e n t n x 6 4 0 0 0 等，这些产品的实现方法各异，下面对几种成熟的产品做简单介绍，详细资料请参考文献 1 3 。a v i c it s r 4 0 a v i c i 的t 比特交换式路由器t s r 一4 0 采用折叠的三维t o r u s 网络交换结构( 已申请专利) ：支持2 2 4 0 个0 c - 4 8 或5 6 0 个0 c - 1 9 2 连接，交换容量达到5 6 t b p s ，系统支持多协议标记交换( m p l s ) 。该设备由多个机框组成，单个机框的交换容量为4 0 0 g b p s ；线卡的类型包括o c 一3 c s t m 一1 ，o c 一1 2 c s l m - 4 ，0 c 一4 8 c s t m - 1 6 ，0 c 一1 9 2 c s t m 一6 4 等，每个线卡实现t o r u s 网络的单个结点的功能，每个结点都包含简单路由器的所有功能；软件采用其自己的i p r i o r i 系统，支持多种路由算法。该网络采用自适应路由方式，以获得良好的容错和负载均衡能力；网络中采用大量的缓存，在一个统一的物理网络中为到不同输出端口和不同种类( 在t s r 4 0 中业务分为两类：保证比特率业务和尽力服务业务) 的业务提供了分离的虚c r o s s b a r 网络，实现了业务的无阻塞传输和一定的服务质量( o o s ) 保证。在t s r 4 0 中采用了精巧的网络折叠技术，交换网络的实现可以由统一的短线来完成，提高了网络带宽和系统成本，同时，t s r 4 0 采用电交换，只在机架间采用光交换。p l u r i st e r a p l e x 2 0 系列2 1p l u r i s 推出的t e r a p l e x2 0 路由器采用光背板实现，利用l o g b p s 全双工的光纤链路完成单个机架的光背板以及机架和机架之间的连接，构成一个超立方体结构。每个机框最高速率支持1 5 个o c 一1 9 2 接口卡，单个机架的交换容量为1 4 4 t b p s ，并可组成1 2 8 个机架的总交换容量可达1 8 4 t b p s 的系统。整个路由器从硬件到软件均采用分布式体系结构，硬件采用6 个自己设计的a s i c 来实现线速转发，包分类，调度和拥塞控制，软件支持b g p - 4 ，o s p f t e ，i s - i s t e 和m p l s 等。j u n i p e rt 6 4 0 系列n 。j u n i p e r 的t 6 4 0 路由器既可单独配置，也可以通过t x 8 的交换机架连接而成更大的路由器。在一个单机框系统中，交换网络由4 个独立运行的交换平面和用于热备份以提供冗余性的第5 个交换平面组成。每个交换平面包含一块1 6端口的交换网络a s i c ，用作c r o s s b a r 。2 个单机框t 6 4 0 路由器可组装成一个机架。单机框t 6 4 0 路由器支持3 2 x o c l 9 2 s t m 一6 4 和1 2 8 x o c 一4 8 s t m 1 6 接口。与j u n i p e rm 系列路由器相比，t 6 4 0 两年内在带宽密度上提高了4 倍。由多个1 6 端口的交换网络单元a s i c 构成的3 级c l o s 网络组成的交换机架t x 8 连接各个机架构成更大容量的路由器。硬件采用自行设计的t 系列a s i c 芯片组，完成人容茸路由器可扩展交换结构及路由算法的研究4第二层第三层分组的处理、交换接口、队列和缓存、交换网络互连以及网络处理功能。软件是单一影像的分布式j u n o s 网络操作系统以及相应的组件。这种结构的优点是交换网络可以实现重配置无阻塞交换，业务转发具有公平性，具有一定冗余和容错能力。1 2 2国内高性能路由器的发展状况在已完成的“中国高速信息示范网”中，运行的核心路由器有中兴通讯研制的z x r l 0 、国防科大与大唐电信共同研制的“银河玉衡”核心路由器。中兴通讯研制的路由器在高速接口电路、i p 地址的线速查找、交换式高速背板、大容量交换结构、高速端口实现、a s i c 设计、以及分布式软件体系结构等多项关键技术取得重大突破，并申报了五项国家发明专利。z x r l 0 已经达到6 4 g 的交换容量，4 8 m p p s 的包转发能力，5 0 2 0 0 万条路由表项，支持2 5 g 高速端口，提供丰富的协议、网络接口和丰富的网络管理特性，已经达到二十世纪9 0 年代术期的国外高性能路由器的水平。由国防科技大学计算机学院与大唐电信共同研制开发的“银河玉衡”核心路由器是我国首台拥有自主知识产权的高端线速核心路由器，这台路由器达到了2 5 m p p s 的包转发能力，4 0 g 的交换容量，它在分布式体系结构、无阻塞交换网络、大步调度策略、网络处理器、协议软件分布等关键技术上取得了突破。谈到技术突破，虽然华为核心路由器产品没有出现在“示范网”中，但是它推出的n e 8 0 与国际先进水平更加接近，n e 8 0 具备大容量、高端口密度的特性，支持1 2 8 g 的线速无阻塞交换。采用了业界先进的网络处理器技术，实现了2 5 g接口的m m p l s 线速转发，整机处理能力超过7 2 m p p s 。1 3t 比特路由器中的关键技术从1 2 节的介绍可以看出，国外的几种成熟t 比特级路由器产品采用的都是分布互连式方案。这种方案的提出是受采用分布式系统( d i s t r i b u t e ds y s t e m )超大规模并行计算机系统的启发。因此我们的研究方向就是研究如何实现易于扩展，具有高性能的分稚交换式路由器。分布交换式路由器的关键技术问题很多，包括交换拓扑的选择、路由算法、调度算法的设计以及反压机制、流量控制和多播的实现等，以下只对交换网络拓扑和路由算法做简要介绍。1 3 1交换网络的拓扑结构交换网络的交换结构分为单级交换网络、多级交换网络。其中单级交换网络中c r o s s b a r 结构能够在每条输入与输出之间提供独立、直接的通路，内部阻塞小，因而被广泛采用。但是构造c r o s s b a r 的复杂度按输入输出端口数目的平第1 章绪论方率增长，因此构造规模很大的交换网络往往采用多级互连方式，把多个c r o s s b a r 交换单元按照一定的规则连接起来。这种互连方式又分为两大类，一是直接连接网络，另一种是i 自j 接连接网络。直接连接网络最早应用于并行交换机中把多个计算结点连接起来，而后又应用于路由器中，如a v i c i 公司的路由器t s r 一4 0 就采用这种结构。另一种连接方式是间接连接网络，传统的a t m 交换机都采用这种方式，典型的如b a n y a n 网络、c l o s 网络，在j u n i p e r 的t 6 4 0 中就是采用c l o s 网络来实现路由器的逐级扩展。1 3 2 路由算法路由器的拓扑结构确定以后，路由算法负责为分组在交换网络中选择一条从输入端口到输出端口的路径。它们不但影响着整个路由器的吞吐率，同时也影响着用户业务的时延、时延抖动。随着i n t e m e t 中不断引入新的业务，因此新一代的路由器应该为各类业务提供有服务质量保证的服务。服务质量在路由器中体现为分组的时延、时延抖动、分组丢失率等。i n t e r n e t 中针对服务质量，提出过两种模型，一种是集成服务模型，另一种是区分服务模型。集成服务模型能够为用户确保分组的时延，但是需要路由器维护每个业务流的状态信息，丌销较大，可扩展性较差。而区分服务模型将业务流划分为优先级不同的类，保证每一类业务能够得到不同对待。区分服务模型实现简单，但是高优先级的业务能否得到满意的服务，需要互连网的资源得到合理的分配和使用，一般采用流量工程和接入控制的方法。作为网络的核心设备，t 比特路由器实现q o s 机制是必然趋势，而交换网络又是t 比特路由器的核一t l , ，在研究服务质量问题中的一个关键技术是优化选路的q o s 路由技术。o o s 路由的主要目标是为接入的业务选择满足其服务质量要求的传输路径，同时保证网络资源的有效利用。q o s 路由是在给定的拓扑结构中，根据特定的q o s 参数以及交换网络的可用资源，为不同q o s 要求的数据流路由的机制。度量参数的选择直接关系到算法的复杂度【l3 1 ，其中常用的q o s 参数可能包含可用带宽、时延、时延抖动、跳数、以及资源消费量等。相应的路由策略包括源路由策略、分布式路由策略等。源路由具有简单、集中处理和不产生环路的优点，但是扩展性不好，为与不断变化的网络参数( 如带宽和时延) 保持一致，结点的全局状念必须频繁更新，这对大型网络来说开销很大。另外，为减少开销而降低更新频率以及更新消息本身有一定的传播时延，结点只能提供不太精确的状态信息。结果q o s 路由可能发现不了实际存在的一条可行路径。采用分布式路由对于每个路由器来说可以节省内存，因而具有较少的额外丌销以及较短的建立时间等优点。但是，分布式路由由于没有详细的拓扑信息和人容最路由器可扩展交换结构及路由算法的研究6链路信息，当不同结点的全局信息不一致时，就有可能产生环路，从而导致路由失败。1 4论文内容及安排本文所作的工作是属于8 6 3 研究项目“高性能宽带信息示范网创新技术研究t 比特级路由器交换网络关键技术研究”，主要完成的工作如下： 对可扩展的直连网络结构2 d t o r u s 网络性能进行了研究。与课题组其他成员共同提出了一种类似于c l o s 网络，但具有良好可扩展交换性的网络拓扑一m r ( m a g i cr i n g ) 网络。 建立了多级间接连接网络的仿真模型。 利用该模型分析了不同规模、路由算法下m r 网络的性能。本文研究的重点是路由器的可扩展交换结构及路由算法，从路由器设计的全局性出发，分为以下几个部分：第二章介绍大容量路由器的各种交换结构，重点介绍直连网络的2 维平面结构2 d t o r u s ，总结了直连网络和级连网络的优点和不足，第三章详细介绍m r网络的拓扑结构，在理论上分析其扩展性，将m r 与经典的具有良好性价比的交换网络c l o s 进行对比，同时针对其特殊的交换结构特点提出多种路由算法，最后建立m r 网络仿真模型，对均匀流量模式下不同规模、不同路由算法、不同注入的m r 网络性能进行了仿真与分析。第四章提出直连网络结构2 d t o r u s仿真模型，并给出了不同流量模式、不同路由算法、链路利用率和速率下2 d t o r u s的性能曲线，第五章总结全文，指出工作的不足和还需进一步研究的内容。第2 章大容量路由器的交换结构第2 章大容量路由器交换结构交换网络结构( s w i t c h i n gf a b r i c ) 可以从不同方面进行分类，主要包括从时分和空分、单通路与多通路、单级与多级等方面。在大容量高端路由器中空分交换应用很广，所以这罩所讲的交换网络结构主要是指空分交换网络结构。下面首先介绍一下交换网络结构的分类。2 1 网络拓扑的分类如前所述，构造规模大的交换网络往往采用多级互连方式，把多个c r o s s b a r交换单元按照一定的规则连接起来。这种互连方式又分为两大类，一是直接连接网络1 引，另一种是间接连接网络1 6 】【7 】。在分析这些网络时，我们把连接的对象( 如交换单元) 称为结点，连接结点的单向或双向链路称为边。直接连接网络是指结点之间直接连接，每一个结点都是具有完整路由器功能的自治系统，控制简单，便于实现分布式管理，具有良好的可扩展性，有关大规模直连网络交换拓扑的研究，见参考文献 4 5 】，本文主要介绍一种小规模的直连网络拓扑2 d t o r u s ，并在第四章给出不同结点数的该网络的在不同业务源、链路利用率下的分组丢失率分析与仿真结果，并对单结点所需的输出缓存容量和丢失率的关系作了研究。在问接连接网络中，单个结点并不具有完整的路由器功能，每个交换单元的功能很单一，在控制信号的作用下，通过网络开关的设置来建立输入、输出端口之间间接的、可变的连接通路。间接连接网络具有良好的适应性。在大容量交换网络中，可扩展和分布式管理是网络设计者必须考虑的重要因素，所以，直接连接网络被很多大容量交换机设计者所采用【”1 2 1 ，而多级动态连接网络由于其良好的适应性也被一些大容量交换机设计者所采用，其中b a n y a n 网络及其变形，c l o s 网络等被采用的较多pj 。2 2 直连网络结构2 d t o r u s根据直连网络拓扑的度量标准5 1 ，2 d t o r u s 具有良好的对称性、可扩展性，且平均距离小，实现成本低，是小规模直连网络拓扑的一种良好的选择。定义2 1 ：k 元n 立方环绕网络是一种有n 个维度的互连结构，每个维度上的结点数都为k ，k元r l 立方网络中每个结点的坐标都可以用n 维向r1，r1、lj - ( rr-上lj -( ，一-，fic 节。1-q l p；厂r一 ，i p ,- 、i 【图2 11 6 个结点的2 dt o r u s人容龄路由器可扩展交换结构及路由算法的研究墨量( x 。、x x h ) 来描述，其中，0 4x 。k - 1 ，两个结点( x 。、x 。x )和( y 。、y 。y 。一) 相邻的充要条件是存在这样一个i ，使得x 。= ( y ；1 ) m o dk ，并且x j ：y j ( j i ) 。当n = 2 时，k 元n 立方环绕网络被称为2 dt o r u s ，它的总结点数为n = k 2 。如图2 1 所示。定理2 1h 1 ：当目的地址均匀分布时，设2 dt o r u s 每个维度上的结点数为k ，k 为偶数时，内部链路上的流量与注入业务量的关系为旯内部链路= a 注入k 8 ，当k为奇数时，内部链路流量为旯内部链路= 旯注入( k 8 - 1 8 k ) ，设c f f ，t t 为内部链路带宽，则内部链路利用率为l 钿部链杉：堍入。钐，露为偶数一 籼 j i ：链形：缸入( 专一矗么，后为奇数2 3 直连网络的交换机制与路由算法 4 】2 3 1 交换机制这罩的交换机制是指交换路由器内部采用的消息交换方式，也就是我们通常所说的交换技术，需要说明的是，交换机制并不限于直连网络，级连网络中也可以采用多种交换机制。交换机制大体分为：电路交换( c i r c u i ts w i t c h i n g ) 、分组交换( p a c k e ts w i t c h i n g ) 和切通交换( c u t - t h r o u g h ) 。这三种交换机制各有各的特点，下面对这三种交换机制的特点分别进行讨论。电路交换的特点就是“独占”，消息独占一条信道，因此消息在传送阶段从不阻塞，因此在交换的中间节点处不需要设置缓存区( b u f f e r ) 。分组交换方式也就是存储转发方式( s t o r e a n d f o r w a r d ) ，它的特点是中间节点需要将分组先整个存储下来后再转发，并且各个分组独立路由。因此，中间节点需要设置大小至少为一个分组大小的缓存区。分组交换方式下的通信时延要与通信的两个节点之i b j 的距离，即跳数( h o p ) 成j 下比。实际上，当一个中间节点接收到一个分组中的路由信息后，就可以立即决定转发到哪个节点，并且开始转发工作，并不需要接收到整个分组后才转发。这就是所谓的“切通”技术。它的意义在于“切”( c u t ) 和“通”( t h r o u g h ) 。将分组“切”成更小的片( f l i t ) ，这些片( 包括头片和数据片) 首尾相连，“流水线”式的“通”过各个中间节点。头片( h e a df l i t ) 中包含了路由信息，一旦头片通过了某个节点，后续的数据片( d a t af l i t ) 紧跟着头片穿过此中间节点。由于头片在中间节点可能受阻，因此要在各个中间节点处为受阻的头片和后续的数据片设置一定大小的缓存。根据设置的缓存大小，导致了两种不同的切通实现方法。一种被称为虚拟切通方式( v i r t u a lc u t t h r o u g h ) ，它的缓存区第2 章大容茸路由器的交换结构9大小与存储转发方式一样，等于分组的长度。因此一旦头片在中问节点阻塞，后续的数据依次到达被阻塞的中间节点，从把其占用的链路带宽释放出来。另一种实现是虫孔1 1 5 j ( w o r m h o l e ) 方式，它的缓存区大小为一个或几个f lit 。虫孔交换使用切通的交换技术，每一个分组分成一些数据片( 流控数抓)来传输。数据片的大小取决于系统参数，尤其是信道的数据宽度。一个分组的头一个数据片指导整个分组的路由。当领头数据片沿着选定的路径向日，j 传输时，剩余的数据片以一种流水线的方式向前行进。旦领头的数据片选择的信道已被占用时，网络中的流控阻塞后面的数据片使得它们被保留在途经路径的各个节点上直到信道重新可用。为当前分组占用的信道一直为该分组预留着，直到该分组的最后一个数据片到达该信道，才将该信道释放。2 3 2 路由算法在直连网络中，网络内部存在回路，如果不允许交换网络内部分组丢失，算法需要着重解决防死锁问题【1 6 】【1 7 】【1 8 】，同时还要避免活锁。以下介绍两种简单有效的路由算法，维序路由和随机路由算法。维序路由算法是源路由算法的一种，它的基本思想就是给网络中所有的维度赋以不同的优先级，分组在网络中首先沿着优先级最高的维度f j 进，以最短路径到达与目的结点在该维度上坐标一样的结点；然后再沿着次高维前进，直到到达与目的结点在该维度上坐标一样的结点为止；依此类推，直到分组最终到达目的结点。维序路由算法在二维网络中也叫做x y 路由。随机路由算法是一种分布式路由，分组可以随机选择从源结点到目的结点的所有最短路径。自适应路由提供的可选路径数大大多于维序路由，增加了路由的容错性，同时也增大了发生死锁的可能性。2 4 直接连接网络面临的问题直连网络具有分布式特点，因而有良好的可扩展性和容错能力，因此是实现大容量路由器的一种选择方式。但是采用直连网络的方法也同样面临着一些问题，分为以下几点：( 1 ) 直连网络中拓扑结构中存在着回路。如果交换网络中不允许分组丢失，直连网络中由于会出现对资源的环形依赖，因而路由算法必须是防死锁的。如果采用非最短路由，算法还必须还是防活锁【1 0 】【l l l 【1 6 】1 1 8 】的，防止分组始终在交换网络中传输，却到达不了目的地。通常情况下，好的防死锁算法比较复杂，简单的防死锁算法如维序路由会导致某一个维度上的链路和端口负载积压，而其他维度上负载较轻，即难以实现负载均衡，从而对系统的吞吐率、时延都造成不利影响。但是复杂的路由算法又给高速可实现性带来了问题。火容量路由器可扩展交换结构及路由算法的研究卫( 2 ) 直连网络由于受拓扑结构的限制，衡。这是因为直连网络的通信往往具有区域局部性的特性，从输入结点到输出结点，未必要跨过整个交换网络。例如图2 2中a 、b 两个结点通信时，采用的路径一般包括在以a 、b 为端点的矩形中。与整个网络的交换能力相比，以a 、b 为端点的矩形的交换能力只是其中的一小部分。a 到b 间通信流量如果扩散到整个交换网很难在整个交换网络内实现负载均1j )图2 2 直连网络两个结点之间的通信络中，再汇聚到b ，显然是不合理的。但是如果仅局限在以a 、b 为端点的矩形中，又难以利用整个网络的交换能力，即整个网络中其他部分的交换能力对于以a 、b 间的通信是没有帮助的。( 3 ) 直连网络中各个结点之间通信，需要经过的最小跳数是不同的。有的结点间只需要很短的几跳，而有的结点问需要经历很长的距离。跳数多带来的缺陷是时延大，因为在每个中间结点都需要经历存储排队。除此之外，虽然直连网络能够为结点提供比较丰富路径进行通信，但是这些路径的跳数往往是不同的，如果同一个流的分组经历不同跳数的路径，分组之间的乱序与时延抖动将是难以避免的。( 4 ) 直连网络的易扩展性是受一定条件制约的。当网络规模不断扩大时，同一条链路上的负载也随之不断增大。例如常见的3 0 t o r u s 与2 d m e s h 都是以环为基础的，环上结点增多时，需要链路上的带宽也越来越宽，环上结点的转发能力越来越强，缓存的容量也越来越多。如果这些要求不能满足，很难实现扩展。由于交换芯片的端口速率和缓存器的容量大小在设计之初都是固定的，因此直连网络的扩展性也受到这些因素的限制。由于采用直连网络拓扑存在以上的问题，而多级连接网络很多情况下比直连网络具有更好的适应性。2 5 多级连接网络【6 】【7 】【2 0 】级连网络是间接连接网络的一种，是大容量路由器交换网络拓扑的另一种选择，最简单的级连网络c r o s s b a r 在低端路由器交换网络中得到极为广泛的应用，由于在大容量路由器中对交换网络交换能力和交换速度的要求很高，采用单个c r o s s b a r 已经无法适应，所以通过将交换容量和速度较低的交换单元通过一定的拓扑连接来实现大容量和高的交换速度的交换网络是大容量路由器交换网络实现的常用方式。下面就对在大容量交换网络中最常用的几种间接连接网络的网络结构进行分析和讨论。第2 章大容母路由器的交换结构2 5 1b a n y a n 网络 网络的定义和结构b a n y a n 网络早在1 9 7 3 年即己提出，是一种覆盖范围较广的网络结构，早先用于并行计算机系统中的连接，后用于快速分组交换。b a n y a n 网络种类庞杂。在实用上，有时就将由2 x 2s e ( 交换单元s w i t c h i n ge l e m e n t ) x 乏j 成的单通路网络称为b a n y a n 网络。采用2 2 的s e ，网络级数k = l o g2 n ，每级有n 2 个s e 。图2 2 表示了n = 8 的由2 x 2s e 构成的3 级b a n y a n 网络。从图中可以看出，与基于矩阵拓扑或全连接拓扑的c r o s s b a r 不同，b a n y a n 网络是基于树型拓扑结构。但每个s e 却是基于c r o s s b a r 的结构，2 2 的s e 也具有b a r 和c f o s s 两种状念。每个输入分组通过3 级s e 可以到达任何输出。如果每个s e 内部具有缓冲器，称为缓冲型b a n y a n ( b u f f e r e db a n y a n ) 网络，否则，就称为无缓存型b a n y a n ( u n b u f f e r e db a n y a n ) 络。图2 38 8 的3 级b a n y a n 网络图2 4b a n y a n 网络内部竞争示意图 b a n y a n 网络的基本特征树型结构特性从b a n y a n 网络的任一输入端口( 或输出端1 5 1 ) 引出的一组通路形成了2分支树。级数越多，分支越多，这就决定了级数k = l o g2 n 。单通路特性b a n y a n 网络的任一入端到任一出端之间，具有一条且仅有一条通路。自选路由特性【2 0 】从以上两个特性可以看出，b a n y a n 网络可以使用对应于出端号的2 进制码的选路标签来自动选路，使信元到达所需的出端。在选择过程中，每级s e 依次按照选路标签中的某1 位来自选路由，该比特为0 时选s e 的上l条出线，该比特为l 时选s e 的下1 条出线。内部竞争性b a n y a n 网络是具有内部竞争的有阻塞结构。考虑到各个入端与出端之o1234567o1234567人容量路由器可扩展交换结构及路由算法的研究坚间的单通路并非完全分离，会出现公共的内部链路段，那么就有可能产生内部竞争。在图2 3 中给出示例：在同时刻，入端3 至出端5 和入端6 至出端4 同时要传送信元时，会在级间链路上产生冲突。内部竞争会降低b a n y a n网络的吞吐率，且随着网络容量的增大而恶化。可扩展性b a n y a n 网络的构成有一定规律，可以用有规则的扩展方法将较小容量的b a n y a n 扩展成较大规模。这种有规则的连接有利于v l s i 的实现。在具体的实现中，根据使用要求的不同，b a n y a n 网络有很多的变形，如b e n e s 网、b u t t e r f l y 网、复份型b a n y a n 、增长型b a n y a n 、膨胀型b a n y a n等等。2 5 2c l o s 网络网络的定义和基本结构n x n 的c l o s 网络基本结构如图2 4 所示，n 为入线和出线数。第l 级的交换单元( s e ) 为n r n ，共有n n 个，第3 级的交换单元为m n ，也有n n个，中间级的交换单元为n n n 1 1 ，共有r n 个。这种3 级c l o s 网络可记为m ，n ，m ) 。显然，c l o s 网络是多通路网络，任何一对指定的入端与出端之问有m条通路，每一条通路通过不同的中间级交换单元。为了更好的描述c l o s 网的连接方式，图2 5 画出了1 6 端口3 级( 1 6 ，4 ，6 ) c l o s 网络结构图。图2 5c l o s 网络基本结构第2 章大容量路由器的交换结构图2 6 ( 1 6 ，4 ，6 ) c l o s 网络结构图 c l o s 网络的特性网络的无阻塞性【6 】在电路交换中有三种无阻塞网络：严格无阻塞( s t r i c t - s e n s en o n b l o c k i n g ) 、广义无阻塞( w i d e - s e n s en o n b l o c k i n g ) 和重配置无阻塞( r e a r r a n g e a b l yn o n b l o c k i n g ) 。严格无阻塞是指从不同入线到不同出线的电路连接不会发生阻塞，换句话说，只要交换网络输出端口空闲，在任何情况下网络内部决不可能产生阻塞。广义无阻塞是指只有遵照某种特定的交换网络内部的选路算法才能做到无阻塞。重配鼍无阻塞则是要通过调整已有连接的占用路径来做到无阻塞。对于电路交换( n ，n ，m ) c l o s 网络的严格无阻塞条件是：m 2 n 一1 ，重配置无阻塞条件：m n 。对于采用分组交换的c l o s 网络严格无阻塞( s t r i c t l yn o n b l o c k i n g ) 的定义和条件则要进行很大的调整。分组交换c l o s 网络的严格无阻塞定义可以对电路交换的定义进行推广，即从网络不同输入端口输入的信息流，如果到达不同的输出端口，它们可以被网络同时转发而不会在网络内部发生阻塞，广义无阻塞、重配黄无阻塞的定义可做类似推广。目前，对于分组交换c l o s 网络的严格无阻塞条件尚未有一个令人很信服的结论，只能根据具体情况来具体分析。不过，要实现严格无阻塞的c l o s 网络对中间级的模块数要求太多，在大容量交换中一般都采用重配置无阻塞的c l o s 网络p 】。c l o s 网络的路径多样性在( n ，n ，m ) c l o s 网络中，网络为每一个输入端口到每一个输出端口提供了m 条等价链路，这样可以为网络提供很大的负载均衡能力和容错能力。( 要) c l o s 网络可以进行分布式管理在c l o s 网中，每一个s e ( 交换单元) 都是相互独立的实体，这就意味着c l o s 网络不需要集中式调度来协调各个s e ( 交换单元) ，这样网络就可以实现大容量路由器可扩展交换结构及路由算法的研究坠分布式管理，便于降低管理的复杂度和网络的扩展升级。多级c l o s 网络随着交换网络容量的扩大，用3 级c l o s 网络不够经济，可以采用5 级、7级的c l o s 网络。其结构的无阻塞原理同3 级一样。只要将3 级c l o s 网络的中间一级代之以3 级c l o s 子网络，就构成5 级c l o s 网络，以此类推，可以扩展级数。使用这种子网络嵌套的方法，可进行到再次嵌套时不再带来好处为止。一个5 级c l o s 网络的结构如图2 6 所示。图2 65 级c l o s 网络2 5 3小结综上所述，作为大容量路由器的交换网络，直连网络和级连网络都具有各自的优势和劣势，而级连网络总的来说比直连网络具有的更好的适应性，在现有的级连方式中，c l o s 网络由于其良好的网络性能和均衡特性在大容量路由器交换网络实现中得到广泛的应用。为了满足网络经营者对灵活性、经济性、高性能和可靠性的要求，大容量路由