Researches On Torus Networks Used As Packet Switching Fabrics

The next-generation core routers should have extremely high capacity, flexible and economical scalability, and high reliability as well. As the core components of routers, packet switching fabrics (PSF) have definitive influence on the performance of routers. The traditional PSF technologies suffer from the constraints such as the scale of crossbars, the bandwidth of buses, the reading/writing rate of buffers, and the centralized arbitration mechanism. Therefore it is difficult to construct PSF of extremely high capacity and huge number of I/O ports with traditional technologies. The scalability is also a serious problem for traditional technologies, and the reliability is degraded by the single point failure problem due to the centralized arbitration mechanism.On the other hand, direct networks such as the torus network have been widely used in high performance computing systems in the last 20 years. Most of them function as processor/memory interconnects. Torus networks have the advantages such as high capacity, scalability and reliability, so they meet the requirements of the PSF in next-generation core routers. However, the torus networks used as PSF (T-PSF) are very different from the torus networks in high performance computing systems in many perspectives, such as the scale of network, the characteristics of traffic, and the performance requirements. Therefore it is a challenging open issue to construct PSF of high capacity and scalability with torus networks. This dissertation is focused on the key technologies of that issue. The topics that are addressed include the adaptive routing algorithms in torus networks, the load patterns of T-PSF and their impact on the performance, the solutions to the adversarial load patterns, and the scaling scheme of T-PSF.Before the detailed description of torus networks, some important concepts are introduced in Chapter 2. Mathematical definitions and/or formal representations are given if necessary. According to the understanding of the author, the relations of some concepts are interpreted, and some confusing usage of terms in previous works is clarified.Chapter 3 studies deadlock-free adaptive routing algorithms in torus networks. Two strategies to handle deadlock, deadlock avoidance and deadlock recovery, are summarized and compared with each other. Then a fully adaptive routing scheme named as DALD (Deadlock-Avoidance with Local Detection) is proposed. Routing algorithms following DALD scheme need only two virtual channels integrated on each physical channel to be deadlock-free, and can provide satisfactory performance. This is the minimal requirement of buffers among all routing algorithms for torus networks. Two virtual channels per physical channel has in fact reached the minimum of buffer requirement in torus networks. Another adaptive routing scheme named as PDR (Path-Division Routing) is also proposed. Two methods, division method and integration method, to design routing algorithms following PDR are also given. A routing algorithm named as ELadder, which is designed through the division method, is presented in detail. ELadder is very simple and easy to implement, and it can provide satisfactory performance with the cost of employing more virtual channels.The performance of torus networks is significantly influenced by their load patterns. The previously published load pattern models are designed for traditional PSF or torus networks used in high performance computing systems, and they are not appropriate for T-PSF. In Chapter 4, the best one of all the known load pattern models for PSF, the Zipf Distribution (ZD) model, is summazied. It is demonstrated with both mathematical analysis and simulation results that ZD model is not appropriate for T-PSF, because it lacks the information on the distance between packet sources and destinations. Two load pattern models are proposed, which are appropriate for T-PSF because the information on the distance is integrated into the models. Different values of parameters in the models lead to different destination distributions and average distances between packet sources and destinations. Those are the first two load pattern models appropriate for T-PSF. Both of them are insensitive to the topology or scale of the network, so they can be used for networks of various topologies and scales.In many applications, torus networks are required to achieve high throughput on various load patterns, including adversarial ones (the load patterns that may cause load imbalance). By far the best solution to this problem is globally adaptive load-balance routing algorithms. In Chapter 5, a globally adaptive load-balance routing algorithm named as GALME (Globally Adaptive Load-balanced routing with Mutual Exclusion) is proposed. GALME achieves global load balance according to the packet-forwarding history of nodes, and achieves local load balance according to the state of each virtual channel. A deadlock-avoidance scheme based on mutual exclosion is proposed and employed in GALME, and it results in very high routing adaptability. GALME outperforms previously publishd algorithms on various load patterns. In this chapter, a load configuration algorithm is also proposed, which is appropriate for T-PSF. The load patterns in T-PSF are in fact irrelevant to the position of each node in the network, so it is possible to make the nodes that communicate frequently to be close to each other. Therefore the average distance between packet sources and destinations is decreased, and the performance is improved. This algorithm is the first solution dedicated to adversarial load patterns in T-PSF.The scaling scheme of T-PSF is studied in Chapter 6. Three principles to construct scalable T-PSF are presented. Then a modular subnetwork named as CB (Configurable Board) is proposed. Totally 16 nodes are integrated on each CB. If adding CBs incrementally and configuring the inter-board and intra-board links properly, a scaling from 4×4 torus (totally 16 nodes) to 16x16x16 torus (totally 4096 nodes) can be implemented. With carefully selection of node number along each dimension and the bandwidth of each link, the network capacity of the T-PSF is always greater than its I/O capacity. So the performance of the T-PSF does not degrade during scaling.In Chapter 7, the torus network simulation platform developed with C++ and OPNET Modeler system is introduced. The features supported by the simulation platform include: up to 4-dimensional torus/mesh topologies of any scale, various packet arrival models, various load pattern models, variable-length packet of different length distribution models, various routing algorithms, various scheduling algorithms, multiple-priority traffic, multicast/broadcast. The simulation platform is designed to be extended easily. New routing/scheduling algorithms and load pattern models can be implemented conveniently on this platform.In the last chapter, the whole dissertation is summazied, and conclusions are given.