K-ary N-exchange Structure Of The Multicast Research

Confronted with the explosion of communication traffic in Internet, the communication networks architects make great efforts to provide scalability for switching fabric in high speed routers. As the core technology of high speed router, a new switch fabric is needed to meet the requirements of capacity, scalability, and reliability. 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 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, this thesis proposes two novel software multicast algorithms, PAMR algorithm and EPIL algorithm, both of 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 resultsm. Simulation results show that the propose algorithms can perform efficient multiple multicast operations in k-ary n-cube switching fabric.First, this thesis intoduces the basic research backgrounds about k-ary n-cube switching fabric, such as topology, wormhole switching, virtual channel flow control and deadlock problem. Then, the prospect of multicast research in k-ary n-cube switching fabric is decribed. This thesis also studies the mathematic models of multicast problem in k-ary n-cube, and presents the solutions that used in this thesis, including schemes of multicast routing, solution of deadlock, criteria of performance evaluation, traffic patterns of applied load and multi-address encoding scheme. Moreover, the current software multicast algorithms are discussed, and so is the engineering issues.Seond, based on problem analysis, this thesis proposes two novel algorithms: PAMR (Partition-based Adaptive Multicast Routing) algorithm and EPIL (Enhanced PAMR with Injection Limitation) algorithm. PAMR 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, PAMR can decrease the delay caused by channel contention. Simulation results show that PAMR achieves good performance under low applied load. However, PAMR might accelerate the switching fabric reaching saturation point and result in beyond saturation. Beyond saturation could cause considerably degraded on performance. Following the studies on node contention issue under multiple multicasts and beyond saturation problem, this thesis proposes an enhance algorithm, EPIL algorithm. By organizing the software tree carefully, EPIL can decrease the node contention in routing and improve the performance of multicasting. Moreover, EPIL disposes beyond saturation problem by applying injection limitation mechanism.Finally, a general simulation model is built to test the performance of the proposed algorithms 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.