An Efficient Algorithm for Token Management of Message Dependent Deadlocks Recovery Architecture

Abstract

Interconnection networks are the backbone for communication in multicomputer environment based on point-to-point switches which are benefited 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 where some resources are de-allocated and granted to some other packets. 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 because they assume that messages in the network always sink upon arrival at their destinations. There are various approaches to avoid message dependent deadlock but these techniques are not very scalable since the size of the message queues grow there number of partitioned logical and physical network also increases which creates an extra overhead on the network. Therefore in such cases recovery technique called mDisha is used, where network is recovered from message dependent deadlocks by giving an alternate path on the network which pre-empts the controller. But, in mDisha there is no reliable token management system i.e. there is no provision to handle lost token. This paper proposes an algorithm to manage the token in the case of lost packet or acknowledgement. The algorithm has considered four nodes ring based mDisha architecture and has been implemented in Java language. The handling of token has been shown through simulation