Freedom from deadlock is a key issue in cut-through, wormhole, and store and forward networks, and such freedom is usually obtained through careful design of the routing algorithm. Most existing deadlock-free routing methods for irregular topologies do, however, impose severe limitations on the available routing paths. We present a method called layered routing, which gives rise to a series of routing algorithms, some of which perform considerably better than previous ones. Our method groups virtual channels into network layers and to each layer it assigns a limited set of source/destination address pairs. This separation of traffic yields a significant increase in routing efficiency. We show how the method can be used to improve the performance of irregular networks, both through load balancing and by guaranteeing shortest-path routing. The method is simple to implement, and its application does not require any features in the switches other than the existence of a modest number of virtual channels. The performance of the approach is evaluated through extensive experiments within three classes of technologies. These experiments reveal a need for virtual channels as well as an improvement in throughput for each technology class.

Existing solutions for fault-tolerant routing in interconnection networks either work for only one given regular topology, or require slow and costly network reconfigurations that do not allow full and continuous network access. In this paper, we present FRroots, a routing method for fault tolerance in topology-flexible network technologies. Our method is based on redundant paths, and can handle single dynamic faults without sending control messages other than those that are needed to inform the source nodes of the failing component. Used in a modus with local rerouting, the source nodes need not be informed and no control messages are necessary for the network to stay connected despite of a single fault. In fault-free networks under nonuniform traffic our routing method performs comparable to, or even better than, topology specific routing algorithms in regular networks like meshes and tori. FRoots does not require any other features in the switches or end nodes than a flexible routing table, and a modest number of virtual channels. For that reason, it can be directly applied to several present day technologies like InfiniBand and advanced switching

Summary form only given. Dynamic faults in irregular networks are difficult to handle when discarding uncorrupted packets is undesirable, deadlocks must be avoided, and in-order delivery of packets must be maintained. Current reconfiguration approaches involve all or many nodes to handle a fault. We introduce the LORE approach, a dynamic local reconfiguration which allows most of the network to remain oblivious of a one-fault. Only a small subnetwork, consisting of fault adjacent nodes and some nodes and links to connect these, is affected. LORE can be adapted to several topologies and several routing algorithms without introducing deadlocks, and can maintain in-order delivery in deterministic routing.