在因特网快速发展的今天,宽带视频、多媒体等业务对路由器技术提出了更高的要求,快速增长的网络流量也要求交换容量不断升级。k元n方交换结构由于其灵活的扩展性,已成为构建大容量可扩展路由器的常用选择。一方面,采用多维交换结构建分布式的大容量交换网络是分组交换技术的发展趋势。比较相同拓扑类型、不同维度的多维交换结构,一般情况下,高维的结构在吞吐率、交换延迟等性能指标上具有天生的优势。如果交换节点总数(即交换结构规模)固定不变,维度高意味着每维节点数少,节点连接度高,从而交换结构的直径更小,对分带宽更大。直径小有利于减小交换延迟,而对分带宽大有利于提高吞吐率,因为多维交换结构理论上能达到的交换能力与其对分带宽成正比。但是高维度也会带来成本上与技术上的问题。维度高意味着每个节点的连接度高,从而需要更多的互连通道及节点缓存。这直接增加了交换结构的实现成本,同时加大了交换节点上的缓存管理、调度、控制信息传输与处理等模块的难度,不利于节点实现。而且由于互连通道数随着节点数的增加而快速增大,使得其可扩展性受到限制。因为受限于复杂互连的可实现性限制等,所以今后的研究方向之一是采用光介质来连接多维交换结构。另一方面,面对视频会议、计算机协同工作等新业务的快速增长,多播通信的应用越来越广泛,相对传统的点到点通信方式,多播不仅能够节约大量的网络带宽,而且可以提高工作效率。随着对多播性能要求的不断增加,多播应用逐渐从应用层向网络结构的下层延伸,在交换和路由层上实现多播已经成为当前国内外研究的热点。k元n方中的多播既可以通过软件,也可以依靠硬件的支持得以实现。但硬件开销会增加系统的设计成本和实现的复杂度,并会降低路由硬件的速度。同时,现有的k元n方实现系统大多只支持点对点的单播路由。因此,利用现有的单播技术在软件层面上实现多播是目前和今后很长一段时间内的很好的选择。针对以上问题,对现有的软件多播算法做出了改进;设计了以单播路由为基础的多播路由算法:KMPAMR(K-Mesh Partition-based Adaptive Multicast Routing)算法;搭建了k元n方交换结构的通用仿真模型,采用面向策略的设计模式为不同的路由算法提供了通用的访问接口,并对算法性能进行了分析和讨论。实验表明,本文提出的两种算法能够取得较好的性能。首先,本文从k元n方交换结构、死锁问题、虫孔交换、路由算法和虚通道流控制几个角度出发,介绍了本文研究的背景知识。接着描述了构建多维交换结构需要注意的问题和介绍了多播的前景。其次,介绍了多维交换结构的研究背景,并对不同维数的拓扑结构进行了仿真。分析了由维数引起的torus交换结构性能和复杂度上的变化。再次,本文在分析已有的软件多播算法的基础上,提出一种针对并发多播业务设计的多播路由算法:KMPAMR算法。KMPAMR算法具有更为灵活的分区方式,通过增大多播的并行性和路由的灵活性来改善多播性能。仿真表明,KMPAMR算法在负载较低的情况下能取得较高的吞吐率和较低的延迟,但会加速交换结构“过饱和”现象的出现。一旦出现“过饱和”,交换结构的性能(特别是吞吐率)会急剧下降。最后,为了考察多维交换结构和KMPAMR算法的性能,我们在OPNET平台下搭建了基于虫孔交换和虚通道流控制的k元n方交换结构的通用仿真模型,采用面向策略的设计模式,为不同的路由算法提供了通用的访问接口。此外,本文还结合对仿真结果的讨论,提出了开展下一步研究的参考性建议。