在因特网快速发展的今天,宽带视频、多媒体等业务对路由器技术提出了更高的要求,快速增长的网络流量也要求交换容量不断升级。k元n方交换结构由于其灵活的扩展性,已成为构建大容量、可扩展路由器的常用选择之一。另一方面,面对视频会议、计算机协同工作等新业务的快速增长,多播应用发展得越来越快。相对传统的点到点通信方式,多播通信不仅能够节约大量的网络带宽,而且还可以提高设备终端的工作效率。随着对多播性能要求的不断增加,多播应用正逐渐从应用层向网络结构的下层延伸,在交换和路由层上实现多播已经成为当前国内外研究的持续热点。k元n方中的多播既可以通过软件,也可以依靠硬件的支持得以实现。但硬件开销会增加系统的设计成本和实现的复杂度,并会降低路由硬件的转发速度。同时,现有的k元n方实现系统大多只支持点对点的单播路由。因此,利用现有的单播技术在软件层面上实现多播是目前和今后很长一段时间内的很好的选择。针对以上问题,本文的主要贡献和创新在于:通过对k元n方交换结构中并发多播问题的研究,对现有的软件多播算法做出了改进;设计了以单播路由为基础的两种多播路由算法:PAMR(Partition-based Adaptive Multicast Routing)算法和EPIL(Enhanced PAMR with Injection Limitation)算法;搭建了k元n方交换结构的通用仿真模型,并采用面向策略的设计模式为不同的路由算法提供了通用的访问接口,还对算法性能进行了分析和讨论。实验表明,本文提出的两种算法都能够取得较好的性能。首先,本文从k元n方的拓扑结构、虫孔交换技术的基本理论、虚通道流控制和路由死锁几个角度出发,介绍了本文研究的背景知识,并展望了k元n方中多播研究的发展前景;接着在描述k元n方中多播问题的数学模型的基础上,提出本文的解决方案,并阐述本文解决路由死锁的方法,评估算法性能的标准,以及多播业务的分布模型和对多播地址的编码方案;随后分析了现有的软件多播算法,并对多播的工程实现问题展开讨论。其次,本文在分析已有的软件多播算法的基础上,提出两种针对并发多播业务设计的多播路由算法:PAMR算法和EPIL算法。其中,PAMR算法通过增大多播消息转发的并行性和路由的灵活性来改善多播性能。仿真表明,PAMR算法在负载较低的情况下能取得较高的吞吐率和较低的延迟,但会加速交换结构“过饱和”现象的出现。一旦出现“过饱和”,交换结构的性能(特别是吞吐率)会急剧下降。紧接着,本文在分析PAMR算法的不足的基础上,提出了EPIL算法。EPIL算法不但可以减小消息转发中的节点冲突,从而改善延迟性能,而且还通过采用注入限制的办法,较好地解决了交换结构在出现“过饱和”时,性能(特别是吞吐率)急剧下降的问题。最后,为了考察PAMR算法和EPIL算法的性能,我们在OPNET平台下搭建了基于虫孔交换和虚通道流控制的k元n方交换结构的通用仿真模型,并采用面向策略的设计模式,为不同的路由算法提供了通用的访问接口。此外,本文还结合对仿真结果的讨论,提出了开展下一步研究的参考性建议。