On Buffer-Economical Store-and-Forward Deadlock Prevention

This note deals with store-and-forward deadlock prevention in communication networks. The approach we adopt is that of establishing buffer classes in order to prevent cyclic wailing chains. This type of solutions usually tends to require many buffers. The main contribution of the current note is in showing that the number of required buffers can be reduced considerably by employing a hierarchical organization of the network. The note proposes a new hierarchical scheme for arbitrary networks, that features a tradeoff between the communication overhead and the buffer requirements of the routing. This tradeoff can be shown to be close to optimal. © 1994 IEEE