Fault-tolerant wormhole message routing in computer/communication networks.

摘要

The problem of fault-tolerant wormhole message routing in multiprocessors and computer/communication networks is investigated. It is assumed that some nodes and/or links can be faulty, and it is necessary to route messages without deadlocks, using only local information at each step. This problem is well known and is important for practice. Most of existing methods lead to a high message delivery time and imply some restrictions on fault patterns. New, efficient and scalable approaches for unicast wormhole message routing are proposed to solve this problem for the cases of both regular communication networks (2-dimensional mesh) and irregular topologies. These algorithms are local and consist of pre-routing and routing stages, pre-routing stage is executed only when there is new fault or change in network topology. To the best of our knowledge, the developed algorithms provide for higher throughput than known approaches and have low complexity.; For the case of two-dimensional meshes/tori algorithm constructs fault-free rectangles (FFRs) at the pre-routing stage and store the information about their boundaries in local memories. At the routing stage, the direction for sending a message at any node is determined by FFR to which the destination node belongs. The algorithm is generalized to the cases of multidimensional meshes and tori.; For the case of irregular network topologies, the problem of finding a minimal set of prohibited turns for eliminating all cycles in a given graph G is analyzed. A new algorithm is proposed, which guarantees that the number of prohibited turns does not exceed 1/3 of the total number of turns and that it is still possible to send messages between any two initially connected nodes. For specific topologies, upper and lower bounds on minimal number of prohibited turns are constructed. The problem of routing in the presence of prohibited turns is considered and appropriate methods developed.; Developed algorithms can be realized both in hardware in routers and in software as network protocols. The program experiments show the improvement in message delivery time and saturation point (maximal system throughput), compared to existing methods.