（通信与信息系统专业论文）新型组播路由系统mscr研究及实现.pdf

摘要 摘要 随着i p t v 等体现人类群体特性业务的快速展丌，现有单播方式的路由系统不 仅造成带宽的浪费还带来网络处理性能的下降，这就要求一种新型路由系统一组 播路由系统来解决这样的问题。 本文分析研究了组播路由系统的关键技术，其中包括交换技术、队列技术、仲 裁调度技术和组播实现技术；详细介绍对比组播路由系统的两种主要设计方案和 对市场相关的主要芯片进行了调研并在此基础上确立了m s c r ( 组播交换核心路 由器) 的系统方案：依据系统方案构建了m s c r 的硬件平台，并详尽的阐述了 m s c r 的结构功能：分步骤的阐述了m s c r 的组播流程，并构建测试平台对其组 播性能进行测试。 m s c r 的交换容量可由6 4 0 g b p s 平滑升级到2 t b p s ，支持丰富的端口类型，采 用共享和独立队列两种组播方式，通过测试证明m s c r 满足新型组播路由系统的 需求。 关键词：组播单播路由m s c r 垒旦! ! 坠竺! 一一 a b s t r a c t w i t ht h ef u r t h e ri n f l a t i o no fg r o u pb u s i n e s ss u c ha si p t v ，n o to n l yt h ei n t e r n e t s b a n d w i d t hi sw a s t e dg r e a t l yb u ta l s ot h ep e r f o r m a n c eo ft h ei n t e r n e t sp r o c e s s i n gi s r e d u c e dv e r ym u c hb yt h eu s i n go ft h eu n i c a s tr o u t i n gs y s t e m s o ，i tn e e d sak i n do f n o v e lr o u t i n gs y s t e m m u l t i c a s tr o u t i n gs y s t e m t h ek e yt e c h n o l o g i e so nm u l t i c a s tr o u t i n gs y s t e m ss u c ha ss w i t c h i n g ，q u e u i n g ， s c h e d u l i n ga n dm u l t i c a s ti m p l e m e n t a t i o na r ea n a l y z e d a tf i r s t ；s e c o n d l yt w o s y s t e m a t i c s c h e m e so fm u l t i c a s tr o u t i n gs y s t e m a r e s u r v e y e d a n da n i n v e s t i g a t i o n t ot h e i n t e r r e l a t e d c h i p s i sd o n ea n dt h e nt h e s y s t e m a t i c s c h e m eo fm s c r ( m u l t i c a s t s w i t c h i n gc o r er o u t e r ) i s a c h i e v e d t h e nt h ep l a t f o r mo fm s c r i sc o n s t r u c t e da n di t s f u n c t i o na n dc o n s t r u c t i o na r ed i s c u s s e df i n a l l y ，t h ep r o c e d u r eo f m u l t i c a s ti nm s c ri s d e s c r i b e ds t e pb ys t e pa n dat e s t i n gp l a t f o r m i s p u tu pt o e v a l u a t et h em u l t i c a s t p e r f o r m a n c e t h es w i t c h i n gc a p a c i t yo fm s c r c a l le x p a n df r o m6 4 0 g b p st o2 t b p ss e a m l e s s l y , s u p p o r ta n yh e t e r o g e n e o u sp o r t s ，a n d a c c o m m o d a t et w ow a y st oi m p l e m e n tt h e m u l t i c a s t i ti sv a l i d a t e db yt e s t i n gr e s u l t st h a tm s c r c a ns a t i s f yt h ed e m a n d so fn o v e l m u l t i c a s tr o u t i n gs y s t e m k e y w o r d ：m u r i c a s t u n i c a s t r o u t em s c r 创新性声明 y 6 9 5 3 8 6 本人声明所呈交的论文是我个人在导师指导f 进行的研究工作及取得的研究 成果。尽我所知除了文中加以标注和致谢中所罗列的内容以外，论文中不包含 其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或其它 教育机构的学位或证书而使用过的材料。与我同工作的同志对本研究所做的任 何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承扫切相关责任。 本人签名：幽口期：缨羔：三： 。 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证离 校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学校 有权保留送交沦文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或 部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在解 密后遵守此规定) 本学位论文属于，在一年解密后使用本授权书。 本人签名：拄盈：亟 导师签名= 荀霞一 导师签名：鲨三：，、一一 同期：坦竺! 1 五 日期：丝；兰：兰扣一 第一章绪论 第一章绪论 1 1 组播 随着网络的日益普及，像视频会议、网络电视、远程教学、远程医疗等很多能 够体现人类生活群体特性的业务的涌现已然是一个不可逆转的趋势，此类业务的 特点为参与者的群体性和参与者的空间分散性。但是，随着大量此类业务的普及， 依靠传统的点对点的单播方式或稍显莽撞的广播方式来实现这种群体性业务已经 是不可能的事情了，这是因为：单播方式要求信源反复地向不同的目的地址发送 内容相同的数据包，这不仅大量地浪费网络资源而且必将导致网络处理性能的严 重下降：而广播方式由于泛洪( f l o o d i n g ) 等危害造成的效果更为恶劣。而组播却 克服了前面两者的缺点，支持使用者的群体性和分散性，借此可以实现分布在世 界各地的使用者的共同参与。 自从上世纪8 0 年代末s t e v e d e e r i n g 在他的搏士论文中阐释了组播( m u l t i c a s t ) 这一概念以来，组播技术得到越来越多的关注，i e t f ( i n t e r n e te n g i n e e r i n gt a s k f o r c e ) 也建立了m b o n e ( m u l t i c a s t b o n e ) 试验网并对各类组播协议进行了大量 试验，研究者们希望这一技术能够为因特网种类繁多的业务再添一道别样的风景。 r f c 一1 1 1 2 1 2 1 对组播已有详细的界定，简单地说，组播技术就是一种支持多点通信的 技术：组是一个逻辑上的概念，不受网络物理连接方式和地域分布限制，也没有 对组成员数量的限制；每个组有一个逻辑上的组地址；每台主机都可以根据自己 的需求加入某一个组或几个组，也可以在任何时刻退出某个已加入的组；任何主 机都可以作为源向任何一个组发送数据，而它本身却不必加入该组；组的成员构 成是动态的，每个组中各台主枫的地位平等，没有相互之间的制约关系，主枫有 权根据自己的需求情况选择加入或者退出某个组，当主机上有不止一个网络接口 时，主机可以在多个网络接口上加入同一个组，也可以在一个网络接口上加入多 个组。在i e t f 的统一管理下，设计者已经为i p 组播机制做了大量的工作。i p v 4 的地址管理协议中规定d 类的i p 地址1 3j 用于组播机制，其地址范围是 2 2 4 0 0 0 2 3 9 2 5 5 ，2 5 5 2 5 5 ，i p v 6 地址管理协议 4 1 中规定最高字节为0 x f f 的【f f ：】 类地址为组播地址。组地址分为永久组地址和临时组地址两种，i a n a 0 n t e m e t a s s i g n e dn u m b e r sa u t h o r i t y ) 拥有地址的分配权，永久组地址分配给用途固定并且 众所周知的组，即便某时刻没有任何主机加入该组，该组也依然存在。临时组地 址是永久组地址之外的组播地址，当临时组的最后一个成员退出该组的时候，该 组旋即消失，其原有组地址将会被其他新出现的组使用。组播i p 包除了目的地址 新型组播路由系统m s c r 研究及实现 部分是组地址之外，其与普通i p 包基本上没有区别。组播i p 包在网络上的转发 由支持组播的路由系统来处理，组播路由系统会尽力把组播包转发到所有包含该 组成员的网络上，但是并不保证一定能送达组播组中的每一个成员主机。组播包 传递的范围由包的生存期值决定。 为了能够通过组播方式在网络上传递数据，我们需要适用于数据组播的技术。 综观目前对组播机制的界定，可以归纳出组播技术领域必须解决的四个基本问题： 1 ) 组播源的发现：2 ) 组播接收者的发现和管理；3 ) 网络组播拓扑结构的发现和维 护；4 ) 服务于组播机制的路由策略。解决以上四个基本问题是实现组播机制的前 提，如果能够很好地解决这几个问题，那么就可以使组播接收者正确地接收来自 组播源的数据。组播数据的传递途径是由组播源信息、接收者信息、网络组播拓 扑信息综合而构造出的组播分布树，而组播分布树的构造有赖于上述问题的解决。 故此，目前的一系列组播技术中包含了若干以解决上述问题为目的的组播协议， 大致分为组播源发现协议( m s d p ) 、组播接收者发现及管理协议( i g m p 、m l d ) 、组 播路e h 协议( m o s p f 垆j 、d v m 路由处理器1 6 j 、p i m d m 、p i m s m 、b g m p 等) 、组播拓扑 发现协议( p i m l 7 j 、m b g p 等) 等几类，考虑到组播地址的分配问题，还要加上组播 地址分配协议( m a s c ) ，这样就构成了一套相对完整的网络层面的组播系列协议， 从而保证组播数据在网络上的传输。随着组播协议的不断完善和受控组播的不断 完备，越来越多的i s p s 将推出能够真正可管理、可运营、可赢利的组播业务。 1 2 组播路由系统 然而，对这些日益发展和普及的组播业务而言，如果处理平台仍然是现有的单 播方式的路由系统，必将大大的占用现有系统的交换带宽和处理时间，这不仅对 系统中有限的交换容量和处理能力是个极大的浪费，而且由于处理能力和处理时 间的不足，像时延等这些组播性能指标必将极为恶劣。所以，具有完善组播功能 的路由系统( 简称组播路由系统) 受到越来越多的关注。特别随着p 2 p 对等技术 的广泛应用，网络带宽资源将日益匮乏，在以后的高端路由系统设计中，组播的 实现性能必将会得到越来越多的重视。 但是，像z t e 、h u a w e i 、c i s c o 等网络设备供应商通常面临着一个似乎不可逾 越的问题：复杂性不断提高的产品需要一个很长并且很昂贵的开发周期，一般地 是2 3 年的开发周期和l 1 5 千万元的开发经费。然而所得到的产品确一般只有 三年的生命周期，甚至更短，这样导致他们设备供应商的利润空间越来越小。 所以，为了既满足今后运营商对具有良好组播功能商端路由设备的需求，又给 产品带来尽可能长时间的生命周期和尽可能大的经济效益，组播路由系统必须满 足下面几个需求：更多的端口数量、更高的端口速率、更完善的q o s 保障、可持 第一章绪论 续扩展能力和更完善的组播功能。作者和所属团队共同开发的m s c r ( m u l t i c a s t s w i t c h i n gc o r er o u t e r ) 就能够较好地达到上面这些要求。 1 3 现状及趋势 尽管在协议和受控方面，组播日益成熟，但是作为组播应用的主要平台：组播 路由系统却没有随着组播业务的普及而快速发展，这不仅不能对组播业务的普及 起到相应的推动作用，在一定程度上还制约了组播业务的发展。 目前，包括h u a w e i 、c i s c o 、a v i c is y s t e m s 、j u n i p e rn e t w o r k s 、p l u r i s 和l u c e n t 等厂商的许多设备供应商都已经研发出可以提供t 比特级交换容量的核心路由系 统，并且都支持组播功能。但是，正如国家8 6 3 项目清华3 2 0 g b s 的核心路由系统 t c r 的设计中所描述的一样【8 j ，尽管该核心路由系统在一定程度上能够支持组播 业务，但是实现技术的局限性导致该路由系统对组播的支持力度远远不够，不能 很好的满足组播发展的需要。所以组播路由系统仍是今后路由系统和组播研究的 关键点之一。 此外，在目前和今后的很长一段时间内，组播业务和单播业务相比，所占的比 例相对比较小，这就导致了大多数的路由厂商仍然把单播业务的功能实现作为设 计的首要目标，在此基础之上，相应地丰富组播功能。这也导致了组播在现有路 由系统设计中所占的比例较小。但是，随着组播业务的目益普及和网络带宽的同 益匮乏，组播功能的实现在路由系统设计中的比例将会越来越高，甚至出现单纯 以组播业务为对象的路由系统也不足为怪。 所以，在今后很长一段时间内，路由系统的设计仍是以单播方式为主，在此基 础上逐步地增加组播的比例，最终达到组播和单播的完美结合。 1 4 文章内容 系统整理和分析了在设计核心组播路由系统中的理论基础和关键技术：交 换技术、排队策略及调度算法、组播实现技术。 对比了两种核心组播路由系统的系统实现方案，并对市场上的主要相关芯 片进行调研，在此基础上确立m s c r 的设计方案。 依据设计方案构建了m s c r 硬件平台，并对其各个组成部分及其功能进行 了详细的介绍。 分步骤的介绍了m s c r 中组播实现流程，并搭建了一个测试平台对其组播 性能进行测试，并对测试结果进行分析。 新型组播路由系统m s c r 研究及实现 1 5 意义 本文重点论述和研究了一种新型核心组播路由系统m s c r 的系统实现和组播 性能，m s c r 中采用的并行交换技术、基于信用点数的推拉式拥塞控制方法等都 有很高新颖性，大大地提高了组播路由系统的持续可扩展能力和流量管理功能。 并且通过测试表明，m s c r 在线速情况下，具有零乱序、低时延、低丢包率和高 吞吐率等优点。 这对进一步开发下一代具有高容量的核心组播路由系统积累了宝贵的经验；促 进了相应路由系统产业的发展；对组播业务的进一步普及有一定的推动作用。 第二章关键技术分析 第二章关键技术分析 组播路由系统中的关键技术主要包括交换网采用的交换技术，系统各部分特别 是流量管理器采用的排队策略及仲裁调度算法，以及在组播路由系统中的各种组 播实现技术。 2 1 交换技术 由于交换网的实现方式不同，因此需要面对的问题也是多种多样的，但碰撞冲 突与阻塞是每个交换网都是必须解决的。所谓碰撞冲突就是多个数据信元输入同 时输出至同一个端口，碰撞冲突会引起阻塞。如果交换在所有输入输出之间具有 点到点的配置，这种结构称之为无阻塞交换网，反之为阻塞交换网；如果任一新 的连接不需要重新配置已有的连接，这种结构则称之为严格无阻塞交换网；如果 任一新的连接需要重新配置已有的连接，这种结构称为重排无阻塞交换网。 多年来，各交换芯片开发商、科研院所针对交换网提出了许多方案，从实现机 制上分，大体上可分为两类：时分交换网、空分交换网。 2 1 1 时分交换网 时分交换网可分为共享总线交换网、环状交换网和共享内存交换网。 共享总线交换网 共享总线交换方式利用了共享总线，如图2 1 所示，该总线能够传输n 个端口 数据传送至一个目的地址，因此总线容量应该是单口容量的n 倍以提供足够的带 宽。输入控制器标志信元将要发送到的输出端口号，每个输入端口以一定的优先 级，如菊花链结构，向总线发送数据。当一个输出控制器发现一个数据目的标签 与其地址相匹配时，则将其存贮至本控制器缓冲区。 新型组播路由系统m s c r 研究及实现 共享总线 图2 1共享总线交换网 总线结构是数据通信领域的一种基本结构，它具有的优点在于其简单和各结点 之间的相对独立性，但共享总线交换网的可扩展性受背板总线速率与输入输出缓 冲容量所限，为了实现无阻塞，总线交换速度与缓冲区大小都应该是一个端口速 率的n 倍( n 为端口数) ，并且当背板总线可靠性不佳和一个端口进入超长传输的 时候，那么可能导致整个交换的崩溃。 对共享总线交换网的进一步研究也在进行当中，如分层总线( h i e r a r c h i c a lb u s ) 交换网，局部的交换可以通过当地总线，只有全局的交换需要经过多个总线，如 图2 2 所示。 环形交换网 ) 一 厂厂 i 一 i _ j ) 一 厂 厂一一 i _ j i 一 ) 一 厂厂 i _ j ) 一 ) 一 厂l i 一 图2 2分层总线交换网 在环形交换网中，每端口通过一个接1 ：3 共享环路带宽。输入端口将数据送到环 上，采用适当的环竞争策略( 如令牌技术) 来控制接入。与总线交换网类似，每 个输出端口必须在每个数据传输周期内做好接收准备，环速率必须是链路速率的n 倍，但由于每个环接口可以再生信元数据，因此可以支持更高的速率。环形交换 网如图2 3 所示。 第二章关键技术分析 共享内存交换网 图2 3环形交换网 共享内存结构非常简单有效，被广泛应用于中小型交换网的实现当中。共享内 存交换网提供在输入端口与输出端口之间的一个公共存贮区间，以存储转发数据， 如图2 4 所示。一个复用器( m u l t i p l e x e r ) 和解复用器( d e m u l t i p l e x e r ) 分别应用 在输入与输出端口。到达输入复用器的数据被置于交换网的一个输入端口上，在 这里数据由串行转换为并行并被顺序地写入共享内存当中，内部数据路由标签由 共享内存控制器判别其优先级，输出数据在输出端口被解复用并由并行转换为串 行。 每个输入端口被分配了一个时隙将其数据存储至共享内存，同样输出端口也需 要获得一个时隙将一个数据读出内存，因此如果存在n 个端口，那么共享内存就 需要有2 n 倍的处理速率，共享内存的存取速率很大程度上决定了交换性能。 图2 4共享内存交换网 共享内存交换网的主要优点在于缓冲区由所有端口共享，并且能根据不同的设 置，交换被相应的优化。共享内存交换网的不足之处在于调度算法比较复杂，可 扩展性差，这是由于交换管理算法应该为端口速率2 n 倍的原因，并且如果共享内 存可靠性不好导致共享内存失效，则整个交换网就会崩溃。 新型组播路由系统m s c r 研究及实现 2 1 2 空分交换网 根据空分交换网的拓扑结构，可以将其分为单级交换网、多级交换网、群集交 换网。 单级交换网 作为单级交换网，c r o s s b a r 是一种严格非阻塞交换网，可以同时提供多个数据 通路。一个c r o s s b a r 结构由n n 交叉矩阵构成，当交叉点闭合时，数据就从输 入端输出到输出端。交叉点的打开与闭合由调度器控制，调度器是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 r o s s b a r 拓扑结构 如图2 5 所示。 、r 、r 、，、，、r 、r 、r 、， 图2 5c r o s s b a r 交换网 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 r o s s b a r 交换 单元。多级结构能够容纳非常多的输入输出端口，其内部控制比较复杂，但各小 交换单元的输入输出端口数较整机交换机少，这样就可以采用现有成熟技术。通 过互联多个小的交换单元，就可构造出一个大型的、容量可扩展的交换机。多级 结构之间的不同取决于交换单元之间是如何互联的，图2 6 列出了几种研究较为广 泛的多级交换网。 瓣鼗 f b ) b a s e l i n e 疆骚 ( d ) f l i p 藜臻 ( e ) d e l t a( f ) 全互联 图2 6多级交换网的各种拓扑结构 从直观上看全互接( f u l l yi n t e r c o n n e c t e d ) 网络是交换性能最好的一种，但这 种方式除了成本昂贵外，并且因为互连线众多，故需要花更多时间去处理调度相 对多的输入端口，影响了处理速度，因此实际上往往考虑其它类型的多级交换网。 b a n y a n 网络是研究比较多的一种交换网，它的特点在于它的可伸缩性、固定 交换时延、数据传输的自路由( s e l f - r o u t i n g ) 性与有序性。 新型组播路由系统m s c r 研究及实现 由于b a n y a n 交换网具有自路由特性，路由过程非常简单，并且数据信元能并 行通过该结构，但如果超过一个信元在同一时刻到达一个交换单元的话，信元之 间会产生碰撞冲突，因此b a n y a n 网络会由于内部的信元阻塞可能导致相关信元的 丢失，对此存在着两个解决方案，实际卜两个方法可以同时应用在实际交换网络 中。 在每个交换单元进行数据信元缓冲可以减少碰撞冲突； 使内部交换速率比信元输入速率更快，以保证交换单元中没有碰撞几率。 人们对b a n y a n 网络一直进行着广泛深入的研究，在此基础上提出了许多 b a n y a n 网络的改进方案，如b a t c h e r - b a n y a n 网络、l l e v e lb a n y a n 网络、b a n y a n d e l t a 网络、t a n d e m b a n y a n 网络、扩展b a n y a n 网络等，这些都在一定程度上改进了 b a n y a n 网络的性能。 b e n e s 网络实际是一种特殊的b a n y a n 网络，它的交换级数是( 1 0 9 2 n ) 一l 级( n 为输入端口数) 。b e n e s 网络采用方形交换单元( 输入输出端口数相同) 构造并进 行多级互联，这种格形结构保证在每个输入端和每个输出端之间都有n 个可能的 通路。b e n e s 网络可以扩展至任意奇数级，它是一个重排非阻塞交换网。图2 7 为 b e n e s 网络拓扑图。 幽2 7b e n e s 网络 c l o s 网络是b e n e s 网络的推展。b e n e s 网络采用方形交换单元，是一种较便于 实现的方案，丽c l o s 网络用非方形交换单元构造，交换单元的互联与b e n e s 网络 类似。常用的c l o s 网络是3 级c l o s 网络，其中第一级与第二级完全连接，第二级 与第三级完全连接，第一级和第三级互相不连接。三级c l o s 网络可以由5 元组( m 1 ， r l ，r 2 ，r 3 ，n 3 ) 表示，如果r 2 m i + n 3 1 ，它是一个严格非阻塞结构。如果 r 2 ，m a x ( m 1 ，n 3 ) ，则是一个重排非阻塞结构。如图2 8 所示。 第二章关键技术分析 图2 8c l o s 网络 另外，在空分交换网中，还有一种非常重要的交换网：并行交换网。并行交换 网可以与多种交换网结合，如c r o s s b a r 、c l o s 等。在并行交换网中，属于同一连接 的所有信元将通过同一平面，使用哪一个平面由连接呼叫过程中确定。应用并行 交换平面能够获得非常高的交换速率。绝大多数交换芯片制造商，如i b m 、a g e r e 、 b r o a d c o m 、a m c c 、z e t t c o m 等公司，与设备制造商，如c i s c o 、j u n i l c l e r 等公司， 都采用并行交换的思想来实现t e r a b i t 级路由系统。 群集交换网 与多级交换网相类似，群集交换网也是通过一些小的交换网搭成一个大的交换 网，但不同的是，群集交换网的每一交换单元都与线卡直接连接，通过各个线卡 上的小的交换单元堆叠成一个大的交换网。 群集交换网中某些交换网都可以归类为k a r yn ，c u b e 形网络( 其中n 为维数、 k 维每条边的结点数) ，如r j n g 网络可以看作是6 - a r y1 - c u b e 网络，m e s h 网络是 4 a r y2 - c u b e 网络，而3 dh y p e r c u b e 网络实际上是一种2 - a r y3 - c u b e 形网络。这些 交换网是可以互相渗透的，如h y p e r c u b e 可以嵌入t r e e 、m e s h 中以获得更好的交 换性能。 一个具有良好性能的群集交换网，应该是一个具有小直径、无限可扩展性、高 对分带宽、低价格性能比、多连通路径、低延时、无阻塞、非死锁的交换网，当 然其中的某些性能指标同样也适用于其它类型的交换阏。 一般说来，群集网络的可扩展性好、传输通量高，但由于各交换单元之间需要 互连，交换单元的多数端口用在互相连接当中，因此比较昂贵，难以构造。并且， 群集网络是分散控制并且拓扑复杂，因此会在技术上带来一些新的问题，如死锁 ( d e a d l o c k ) 问题。 另外，由于群集网络的信元传送需要经过多个交换结点，因此会带来延迟问题。 这一方面可以通过增加维数，减小直径的方法加以解决，也可以通过加快备交换 2 n，2 n l 2 n 2 m ，z m 2 m 新型组搔路由系统m s c r 研究及实现 结点交换处理速度等。现在，随着交换单元技术的进步，各交换单元的交换速率 越来越快，直径所带来的延迟因素在一定范围内不是主要考虑因素。因此，虽然 犬于三维的h y p e r c u b e 网络具有更小的直径，但由于控制的复杂性、价格昂贵等因 素，今年的研究与实践逐渐趋向对三维网络的研究特别是对3 dt o m s 网络的研 究与实践不断深入。 2 2 排队策略及调度算法 2 2 1 队列技术 在组播交换网中，为了包交换中不产生丢包的现象，需要引入队列进行包的缓 冲处理，根据信元缓冲队列位于输入端还是输出端，有输出排队( o q ) 、输入排 队( i q ) 、混合输入输出排队( c 1 0 q ) 和了虚拟输出排队( v o q ) 等技术。 输出排队技术 输出排队是指当一个包或信元数据进入交换网，交换网络即把该数据传送至输 出队列，输出队列缓冲在当前时间片不能发送的数据。如图2 9 所示。 图2 9 o q 示意图 输出排队技术有以下一些优点：能提供非常好的q o s 性能；能够应用诸如 w f q 的调度算法进行包输出优先级调度；满足延时要求。 输出排队技术有以下一些缺点：加速比为n ，这加大了交换网的实现难度；对 于高带宽交换机的可扩展能力差。 输入排队技术 输入排队是指输入数据流在交换网输入端口处进行缓冲，数据流不能在当前时 间片进入交换网进行交换，但一旦数据流到了交换网输出端，就不需要输出缓冲， 第二章关键技术分析 马上发送出去。如图2 1 0 所示。 国2 1 0i q 示意图 输出排队技术有以下一些优点：交换网容易实现，不需要加速比：能够采用非 常适合的调度算法，一般应用i s l i p 或类似算法实现高的数据通量；输出排队技术 但也有以下一些缺点：有线头阻塞，通量受限，在端口数较多的情况下最多达到 5 8 的吞吐率；不能提供q o s 保证：只比较适合低速的交换网。 混合输入输出排队技术 输入排队技术与输出排队技术都有其优点与缺点，将这两种技术统一起来就是 混合输入输出排队技术。 图2 1 1 c i o q 示意图 由于输入排队效率不高，输出排队需要有n 的加速比，难以实现，因此人们 提出了c i o q 技术。c i o q 综合了i q 、o q 两者的优点。并且非常重要的是在加速 比上。输入排队的加速比为1 ，而输出排队的加速比为n ( n 为端口数) ，c i o q 的加速比介于l 和n 之间，可以证明c i o q 只需要加速比为2 就可以于输出排队 的性能完全一样。 虚拟输出排队技术 由于c i o q 技术有许多优点，人们在其基础上研究了虚拟输出队列( v i r t u a l o u t p u tq u e u i n g ，v o q ) 技术，每个输入队列种根据其输出端口的不同设置相应的 新型组播路由系统m s c r 研究及实现 队列，即每个输入队列被分为n ( n 为输出端口) 个队列，因此在所有的输入种， 有n n 个v o q ，如图3 所示。v o q 的最大优点是能够防止线头阻塞。在图2 1 2 中还可以将现有的v o q 再根据优先级进行细分，以达到更好的转发效果。 图2 1 2v o q 示意图 2 2 2 仲裁调度算法 交换体系结构分为两个主要部分：数据通道和调度器。设计一个高带宽的数据 通道相对较为容易，困难的是如何为调度器设计一个好的调度算法。 仲裁调度算法的基本要求是： 效率高：高效率的调度算法应该能够同时匹配尽可能多的输入队列。一般来说， 使用硬件很难快速计算最佳匹配，因此一般在设计调度算法时总是尽力寻找次 优的算法； 稳定性：无论队列情况如何，调度算法都应该迅速找到可行的调度； 公平性：不会出现某些队列永远得不到响应的情况； 高速性：调度算法必须快速执行，否则将会抵消交换网的带宽增加； 易于实现：调度算法应该易于硬件实现，实现的复杂性包括调度器维护的状态 的数量，基于这些状态做出决策的逻辑的复杂性和修改状态时的通信开销。 早期的调度算法都采用避免线头阻塞的方法，要么努力达到输入输出的最大匹 配，要么力求信元到达后在最短时间内转发出去，包括最大匹配算法、神经网络 算法、预期算法、并行迭代匹配算法等。其中并行迭代匹配( p a r a l l e li t e r a t i v e m a t c h i n g ，p i m ) 算法是当今采用较多的s l i p 算法的基础。 p i m 算法采用随机的办法避免饿死( s t a r v a t i o n ) 和减少收敛到最大匹配的迭代 次数。p i m 用多次迭代产生不会冲突的匹配，每次迭代包括三个步骤。所有输入 输出都初始化为未匹配，而且只有哪些知道最后一次迭代都未能匹配的输入输出 力留到下一次。三个步骤分别为： 请求( r e q u e s t ) ：每个未匹配的输入向所有可能的输出发送请求： 第二章关键技术分析 响应( g r a n t ) ：如果未匹配的输出端接收到请求，随机选择一个响应； 确认( a c c e p t ) ：输入端收到响应后从所有相应中选择一个予以确认。 在响应( g r a n t ) 步骤中输出端是随机从请求中选一个响应，这有三个效果： 每次迭代都会在剩下的可能匹配中至少找到和排除3 4 的连接，算法在o ( 1 0 9 2 n 1 次迭代后收敛； 保证所有请求都最终会被响应，不会出现端口饥饿情况： 不用跟踪过去情况的存储空间，每个信元周期匹配算法都重新开始，独立于以 前周期。 该算法在理论上是简单易懂的，但使用随机方式也带来问题。首先高速情况下 实现困难且昂贵，每个调度器必须在一个变化的集合里做随机选择；其次对于刁i 稳定流量它可能导致连接间的不公平；最后，p i m 算法在单次迭代情况下只能达 到6 3 的吞吐率。 现在普遍采用的算法都是以前算法发展而来的，可分为最大权重匹配、最大( 不 加权重) 、稳定结合等三类。其中被c i s c o 的高端路由系统g s r l 2 0 0 0 采用的是i s l i p 算法。 s l i p 算法也分为三个步骤： 请求( r e q u e s t ) ：每个输入向它的队列中信元可能到达的输出端发送请求； 响应( g r a n t ) ：输出端收到请求后从它的固定轮转顺序的优先级列表中，选 择当前优先级最高的元素，输出端通知所有输入端它的请求是否被响应。固定 轮转顺序表里指向最高优先级的指针增加l ( 模为n ) 移到下一个地方当且仅 当该响应在第三步里得到确认； 确认( a c c e p t ) ：输入收到响应后从它的固定轮转顺序表中选择当前优先级指 针所指的元素，在固定轮转顺序表中纸箱最高优先级的指针增加l ( 模为n ) 移到下一个地方。 s l i p 算法有如下特点 最近刚建立的连接被置为最低优先级： 不会出现饿死现象： 在高负载情况下，各输出端口都有着相同的吞吐率。 在每个信元周期多次迭代s l i p 算法，称为i s l i p 算法。i s l i p 算法提高了性能， 每次迭代都力求增加以前没有的连接。 i s l i p 算法有如下特点： 在第一次迭代中找到的连接在下一个信元周期转为最低优先级； 不会出现饿死现象： 对于1 次迭代的i s l i p 算法在高负载的情况下，所有输出端口具有同样的吞吐 率： 新型组播路由系统m s c r 研究及实现 对于多余1 次迭代的i s l i p 算法在高负载情况下，各输出端口可能有着不同的 吞吐率，虽然每个非空队列都会得到服务，但得到服务的次数不一样。 算法最多经过n 次迭代就会收敛； 算法不必要收敛于最大匹配，它会找到最多的匹配，在不移除以前连接的条件 下找到最多的匹配数。 这里只论述了i s l i p 算法，还有许多算法诸如g a l e s h a p l e y 算法、l q f 算法、 o c f 算法、c c f 算法、j m p 算法等，这些算法都在某些性能上具有优良的品质。 2 3 组播实现技术 理论上，如果采用目前路由系统中单播实现的队列策略，对于一个1 2 8 1 2 8 交换的路由系统，要实现一个绝对无阻塞的组播交换网，每个输入端口需要2 1 2 8 一l ( c 1 2 。+ c 矗。+ + c 罢) 个的输入队列，这显然是无法忍受的。所以在目前 组播业务并不是很突出、单播业务仍然占主要部分的前提下，大多数的交换芯片 制造厂商都选择采用一些牺牲组播效率来换取系统资源的实现技术，例如所有的 组播信元由输入端口进入后都进入唯一的一个组播队列，该组播队列中的信元再 被分别复制到组播组中的各个输出端口。 由于加速比和线头阻塞的问题 9 】i m j ，目前大多数的交换芯片都采用基于虚拟输 出排队的组合输入输出排队技术来实现高速包交换路由系统的设计，所以本文下 面在讨论组播实现方式都是基于c i o q 构架的实现。 目前，国外各个主要交换芯片厂商也都是基于c i o q 构架的交换网来设计高速 交换芯片。其中组播实现方式有共享队列组播、独立队列组播和混合组播，下面 我们对这几种方式分别进行介绍，并分析得出其主要优缺点。 2 3 1 共享队列组播 共享队列组播即组播数据的转发是通过单播队列来实现的，该组播方式的实现 不需要额外的队列，通过内部的复制和循环来实现，组播信元在输入队列模块中 被复制，再像单播信元一样被转发到组播组中的输出端口。 图2 1 3 是一例共享队列组播的实现过程：来自输入端口的信元在进入输入队 列后被复制成两份输入到对应的循环输出队列，循环输出队列把该信元再循环到 对应的输入队列，两输入队列再把信元分别复制成两份输出到各自对应的循环输 出队列，如此反复直到信元被复制成可以输出到包含组播组中所有的输出端口。 第二章关键技术分析 煎查塑 输出队判 输t ：l a 队，q 图2 1 3 一例共享队列组播实现过程 匦圃一 匦圃一 际丽一磐 由于采用单播队列来对组播数据进行转发，共享队列组播不需要耗费系统额外 的队列资源和调度资源。但是输入队列中的数据复制到循环输出队列时和循环输 出队列把组播数据循环到对应的输入队列时策略的选择和实现，给共享队列组播 的实现带来很大的麻烦。 2 3 2 独立队列组播 独立队列组播中组播策略是采用单独的组播队列来实现组播数据的转发，组播 数据在输入队列或交换网中进行复制，这个过程并行于单播数据的转发。在独立 队列组播模式中，组播数据在输入端先由输入端口进入组播队列中，相应的组播 调度器根据系统流量等状态把组播数据调度到中间的交换网中，交换网把组播信 元直接进行复制到组播组中的输出端口对应的输出队列中。 图2 1 4 一个独立队列组播实施例 图2 1 4 是一个独立队列组播的实施例，其组播实现步骤概括如下 1 接收到的组播信元被放在组播缓冲队列的尾部。 2 组播连接处理器根据组播组建立分支信息，得到组播分支树。 3 组播分支树被装载到组播分支端口位图中。 = 二一 鼍一 ， 、 蒌i 一 蓦一 巫 新型组播路由系统m s c r 研究及实现 4 组播分支被安排在调度组中等待服务。组调度器从位图表中扫描，把这个信元 复制到所有的分支上。 5 当信元被复制到所有的分支中，组播缓冲队列开始循环。 独立队列组播的实现较循环组播简单，在交换网中对信元直接复制再转发到输 出端口；并行于单播信元的转发。但是正由文章开始所描述的一样，在现有路由 系统构架下，组播在路由系统的设计比重较小，不可能采用大量的组播队列和交 换网中大量资源来对组播信元进行复制转发，所以独立队列组播在现有路由系统 构架中应用范围相对较小。 2 3 3 混合组播 在混合组播的实现方式中，输入队列中即有组播队列又有单播队列。在具体实 现中一般是采用少量的组播队列和大量的单播队列来实现，即通过预先配置使系 统处在独立队列组播或共享队列组播状态，也可通过更新转发表的方式使组播信 元在转发过程中具体选择对应的组播转发模式。 混合组播具有配置灵活和对不同业务处理多样性等特点，很多交换芯片厂商都 选用它作为组播的实现方式，但是正是其灵活性导致了其配置和更新的复杂性， 所以在某些时候往往还没有前两种组播实现方式的组播转发性能高。 2 4 本章小结 对于个高端组播路由系统，其性能不仅是由交换网的交换容量所决定，还由 排队策略决定和调度算法等因素所决定【1 1 1 。除此之外，各种组播实现方式在承载 业务不同时对组播路由系统造成的性能差别也比较大，不能单一的断定哪种组播 实现方式比较优秀，哪种方式效果不好。这需要综合考虑整个路由系统的所处环 境，例如对一个主要承载流媒体业务的组播路由系统独立队列的组播实现更为合 适，而在承载i p 数据包业务较多的路由系统中共事队列的组播实现方式更为合适。 所以，设计一个性能优秀的组播路由系统，除了需要有巨大的交换容量和简洁 高效的排队技术及调度算法之外，还需要有和运行环境相匹配的组播实现技术。 除此之外，各种关键技术之间的相互匹配也是一个需要关注的问题。 第三章m s c r 系统平台 第三章m s c r 系统方案 本章介绍了组播路由系统两种主要系统方案及其结构组成，对各个主要组成部 分进行了功能描述和方案论证，并对相应芯片进行调研，在此基础上确立了m s c r 的系统方案。 3 1 传统组播路由系统 传统组播路由系统和通常的路由系统组成大致相同，主要是基于c i o q 交换系 统构成，其系统框图如图3 1 所示。 交换网 图3 1传统组播路由系统框图 3 1 1 转发处理模块 转发处理模块的主要功能包括对来自二层的数据帧进行拆帧和输入缓冲管理， 数据流的控制、路由表的查找、统计信息收集，输出队列管理和组帧。主要可以 通过专用集成电路( a s i c ) 和网络处理器( n p ) 两种方式来实现。 a s i c 基于硬件的数据处理给转发处理提供了非常高的包转发速率，并且批量 生产的a s i c 成本也很低，但是a