Predicting deadlock in store-and-forward networks

We consider the problem of predicting whether a deadlock will necessarily occur in a store‐and‐forward network. We define two versions of this problem, depending on whether or not the routes to be followed by packets are fixed. For networks with only one buffer per vertex, both versions of this prob...

Full description

Saved in:
Bibliographic Details
Published in:Networks 1990-12, Vol.20 (7), p.861-881
Main Authors: Arbib, Claudio, Italiano, Gluseppe F., Panconesl, Alessandro
Format: Article
Language:English
Subjects:
Applied sciences
Exact sciences and technology
Telecommunications
Telecommunications and information theory
Teleprocessing networks. Isdn
Valuation and optimization of characteristics. Simulation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the problem of predicting whether a deadlock will necessarily occur in a store‐and‐forward network. We define two versions of this problem, depending on whether or not the routes to be followed by packets are fixed. For networks with only one buffer per vertex, both versions of this problem are shown to be NP‐complete even for simple classes of graphs (among others bipartite graphs, two terminal series‐parallel [TTSP] graphs and therefore planar graphs). On the other hand, the same problems are shown to be polynomially solvable for treelike networks. In this case, two efficient algorithms for checking whether a treelike network with n vertices and p packets is bound to deadlock are proposed. The former has an O(pn) time and space complexity, whereas the latter runs in O(n log n)1 time and requires O(n) space. In the case of multibuffered networks, both versions of the problem are shown to be NP‐complete even on treelike networks.
ISSN:0028-3045
1097-0037
DOI:10.1002/net.3230200705