A Hierarchical Approximation Algorithm for Large Multichain Product Form Queueing Networks
Technical Report Identifier: CSD-87-382
Abstract: In recent years we have witnessed an increasing proliferation of local area network-based distributed systems. Very large distributed systems based on wide-area networks are already in the design stages in numerous research organizations. In these systems, resources such as processing power, databases, and software are shared among users and jobs at different sites. Modeling and evaluating the performance of such large systems typically require the solution of queueing network models with large numbers of chains (classes), service centers, and populations. These large models preclude any use of exact solution techniques. Therefore, it is important that efficient and cost effective approximate algorithms for the solutions of large multichain queueing networks be devised to aid in the modeling, configuration, planning, performance evaluation, and design of the systems these models represent. In this paper we propose a hierarchical approximation technique for multiclass separable queueing networks. This technique, which relies on network transformations, provides us with a smooth tradeoff between cost and accuracy. The key elements of the approach entail transforming queueing networks containing multiple infinite servers into ones containing a single infinite server model in the first step. In the next stage at least some of the closed chains are transformed into open chains, resulting in a mixed network; this is done on the basis of the desired error and computational cost. If necessary, a completely open network may be obtained. Furthermore, upper and lower bounds of the performance measures can be computed. These bounds are asymptotically correct. Numerical results are presented which compare this method with those yielding exact values and with other approximate algorithms.