A Deadlock Prevention Strategy for Adaptive Routing Systems

A fundamental issue in the design and implementation of adaptive routing algorithms is deadlock treatment, either avoidance, prevention, or recovery. In case of store-and-forward networks, the resources that can cause deadlock are the buffers used to store messages in intermediate nodes. In this paper, we present a deadlock prevention mechanism that reserves a very limited number of additional buffers specially handled by the routing system. The considered routing system is adaptive and uses message misrouting. The main advantages of this approach are intrinsic locality without need of synchronisation between neighbouring nodes, and low intrusion on the routing system.