A DEADLOCK PREVENTION STRATEGY FOR ADAPTIVE ROUTING SYSTEMS

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