The Study Of Routing Algorithm In Terabit Router's Switching Fabrics

Terabit routers are high-speed routers which have multi-terabit switching throughput and can support multi-services. It is the critical equipment of next-generation Internet backbone. The switching fabric is the central part of high-performance routers. Because shared-memories and crossbars used in today's gigabit routers have poor scalability and can not be used in terabit switching, so a more scalable switching architecture is needed in terabit routers.The static interconnection network is a scalable switching architecture with some kind of topologies. As viewed from the development of high-performance switching technologies and today's terabit router products, it is feasible to make reference to the static interconnection network technology which is presently mature and is widely used in today's MPP supercomputers. Because the requirements of switching fabrics in routers have some difference from that of interconnection systems in MPPs, so we must study the critical technologies in MPP interconnection networks in depth based on the characteristics of routers, and propose solutions suitable for switching fabrics.Issues about terabit routers include the selection of network topology, the design of routing algorithm, QoS technology and so on. In this thesis, we focus on the study of the routing algorithm of switching fabrics. We propose a multi-path routing algorithm based on 3D-Torus topology which is called DMR algorithm. It is based on e-cube routing algorithm, and can distribute traffic across at most six different data-switching paths determined by the six permutations of the three dimensions (XYZ, YZX, ZXY, XZY, YXZ, ZYX), preserving packet order within the same flow at the same time. Multi-path routing scheme not only can balance the load on the midway nodes, but also can support fault tolerance.We also describe in detail the design and implement of a 3D-Torus switching fabrics simulation environment called TSFSE in this paper. It constructs an interconnection system with 3D-Torus topology based on a popular switch simulator called SIM which is developed by Stanford University, and provides the implementation of three routing algorithms: e-cube routing, random routing and DMR. We did a series of simulation experiments in this environment.The results demonstrate that DMR has good performance in various traffic load conditions of switching fabrics. When the traffic pattern is uniform, DMR out-performs random routing and has equivalent performance with e-cube routing. When the traffic pattern is bursty and nonuniform, DMR out-performs e-cube routing and has equivalent performance with random routing. It can balance the load on the network across multiple paths when the traffic pattern is unbalanced which will improve network bandwidth and decrease network delay.