ON BUFFER-ECONOMICAL STORE-AND-FORWARD DEADLOCK PREVENTION

This note deal with store-and-forward deadlock prevention in communica tion networks. The approach we adopt is that of establishing buffer cl asses in order to prevent cyclic waiting chains. This type of solution s 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 n etwork. The note proposes a new hierarchical scheme for arbitrary netw orks, 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.