Multidimensional Exchange Structure Of Fault-tolerant Technology

With the development of the optical transmission network,the Internet bandwidth is increasing rapidly.Furthermore,the cost of the optical transmission device is decreased continually.However,routers and the related technologies can't keep up with these developments and become the bottleneck in the exploiting of the Internet.With the flexible scalability and large capacity,multi-dimensional switching fabric is being widely used to construct high speed terabit routers.And Mesh and Torus are two typical network topologies employed in multi-dimensional switching fabric.Hence,this thesis investigates the fault-tolerance stratagem on the two structures.On the other hand,the fault probability of switching fabric also increases with the increasing of components. Therefore,supporting fault-tolerance in high speed routers becomes a hot issue for research.The so-called fault-tolerance of the multi-dimensional switching fabric means its capability of working properly in the presence of faulty switching network.However, those proposed fault tolerant technologies always degrade performance obviously. Hence,designing the high performance inner switching technology with the fault tolerant capability is a chanllengable but effective research.Fault tolerant routing is a communication mechanism for solving the above fault problem,which can transmit a packet from the normal source node to its destination node normally.In order to guarantee the high performance and reliability of the network,we must design the routing algorithms with the high fault tolerant capability.Firstly,this thesis introduces the basic research backgrounds about the Mesh and Torus network,such as topology,wormhole switching,virtual channel flow control and deadlock problem.Then,this thesis introduces the main content about fault tolerant routing in multi-dimensional switching fabric and the related basic knowledge.Before proposing the novel fault tolerant ronting algorithms for Mesh and Torus,this thesis introduces some famous fault tolerant routing algorithms in this field and concludes that which the necessary traits and performance parameters are the excellent fault tolerant routing algorithms need.To address the above issues,this thesis proposes two novel fault tolerant routing algorithms,MMAR algorithm and EFAM algorithm.The first one is called as the deadlock recovery-based fault tolerant routing algorithm,because this algorithm adopts deadlock recovery mechanism to solve the deadlock problem.And based on the status of the links around each fault-free node,MMAR can accommodate each shaped fault model in the fault switching network.,When encountering concave fault models, through setting the position tables for the nodes within the concave regions at the surface nodes of each concave region,MMAR can minimize the length of the misrouted paths by avoiding routing the message into the irrespective holes.The second algorithm is called as fault balanced ring-based fault tolerant adaptive routing algorithm,which solves the problem within the previous fault tolerant routing algorithms.Traditionally,nodes on fault ring become hot spots easily,thus causing uneven distribution of the traffic loads.To avoid such traffic congestion,the proposed balanced ring,defined as concentric rings of a given fault ring,can be applied to 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.When there are wide hole concave fault models,to make the algorithm work without disabling any healthy nodes,EFAM adopts the agent mechanism on the surface nodes of the holes.Thus,those nodes within the concave region can inject,eject and transmit packets normally to improve the network performance.The simulation results indicate lager througput and smaller latency than those previous algorithms.Finally,this thesis introduces the performance simulation platform which is used to test the performance of the two proposed algorithms.This simulation platform is based on the OPNET 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.