Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

A Hierarchical Approximation Algorithm for Large Multichain Product Form Queueing Networks

Hamid Reza Bahadori

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-87-382
November 1987

http://www.eecs.berkeley.edu/Pubs/TechRpts/1987/CSD-87-382.pdf

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.


BibTeX citation:

@techreport{Bahadori:CSD-87-382,
    Author = {Bahadori, Hamid Reza},
    Title = {A Hierarchical Approximation Algorithm for Large Multichain Product Form Queueing Networks},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1987},
    Month = {Nov},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1987/6220.html},
    Number = {UCB/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.}
}

EndNote citation:

%0 Report
%A Bahadori, Hamid Reza
%T A Hierarchical Approximation Algorithm for Large Multichain Product Form Queueing Networks
%I EECS Department, University of California, Berkeley
%D 1987
%@ UCB/CSD-87-382
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/1987/6220.html
%F Bahadori:CSD-87-382