An adaptive deadlock and livelock free routing algorithm

The paper is concerned with store and forward deadlocks (DL) arising in interprocessor network systems with buffered packet switched communications. Algorithms which implement DL free routing use adaptive or nonadaptive routing modality. Nonadaptive algorithms underuse the interconnection network bandwidth because they impose restrictions to the routing paths; adaptive algorithms are DL free only if certain hypotheses on the communication topology occur. In order to override these drawbacks, we have implemented an adaptive DL free routing which fully exploits the connectivity of the network and which is unrelated to its topology. DL is avoided by adopting a recovery policy. Whenever DL arises, our algorithm is able to remove it within a finite time. We demonstrate 'deadlock' and 'livelock' avoidance by ensuring the presence of a hole in the network buffers; the hole is subjected to casual movement. Performance tests, executed on a transputer based parallel machine, show the effectiveness of the algorithm and demonstrate its fault tolerance capabilities.