On buffer-economical store-and-forward deadlock prevention

Store-and-forward deadlock prevention in communication networks is addressed. The approach adopted is that of establishing buffer classes in order to prevent cyclic waiting chains. This type of solution usually requires many buffers. The main contribution of the current study is in showing that the number of required buffers can be reduced considerably by using a hierarchical organization of the network. A novel hierarchical scheme for arbitrary networks is proposed, 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