Deadlock Properties of Queueing Networks with Finite Capacities and Multiple Routing Chains

Report
Authors:Liebeherr, Jorg, Department of Computer ScienceUniversity of Virginia Akyildiz, Ian, Department of Computer ScienceUniversity of Virginia
Abstract:

Blocking in queueing network models with finite capacities can lead to deadlock situations. In this paper, deadlock properties are investigated in queueing networks with multi- ple routing chains. The necessary and sufficient conditions for deadlock-free queueing networks with blocking are pro- vided. An optimization algorithm is presented for finding deadlock-free capacity assignments with the least total capacity. The optimization algorithm maps the queueing net- work into a directed graph and obtains the deadlock freedom conditions from a specified subset of cycles in the directed graph. In certain network topologies, the number of deadlock freedom conditions can be large, thus, making any optimiza- tion computationally expensive. For a special class of topo- logies, so-called {\\m tandem networks}, it is shown that a minimal capacity assignment can be directly obtained without running an optimization algorithm. Here, the solution to the minimal capacity assignment takes advantage of the regular topology of tandem networks. March 21, 1994

Rights:
All rights reserved (no additional license for public reuse)
Language:
English
Source Citation:

Liebeherr, Jorg, and Ian Akyildiz. "Deadlock Properties of Queueing Networks with Finite Capacities and Multiple Routing Chains." University of Virginia Dept. of Computer Science Tech Report (1993).

Publisher:
University of Virginia, Department of Computer Science
Published Date:
1993