Clos网络中的组播路由算法

2  组播实现方案

在对组播业务及常见算法的比较分析的基础上，本文设计出一种路由方案，针对不同的业务采用不同的处理方法。

由于三级均有扇出的CMFFMA算法的阻塞率最低，因此对于固定扇出业务可以采用该算法进行路由。

针对递增业务的特点，同时为了降低对链路资源的占用，采用先输出级、再中间级、最后输入级扇出的策略。由于递增业务是在固定扇出业务的基础上增加的业务，因此首先判断是否可以在固定业务已占用的输出模块内完成扇出，如果路由成功则退出；否则再判断是否可以通过固定业务已经占有的中间级模块完成路由，如果成功则退出；否则采用输入模块进行扇出，如果成功则退出；否则返回路由失败。

图7为采用本方案后的C(16, 16, 16)规模的Clos网络，在单播比例为0.5、负载为0.8、平均扇出为8的时的阻塞率变化图，其中递增业务比例为递增业务占组播业务的比例。由于递增业务均是以单播的形式处理，而且对于递增业务处理思想与固定组播业务类似，首先从输出模块进行扇出、再中间模块、最后输入级，因此递增业务的阻塞率接近于单播业务的阻塞率，而且随着递增业务量的增加，网络的阻塞率无太大变化。

3  结束语

随着单播比例的增加，网络中的组播业务的阻塞率会随之增加。其中，中间级优先扇出算法要求输入级和输出级都要有扇出功能，充分利用了交叉矩阵中的链路资源，因此阻塞率最低。虽然组播严格无阻塞所需要的中间模块数很多，但是在实际的应用中并不需要很多就可以达到很低的阻塞率。而且在相同的条件下，随着中间级模块数量的增加，输入级和输出级同时扇出的算法的阻塞率下降更快。对于递增业务处理时可以按照组播扇出的思想进行处理，这样对整体网络中的阻塞率无明显影响。

下一步的工作是将重排算法引入Clos网络中的组播业务，通过对已建立的业务进行重排来降低阻塞率。

4  参考文献

[1]SUNShutao,HE Simin, ZHENG Yanfeng, et al. Multicast scheduling in buffered crossbar switches with multiple input queues[C]//Proceedings of 2005 Workshop on High Performance Switching and Routing(HPSR’05), May 12-14, 2005, Hong Kong, China. Piscataway, NJ, USA: IEEE, 2005: 73-77.

[2]FUHunglin,HWANG F K. On 3-stage Clos networks with different nonblocking requirements on two types of calls[J]. Journal of Combinatorial Optimization, 2005, 9(3):263-266.

[3]HWANGFK, SHENG-CHYANG L. On nonblocking multicast three-stage Clos networks[J].IEEE/ACM Transactions on Networking, 2000, 8(4): 535-539.

[4]CLOSC.A study of non-blocking switching network[J]. Bell System Technical Journal, 1953, 32(2): 406-424.

[5]HWANGFK. A survey of nooblocking multicast three-stage Clos networks[J]. IEEE Communications Magazine, 2003, 41(10): 34- 37.

[6]FRIEDMANJ.A lower bound on strictly non-blocking network[J]. Combinatorica, 1988, 8(2): 185-188.

[7]PARKWon-Bae,HENRY L. Owenand ellen wine zegura, SONET/SDH multicast routing algorithms in symmetrical three stage networks[C]//Proceedings of International Conference on Communications (ICC'95): Vol 3, Jun 18-22, 1995, Seattle, WA, USA. Piscataway, NJ, USA: IEEE, 1995: 1912-1917.

[8]KimDS, DU Dingzhu. Performance of split routing algorithm for three-stage multicast networks[J], IEEE/ ACM Transactions on Networking, 2000, 8(4): 526-534.

[9]YANGYuanyuan,MASSOG G M. Fast path routing techniques for nonblocking broadcast networks[C]//Proceedings of IEEE 13th Annual International Phoenix Conference on Computers and Communications, Apr 12-15, 1994, Tempe, AZ, USA. Piscataway, NJ, USA: IEEE, 1994: 358-364.

[10]YANGYuanyuan,WANG Jianchao. A more accurate analytical model on blocking probability of multicast networks[J]. IEEE Transactions on Communications, 2000, 48(11): 1930-1935.

作者简介：

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