Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-23T12:05:53.536Z Has data issue: false hasContentIssue false
  • English
  • Français

Analytic error bounds for approximations of queueing networks with an application to alternate routing

Published online by Cambridge University Press:  17 February 2009

Nico M. Van Dijk
Nico M. Van Dijk
Affiliation:
Free University, Amsterdam, The Netherlands.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A general condition is provided from which an error bound can be concluded for approximations of queueing networks which are based on modifications of the transition and state space structure. This condition relies upon Markov reward theory and can be verified inductively in concrete situations. The results are illustrated by estimating the accuracy of a simple throughput bound for a closed queueing network with alternate routing and a large finite source input. An explicit error bound for this example is derived which is of order M—1, where M is the number of sources.

Type
Research Article
Information
The ANZIAM Journal , Volume 31 , Issue 3 , January 1990 , pp. 241 - 258
Copyright
Copyright © Australian Mathematical Society 1990

References

[1] Ash, G. R., Kafker, A. H. and Krishnan, K. R., “Intercity dynamic routing architecture and feasibility”. Proc. 10th Int. Teletraffic Congress, Paper 3.2.2 (Montreal 06 1983).Google Scholar
[2] Barbour, A., “Networks of queues and the method of stages”, Adv. in Appl. Prob. 8 (1976) 584–591.CrossRefGoogle Scholar
[3] Baskett, F., Chandy, M., Muntz, R. and Palacios, J., “Open, closed and mixed networks of queues with different classes of customers”, J. A. C. M. 22 (1975).Google Scholar
[4] Burman, D. Y., Lehoczky, J. P. and Lim, Y., “Insensitivity of blocking probabilities in a circuit switching network”, J. of Appl. Prob. 21 (1982) 850–859.CrossRefGoogle Scholar
[5] Chandy, K. M., Howard, J. H. and Towsley, D. F., “Product form and local balance in queueing networks”, J A. C. M. 24 (1977) 250–263.Google Scholar
[6] Chandy, K. M. and Martin, A. J., “A characterization of product-form queueing networks”, J. A. C. M. 30 (1983) 286–299.Google Scholar
[7] Hinderer, K., “On approximate solutions of finite-stage dynamic programs”, in Dynamic Programming and its Application (ed. Puterman, M.), (Academic Press, New York, 1978) 289–318.CrossRefGoogle Scholar
[8] Hordjik, A. and van Dijk, N. M., “Networks of queues. Part I: Job-local-balance and the adjoint process. Part II: General routing and service characteristics”, Lecture Notes in Control and Informational Sciences (Springer Verlag, 60 1983) 158–205.Google Scholar
[9] Hordjik, A. and van Dijk, N. M., “Networks of queues with blocking”, in Performance '81 (ed. Kylstra, K. J.), (North Holland, 1983) 51–65.Google Scholar
[10] Hordjik, A. and van Dijk, N. M., “Adjoint process, job-local-balance and insensitivity of stochastic networks”, Bull. of 44th Session of the Int. Stat. Inst. 50 (1983) 776–788.Google Scholar
[11] Jackson, J. R., “Jobshop-like queueing systems”, Manag. Sci. 10 (1963) 131–142.CrossRefGoogle Scholar
[12] Kemeny, J. G., Snell, J. L. and Knapp, A. W., Denumerable Markov chains (Van Nostrand, Princeton, NJ, 1966).Google Scholar
[13] Kelly, F. P., Reversibility and stochastic networks (Wiley, 1979).Google Scholar
[14] Kohlas, J., Stochastic methods of operations research (Cambridge University Press, 1982).Google Scholar
[15] Kurtz, T. G., “Extensions of Trotter's operator semigroup approximations theorems”, J. Functional Analysis 3 (1969) 111–132.CrossRefGoogle Scholar
[16] Kurtz, T. G., “Semigroups of conditional shifts and approximation of Markov processes”, Ann. Prob. 3 No. 4 (1975) 618–642.CrossRefGoogle Scholar
[17] Kushner, H. J., Probability methods for approximations in stochastic control and for elliptic questions (Academic Press, New York, 1977).Google Scholar
[18] Lax, P. D. and Richtmeyer, R. D., “Survey of the stability of linear finite difference equations”, Comm. PureAppl. Math. 9 (1956) 267–293.CrossRefGoogle Scholar
[19] Meis, T. and Marcowitz, U., Numerical solution of partial differential equations (Springer- Verlag, Berlin, 1981).CrossRefGoogle Scholar
[20] Noetzel, A. S., “A generalized queueing discipline for product form network solutions”, J. of ACM 26 (4) (10., 1979) 779–793.CrossRefGoogle Scholar
[21] Ott, T. J. and Krishnan, K. R., “State dependent routing of telephone traffic and the use of separable routing schemes”, Proc. 11th Int. Teletraffic Cong., Tokyo, 1985.Google Scholar
[22] Ross, S. M., Applied probability models with optimization applications (Holden-Day, San Francisco, 1970).Google Scholar
[23] Rohlicek, J. R. and Willsky, A. S., “The reduction of perturbed Markov generators: an algorithm exposing the role of transient states”, J. A. C. M. 35 (1988) 675–696.Google Scholar
[24] Schassberger, R., “Insensitivity of steady state distributions of generalized semi-Markov processes with speed”, Adv. Appl. Prob. 10 (1978) 836–851.CrossRefGoogle Scholar
[25] Schwartz, M., Telecommunication networks (Addison Wesley, 1987).Google Scholar
[26] Seneta, E., Non-negative matrices and Markov chains (Springer Verlag, 1980).Google Scholar
[27] Shanthikumar, J. G. and Yao, D., “Stochastic monotonicity of the queue length in closed queueing networks”, Oper. Res. 35 (1987) 583–588.CrossRefGoogle Scholar
[28] Stoyan, D., Comparison methods for queues and other stochastic models (Wiley, New York, 1983).Google Scholar
[29] Tijms, H. C., Stochastic modelling and analysis. A computational approach (Wiley, New York, 1986).Google Scholar
[30] Trotter, H. F., “Approximations of semigroups of operators”, Pac. J. Math. 8 (1958) 887–919.CrossRefGoogle Scholar
[31] van Dijk, N. M., Controlled Markov processes: time-discretization, TWI Tract 11 (Amsterdam, 1984).Google Scholar
[32] van Dijk, N. M., “Simple bounds for queueing systems with breakdowns”, Performance Evaluation 8 (1988) 117–128.CrossRefGoogle Scholar
[33] van Dijk, N. M., “On the finite horizon Bellman equation for controlled Markov jump models with unbounded characteristics: Existence and approximation”, Stochastic Proc. Appl. 28 (1988) 141–157.CrossRefGoogle Scholar
[34] van Dijk, N. M., “A formal proof for the insensitivity of simple bounds for finite multiserver non-exponential tandem queues based on monotonicity results”, Stochastic Proc. Appl. 27 (1988) 261–277.CrossRefGoogle Scholar
[35] van Dijk, N. M. and Puterman, M. L., “Perturbation theory for Markov reward processes with applications to queueing systems”, Adv. Appl. Prob. 20 (1988) 79–98.CrossRefGoogle Scholar
[36] van Dijk, N. M. and van der Wal, J., “Simple bounds and monotonicity results for multi-server exponential tandem queues”, to appear in Queueing Systems.Google Scholar
[37] Walrand, J., Introduction to queueing networks (Prentice-Hall, 1988).Google Scholar
[38] Whitt, W., “Approximations of dynamic programs”, J Math. Oper. Res. 3 (1978) 231–243.CrossRefGoogle Scholar
[39] Whitt, W., “Comparing counting processes and queues”, Adv. Appl. Prob. 33 (1981) 207–220.CrossRefGoogle Scholar
[40] Whitt, W., “Open and closed models for networks of queues”, AT&T Bell Lab. Tech. J. 63 (1984) 1911–1979.CrossRefGoogle Scholar
[41] Whittle, P., Systems in stochastic equilibrium (1984).Google Scholar
[42] Zahorjan, J., Sevcik, K. C., Eager, D. L. and Galler, B. “Balanced job bound analysis of queueing networks”, Commun. of the Assoc. for Comput. Mach. 25 (1982) 134–141.Google Scholar