Abstract:
Store-and-forward deadlock in store-and-forward networks may be avoided by forwarding messages from buffer to buffer in accordance with a loop-free directed buffer graph ...Show MoreMetadata
Abstract:
Store-and-forward deadlock in store-and-forward networks may be avoided by forwarding messages from buffer to buffer in accordance with a loop-free directed buffer graph which accommodates all the desired message routes. Schemes for designing such buffer graphs are presented, together with methods for using them to forward the messages in an efficient and deadlock-free manner. These methods can be implemented by a set of counters at each node. Such an implementation increases the efficiency of buffer use, and simplifies jumping between normal lowoverhead operation when deadlock is far and more careful operation when deadlock is near. The proposed deadlock avoidance mechanism works for any network topology and any finite routing algorithm.
Published in: IEEE Transactions on Communications ( Volume: 28, Issue: 3, March 1980)