An Efficient Token Management Algorithm for Message Dependent Deadlocks Recovery Architecture

Abstract

Interconnection networks are the backbone for communication in multicomputer environment based on point-to-point switches which are benefitted from the parallelism offered by non-blocking switches capable of forwarding packets at full link speed concurrently between input and output ports. These networks being lossless networks are more prone to deadlocks where probability of occurrence of deadlock is rare; there deadlock recovery strategies are used and are discussed in this thesis. Two kind of deadlock occurs Routing dependent and Message dependent where as routing dependent deadlocks occur when router allocates network resources to the messages in such a way that the complete set of resource dependencies form knotted cycles along escape resources. Techniques for handling routing deadlock are not sufficient for dealing with message-dependent deadlocks. There are various approaches to avoid message dependent deadlock but these techniques are not very scalable .So recovery technique is used called m-disha where network is recovered from message dependent deadlocks by giving an alternate path on the network which pre-empts the controller .Again there is a limitation in this is that no reliable token management system. In this thesis, a new algorithm has been proposed to manage token in the network. The proposed algorithm uses pre-defined arrival time and hop time to manage token. The results have been shown on how the proposed algorithm manages the token which was not shown in previous work.