Clos网络中的组播路由算法.pdf

Clos 网络中的组播路由算法摘要： 对于三级 Clos 网络，扇出机制会影响 Clos 网络的阻塞率、算法的时间复杂度及网络成本，因此选择好的扇出方式能充分发挥网络的组播能力根据输出级扇出、中间级扇出、输入级扇出等不同的扇出机制分类，可将组播算法分为输入级扇出算法(IFMA)、最迟扇出算法(LFMA)、 切割扇出算法(SFMA)、中间级优先扇出算法(CMFFMA)在对 4 种算法仿真比较的基础上，文章提出针对不同的业务采用不同的处理方法的路由方案， 对于固定扇出业务可采用 CMFFMA 算法进行路由，针对递增业务采用先输出级、再中间级、最后输入级扇出的策略，可有效地降低阻塞率关键词：Clos 网络；组播；路由算法；扇出随着宽带技术的不断发展，视频点播、远程教学、新闻发布、网络电视等业务成为新一轮运营竞争的焦点，它们的特点是，信息由一个服务器向大量的客户端发布组播技术非常适合这类业务，并具有如下优点：服务器不必知道某个客户端是否存在，它只负责按多播地址将媒体流发送出去，即使有成千上万个客户端，也仅发送一份即可；客户端如果希望接收某媒体流服务器的数据，只需加入该媒体流服务器播放数据使用的组播组即可[1]。

目前智能光网络的发展要求节点设备的交叉矩阵具有容量高、快速的端口配置和组播支持能力，组播业务根据目的节点数的不同，可以分为单播、组播和广播 3 种类型[2]单播是指待转发的消息在传送网中要求实现点对点的传输，广播业务是指在传送网中把待转发的一个消息从源节点转发到传送网的全部输出端口上，而组播业务是则把消息转发到传送网中的一组输出端口上从广义上来讲，单播和广播是组播的一个特例根据组播请求的多个目的输出端口的产生时间，可以把组播分为两类[3]：第一类是固定扇出业务，所有的目的输出端口是在请求一开始就确定；第二类是递增业务，它的目的端口递增，是不确定的1 Clos 网络的组播业务为了支持网络中的组播业务，网络中的核心设备交换设备也应当具有组播功能Clos 网络自提出以来[4]由于其低成本、易大规模实现，在交换设备中得到了广泛的应用图 1 为一个对称的三级 Clos 网络， 用 n 表示输入输出模块的端口数量，N 表示总的输入端口数，f 表示扇出值，m表示中间模块的数量，r 表示输入和输出模块的数量，则一个三级 Clos 网络可以表示为 C(n, m, r)如果用 Ip 表示输入端口， Pi 表示输出端口， 那么一个组播请求可表示为(Ip： P1，P2……Pk)。

对称的三级 Clos 网络在任意级有扇出功能的组播严格无阻塞的条件为 m≥min{(n -1)f +n,(N -1)f,N }[5]，而且对于任意一个组播严格无阻塞网络，需要的开关数最少为O(N 2)[6]，但是在实际应用中并不需要达到严格无阻塞就可以有很好的性能1.1 Clos 网络扇出机制对于三级 Clos 网络， 不同的扇出机制不但影响 Clos 网络的阻塞率，而且影响算法的时间复杂度及网络成本，因此选择好的扇出方式才能充分发挥网络的组播能力以下将对Clos 网络各级扇出的性能特点进行分析1) 输出级扇出输出级扇出指输出级模块具有扇出功能，如果输出级具有扇出功能，那么对于同一个业务源到一个输出模块中的多个输出端口只需要经过一个中间模块，否则有多少输出端口就需要经过多少个中间模块， 在三级 Clos 网络中路由分配主要就是中间级模块的分配，因此必须降低对中间级模块的需求，而第三级扇出可以降低对中间级模块的要求，所以采用第三级扇出可以有效的降低阻塞率，这样我们就可以将一个组播请求由原来的端口表示(Ip：{P1，P2……Pk})转化成模块表示(I：{O1，O2……Ok})，其中 I 表示输入模块，Oi 表示输出模块。

