A. E. Conway
Abstract
The class of product-form semi-homogeneous queueing networks is introduced as a generalization of the class of homogeneous networks, which has been considered by Balbo et al for the performance modeling of local area networks. In semi-homogeneous networks, the relative traffic intensity at the various shared resources may depend on the routing chain to which a customer belongs. We develop an efficient algorithm for the exact analysis of this class of networks. It is based on the equations which form the foundation of RECAL, a general purpose exact algorithm for multiple-chain closed queueing networks. The complexity of the algorithm is shown to be of order less than exponential in (P-1)1/2, where P is the number of processors (workstations) in the network. It is therefore, in general, more efficient than a direct application of either convolution, MVA or RECAL to the class of semi-homogeneous queueing networks. The algorithm presented here may be situated between the algorithms of Balbo et al and the general purpose algorithms, both in terms of its generality and efficiency.
- 1 G. Balbo, S.C. Brue11, and S. Ghanta, "The solution of homoaeneous queueing networks with many job classes", Proceedings of the I#t#rnationaZ Workshop on Mod#Zing and P#rfo#mance Evaluation of P##I# System#, Grenoble, France, pp.385-417, 1984.]]Google Scholar
- 2 G. Balbo, pr/uate communicat#n, May 1985.]]Google Scholar
- 3 F. Baskett, K.M. Chandy, R.R. Muntz, and F. Palacios, "Open, closed, and mixed networks of queues with different classes of customers", J. Assoc. CompS. Math., 22, pp.248-260, 1975.]] Google ScholarDigital Library
- 4 A.E. Conway, and N.D. Georqanas, "RECAL: A new efficient algorithm for the exact analysis of multiple-chain closed queueing networks", J, Assoc. CompS. Math., to appear.]] Google ScholarDigital Library
- 5 A. Goldberg, G. Popek, and S.S. Lavenberg, "A validated distributed system performance model ", i n PERFORMANCE 83, A.K. Agrawal a and S.K. Tripathi, Eds., North Holland, Amsterdam, pp.251-268, 1983.]] Google ScholarDigital Library
- 6 M. Hall, CombinatoriaZ Theory, Blaisdell Publishing Company, Waltham, Massachusetts, 1967.]]Google Scholar
- 7 P. Heide}berger, and S.S. Lavenberg, "Computer performance evaluation methodology", IEEE T#. on Compute#, C-33, 12, pp.}195-1220, Dec. 1984.]]Google Scholar
- 8 S.S. Lain. and Y.L. Lien, "A tree convolution algorithm for the solution of queueing networks", Commun. ACM, 26, pp.203-215, 1983.]] Google ScholarDigital Library
- 9 S.S. Lain, and J.W. Wong, "Queueing network models of packet switching networks, Part 2: Networks with population size constraints", Pev#formancc Ev#at#n, 2, 3, pp.161-180, 1982.]]Google Scholar
- 10 E.M. Reingold, J. Nievergelt, and N. Deo, Combinatorial Algo#hms :Theory and practice, Prentice-Hall, Englewood Cliffs, New Jersey, 1977,]] Google ScholarDigital Library
- 11 M. Reiser, and H. Kobayashi, "Queueing networks with multiple closed chains:Theory and computational al gori thms", ZBM j. Res. and Dev., 19, pp.283-294, 1975.]]Google ScholarDigital Library
- 12 #. Reiser, and S.S. Lavenberg, "Mean value analysis of closed multi-chain queueing networks", J. Assoc. Comput. Math., 27, pp .313-322, 1980.]] Google ScholarDigital Library
- 13 P. Schweitzer, "Approximate analysis of multiclass closed networks of queues", in Proc. Int. Con#. Stochastic Control and Optimization, Amsterdam, 1979.]]Google Scholar
- 14 E.de Souza e Silva, S.S. Lavenberg, and R#R. "A #.untz, perspective on iterative methods for the approximate analysis of closed queueing networks", in Mathematical Comp# Performance and Reliability, North Holland, 1984.]] Google ScholarDigital Library
Index Terms
- An efficient algorithm for semi-homogeneous queueing network models
Recommendations
An efficient algorithm for semi-homogeneous queueing network models
SIGMETRICS '86/PERFORMANCE '86: Proceedings of the 1986 ACM SIGMETRICS joint international conference on Computer performance modelling, measurement and evaluationThe class of product-form semi-homogeneous queueing networks is introduced as a generalization of the class of homogeneous networks, which has been considered by Balbo et al for the performance modeling of local area networks. In semi-homogeneous ...
Multiserver Queueing Models of Multiprocessing Systems
Conventional time sharing and multiprogramming systems have been extensively modeled as single-server queues. In contrast, multiprocessing systems must be modeled as multiserver queueing systems. This paper investigates the effect of the scheduling ...
Occupancy Distributions of Homogeneous Queueing Systems Under Opportunistic Scheduling
This paper analyzes opportunistic schemes for transmission scheduling from one of n homogeneous queues whose channel states fluctuate independently. Considered schemes consist of an LCQ policy that transmits from a longest connected queue in the entire ...
Comments