k元n方的高维交换结构和多播研究

【作者】 姚青；

【导师】 许都；

【作者基本信息】 电子科技大学 ， 通信与信息系统， 2008， 硕士

【摘要】 在因特网快速发展的今天,宽带视频、多媒体等业务对路由器技术提出了更高的要求,快速增长的网络流量也要求交换容量不断升级。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方交换结构的通用仿真模型,采用面向策略的设计模式,为不同的路由算法提供了通用的访问接口。此外,本文还结合对仿真结果的讨论,提出了开展下一步研究的参考性建议。更多还原

【Abstract】 Confronted with the explosion of communication traffic in Internet, the applications of broadband video and multimedia require routers to provide better services and a new switch fabric is needed to constantly meet the requirement of increasing capacity. With the flexible scalability and large capacity, k-ary n-cube switching fabric is being widely used to construct high speed terabit routers.On the one hand, it would be a develop trend of packet switch technology to build distributed, vast capacity switch networks with multi-dimension switch fabrics. Under the condition that the topologies are same, in general, high-dimensional torus networks have some inherent advantages in performance indexes such as throughput, switch delay, and so on. High dimension implies few nodes in each dimension, short diameter and wide bisection bandwidth if the total number of switch nodes (the size of switch topology) is fixed. Short diameter is beneficial to decrease switch delay, and wide bisection bandwidth is helpful to increase throughput as the switch capacity of multi-dimension switch fabric and bisection bandwidth has the direct ratio theoretically. But, high-dimension also incurs the problems of cost and technology.Higher-dimension implies more node degree, so there must be more interconnect channels and node temporary memory. That directly adds the cost of switch fabric, and increases architectural complexity in managing temporary, scheduling and controlling information transport and handle. The Higher-dimension switch fabrics’potential of scalable is restricted, because the total number of interconnection channels increases fleetly while the number of nodes adds.On the other hand, to meet the development of new services, such as video conference and cooperative computing etc., the traditional point to point communication would be replaced by multicast communication. Not only multicast can save vast communication bandwidth, but also it improves the working efficiency of terminal equipment. Along with the fast growing of performance requirement, multicast is extending from application layer to lower layers of network architectures. Therefore, supporting multicast in high speed switch and routers becomes a hot issue for research. Although multicast can be implemented in either software or hardware, adding hardware support for it will increase cost and complexity, possibly slowing down the routing speed. Furthermore, most existing wormhole-switched systems only support unicast in hardware. Hence, multicast should be implemented in software in such systems by sending multiple unicast messages, and therefore is suitable for current and future systems.To address the above issues, we enhance the existent software multicast algorithm and propose a novel software multicast algorithm, KMPAMR (K-Mesh Partition-based Adaptive Multicast Routing) algorithm, which are based on unicast routing and applicable for multiple multicasts. And this thesis also introduces the general model for simulation, provides a common interface for different routing algorithms with the strategy design pattern, and also discusses the simulation results. Simulation results show that the propose algorithm can perform efficient multiple multicast operations in k-ary n-cube switching fabric.First, this thesis introduces the basic research backgrounds about k-ary n-cube switching fabric, such as topology, deadlock problem, wormhole switching and virtual channel flow control. Then, some issues about building multi-dimension switch and the prospect of multicast research in k-ary n-cube switching fabric is described.Second, the research background of multi-dimension switch fabric has been introduced. And we have done some simulation in the topologies with different dimensions, then the effect of dimension on performance and complexity has been studied.Third, based on problem analysis, this thesis proposes a novel algorithms: KMPAMR (K-Mesh Partition-based Adaptive Multicast Routing) algorithm. KMPAMR can achieve high degree of parallelism by dividing the network into several separated blocks dynamically and sending message copies concurrently in each block. By applying adaptive unicast scheme, KMPAMR can decrease the delay caused by channel contention. Simulation results show that KMPAMR achieves good performance under low applied load. However, KMPAMR might accelerate the switching fabric reaching saturation point and result in beyond saturation. Beyond saturation could cause considerably degraded on performance.Finally, a general simulation model is built to test the performance of multi-dimension switch fabric and the proposed algorithm, and provides a common interface for different routing algorithms with the strategy design pattern. Furthermore, simulation results are shown and discussed. Some improvements and future works are also be proposed.更多还原