2) 中间级扇出中间级扇出指中间级的模块具有扇出功能假如第一级没有扇出功能，那么所有组播分支只能在一个中间级模块进行扇出，因此只有那些满足所有扇出要求的中间交换单元才可以成功建立连接所以在组播请求的扇出值很大的情况下，网络的阻塞概率将会急剧上升，但是由于只使用一个中间模块，可以避免外部阻塞的发生3) 输入级扇出输入级扇出指输入级模块具有扇出功能，可以从一个输入端口到达不同的中间级模块如果第三级有扇出的话，那么组播请求要到达几个输出级模块，就需要占用几个中间级模块对于输入级扇出可以将组播分解成不同的单播请求进行处理，这样可以利用单播中成熟的算法来进行处理，实现简单，而且可以降低内部阻塞率但是由于每个组播请求只在第一级扇出，因此需要大量的中间模块，容易出现外部阻塞问题1.2 Clos 网络组播算法介绍Clos 网络中的组播算法性能主要受扇出机制的影响，这样我们就根据扇出策略的不同将组播算法分为以下几种输入级扇出算法(IFMA)[7]是基于输入级扇出的算法，其主要思想是通过将一个扇出值为 f 的组播请求转化成 f 个单播请求， 然后按照单播请求的路由算法进行路由， 这样在 Clos网络中每个组播请求只在输入级进行扇出，这样可以将组播业务理解为多个相互独立的单播业务，这样就可以利用单播算法中的成熟算法。

如图 1 中的输入端口 0 到输出端口 0、输出端口 4 和输出端口 8 的组播业务采用输入级扇出方式，在输入模块IM1中完成所有的扇出， 分别经过中间模块CM1、CM2 和 CM3 到不同的目的模块最迟扇出算法(LFMA)[6] 是基于中间级扇出的算法，该算法的思想是只有在必须进行扇出时才进行扇出，即先在输出级扇出再在中间级扇出因此对于每一个组播请求只使用一个中间模块， 如图 1 中输入端口 2 中的请求(2： {1， 3， 7})，只使用了一个中间模块 CM4这两种扇出机制都存在着自身的局限性，但是又有很强的互补性，因此将两种扇出相结合的思想就应运而出在三级Clos网络中， 内部阻塞的产生主要是由于级间链路的竞争，如果没有第三级扇出，那么每个组播请求在一个输出模块的每个输出端口都要占用一个从中间级到输出级的链路，否则只需要一个链路同样，如果中间级没有扇出，那么每一个子请求都要占用一条输入模块到中间模块之间的链路，这样就会出现外部阻塞各种扇出机制各有优缺点，可以结合使用在在输入级和输出级同时扇出的机制中又可以根据不同的分配方式分为切分扇出算法及先中间级后输入级算法两种切割扇出算法(SFMA)[8]是把目的输出模块进行分组，分组数 g 为扇出值 F 和切割值 s 的比值向上取整， 然后在进行路由时在第一级就进行扇出， 即需要在第二级选择 g 个可用的中间交换单元，然后再在第二级和中间级扇出机制一样进行同样的处理。

如图 1 中输入端口 3 的请求，如果按照切割算法理解的话其扇出值 F 为 3，切割值 s 为 2，分为两组，一组通过中间模块 CM1 路由，另一组通过中间模块 CM2 路由最后一种算法是中间级优先扇出算法(CMFFMA)[9-10]，利用尽量少的中间模块完成扇出，即首先选择一个可以建立尽量多扇出的中间单元，建立其到输出模块的连接如果到全部输出模块的连接均建立完成则路由成功，否则将余下的尚未完成的连接继续按照上一步的方法处理，利用其他中间级单元的扇出能力完成扇出例如在图 1 中，由于没有一个中间模块能够满足输入端口 3 的所有扇出请求，因此通过CM1 建立其中的两条，然后再通过 CM2 建立剩余的连接通过以上对扇出的分析，我们可以得到采用先中间级后输入级算法的扇出机制是最优的与切割扇出机制相比，它少了盲目性，多了预先检测性，可以在第一级进行有目的扇出；与最迟扇出机制相比，它又有很强的灵活性1.3 Clos 网络组播算法仿真(1) 仿真条件采用 OPNET 软件对不同的组播算法进行仿真， 仿真中的请求是按照占用-空闲源模式产生， 即每个输入端口有占用和空闲两种状态，占用状态表示该输入端口当前存在一个链接，每种状态的持续时间均服从指数分布，如果 1/μ 表示占用的平均时间，1/λ 表示空闲的持续时间，那么在以输入端的状态判断，网络中的负载 p1=1/u/1/u+1/λ =λ /u+λ ，如果用 f表示组播的平均扇出，Pptp 表示业务中单播的比率，那么网络中的实际负载ρ =(Pptp+(1-Pptp)×f )×ρ I。

