Time-Stamp Approach to Store-and-Forward Deadlock Prevention

This paper deals with the problem of store-and-forward deadlock prevention in store-and-forward networks. The presented solution uses time stamping of all messages in the network, and a nonpreemptable message exchange mechanism. By combining these ideas, a new distributed flow control procedure is derived which guarantees that all messages are delivered to their own destinations, thus avoiding both deadlock and livelock without any message loss. It is shown that some properties of this procedure depend on the policy of the allocation of exchange buffers to nodes. On the one hand, an optimal allocation strategy is presented which results in a maximally optimal deadlock prevention procedure. The procedure is network sizeand topology-independent and allows unrestricted packet routing. On the other hand, the allocation of one exchange buffer per node is discussed, which, even if not optimal, makes the derived deadlock prevention procedure completely independent of network reconfigurations. The last feature is extremely important from the practical point of view and, therefore, such a solution is strongly recommended. When compared to store-and-forward deadlock prevention procedures described so far, which lack some or all of these desirable properties, the procedure presented here behaves favorably. However, it imposes other drawbacks, i.e., the possibility of extra hops as a result of exchange operations. It is argued that this drawback appears rarely in practice, and some strategies which aim at a reduction of it are proposed.