Research On Key Issues In Direct Interconnection Netwroks

Direct interconnection network is one of major classes of interconnection networks It has been widely used in many areas, such as graph theory, algorithm design and analysis, computer architecture, parallel and distributed computing, computer networks. LSI and so on. In this thesis, we focus on studying the key technologies in the direct interconnection networks, including topology, switching mechanism and routing algorithm. Particular emphasis is laid on discussing the technologies and theory on the application of direct interconnection networks in the terabit router, with a new implementation strategies proposed.Firstly, based on the requirements of terabit class routers, analysis and simulations of various switching mechanisms are made. The results show that virtual cut through exhibits superior performance characteristics over other switching mechanisms under various conditions. Hence, it is the best choice for the terabit routers. Simulations of the performances of virtual cut through with different network parameters are carried out, and the results are useful for designs of the router systems.Secondly, routing algorithms are studied with emphasis on solving the problems of fault tolerance and load balancing. A new distributed load-balanced routing algorithm is proposed in Chapter 3. The new algorithm is based on the limited global information, which is a tradeoff between local and global information. It makes decisions based on the states of the links within r hops of the current node. Compared with previous algorithms that are based on deadlock avoidance mechanism, the new algorithm makes use of the deadlock detection and recovery mechanism, thus making it a true fully adaptive routing algorithm. Simulations results show that it achieves a better performance (latency and throughput) under various traffic patterns than the previous algorithms.The concepts of "Hole" and "Balanced ring" are proposed in Chapter 4 to improve the previous fault tolerant routing algorithms. Traditionally, nodes on the fault ring become hot spots, thus causing uneven distribution of the traffic loads. To avoid such traffic congestion, a concept of the balanced ring is proposed. The proposed balanced ring, defined as concentric rings of a given fault ring, can be applied to the previous fault tolerant routing algorithms. By properly guiding messages to route on the balanced ring and the fault ring, more balanced link utilization and better network performance can be achieved. The use of balanced ring does not need to add new virtualchannels. No changes are made on the virtual channel assignments and misrouting rules. The modification method is of low cost and easy to implement. The simulation results indicate that routing algorithms with the balanced rings constantly yield larger throughput and smaller latency than those without.To make the exiting routing algorithms tolerate concave fault regions without disabling any healthy nodes, the concept of "Hole" is proposed in this paper. By guiding the packet routing inside and outside the hole, the new routing method empowers the convex fault tolerant routing algorithm to tolerate concave shape regions without disabling any healthy nodes. It does not add new virtual channels and change the rules of the previous algorithms. The proposed modification method is simple and easy to implement.Based on the research above, we present an implementation scheme of switching fabrics in terabit routers based on XD network. The topological property of XD network is studied and compared with that of other popular topologies. Two kinds of deadlock free routing algorithms are proposed for XD network including CFRA and EDFL. Particularly, EDFL takes deadlock freedom, fault tolerance and load balancing into consideration and achieves good network performance. Finally, a new implementation scheme is proposed, which utilizes distributed architecture. It can be extended to large scale easily. The quality of service is guaranteed for different classes of traffic. The network can continue to work even with faulty parts existed.