K-ary N-dimensional Exchange Structure And Multicast Research

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.