每个组播的扇出值按指数分布产生2) 仿真结果在具有组播业务的Clos网络中网络的阻塞率主要受组播业务的扇出值、组播比例和中间模块数的影响，下面就分别进行仿真分析图 2 是 4 种不同的算法在 C(16, 16, 16)网络规模、0.8 负载以及单播比例为 0.5 时的阻塞率随扇出值变化的曲线图从图 2 中可以看出随着扇出值的增加阻塞率会有所增加，但是当扇出值达到一定值时，阻塞率将趋于稳定，这是因为在负载固定、输出级有扇出的情况下，随着扇出值的增加请求数量会减少同时由于输出级具有扇出功能，而输出级的模块数固定，所以当扇出值超出一定值后扇出的目的模块数不会有太多的变化，因此在扇出值大于一定范围后，阻塞则趋于稳定在这几种算法里 CMFFMA 的阻塞率最低，因为他的扇出顺序是先输出级、再中间级、最后输入级，这样可以最低限度地节约网络中的链路资源，避免阻塞发生图 3 为 C(16,16,16)的 Clos 网络在负载为 0.8 时的阻塞率随单播比例变化的仿真结果从图 3 中可以看出随着单播比例的增加 IFMA 算法、SFMA 和 LFMA 算法的阻塞率单调下降，而 CMFFMA 算法的阻塞率随着单播比例的变化成抛物线状，这是因为这两种算法适宜于组播请求的建立，能够最大程度的利用已有的空闲资源，因此在单播比例较低时网络的阻塞率比较低，但是随着单播比例的增加阻塞率会逐渐增加，当到达一定的比例时阻塞率又随着单播比例的增加而下降， 直到单播比例为 1 时，以上几种算法的阻塞率均达到一个固定值。

图 4 为 C(16,16,16)规模的 Clos 网络在 0.8 的负载，平均扇出值为 8 时及单播比例为 0.5 时各种算法的阻塞率随中间模块数的变化曲线从图 4 中可以看出随着中间模块数的增加，不同算法的阻塞率下降的速度不同，其中 LFMA 算法和 IFMA 算法的下降最缓慢，其他两种算法的下降速度很快；而且在中间模块数远小于严格无阻塞所需要的中间模块数的情况下，Clos 网络的阻塞率可以下降到很低从以上分析可知 IFMA 算法的阻塞率在所有算法中是最高的，这是因为该算法采用输入级扇出，组播业务的扇出均要在输入级实现，这样会造成很高的外部阻塞，而且占用的第一级链路数与第二级链路数相等图 5 为 IFMA 算法的阻塞率随中间模块数的变化趋势，网络规模为 C(16, m, 16)，平均扇出值为 8，负载为 0.8，全组播业务图 5 中可以看出内部阻塞率较小，故网络的整体阻塞率主要由外部阻塞率决定上面分析了在单、组播业务混合的情况下网络的整体阻塞率， 但是由于单播和组播业务的不同， 其阻塞率不尽相同，图 6 为不同算法随单播比例变化对组播业务阻塞率的影响从图 6 中可以看出随着单播比例的增加，组播业务的阻塞率单调递增。

