On Buffer-Economical Store-and-Forward Deadlock

Prevention

Baruch Awerbuch \Lambda  Shay Kutten y David Peleg z

September 9, 1996



	Abstract 


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 waiting 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 trade-off between the communication overhead and the buffer
requirements of the routing. This trade-off can be shown to be close to optimal.