Software-Based Deadlock Recovery Technique for True Fully Adaptive Routing in Wormhole Networks

Networks using wormhole switching have traditionally relied upon deadlock avoidance strategies for the design of deadlock-free routing algorithms. More recently, dead-lock recovery strategies have begun to gain acceptance. In particular, progressive deadlock recovery techniques are very attractive because they allocate a few dedicated re-sources to quickly deliver deadlocked packets, instead of killing them. Deadlock recovery is based on the assump-tion that deadlocks are rare. Very recently, the frequency of deadlock occurrence was measured [21, 18], showing that deadlocks are highly unlikely when enough routing free-dom is provided. However, deadlocks are more prone when the network is close to or beyond saturation. Additionally, some performance degradationhas been observed at satur-ation. Similar performance degradation behavior at satur-ation was also observed in networks using deadlock avoid-ance strategies [9]. In this paper we take a different approach to handle deadlocks and performance degradation. We propose the use of an injection limitation mechanism that prevents performance degradation near the saturation point and reduces the probability of deadlock to negligible values even when fully adaptive routing is used. We also propose an improved deadlock detection mechanism that only uses local information, detects all the deadlocks, and consid-erably reduces the probability of false deadlock detection over previous proposals. In the rare case when impend-ing deadlock is detected, our proposed recovery technique absorbs the deadlocked message at the current node and later re-injects it for continued routing towards its destin-ation. Performance evaluation results show that our new approach to deadlock handling is more efficient than pre-viously proposed techniques