其中，CMFFMA 算法的阻塞率最低，这是由于其更好的利用了网络中的空闲链路资源； IFMA 算法采用输入级扇出，所以单播比例的增加并没有影响其可用的链路资源的减少，因此阻塞率的增长最慢2 组播实现方案在对组播业务及常见算法的比较分析的基础上，本文设计出一种路由方案，针对不同的业务采用不同的处理方法由于三级均有扇出的 CMFFMA 算法的阻塞率最低， 因此对于固定扇出业务可以采用该算法进行路由针对递增业务的特点，同时为了降低对链路资源的占用，采用先输出级、再中间级、最后输入级扇出的策略由于递增业务是在固定扇出业务的基础上增加的业务，因此首先判断是否可以在固定业务已占用的输出模块内完成扇出，如果路由成功则退出；否则再判断是否可以通过固定业务已经占有的中间级模块完成路由，如果成功则退出；否则采用输入模块进行扇出，如果成功则退出；否则返回路由失败图 7 为采用本方案后的 C(16, 16, 16)规模的 Clos 网络，在单播比例为 0.5、负载为 0.8、平均扇出为 8 的时的阻塞率变化图，其中递增业务比例为递增业务占组播业务的比例由于递增业务均是以单播的形式处理，而且对于递增业务处理思想与固定组播业务类似，首先从输出模块进行扇出、再中间模块、最后输入级，因此递增业务的阻塞率接近于单播业务的阻塞率，而且随着递增业务量的增加，网络的阻塞率无太大变化。

3 结束语随着单播比例的增加，网络中的组播业务的阻塞率会随之增加其中，中间级优先扇出算法要求输入级和输出级都要有扇出功能，充分利用了交叉矩阵中的链路资源，因此阻塞率最低虽然组播严格无阻塞所需要的中间模块数很多，但是在实际的应用中并不需要很多就可以达到很低的阻塞率而且在相同的条件下，随着中间级模块数量的增加，输入级和输出级同时扇出的算法的阻塞率下降更快对于递增业务处理时可以按照组播扇出的思想进行处理，这样对整体网络中的阻塞率无明显影响下一步的工作是将重排算法引入Clos网络中的组播业务，通过对已建立的业务进行重排来降低阻塞率4 参考文献[1] SUN Shutao, HE Simin, ZHENG Yanfeng, et al. Multicastscheduling in buffered crossbar switches with multiple inputqueues[C]//Proceedings of 2005 Workshop on HighPerformance Switching and Routing(HPSR’05), May 12-14, 2005,Hong Kong, China. Piscataway, NJ, USA: IEEE, 2005: 73-77.[2] FU Hunglin, HWANG F K. On 3-stage Clos networks withdifferent nonblocking requirements on two types of calls[J].Journal of Combinatorial Optimization, 2005, 9(3):263-266.[3] HWANG F K, SHENG-CHYANG L. On nonblockingmulticast three-stage Clos networks[J].IEEE/ACM Transactionson Networking, 2000, 8(4): 535-539.[4] CLOS C. A study of non-blocking switchingnetwork[J]. Bell System Technical Journal, 1953, 32(2): 406-424.[5] HWANG F K. A survey of nooblocking multicastthree-stage Clos networks[J]. IEEE Communications Magazine,2003, 41(10): 34- 37.[6] FRIEDMAN J. A lower bound on strictly non-blockingnetwork[J]. Combinatorica, 1988, 8(2): 185-188.[7] PARK Won-Bae, HENRY L. Owenand ellen wine zegura,SONET/SDH multicast routing algorithms in symmetrical threestage networks[C]//Proceedings of International Conference onCommunications (ICC'95): Vol 3, Jun 18-22, 1995, Seattle, WA,USA. Piscataway, NJ, USA: IEEE, 1995: 1912-1917.[8] Kim D S, DU Dingzhu. Performance of split routingalgorithm for three-stage multicast networks[J], IEEE/ ACMTransactions on Networking, 2000, 8(4): 526-534.[9] YANG Yuanyuan, MASSOG G M. Fast path routingtechniques for nonblocking broadcastnetworks[C]//Proceedings of IEEE 13th Annual InternationalPhoenix Conference on Computers and Communications, Apr12-15, 1994, Tempe, AZ, USA. Piscataway, NJ, USA: IEEE, 1994:358-364.[10] YANG Yuanyuan, WANG Jianchao. A more accurateanalytical model on blocking probability of multicastnetworks[J]. IEEE Transactions on Communications, 2000,48(11): 1930-1935.收稿日期：2007-09-27石增增，西安电子科技大学计算机学院在读硕士研究生。

主要研究方向为 Clos 交换网络顾华玺， 西安电子科技大学 ISN 国家重点实验室副教授博士毕业于西安电子科技大学主要研究方向为互连网络、片上网络以及无线传感器网络中的关键技术等，已发表论文30 余篇王长山，西安电子科技大学计算机学院副教授毕业于吉林大学，主要研究方向为计算机软件与网络技术已发表论文 40 余篇。