Standoff and Standoff Resolution in Deadlock Free Networks with Virtual Circuits

Abstract

The issue of deadlock prevention in computer communication networks has received much attention in the past literature. One of the most common approaches to deadlock prevention is a mechanism known as buffer preallocation. The key concept is that buffers are allocated, most usually for a virtual circuit or class of virtual circuits, before any data is transmitted, and this allocation is done in such a way that no deadlocks are possible. This preallocation typically occurs through the transmission of “reservation” control messages prior to the transmission of normal data traffic. Control traffic deadlock prevention has yet to be studied. In this paper it is shown that deadlocks may occur in connection with this initializing control traffic, and that the resolution of such deadlocks must be handled with some care. More specifically, if such resolution is not handled with sufficient care, a condition which we term standoff may result. Standoff is a condition where contention for the allocation of one or more critical buffers results in resource being allocated to none of the contending parties. The paper then proceeds to describe protocols that prevent the phenomenon of standoff, thereby ensuring true deadlock free operation. © 1992 IEEE