Abstract
Blocking queueing networks are of much interest in performance analysis due to their realistic modeling capability. One important feature of such networks is that they may have deadlocks which can occur if the node capacities are not sufficiently large. A necessary and sufficient condition for the node capacities is presented such that the network is deadlock free. An algorithm is given for buffer allocation in blocking queueing networks such that no deadlocks will occur assuming that the network has the special structure called cacti-graph. Additional algorithm which takes linear time in the number of nodes, is presented to find cycles in cacti networks.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
I.F. Akyildiz, On the exact an approximate throughput analysis of closed queueing networks with blocking, IEEE Transactions on Software Engineering (1988) 62–71.
I.F. Akyildiz, Product form approximations for queueing networks with multiple servers and blocking, IEEE Transactions on Computers (1989) to appear.
S. Balsamo and G. Iazeolla, Some equivalence properties for queueing networks with and without blocking, Proc. Performance 83 Conference, eds. A.K. Agrawala and S. Tripathi (North-Holland Publ. Co., 1983) 351–360.
M. Behzad, G. Chartrand and L. Lesniak-Foster;Graphs and Diagraphs (Wadsworth International Group, California, 1979).
O.I. Boxma and A.G. Konheim, Approximate analysis exponential queueing systems with blocking, Acta Informatica 15 (1981) 19–66.
W.J. Gordon and G.F. Newell, Cyclic queueing systems with restricted queues, Operations Research 15, Nr. 2 (April 1967) 266–277.
A. Hordijk and N. van Dijk, Networks of queues with blocking,Proc. 8th Int. Symp. on Computer Performance Modelling, Measurement, and Evaluation, Amsterdam, November 4–6, 1981.
D.B. Johnson, Finding all the elementary circuits of a directed graph, SIAM Journal on Computing 4 (1975) 77–84.
A.G. Konheim and M. Reiser, Finite capacity queueing systems with applications in computer modeling, SIAM Journal Computing 7, No. 2 (1978) 210–229.
R.O. Onvural and H.G. Perros, On equivalences of blocking meachanisms in queueing networks with blocking, Operations Research Letters 5 (1986) 293–297.
H.G. Perros, Queueing networks with blocking: a bibliography, ACM Sigmetrics Performance Evaluation Review, (1984).
H.G. Perros and T. Altiok, Approximate analysis of open networks of queues with blocking: tandem configurations, IEEE Transactions on Software Engineering, Vol. SE-12, No. 3 (1986) 450–462.
Author information
Authors and Affiliations
Additional information
Akyildiz's work was supported in part by School of Information and Computer Science, ICS, of Georgia Tech and by the Air Force Office of the Scientific Research (AFOSR) under Grant AFOSR-88-0028.
Rights and permissions
About this article
Cite this article
Kundu, S., Akyildiz, I.F. Deadlock free buffer allocation in closed queueing networks. Queueing Syst 4, 47–56 (1989). https://doi.org/10.1007/BF01150855
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01150855